Chapter 13

ストリーム暗号と LFSR — GF(2) 上の漸化式

この章の位置づけ. 12 章で、ワンタイムパッドは完全に安全だが、平文と同じ長さの鍵が必要で実用にならないことを見た。 そこで、短い鍵から長い「ランダムに見える」ビット列を作り、それを平文と XOR する方法が考えられる。これがストリーム暗号である。安全性は、作ったビット列が本当にランダムな列と区別できないかどうかにかかっている。

この章では、そのための最も基本的な生成器であるLFSRを扱う。LFSR は\(\mathrm{GF}(2)\)上の漸化式で、04 章の多項式の性質がそのまま使える。 ただし LFSR を単独で暗号に使うと簡単に破れる。その理由も示す。

この章で使う既出の用語（定義は各リンク先）. 位数（02 章 1 節）、有限体上の連立 1 次方程式と掃き出し法（03 章 4 節）、 XOR（04 章 1 節）、既約多項式（04 章 3 節）、原始多項式と\(x\)の位数（04 章 4 節）、拡張ユークリッドの互除法（04 章 5 節）、 バーレカンプ・マッシー法（11 章 3 節）、鍵・既知平文攻撃・ワンタイムパッド・IV（12 章）

1. ストリーム暗号の枠組み

平文をビット列\(P_0, P_1, P_2, \dots\)、暗号文を\(C_0, C_1, \dots\)とし、

と暗号化する。\(Z_0, Z_1, \dots\)は鍵ストリームと呼ぶビット列で、秘密の鍵\(K\)から生成器で作る。 復号は同じ\(Z_i\)をもう一度 XOR するだけである（\(C_i \oplus Z_i = P_i \oplus Z_i \oplus Z_i = P_i\)）。

同じ鍵ストリームを 2 度使ってはならない。12 章 5 節のワンタイムパッドの鍵の再利用と同じく、2 つの暗号文の XOR から平文どうしの XOR が分かってしまうからである。 そのため実用の生成器は、秘密の鍵\(K\)と、メッセージごとに変える公開の値IV（初期化ベクトル、ノンスとも呼ぶ）の 2 つを入力に取り、\((K, \mathrm{IV})\)の組から鍵ストリームを作る。\(K\)が同じでも IV が違えば別の鍵ストリームになる。 この章の LFSR では、\(K\)と IV を混ぜたものを初期状態（2 節）として入れる。

2. LFSR (線形帰還シフトレジスタ)

構造

LFSR（Linear Feedback Shift Register）は、\(L\)個のビットを入れた箱（レジスタ）と、それを 1 クロックごとに更新する規則からなる。クロックとは 1 回の更新操作のことで、時刻\(n\)の状態から時刻\(n+1\)の状態を作る。

出力されるビット列を\(s_0, s_1, s_2, \dots\)と書く。最初の\(L\)ビット\(s_0, \dots, s_{L-1}\)が初期状態（利用者が与える）で、それ以降は次の漸化式で決まる:

\(c_1, \dots, c_L \in \{0,1\}\)は固定の定数で、\(c_i = 1\)の位置をタップという（XOR に参加するビットの位置）。\(c_L = 1\)とする（\(c_L = 0\)なら実質\(L-1\)ビットの LFSR になる）。

時刻\(n\)のレジスタの中身（状態）は、直近の\(L\)ビット\(s_n, s_{n+1}, \dots, s_{n+L-1}\)である。1 クロックで次のことが起きる。

1. 一番古いビット\(s_n\)を出力する。
2. 漸化式で新しいビット\(s_{n+L}\)を計算し、レジスタに入れる。
3. 状態は\(s_{n+1}, \dots, s_{n+L}\)になる。全体が 1 つずれるので「シフト」レジスタという。

この章では状態を、左が新しく右が古い順に並べて書く。時刻\(n\)の状態は\(s_{n+L-1} \cdots s_{n+1} s_n\)で、右端が次に出力されるビット、左端に新しいビットが入る。

上の図で特性多項式（次の小節）を選ぶと、状態の変化と出力列、周期が表示される。原始多項式、既約だが原始でない多項式、可約な多項式で周期がどう違うかを比べられる。

特性多項式

タップの構成を多項式で表したもの

を特性多項式（または帰還多項式）という。\(x^L\)の係数は常に 1 で、\(x^{L-i}\)の係数が漸化式の\(c_i\)である。

周期は特性多項式で決まる

状態は\(2^L\)通りしかないので、出力列はいつか必ず繰り返す。繰り返しの長さを周期という。すべて 0 の状態からは 0 しか出ないので、それ以外の状態を考えると周期は最長でも\(2^L - 1\)である。 周期は特性多項式の性質で決まり、次の表のようになる。

原始多項式を使ったときの出力をM 系列（maximal length sequence）という。以下、既約の場合の周期を示す。

