naiの日記

ソフトウェアエンジニアから放射線科診断医にジョブチェンジしました。趣味のことを書きます。

衝突しないランダムな12桁のIDをより安全に払い出す方法

プログラミング

先日Zennを眺めていると、以下の記事を見つけました。

zenn.dev

  • 12桁の整数値 000,000,000,000 ～ 999,999,999,999 の中からランダムなIDを払い出すこと
  • すでに払い出したIDと同じIDを払い出さないこと
  • 払い出しが高速であること
  • ランダムに払い出すこと

以上の条件を満たすID払い出しアルゴリズムを作成することが目的です。なお、現実的には各IDは真の意味でランダムである必要はなく、ランダムっぽい値ならOKとのことです。

確かによくありそうな要件の割には、すぐには良い方法が思いつきません。なかなか面白そうな問題なので、少し考察してみました。

記事で紹介されていた方法

上記の記事で提案されていた手法は、12桁を4桁ずつ、上位・中位・下位の3セグメントに分け、セグメントごとに乱数テーブルを用いて払い出す（下位セグメントが一周したら中位の、中位セグメントが一周したら上位のセグメントの値を変更していく）という方法です。確かに「ある1人のユーザーに払い出されるID」に着目すると完全にランダムであり、1つのIDのみからは何らかの推論をすることが不可能なので、部分的には良さそうな手法です。

しかし問題はありそうです。まずIDの12桁中8桁がほとんど変わらないため、あるユーザーに払い出されたIDの下位セグメントを変更することで、高い確率で他の有効なIDを取得することができてしまいます。また、中位セグメントが1万回に1回しか変わらないことから、ユーザーIDの十分疎なセットからユーザー総数の見当をつけることも可能です。なんとかしてこれらの欠点を改善することはできないでしょうか。

提案手法1: 素数を用いた方法

色々考えて最初に思いついたのは素数を用いた方法です。1012より少し大きい素数pと、p未満の適当な正整数aおよびkを用いて、ID列を以下のように払い出します。

[a, a+k, a+2k, a+3k, ...] (mod p)

つまり、 n 番目 (n \ge 0) のID a_n を a_n = (a+nk) \bmod p で払い出す方法です。ただし計算結果が1012以上となる場合はスキップします。

この方法で払い出したIDは、1012－1番目まではユニークであることが保証されます。証明は簡単なので考えてみてください。なるほど、各IDはランダムっぽい値ですし、素数の性質を利用してユニークネスが担保されており、初期値aをランダムに選べばユーザー総数の見当をつけることもできず、なかなか良い手法に思えます。

しかし依然として問題はあります。攻撃者が数個の連続したユーザーIDの列を取得することができれば、それらが等差であることは容易に確認でき、kやpの具体的な値も含めアルゴリズムの詳細を簡単に推測できてしまいます。一度アルゴリズムの詳細が暴かれてしまえば、過去や未来に払い出される全てのユーザーIDが容易に予測可能ですから、この手法もセキュリティ的に問題があると言わざるを得ません。

提案手法2: 可逆な非線形変換を挟む

よりランダムっぽくする方法として真っ先に考えたのは、生成されたユーザーIDに適当な整数を掛けたり足したりすることですが、これらの操作を行っても実質的にはaやkの値が変わるだけで、問題の解決には全くなっていません。線形変換だと駄目なわけです。

……ということは、可逆な非線形変換を加えてやれば問題は一挙に解決しそうです。可逆な非線形変換にも色々ありますが、簡単なところだと生成されたID列の各桁をdeterministicにシャッフルすれば良さそうですね。

なお、非線形変換の中でも可逆（単射）であることはユニークネスを担保するために必要です。シャッフル以外に可逆な非線形変換としてはmod pでの逆元なんかも挙げられますが、さすがに実装が難解になってしまうため却下しました。

最後に仕上げとして、もう一度ランダムな線形変換を施してやれば完璧です。シャッフルされて得られたIDをxとして、p未満の適当な正整数b, cを用いて bx+c \bmod p を計算する要領ですが、実用的には b=1 でも問題ないでしょう。

というわけで、最終的な提案手法2のPythonコードは以下のような感じです。

import numpy as np

def generate_user_id():
    p = 1_000_000_000_039  # 素数
    a, k, c = np.random.RandomState(42).randint(p, size=3)  # 実際はもっとちゃんとランダムに決めること

    a_n = a
    while True:
        if a_n < 10 ** 12:
            x = int("".join(map(str, np.random.RandomState(42).permutation(list(map(int, f"{a_n:012d}"))))))
            user_id = (x + c) % p
            if user_id < 10 ** 12:
                yield user_id
        a_n = (a_n + k) % p

生成される値は以下の通り。ちゃんとランダムっぽい12桁の値になっていますね！ ちなみに、ユニークであることはもう少し小さい条件（4桁、p=10007）で一応確認済みです。

982686771668
557342633957
611188606345
974944568734
128690531093
...

補足: 暗号論とFormat preserving encryption

以上の解法から何となく察せられる通り、今回の問題設定は「000,000,000,000から999,999,999,999までの1012個の整数の集合を定義域および終域とする全単射写像*1のうち、なるべく都合の良いものを作成すること」と言い換えることができます。Leading zeroを含め12桁の整数を入力とし、同じく12桁の整数を出力する写像ですね。

このように、暗号前（平文）と暗号後（暗号文）のフォーマットが同じであるような暗号化方式のことをFormat preserving encryption (FPE)（フォーマット保持暗号化）といいます。有限集合に対する全単射写像とはpermutationのことなので、完全にランダムなpermutationを用意すれば完全に予測不可能ですが、記事で述べられている通りそれではコストがかかりすぎるため、なるべく低コストで予測しづらいFPEアルゴリズムが必要となってくるわけです。

FPEのアルゴリズムはとても強力なものが色々と提案されていて、一部はライブラリ化されており簡単に使うことができます。例えばPythonならff3というライブラリが簡単に使用可能なので、こういったものが使える環境なら使うことも手だと思います。ただし内容はまあまあ複雑で、自分で一から実装するとなると可読性やバグの観点からも結構大変そうです。本記事で提案した方法ぐらいが丁度良いのではないでしょうか。

で、本記事で提案した手法もFPEアルゴリズムの一種と言えると思いますが、暗号論的に強度が保証されているかどうかはわかりません。おそらく保証はされていないのでしょうね。今回の要件では万が一暗号が解読されても直ちに著しい実害はなさそうですが、解読された際にめちゃくちゃ困るというシチュエーションであれば、他のより強度の高そうなアルゴリズムを使用することが無難かと思います。

*1:厳密には、今回の問題設定では定義域はこれよりも小さくてもよく、その場合は必ずしも全射である必要はありません。提案手法も微妙に全射ではないですね。