Chapter 13

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

ワンタイムパッドの夢と現実. 12 章で「ワンタイムパッドは完全に安全だが、鍵が長すぎて使えない」と分かった。

ならば——短い鍵から、長い「ランダムに見える」列を作れないか?

これがストリーム暗号の発想である。短い種（鍵）から擬似乱数列を生成し、それを平文と XOR する。 安全性は「その擬似乱数列が本物のランダムと区別できないこと」に懸かっている。

この章では、その最も基本的な生成器である LFSR を扱う。 LFSR は\(\mathrm{GF}(2)\)上の漸化式そのものであり、04・05 章の多項式論が直接使われる。 そして——重要なことに——LFSR 単独では暗号として破れる。その理由も導出する。

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

\(Z_i\)は鍵\(K\)から生成される鍵ストリーム。復号は同じ\(Z_i\)をもう一度 XOR するだけ。

必須の要件: 同じ鍵ストリームを 2 度使ってはならない（12 章のワンタイムパッド再利用問題と同じ）。 そのため実用では鍵\(K\)に加えてIV / ノンス（毎回変わる公開値）を入力する。

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

構造

\(L\)個のビットを持つレジスタ。毎クロック:

1. 最下位ビットを出力
2. 全体を 1 ビットシフト
3. 特定の位置（タップ）のビットの XOR を、空いた最上位に入れる

漸化式で書くと:

（\(c_i \in \{0,1\}\)がタップの有無。）

特性多項式

タップの構成を多項式で表す:

これを特性多項式（または帰還多項式）という。

04 章の多項式論がそのまま適用できる. LFSR の振る舞いは、この多項式の性質で完全に決まる。特に周期が:

\(f(x)\)の性質	周期
可約	短くなる（初期値によっても変わる）
既約だが原始でない	\(f\)の位数（\(2^L-1\)の約数）
原始多項式	\(2^L-1\)（最大）

原始多項式を使ったときの出力を M 系列 (maximal length sequence) という。 「原始多項式なら\(x\)のべきが全非零要素を巡る」（04・05 章）ことが、 そのまま「レジスタの状態が全\(2^L-1\)通りを巡る」に対応している。

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

漸化式: \(s_{n+4} = s_{n+3} \oplus s_n\) … ではなく、多項式の対応から \(s_{n+4} = s_{n+1} \oplus s_n\)（タップは\(x\)と定数項）。

初期状態 1000 から始めると:

15 クロック（\(2^4-1\)）で元の状態に戻る = 最長周期 ✓

M 系列の統計的性質

1 周期（\(2^L-1\)ビット）の中で:

• 1 の個数: \(2^{L-1}\)個、0 の個数: \(2^{L-1}-1\)個（ほぼ半々）
• 自己相関: ずらして比較すると、一致数と不一致数の差が常に\(-1\)（鋭いピーク）
• 連（ラン）の分布: 長さ\(k\)の連が全体の\(2^{-k}\)の割合

これらは「ランダムに見える」ための良い性質である. だから M 系列は通信の同期、GPS の測距符号、レーダー、スペクトラム拡散で広く使われる。 GPS 衛星が送る C/A コードは長さ 1023 の M 系列（Gold 符号）である。

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

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

バーレカンプ・マッシー攻撃

定理: 長さ\(L\)の LFSR の出力を連続\(2L\)ビット観測すれば、 その LFSR の構成（タップと状態）が完全に決定できる。

なぜか: 漸化式\(s_{n+L} = \sum_i c_i s_{n+L-i}\)は、係数\(c_i\)に関する線形方程式である。 未知数は\(c_1,\dots,c_L\)の\(L\)個。\(2L\)ビットあれば\(L\)本の式が立ち、 03 章の掃き出し法で解ける。\(O(L^2)\)（バーレカンプ・マッシー法なら効率的）。

11 章と同じアルゴリズムがここに出てくる. RS 符号の復号では「シンドロームを生成する最短 LFSR を求める」ためにバーレカンプ・マッシー法を使った。 ここでは攻撃者が「鍵ストリームを生成する LFSR を求める」ために同じ手法を使う。

符号理論では味方、暗号では敵——同じ数学が立場によって役割を変える好例である。

帰結

\(L = 128\)の LFSR でも、256 ビット観測されれば終わり。 既知平文攻撃（平文と暗号文のペアが少しでも手に入る状況）で、鍵ストリームは即座に露見する。

根本原因は「線形性」。線形な仕組みは連立方程式で解ける。

4. 非線形化の工夫

LFSR を使いつつ線形性を壊す手法:

しかし、これらも多くが破られている.

• A5/1（GSM 携帯電話）: 3 個の LFSR を不規則クロックで動かす。 2000 年代に実時間で破られ、現在はレインボーテーブルで数秒で解読される
• E0（Bluetooth）: 4 個の LFSR + メモリ。\(2^{38}\)程度の計算量で破られた
• Crypto-1（Mifare Classic 交通カード）: 48 ビット LFSR + 非線形フィルタ。完全に破られた

相関攻撃（LFSR の出力と最終出力に統計的相関があると、各 LFSR を個別に攻撃できる）や 代数的攻撃（非線形関数を多変数連立方程式として解く）が有効なためである。

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

LFSR ベースを離れた設計が主流:

ChaCha20 が現代の標準である. 加算・ビット回転・XOR という単純な演算だけで構成され、

• ソフトウェアで高速（AES の専用命令が無い環境では AES より速い）
• タイミング攻撃に強い（テーブル参照が無いのでキャッシュ経由の情報漏洩が起きない）

モバイル端末の HTTPS では ChaCha20-Poly1305 が広く使われている。

6. まとめ