ずらす操作\(E\): 数列\(s = (s_0, s_1, \dots)\)を 1 つ左にずらした数列\((s_1, s_2, \dots)\)を\(Es\)と書く。多項式\(h(x) = \sum h_i x^i\)に対し、\(h(E)s\)は第\(n\)項が\(\sum_i h_i s_{n+i}\)の数列である。 すると漸化式は、第\(n\)項が\(s_{n+L} + c_1 s_{n+L-1} + \cdots + c_L s_n\)の数列が 0 であること、つまり\(f(E)s = 0\)と書ける（標数 2 なので\(\oplus\)は\(+\)）。 \(E\)をまとめてずらす計算は多項式の掛け算と同じ規則に従うので、\((gh)(E)s = g(E)\bigl(h(E)s\bigr)\)である。特に\(f(E)s = 0\)で\(f\)が\(h\)を割り切れば、\(h = fq\)より\(h(E)s = q(E)\bigl(f(E)s\bigr) = 0\)である。 また、\(s\)が周期\(P\)を持つ（すべての\(n\)で\(s_{n+P} = s_n\)）ことは、\((E^P + 1)s = 0\)と同じである。

定理: \(f\)が既約で、\(s\)が 0 でない出力列なら、\(s\)の周期は\(f\)を法とする\(x\)の位数\(N\)（\(x^N \equiv 1 \pmod f\)となる最小の\(N\)）に等しい。

方針: 「\(f\)が\(x^P + 1\)を割り切る」ことと「周期が\(P\)の約数である」ことを行き来する。\(N\)で割り切れるので周期は\(N\)以下、逆に周期\(P\)で割り切れることを拡張ユークリッドで示して\(P \geq N\)を得る。

導出: \(x^N \equiv 1 \pmod f\)より\(f\)は\(x^N + 1\)を割り切るので、\((E^N + 1)s = 0\)、つまり\(s\)は\(N\)ごとに繰り返し、周期\(P\)は\(N\)以下である。 逆に周期を\(P\)とすると\((E^P+1)s = 0\)である。\(d = \gcd(f, x^P + 1)\)とすると、拡張ユークリッドの互除法より\(d = uf + v(x^P+1)\)と書けるので

\(f\)は既約なので\(d\)は\(1\)か\(f\)である。\(d = 1\)なら\(s = 0\)となり仮定に反する。よって\(d = f\)、つまり\(f\)は\(x^P + 1\)を割り切り、\(x^P \equiv 1 \pmod f\)なので\(P \geq N\)である。したがって\(P = N\) ∎

\(f\)が原始多項式なら、04 章 4 節の定義より\(N = 2^L - 1\)なので、0 以外のどの初期状態からでも周期は最長の\(2^L - 1\)になる。周期\(2^L - 1\)の間に状態は 0 以外の\(2^L - 1\)通りをすべて 1 回ずつ通る。

実例: L=4, f(x) = x⁴+x+1（原始多項式）

\(f(x) = x^4 + 0\cdot x^3 + 0 \cdot x^2 + 1 \cdot x + 1\)なので\(c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 1\)で、漸化式は

である。初期状態を\(s_3 s_2 s_1 s_0 = 1000\)（\(s_3 = 1\)、ほかは 0）とする。各時刻で右端のビットを出力し、\(s_{n+1} \oplus s_n\)（右から 2 番目と右端の XOR）を左端に入れる:

たとえば時刻 2 から 3 では、状態 0010 の右端\(s_2 = 0\)を出力し、新しいビット\(s_6 = s_3 \oplus s_2 = 1 \oplus 0 = 1\)を左端に入れて\(1001\)になる。

時刻 15 で初期状態 1000 に戻った。15 回（\(2^4-1\)）の更新で一周し、最長周期になっている。 出力列は\(s_0 \dots s_{14} = 000100110101111\)で、1 が 8 個、0 が 7 個である。

M 系列の統計的性質

M 系列は 1 周期（\(N = 2^L-1\)ビット）の中で次の性質を持つ。

• 1 と 0 の個数: 1 が\(2^{L-1}\)個、0 が\(2^{L-1}-1\)個で、ほぼ半々である。上の例では 8 個と 7 個である。
• 自己相関: 列を\(d\)ビット（\(1 \le d \le N-1\)）ずらしたものと元の列を 1 周期分の各位置で比べ、「一致した位置の数 − 一致しない位置の数」を求めると、どの\(d\)でも\(-1\)になる（ずらさなければ\(N\)）。ずらすと、ほとんど無関係な列に見える。上の例でも\(d = 1, \dots, 14\)のすべてで\(-1\)になる。
• 連の分布: 同じ値が続く区間を連という。上の例は\(000\,1\,00\,11\,0\,1\,0\,1111\)の 8 個の連からなる。長さ\(k\)の連の個数は連の総数のおよそ\(2^{-k}\)倍で、半分が長さ 1、4 分の 1 が長さ 2 である。上の例では長さ 1 が 4 個、長さ 2 が 2 個である。

これらは「ランダムに見える」ための良い性質で、M 系列は通信の同期、GPS の測距符号、レーダー、スペクトラム拡散通信で広く使われている。 たとえば GPS 衛星が送る測距用の符号（C/A コード）は、長さ 1023 の M 系列 2 本を XOR して作る。この作り方の符号をGold 符号といい、衛星ごとに違う組み合わせを使っても互いの相関が小さいので、同時に受信して分離できる。

