前書き
リニアフィードバックシフトレジスタ（LFSR）は、入力ビットの値がシフト前のレジスタの残りのビットの値に基づいて関数によって一意に設定されるビットワードのシフトレジスタです。シフトレジスタは、トランジスタ、抵抗などの個別のコンポーネントで構成されるある種の電気回路にすることができ、マイクロ回路に統合したり、プログラムに実装したりすることもできます。フィードバックを追加すると、シフトレジスタが疑似乱数ジェネレータに変わります。これは暗号化で広く使用されています。この記事では、ハードウェアからさまざまなアプリケーションまでのRSLOSの動作原理を分析します。
一般に、レジスタは、相互接続された1ビットのメモリ要素で構成される回路です。このような回路は、nビットのバイナリデータを書き込み、保存、読み取りできます。この記事では、シフトレジスタと呼ばれる一種のレジスタについて説明します。ほとんどの場合、シフトレジスタは直列に接続されたDフリップフロップに基づいて組み立てられ、これらのフリップフロップの数はビット数nに等しくなります。Dトリガーの原理から記事を始めます。
Dトリガー
非常に基本的なことについて簡単に触れましょう。世界的に、電子機器はアナログとデジタルの2つのセクションに分けることができます。 2番目の主な特徴は、信号が個別の電圧レベルによって設定されることです。さらに、2つの個別のレベルしかありません。したがって、電圧をボルトで記録する代わりに、2つの個別のレベルの1つに名前を付けるだけで十分です。これは、「ゼロ」と「1」という名前の表示方法です。実際、それらはいくつかの電圧レベルを定義しますが、それは何でもかまいません。ただし、ほとんどの場合、「ゼロ」は0ボルトのレベルを意味し、「1」は5 V、3.3 V、1.8 V、1.5Vなどのレベルを意味します。したがって、「入力ゼロで、出力１で」という句は、「ゼロのレベルに対応する入力電圧で、レベル１に対応する出力電圧で」を意味する。
. , ? D- , ! .
– , .
D- – , . ,
D- , . : D (), C ( , , , clk, clock) Q (). : , , . , , .
. 1 - D-
D- : C, . . . - «», «», «».
|
|
||
(D) |
(Q) |
(D) |
(Q) |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
« ». , ( ) . , . , .. . , , . , .
, . D- . , . , , . D-, .
, n D-. . , , . .
? , , , . . «» . , , . ? ( ). . . , , , . . . , , . , : .
№ |
|
0 |
1 |
2 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
3 |
0 |
0 |
0 |
1 |
0 |
4 |
0 |
0 |
0 |
0 |
1 |
5 |
0 |
0 |
0 |
0 |
0 |
- . . ? , . . , , , , . .
hi - , . .
? . , , . , , 1 , . . . , .
, . ? , , . n , n . , . Xi. , . . . N, Xi+N = Xi i. 2n-1, -. , , 2n-1. .
GF(2). . t + 1, (x) p:
Y(t) t. T – n :
, , . , GF(2) - : k 2k-1. . , . , . .
n |
LFSR-2 |
LFSR-4 |
2 |
2, 1 |
|
3 |
3, 2 |
|
4 |
4, 3 |
|
5 |
5, 3 |
5, 4, 3, 2 |
6 |
6, 5 |
6, 5, 3, 2 |
7 |
7, 6 |
7, 6, 5, 4 |
8 |
|
8, 6, 5, 4 |
, , . , n= 8 :
. : . . , . , , , . . : .
. . . . 2n1 , 2n2, . ., 2n1+n2+… , n1, n2, … .
. . . — 2017. — 117 .
. . . — , 2008. — 314 .
Eastlake D., Schiller J., Crocker S. Randomness requirements for security. — 2005. — 48 .