非線形フィードバックシフトレジスタ

非線形フィードバック シフト レジスタ(NLFSR) は、入力ビットが前の状態の非線形関数である シフト レジスタです。

n ビットのシフトレジスタrの次の状態は次のように定義されます。

${\displaystyle r_{i+1}(b_{0},b_{1},b_{2},\ldots ,b_{n-1})=r_{i}(b_{1},b_{2},\ldots ,f(b_{0},b_{1},b_{2},\ldots ,b_{n-1}))}$ 、

ここでfは非線形フィードバック関数である。^{[ 1 ]}

アプリケーション

非線形フィードバックシフトレジスタは、現代のストリーム暗号、特にRFIDやスマートカードアプリケーションに用いられるコンポーネントです。NLFSRは、線形フィードバックシフトレジスタ（ LFSR ）よりも暗号解読攻撃に対する耐性が高いことが知られています。

生成中

最大長2n^のnビットNLFSRを生成し、デ・ブリュイン系列を生成する方法は、 n段の最大長LFSRを拡張することによって知られている。 ^{[ 2 ]}しかし、長周期が保証された他の大規模NLFSRの構築は未解決の問題である。^{[ 3 ]}ブルートフォース法を用いて、 n≤25およびn=27の最大周期nビットNLFSRのリストが作成されている。 ^{[ 4 ] [ 1 ]}

新しい手法では、非線形性を導入するために進化的アルゴリズムの使用が示唆されている。 ^{[ 5 ]}これらの研究では、進化的アルゴリズムはLFSRからの文字列にさまざまな操作を適用して品質を高め、適応度関数（ここではNISTプロトコル） ^{[ 6 ]}の基準を効果的に満たす方法を学習する。

NLFSRベースの暗号

• アハターバーン
• 粒
• KeeLoqアルゴリズム
• トカゲ
• トリヴィアム
• ベスト

参考文献

1. Rachwalik, Tomasz; Szmidt, Janusz; Wicik, Robert; Zabłocki, Janusz (2012年6月3日).特殊用途ハードウェアによる非線形フィードバックシフトレジスタの生成(PDF) . 軍事通信研究所 (ワルシャワ). p. 1. 2017年5月3日閲覧。
2. CG Günther、「de Bruijnシーケンスによって制御される交互ステップジェネレータ」、Advances in Cryptology – EUROCRYPT '87、 doi : 10.1007/3-540-39118-5_2
3. (n, k)-非線形フィードバックシフトレジスタの解析と合成について、2008年。
4. E. Dubrova、「最大周期NLFSRのリスト」、Cryptology ePrint Archive、レポート2012/166、2012年3月、 http://eprint.iacr.org/2012/166。
5. A. Poorghanad, A. Sadr, A. Kashanipour「進化的手法を用いた高品質疑似乱数の生成」IEEE計算知能とセキュリティ会議、第9巻、pp. 331–335、2008年5月[1]
6. NIST.「暗号アプリケーション用乱数および擬似乱数生成器の統計的テストスイート」 NIST、特別出版、2010年4月