-
-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathrand.tex
138 lines (120 loc) · 8.76 KB
/
rand.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
\chapter{乱数}
\label{chap:rand}
この章では安全な暗号を構成するのに不可欠な乱数の紹介をします。
\ref{sec:determin}節で書いたように暗号は確率的アルゴリズムであることが望まれます。
確率的なものを実現するにはよい乱数が必要です。
暗号にとってよい乱数とは何か、その満たすべき性質を紹介します。
\section{擬似乱数}
Vernam暗号では乱数を使いました。
乱数とはサイコロやルーレットのように次に何が出るかわからない、再現性の無いでたらめな数字の列のことです。
しかし、コンピュータでは本当の乱数を扱うのはなかなかやっかいです。
与えられた手順とデータにしたがって常に同じ値を計算することを決定的というのでした（\ref{sec:determin}節参照）。
コンピュータは決定的な処理が得意です。
ですが、やる度に計算結果が異なる確率的な処理は通常できないのです。
そんなプログラムがあったら、それは大抵バグですね。
そのため厳密な乱数を扱うのは諦めて、一見乱数のように見える擬似乱数というものを代わりに扱います。
擬似乱数生成器とは、ある決まった数式と初期値を出発点として決定的に計算される数列を出力する装置やアルゴリズムのことです。
擬似乱数生成器が生成した数列を擬似乱数といいます。
初期値が同じなら常に同じ擬似乱数が出力されます。
大抵のプログラミング言語に用意されている\texttt{rand()}という関数は擬似乱数を生成します。
\[
\texttt{(rand() \% 6) + 1}
\]
の値を使うことでサイコロの値をシミュレーションされた方も多いでしょう（\texttt{a \% b}は\texttt{a}を\texttt{b}で割った余りを表します）。
実行するたびに異なる数列が欲しいときは、初期値にプログラムを起動したときの時刻を設定することが多いです。
\texttt{rand()}は線形合同法と呼ばれるアルゴリズムを使って実装されることがあります。
線形合同法によって生成される擬似乱数はパラメータによっては偶奇が規則的に現れ、ランダム性が高くありません（そのときは\texttt{rand()}をその関数の値のとり得る最大値で割って0～1の間の小数にしてから6倍して整数に切り捨てるとまだましになります）。
様々なシミュレーションではMersenne Twister（メルセンヌ・ツイスタ）、略してMTという擬似乱数生成器が使われるようです。
MTは、高速に計算できる、その擬似乱数列が$2^{19937}-1$という長い周期を持つ、統計的に十分ランダムで均等に分布する、という性質があるからです。
シミュレーションにとって都合のよい擬似乱数が得られるのです。
しかし、MTは暗号のシステムでそのまま使ってはいけません。
\section{暗号論的擬似乱数}
\label{sec:rand}
暗号の用途で使われる乱数は、シミュレーションなどで使われる擬似乱数とは異なる性質が要求されます。
通常の擬似乱数と区別するために暗号論的擬似乱数と呼ばれることがあります。
暗号に使うということがわかっている場合は単に擬似乱数ということもあります。
暗号論的擬似乱数の直感的な定義は、どれだけ過去の生成列を見ても次の1ビットの出力が0か1のどちらか予測できない（$1/2$以上の確率で当てられない）という性質を持つものです。
暗号論的擬似乱数生成器も決定的なアルゴリズムなのですが、生成列から初期値や次に出る値を推測できてはいけないのです。
MTは回路の内部に624個の32ビットの値を持ちます。その内部変数を逐次更新しながら擬似乱数列として出力します。
したがって連続する$624 \times 32$ビットの出力を観察すれば内部状態が決定します。
するとそれから先に出現する値を計算できてしまうので暗号論的擬似乱数生成器ではありません。
先ほど擬似乱数の初期値に時刻を設定する話をしました。
現在時刻のパターンはそれほど多くはないので、その方法では初期値を推測できてしまいます。
ゲームに使うなら十分かもしれませんが、暗号に使う擬似乱数生成器の初期値に時刻を使ってはいけません。
コンピュータで暗号論的擬似乱数を扱うときは
Linuxでは\texttt{/dev/random}や\texttt{/dev/urandom}という乱数生成デバイス、
Windowsでは\texttt{CryptGenRandom()}という専用の関数を使うことが推奨されます。
これらのデバイスや関数は、内部でそのときのHDD、メモリ、マウスやキーボードの情報など常に変動している情報を乱数生成に利用します。
そうすることで誰も予測も再現もできない値を生成しています。
\section{擬似乱数とストリーム暗号}
\label{stream}
Vernam暗号は平文と同じサイズの乱数が必要でした。
乱数の代わりに暗号論的擬似乱数生成器を使ってみましょう。
暗号論的擬似乱数生成器に初期値を入れるとそれに対応した決まった乱数列を生成できます。
相手にその初期値を渡します。すると両者で同じ擬似乱数列を共有できます。
乱数全てを共有する必要があるVernam暗号に比べて初期値の共有だけですみます。
このような考えで作られた共通鍵暗号をストリーム暗号といいます。
\image{stream.pdf}{Vernam暗号とストリーム暗号}
ストリーム暗号は初期値$s$を秘密鍵として決定的な擬似乱数$r$を生成し、それと平文$m$の排他的論理和をとって暗号文$c$とします。
\[
r := \texttt{rand}(s), \quad c:=\Enc(m):=m \oplus r.
\]
ここで「$:=$」は左辺を右辺で定義するという記号です。
復号は同じ$s$を使って擬似乱数$r$を生成し、暗号文$c$との排他的論理和をとって元の平文$m$を得ます。
\[
r := \texttt{rand}(s), \quad \Dec(c):= c \oplus r =(m \oplus r) \oplus r = m.
\]
ストリーム暗号は初期値のサイズが平文のサイズよりも短いので、ブロック暗号と同じく情報理論的安全性を持っていません。
総当たり攻撃以外の効率のよい方法が無いことが求められる計算量的安全性を持つ暗号です。
計算量的安全性については\ref{sec:compute}節を参照ください。
ストリーム暗号にはRC4や日立のEnocoro、九州大学とKDDIによるKCipher-2などがあります。
RC4は長らく使われていましたが2012年頃から攻撃方法が見つかり2013年にはCRYPTRECの運用監視リストに入りました。
\section{CTRモードとストリーム暗号}
\label{CTR}
擬似乱数を作ればストリーム暗号を構成できます。
擬似乱数はどんな方法で作ってもかまいません。
擬似乱数の作り方の一つにブロック暗号を使う方法があります。
初期値$s$と数値$c=0$を連結したもの$s||c$を平文とみなしてブロック暗号で暗号化します。
それから$c$（カウンタという）を一つずつ増やしながら$s||c$を暗号化します。
この操作をカウンタモード（counter mode）、略してCTRモードといいます。
CTRモードで作られた暗号文を擬似乱数とみなし平文と排他的論理和をとるとストリーム暗号になります。
暗号化するときと復号するときは同じ操作で擬似乱数を生成します。
図\ref{fig:ctr.pdf}において$c_i$と$m_i$を入れ換えると復号を表す図になります。
\image{ctr.pdf}{CTRモードの暗号化と復号}
\ref{CBC}節で紹介したCBCモードは一つ前に作った暗号文が次の暗号文の作成に必要でした。
つまり$i$番目のブロックの暗号化は$i-1$番目のブロックの暗号化が終わるまで開始できません。
しかし、CTRモードでは$s||c$の暗号化を一つ前の処理と独立に行えます。
つまり複数の暗号化を並列に実行できるのでCBCモードより高速に暗号化できます（CBCモードの復号は並列実行可能です）。
このように一般的にブロック暗号があればCTRモードを用いてストリーム暗号を構成できます。
ただ構成できるからといってストリーム暗号の研究が不要となるわけではありません。
CTRモードよりも効率よく擬似乱数を生成する方法があるからです。
たとえばKCipher-2はAESよりも高速に暗号化できるように設計され、2013年に電子政府推奨リストに採用されています~\cite{KCipher2}。
またBernsteinが開発したChaCha20というストリーム暗号もモバイル環境でAESより高速です。
2014年からGoogleのChromeブラウザはTLSにおいてRC4の代わりにChaCha20を使うようになっています~\cite{ChaCha20}。
\section{Intel CPUの\texttt{rdrand}命令}
\label{sec:rdrand}
暗号論的擬似乱数は、暗号にとって重要なのに作るのが難しいという悩みがありました。
擬似乱数生成器に渡す初期値をどのように決めるかという悩みもあります。
そのためIntelのIvy Bridge以降のCPUには\texttt{rdrand}という命令が追加されています。
\texttt{rdrand}はCPU内部の不確かな電子状態を使うことで決定的でない乱数列を生成します。
難しいアルゴリズムを知らなくてもこの命令を呼べば暗号に使える乱数が得られるのでとても便利です。
実際、\texttt{gcc}というコンパイラで提供される\texttt{std::random\_device}という乱数生成ライブラリの実装では\texttt{rdrand}が出力する値をそのまま使っています（gcc-4.8.2の\texttt{libstdc++-v3/src/c++11/random.cc}で確認）。
しかし前述の擬似乱数生成デバイス\texttt{/dev/urandom}の実装はこの命令だけに依存するような作り方をしていません。
なぜでしょうか。
仮に\texttt{rdrand}の実装が、あるストリーム暗号で生成される擬似乱数を出力していたとしましょう。
初期値を秘密にしておけば、通常これは暗号論的擬似乱数と区別ができません。
ところが初期値を知っている人（この場合はIntel）にとっては、この乱数は決定的で予測可能です。
これではこの乱数を使って作られた秘密鍵が初期値を知っている人にのみ知られてしまう可能性があります。
このような状況をバックドアがあるといいます。
2013年アメリカの国家安全保障局（NSA）が様々な盗聴を行っていたという告発がありました。
そのためセキュリティに関するオープンでないハードウェア技術は信用するべきではないという考え方が強くなりました。
Intelの\texttt{rdrand}の実装にバックドアがある可能性はとても低いと思われます。
しかし、\texttt{/dev/urandom}の実装者は万一そんなことがあっても安全性を保てるように、\texttt{rdrand}だけには依存しない設計をしているのです。
\section{この章のまとめ}
暗号に使われる乱数は、シミュレーションなどで使われる乱数と違い過去のデータから次の値を推測できてはいけません。
たとえば擬似乱数で有名なMTをそのまま使ってはいけません。
もし次の値を推測できる乱数を使ってしまうと、たとえ暗号自体が安全だったとしてもシステム全体としては安全にならないことがあります。
暗号プロトコルの中で乱数を使うときは十分な注意が必要です。
ストリーム暗号は擬似乱数を使います。
CTRモードを用いるとブロック暗号から擬似乱数を作ってストリーム暗号を構成できます。
近年、AESよりも高速なストリーム暗号も利用され始めています。