暗号理論入門 5.1〜5.7

暗号理論入門 原書第3版

5.1 確率

一般的な確率の話のみ。

5.2 条件付き確率

ここも一般的な話のみ。

5.3 バースデイパラドックス

クラスに同じ誕生日の人がいる確率は思ったより高いという話。

5.4 完全守秘性

ある暗号文があるという事象と、ある平文があるという事象が互いに独立であるとき、したがって がすべての平文 とすべての暗号文 に対して成立するとき、この暗号系は完全守秘性(perfect secrecy)をもつという。

5.5 ヴァーナムの一回使い捨て暗号

を自然数とする。一回使い捨て暗号は長さ のビット列を暗号化する。
それは である。鍵 に対する暗号化関数は
　
である。鍵 の復号化関数も同じである。

平文を暗号化するとき、一様分布に従いランダムに集合 より選んだ鍵 を使って を計算する。
この暗号系は完全守秘性をもつ。

この暗号は効率的ではなく、長さ の任意の新しいブロックに対して、長さ の新しい鍵をランダムに作り、かつ交換しなければならない。
同じ鍵が複数のブロックに使用されると、この方式はもはや完全守秘ではなくなる。

5.6 乱数

乱数というものが本当に存在するかどうかというのは哲学の問題。
実用上はハードウェアとソフトウェアに基づいた乱数バイト発生器を利用する。
本当に一様に発生するかどうかは統計テストで調べる。

5.7 擬似乱数

真に乱数を発生させるのに非常に時間がかかる場合に擬似乱数発生器を利用する。これは乱数の短い系列を与えるとランダムに「見える」長い系列を計算するアルゴリズムである。
多項式計算時間で計算された系列が、真にランダムな系列と区別することができないものになる。