読者です 読者をやめる 読者になる 読者になる

Every day is a new day

ひつじのプログラミング日記。

秘密の国のアリス[第3版] 第12章

秘密の国のアリス

おうちで学べるデータベースのきほん』の次は、『暗号技術入門 第3版 秘密の国のアリス』を勉強しています。

暗号技術入門 第3版 秘密の国のアリス

暗号技術入門 第3版 秘密の国のアリス

パラパラっとめくりながら、第12章の「乱数」をピックアップ。

乱数の性質としては、以下が大事なようだ。

  • 無作為性 統計的な偏りがなく、でたらめな数列になっているという性質。
  • 予測不可能性 過去の数列から次の数を予測できないという性質。
  • 再現不可能性 同じ数列を再現できないという性質。再現するためには、数列そのものを保存しておくしかない。

驚いたのは、c言語のrand関数が上記の無作為性しか持たない線形合同法であるということ。それは確かに、この本に書いてある通り、暗号技術には使えないでしょうね。

  

あとクイズの解答を、答えを見ずにここに書いてみようと思う。果たしてあっているだろうか?w

クイズ1……サイコロ

サイコロを繰り返し投げて作る数列は、再現不可能性を持つを考えられますか。

サイコロを繰り返し投げて作る数列は、再現不可能性を持つと考えられます。 なぜなら、サイコロを投げるというのは物理的な操作で、二度と同じように投げられないからです。

クイズ2……擬似乱数生成器の弱点を探す

一方向ハッシュ関数を使って擬似乱数生成器を作れるという話を聞いたを聞いたアリスは、Fig.12-6(図があるのですが、手順は以下の通り)のような擬似乱数生成器を設計しました。乱数生成の手順は次の通りです。

 

(1)擬似乱数の種を使って内部状態を初期化する。

(2)一方向ハッシュ関数を使って内部状態のハッシュ値を得る。

(3)ハッシュ値擬似乱数として出力する。

(4)そのハッシュ値を新たな内部状態とする。

(5)必要なだけの擬似乱数が得られるまで、(2) ~ (4)を繰り返す。

 

アリスがせっかく考えた擬似乱数生成器ですが、この擬似乱数生成器が生成した擬似乱数列は「予測不可能性」を持ちません。なぜでしょうか。

一方向ハッシュ関数ハッシュ値を新たな内部状態にしてしまうと、内部状態は常に固定長になってしまう。 例えば、SHA−256なら256bitである。この場合、いつかは繰り返しが発生してしまうから・・・かなぁ?

クイズ3……乱数の基礎知識

(1)擬似乱数の種は、攻撃者に秘密にしておく必要がある。

(2)線形合同法は、暗号用の擬似乱数生成器として用いることができる。

(3)無作為性を持っている擬似乱数生成器でも、予測不可能性を持っているとは限らない。

(1)🙆‍♂️ (2)🙅‍♂️ (3)🙆‍♂️

  

で、答えなのですが、クイズ1と3はあってそうのですが、クイズ2、全然見当違いです・・・w

擬似乱数の予測不可能性は、過去の擬似乱数を元にして、次の擬似乱数を予測できないという性質のことです。アリスが考えた擬似乱数生成器では、最後に出力した擬似乱数ハッシュ値をとれば、次の擬似乱数が得られてしまいます。したがって、予測不可能性を持ちません。

焦点は予測可能か不可能というところで、ハッシュ値からまたハッシュ値を求めてしまえば、それは予測可能になってしまうということですね。なるほどぅ。