ただし「統計的にランダムに見える」ことと「暗号として安全」であることは全く別である。次節でそれを見る。

3. LFSR はなぜ暗号として使えないのか

出力 2L ビットからの復元

定理: 長さ\(L\)の LFSR の 0 でない出力を連続\(2L\)ビット観測すれば、その LFSR のタップ\(c_1, \dots, c_L\)と状態が決まる（特性多項式が既約なら、次の連立方程式の解はただ 1 つに決まる）。

方針: 漸化式を、タップ\(c_i\)を未知数とする連立 1 次方程式とみなす。観測したビットは既知の係数になる。

導出: 観測した\(2L\)ビットを\(s_0, \dots, s_{2L-1}\)とする。漸化式を\(n = 0, 1, \dots, L-1\)について書くと

となる。1 本の式には連続する\(L+1\)ビットが現れ、\(L\)本目の式の最後のビットが\(s_{2L-1}\)なので、\(2L\)ビットあれば\(L\)本の式が立つ。 未知数は\(c_1,\dots,c_L\)の\(L\)個で、\(s\)は既知の 0 か 1 なので、式は\(c_i\)について 1 次である。03 章 4 節の掃き出し法（\(\mathrm{GF}(2)\)上）で解ける。状態は、観測した最初の\(L\)ビットそのものである ∎

例: 2 節の出力の最初の 8 ビット\(s_0 \dots s_7 = 00010011\)だけから、\(L = 4\)のタップを求める。4 本の式は

で、\(c_1 = 0\)、\(c_2 = 0\)、\(c_3 = 1\)、\(c_4 = 1\)と決まり、特性多項式\(x^4+x+1\)が復元された。以後の出力はすべて計算できる。

掃き出し法の計算量は\(O(L^3)\)である。11 章 3 節のバーレカンプ・マッシー法を使えば\(O(L^2)\)で済み、しかも\(L\)を知らなくても「観測した列を作る最も短い LFSR」を求められる。 リード・ソロモン符号の復号では、シンドロームを作る最短の LFSR を求めるためにこの方法を使った。ここでは攻撃者が、鍵ストリームを作る LFSR を求めるために同じ方法を使う。

帰結

\(L = 128\)の LFSR でも、連続する 256 ビットの鍵ストリームが分かれば、以後の鍵ストリームはすべて再現できる。 既知平文攻撃（12 章 3 節）で平文と暗号文の組が少しでも手に入れば、\(Z_i = C_i \oplus P_i\)で鍵ストリームが分かるので、これは現実的な攻撃である。

原因は線形性である。出力が状態の XOR だけで決まるので、連立 1 次方程式で解けてしまう。

4. 非線形化の工夫

LFSR を使いつつ線形性を壊す方法として、次のようなものがある。

しかし、これらの多くも破られている。

• A5/1（GSM 携帯電話）: 3 本の LFSR を不規則クロックで動かす。2000 年代に実時間での解読が示され、現在はレインボーテーブル（鍵と出力の対応を事前に大量に計算して表にし、観測した出力から表を引いて鍵を求める方法）を使えば短時間で解読できる。
• E0（Bluetooth の旧方式）: 4 本の LFSR とメモリからなる。鍵は 128 ビットで総当たりなら\(2^{128}\)通りだが、既知の攻撃は約\(2^{39}\)回の演算で済む。
• Crypto-1（Mifare Classic）: 48 ビットの LFSR と非線形フィルタからなる。完全に破られた。

有効な攻撃は主に 2 つある。

• 相関攻撃: 3 本の LFSR（長さ\(L_1, L_2, L_3\)）を組み合わせた生成器で、最終出力が 1 本目の LFSR の出力と確率\(p \neq 1/2\)で一致するとする。1 本目の初期状態だけを総当たり（\(2^{L_1}\)通り）し、それぞれの出力列と観測列の一致率を測ると、正しい候補だけが\(p\)に近い値を示す。全体を一度に総当たりする\(2^{L_1 + L_2 + L_3}\)通りの代わりに、1 本ずつ切り離して攻撃できる。Geffe 生成器では\(z\)が\(a\)と一致する確率が\(3/4\)なので、この攻撃が効く。
• 代数的攻撃: 非線形関数を多変数の連立方程式として書き下し、それを解く。

5. 現代のストリーム暗号

現在は LFSR を土台にしない設計が主流である。

現在の標準は ChaCha20 である。加算・ビット回転・XOR という単純な演算だけでできているので、次の利点がある。

• ソフトウェアで速い: AES の専用命令が無い CPU では AES より速い。
• タイミング攻撃に強い: タイミング攻撃とは、処理時間の差から秘密の値を推定する攻撃である。ChaCha20 は表を引く処理が無いので、キャッシュの状態によって処理時間が変わることがない。

スマートフォンの HTTPS などでは、ChaCha20 と認証方式 Poly1305 を組み合わせた ChaCha20-Poly1305 が広く使われている。

6. まとめ