線形帰還シフトレジスタ
LFSRは、(特に軍事用途で)ストリーム暗号の擬似乱数生成器として使われてきた。これは機械式でも電子回路でも構成が簡単で、周期が長く分布が一様なためである。しかし、LFSRは線形システムであるため、暗号解読は比較的容易である。平文と対応する暗号文がわかっているとき、システムの使用するLFSRの出力を再現でき、Berlkamp-Massey法を使って最小サイズのLFSRを構築でき、容易に暗号文を復号できるようになる。
LFSRに基づく暗号におけるこのような問題への対策として、一般に以下の3つの手法がある。
LFSRの状態のうち、一部のビットを非線形に組み合わせて使う。
2つ以上のLFSRの出力を非線形に組み合わせて使う。
LFSRのクロックを不定間隔で進める(alternating step generator)。
LFSRに基づくストリーム暗号としては、GSM携帯電話で使っている A5/1 や A5/2、Bluetooth で使っている E0、shrinking generator などがある。A5/2 は既に破られており、A5/1 と E0 も非常に弱いと言われている。LTEの暗号アルゴリズムUEA2,UIA2で使用されているストリーム暗号 SNOW 3Gも、LFSRを利用している。