擬似乱数
一般の擬似乱数は、その方式と過去の出力が既知であれば、未来の出力を予測可能であるため、暗号の用途には不適(暗号学的に安全ではないと言う)である。
暗号理論では擬似乱数(生成器)に明確な定義がある。すなわち、多項式時間の計算機が乱数列と識別不能な列を出力する機器のことを、暗号論的擬似乱数生成器と呼び、この列に含まれる数を暗号論的擬似乱数という。いかなる数列であれば乱数列であるか、議論のあるところではあるが、一様分布であることと過去の数から次の数が予測不能であることは同値であることが示されている(Yao)。そこで過去の数から次の数が予測不能であるかで、暗号論的擬似乱数か否かを区別する。
暗号理論では擬似乱数に厳密な定義が与えられている。Σ = {0,1}とする。自然数 k に対し、Σ 上の一様分布を Uk と表す。確率変数の族 {Xk}k∈N が、一様分布の族 {Uk}k∈N と計算量的識別不能な時、族 {Xk}k∈N は暗号論的擬似乱数であるという。
次に暗号論的擬似乱数生成器の厳密な定義をする。l(k) を l(k) > k を満たす多項式とする。G を多項式時間アルゴリズムで、G に k ビットのビット列を入力をすると l(k) ビットの出力を返すものとする。すると G(Uk) は Σ 上の確率分布である。確率分布の族 {G(Uk)}k∈N が暗号論的擬似乱数である時、多項式時間アルゴリズム G を暗号論的擬似乱数生成器という。
一方向性関数が存在すれば暗号論的擬似乱数生成器が存在する事が知られている。
実際の生成法としては、一般の擬似乱数列を暗号学的ハッシュ関数に通す、という、簡単な構成法がある。
線形合同法の
X n + 1 = ( A × X n + B ) mod M {\displaystyle X_{n+1}=\left(A\times X_{n}+B\right){\bmod {M}}}
において、B=0 の場合を区別して特に乗算合同法、B>0 の場合を区別して特に混合合同法と言うことがある。