線形フィードバックシフトレジスタ。フィードバック付き線形シフトレジスタ線形シフトレジスタの例

ストリーム暗号を構築するために、シフトレジスタ上のシーケンスが非常に頻繁に使用されます。フィードバックシフトレジスタは、図に示すように、シフトレジスタとフィードバック機能の2つの部分で構成されています。 87.シフトレジスタ自体はビットのシーケンスであり、その数によってレジスタの長さが決まります。したがって、nビットがレジスタに含まれている場合、それらはnビットシフトレジスタと言います。ビットが取得されるたびに、シフトレジスタのすべてのビットが1桁右にシフトされ、通常は最下位ビットに向かってシフトされます。シフトレジスタの周期は、繰り返しを開始する前の結果のシーケンスの長さです。

米。 87。

ビットに対して演算を実行する数学関数は、フィードバックとして機能できます。最も単純なタイプのフィードバックシフトレジスタは、線形フィードバックシフトレジスタ（LFSR）です。 LFSRでは、フィードバックはレジスタの一部のビットに対するモジュロ2加算（XOR）演算です。これらのビットのリストは、図1に示すように、一連のタップまたはピックアップポイントと呼ばれます。 88.このようなパターンは、フィボナッチ構成と呼ばれることもあります。フィードバックシーケンスが単純なため、かなり開発された数学的理論を使用してLFSRを分析できます。いずれの場合も、生成されたSRPの品質は、特別な一連のテストによって評価されます。

米。 88。

LFSRは多項式の形式で記述されます。この場合、多項式の最初の要素の次数はシフトレジスタのビット数を示し、多項式の残りのメンバーの指数指数は、使用されるピックアップポイントを示します。したがって、たとえば、x 4 + x + 1と書くと、4つの要素のレジスタが使用され、ビットbiとb 0がフィードバックの形成に関与します（図89）。

米。 89.4

図に示すレジスタの動作を考えてみましょう。 89.たとえば、値0101で初期化します（初期初期化は、ゼロのみのシーケンスを除いて、ビットの任意のシーケンスで実行できます。この場合、フィードバックは常にゼロの値を形成し、レジスタは期待されるPSPを生成しません）。したがって、レジスターでは、1つの位置だけ右にシフトします。 1に等しい最下位ビットはレジスタから強制的に出され、PRSの最初のビットを形成します。シフト前に位置bおよびb0にあったビットは、2を法として追加され、新しいビットを形成します。

レジスタの上位ビット。検討したLFSRの動作の実例を図1に示します。 90。

米。 90。

図からわかるように。 90の場合、レジスタの充填は16の可能な状態のうち15の重みを通過します（LFSRが0000の場合、16番目の状態は考慮できないと以前に決定しました）。その後、レジスタの入力は再び初期値0101に等しくなり、ビットシーケンスの展開が繰り返され始めます。レジスタの出力シーケンスは、最下位ビットの文字列（図90の水平線まで）：101011110001001になります。繰り返される前のビットシーケンスのサイズは、ピリオドと呼ばれます。特定のLFSRの最大期間を確保するには（つまり、レジスタがすべての可能な内部状態を通過するため）、レジスタの動作を決定する多項式は2を法とする原始でなければなりません。大きな素数と同様に、そのような多項式を生成します。多項式を取り、それが2を法として既約であるかどうかを確認することしかできません。一般的な場合、次数nの原始多項式は、x 2 "+1の約数である既約多項式ですが、2" -1の約数であるすべてのdのxd + 1の約数ではありません。B。 Schneierは、2を法として既約であるいくつかの多項式の表を提供します。

LFSRの動作例を検討した結果得られた知識をまとめると（図90）、nビットのLFSRは2” -1の内部状態のいずれかになり得ると言えます。理論的には、このようなレジスタは、2 n-1ビットの周期を持つ疑似ランダムシーケンスを生成できます。このようなレジスタは、最大周期のLFSRレジスタと呼ばれます。結果の出力はtシーケンスと呼ばれます。

文部科学省

ロシアの州立社会大学

情報技術学部

情報保護部門

暗号化の方法と情報セキュリティを確保する手段

コースワーク

「R 疑似乱数発生器として線形フィードバックを備えたシフトレジスタ」

完了：

3年生

KZOI-D-3グループ

ラリオノフI.P.

チェック済み：

協会バラノバE.K.

モスクワ2011
コンテンツ

序章 ……………………………..…………………………………….3

仕事の理論的基礎…………………………………………4
1. フィードバックシフトレジスタに関する一般情報…………..4
  1. RgCsLOSに基づくストリーム暗号について…………………。………10
  2. 生成された疑似乱数シーケンスPgCsLOSの線形複雑性について……………………………………。……12
  3. 生成された疑似乱数列PrCsLOSの相関独立性について………..….13
  4. 生成された疑似乱数のシーケンスを開く他の方法についてRgCsLOS……………………………………..14
疑似乱数シーケンスジェネレータとしてのRgCsLOSのソフトウェア実装….…………………………….15
1. アルゴリズムの一般化されたスキーム……………………………………... 15
2. ソフトウェアモジュールとインターフェースの説明……………….16
3. ユーザーマニュアル………………………………………... 20

結論 ………………………………………………………………22

参考文献………………………………………………….....23

附属書A ….………………………………………………………..24

前書き

この作業の目的は、フィードバック付きのシフトレジスタに基づく疑似乱数ジェネレータの動作を実装するソフトウェアアプリケーションを開発することです。グラフィカルインターフェイスを備えたこのアプリケーションの開発は、言語で実行されます WindowsOS用のC ++。

20世紀の暗号化の発展に伴い、暗号学者は、メッセージを迅速かつ確実に暗号化および復号化できる暗号化デバイスとマシンを作成するという課題に直面しました。当時すでにオープンしていた対称暗号化システムはこの要件を満たしていましたが、その弱点は鍵とその機密性への強い依存でした。この目的に使用できる最も便利なクラスの暗号は、ゲーミング暗号です。この問題は、メッセージが復号化されたときに検出できなかったガンマを生成することで発生しました。理論的には、これは、ガンマがランダムで時間の経過とともに変化するたびに可能でした。ただし、完全にランダムに変化するガンマを使用する場合、メッセージの信頼できる暗号化-復号化を提供することは困難です。暗号学者はこの問題を解決するタスクを引き受けました。その目的は、特定のルールに従ってランダム範囲の生成を実装するアルゴリズムを見つけることでした。このようなシーケンスには、「おそらく」ランダムな位置に0と1が含まれている必要があります。 1と0の数はほぼ同じである必要があります。このランダムシーケンスはと呼ばれます疑似ランダムランダムではなく、特定のルールに従って生成されたためです。

解決策はすぐに見つかりました。シフトレジスタの特性の研究により、フィードバックシフトレジスタは、その内部構造のためにデコードに対して十分に耐性のある疑似ランダムシーケンスを生成できることを確立することが可能になりました。

1.仕事の理論的基礎

1.1線形フィードバックを備えたシフトレジスタに関する一般情報

シフトレジスタシーケンスは、暗号化とコーディング理論の両方で使用されます。彼らの理論は十分に発達しており、シフトレジスタベースのストリーム暗号は、電子機器が登場するずっと前から軍事暗号の主力製品でした。

フィードバックシフトレジスタ（以下、PgCsOS）は、シフトレジスタとフィードバック機能の2つの部分で構成されています。シフトレジスタはビットのシーケンスです。ビット数が決定されますシフトレジスタの長さ、長さがnビットの場合、レジスタは呼び出されますnビットシフトレジスタ。ビットを抽出する必要があるときはいつでも、シフトレジスタのすべてのビットが1桁右にシフトされます。新しい左端のビットは、レジスタ内の他のすべてのビットの関数です。シフトレジスタの出力は1ビットで、通常は最下位ビットです。シフトレジスタ期間繰り返しを開始する前の結果のシーケンスの長さです。

図フィードバックシフトレジスタ

シフトレジスタは、デジタルハードウェアを使用して簡単に実装できるため、ストリーム暗号ですぐに使用できるようになりました。 1965年、ノルウェー政府の主任暗号学者であるErnst Selmerは、シフトレジスタシーケンス理論を開発しました。 NSAの数学者であるソロモンゴロムは、彼の結果のいくつかとセルマーの結果を概説した本を書きました。最も単純なタイプのフィードバックシフトレジスタは線形フィードバックシフトレジスタ（線形フィードバックシフトレジスタ、以下LFSRまたはRgCsLOS）。このようなレジスタのフィードバックは、レジスタの一部のビットのXOR（モジュロ2加算）であり、これらのビットのリストはタップシーケンスと呼ばれます。このようなレジスタは、フィボナッチ構成と呼ばれることもあります。フィードバックシーケンスが単純であるため、かなり開発された数学的理論を使用してPgCsLOCを分析できます。結果の出力シーケンスを分析することにより、これらのシーケンスが安全であるために十分にランダムであることを確認できます。シフトレジスタは、暗号化において他のシフトレジスタよりも頻繁に使用されます。

図PgCsLOSフィボナッチ

一般的に、n -ビットPrCsLOSは、次のいずれかになります。 N = 2n -1つの内部状態。これは、理論的には、このようなレジスタがT = 2の周期で疑似ランダムシーケンスを生成できることを意味します。 n -1ビット。（内部状態の数と期間は等しい N = Tmax = 2n -1。PrCsLOCをゼロで埋めると、シフトレジスタが無限のゼロシーケンスを出力するため、これはまったく役に立ちません）。特定のタップシーケンスでのみ、PrCsLOSは2つすべてを循環的に通過します n -1つの内部状態（RgCsLOSなど）は最大期間のRgSsLOS。結果の結果はと呼ばれますM系列.

例。次の図は、1番目と4番目のビットからタップした4ビットのPrCsLOSを示しています。値1111で初期化されている場合、レジスタを繰り返す前に、次の内部状態が発生します。

シフトティック番号（内部状態）	登録ステータス	出力ビット
シフトティック番号（内部状態）		出力ビット
初期値














15（初期状態に戻る）
16（リピート状態）

出力シーケンスは、最下位ビットのストリングになります。11 1 1 0 1 0 1 1 0 0 1 0 0 0、周期T = 15、可能な内部状態の総数（ゼロを除く）、 N = 2 4 -1 = 16-1 = 15 = Tmax したがって、出力シーケンスは次のようになります。 M -順序。

特定のPgCsLOSが最大周期を持つためには、タップシーケンスと定数1から形成される多項式が2を法とする原始でなければなりません。多項式は累乗の合計として表されます。たとえば、次数の多項式です。 n 次のように表示されます：

anxn + a n-1 x n-1 +…+ a 1 x 1 + a 0 x 0 = anxn + a n-1 x n-1 +…+ a1 x + a 0、ここでa i =（0、1 ）i = 1…nの場合、axi –ビットを示します。

多項式の次数は、シフトレジスタの長さです。次数nの原始多項式は、xの約数である既約多項式です。 2n-1 +1ですが、xの約数ではありません d すべてのdが2の約数である場合は+1 n -1。対応する数学的理論はにあります。

一般に、2を法とする特定の次数の原始多項式を生成する簡単な方法はありません。最も簡単な方法は、ランダムに多項式を選択し、それが原始であるかどうかを確認することです。これは簡単ではなく、ランダムに選択された数が素数であるかどうかをチェックするようなものですが、多くの数学ソフトウェアパッケージでこの問題を解決できます。

確かにすべてではありませんが、2を法とするさまざまな次数の多項式を以下に示します。たとえば、エントリ

（32、7、5、3、2、1、0）は、次の多項式が2を法とする原始であることを意味します：x 32 + x 7 + x 5 + x 3 + x 2 + x +1。

これは、最大周期でPrCcLOCに簡単に一般化できます。最初の数字はPrCsLOSの長さです。最後の数字は常に0であり、省略できます。 0を除くすべての数値は、シフトレジスタの左端から数えてタップシーケンスを指定します。つまり、次数の低い多項式の項は、レジスタの右端に近い位置に対応します。

例を続けると、（32、7、5、3、2、1、0）と書くことは、特定の32ビットシフトレジスタに対して、32、7、5、3、2番目のXORによって新しいビットが生成されることを意味します。、および最初のビット、結果のRgCsLOSは最大長になり、2の後に繰り返されるまで循環します。 32-1の値。

図4最大長の32ビットPrCsLOS

タップシーケンスが多項式（32、7、5、3、2、1、0）によって特徴付けられるプログラムコードPgCsLOSについて考えてみます。 C言語では、次のようになります。

int LFSR（）（

static unsigned long ShiftRegister = 1;

/ * 0を除くすべて。* /

ShiftRegister =（（（（ShiftRegister >> 31）

^（ShiftRegister >> 6）

^（ShiftRegister >> 4）

^（ShiftRegister >> 2）

^（ShiftRegister >> 1）

^ ShiftRegister））

＆0x00000001）

<<31)

| （ShiftRegister >> 1）;

ShiftRegister＆0 x 00000001;）を返します

シフトレジスタがコンピュータワードよりも長い場合、コードはより複雑になりますが、それほどではありません。アプリケーションで B 2を法とするいくつかの原始多項式の表が与えられています。後でそれを使用して、これらの多項式のいくつかのプロパティを識別し、ソフトウェアの実装でタップシーケンスを設定します。

表のすべての要素の係数の数が奇数であることに注意してください。 PrCfLOCは、ストリーム暗号を使用した暗号化や疑似乱数ジェネレーターでよく使用されるため、このような長いテーブルは、PrCfLOCでのさらなる作業のために提供されています。この場合、最高次数が7以下の多項式を使用できます。

p（x）がプリミティブの場合、xもプリミティブです。 n p（1 / x）であるため、テーブルの各要素は実際には2つの原始多項式を定義します。たとえば、（a、b、0）がプリミティブである場合、（a、a-b、0）もプリミティブです。（a、b、c、d、0）がプリミティブである場合、（a、a-d、a-c、a-b、0）もプリミティブです。数学的に：

xがプリミティブの場合 a + xb +1、それからそれは原始的でx a + x a-b + 1、

xがプリミティブの場合 a + x b + x c + x d +1、それからそれは原始的でx a + x a-d + x a-c + x a-b + 1。新しいビットを生成するには、シフトレジスタの2ビットのみをXORする必要があるため、プリミティブ三項式はプログラムで実装するのが最も高速です（ゼロ項は考慮されません。つまり、x 0 = 1、上記の例を参照）。実際、表に示されているすべてのフィードバック多項式はまばらです。つまり、係数がほとんどありません。スパース性は常に弱点の原因であり、アルゴリズムを開くのに十分な場合もあります。暗号化アルゴリズムの場合、多くの係数を持つ高密度の原始多項式を使用する方がはるかに優れています。特にキーの一部として密な多項式を使用することにより、はるかに短いPrCcLOCを使用できます。

2を法とする密な原始多項式の生成は簡単ではありません。一般的なケースでは、次数kの原始多項式を生成するには、数2の因数分解を知る必要があります。 k-1。

PgCsLOS自体は、優れた疑似ランダムシーケンスジェネレーターですが、いくつかの望ましくない非ランダム（決定論的）プロパティがあります。シーケンシャルビットは線形であるため、暗号化には使用できません。長さnのPgCsLOSの場合、内部状態はジェネレータの前のn個の出力ビットです。フィードバックスキームが秘密にされている場合でも、非常に効率的なBerlekamp-Masseyアルゴリズムを使用して、ジェネレータの2n出力ビットからフィードバックスキームを決定できます。

さらに、このシーケンスの連続するビットを使用して生成された大きな乱数は高度に相関しており、一部のタイプのアプリケーションでは、まったくランダムではありません。それにもかかわらず、PgCsLOSは、システムおよび暗号化アルゴリズムのコンポーネントとして暗号化アルゴリズムを作成するためによく使用されます。

1.2.RgCsLOSに基づくストリーム暗号について

PrCsLOSベースのキーストリームジェネレータを設計するための基本的なアプローチは単純です。最初に、通常は長さが異なり、フィードバック多項式が異なる1つ以上のPrCsLOSが取得されます。（長さが互いに素で、すべてのフィードバック多項式がプリミティブである場合、生成されるジェネレーターの長さは最大になります。）キーはPrCcLOCレジスタの初期状態です。新しいビットが必要になるたびに、PrCsLOSレジスタを少しシフトします（クロッキングと呼ばれることもあります）。出力ビットは、PrCsLOCレジスタの一部のビットの関数であり、好ましくは非線形です。この関数は結合関数と呼ばれ、ジェネレーター全体は結合ジェネレーターと呼ばれます。（出力ビットが単一のPgCsLOSの関数である場合、発振器はフィルター発振器と呼ばれます。）これらの種類のデバイスの背後にある理論の多くは、SelmerとNealZierlerによって開発されました。あなたは多くの合併症を引き起こす可能性があります。一部のジェネレータでは、異なるPgCsLOSに異なるクロック周波数が使用され、あるジェネレータの周波数が別のジェネレータの出力に依存する場合があります。これらはすべて、第二次世界大戦前の暗号化マシンのアイデアの電子版であり、クロック制御発振器と呼ばれています（クロック制御の発電機）。クロック制御は、1つのPgSsLOSの出力が別のPgSsLOSのクロック速度を制御するフィードフォワード、または1つのPgSsLOSの出力がそれ自体のクロックを制御する閉ループにすることができます。これらのジェネレーターはすべて、少なくとも理論的には、ネスト攻撃と考えられる相関関係に敏感ですが、それらの多くは依然として安全です。

ケンブリッジ大学の純粋数学の元議長であり、ブレッチリーパークの暗号解読者であるイアン・カッセルズ氏は、「暗号解読は数学と混乱の混合物であり、混乱することなく、数学をあなたに対して使用することができる」と述べた。彼が意味したのは、ストリーム暗号では、最大長やその他のプロパティを提供するためにPrCcLOCなどの特定の数学的構造が必要ですが、誰かがレジスタの内容を取得してクラッキングするのを防ぐために、複雑な非線形の混乱を導入する必要があるということです。アルゴリズム。このアドバイスは、ブロックアルゴリズムにも当てはまります。

ほとんどの実際のストリーム暗号は、PrCsLOSに基づいています。エレクトロニクスの初期の頃でさえ、それらは簡単に構築できました。シフトレジスタはビットの配列にすぎず、フィードバックシーケンスはXORゲートのセットです。 VLSIを使用する場合でも、PrCsLOSに基づくストリーム暗号は、いくつかの論理ゲートの助けを借りてかなりのセキュリティを提供します。 PgCsLOSの問題は、ソフトウェアの実装が非常に非効率的であることです。スパースフィードバック多項式は避けなければなりません-相関攻撃を容易にします-そして高密度フィードバック多項式は非効率的です。

この暗号化の分野は急速に成長しており、政府の監視下にあります。 NSA 。ほとんどの開発は分類されています-今日使用されている多くの軍事暗号化システムはPrCsLOSに基づいています。実際、ほとんどのCrayコンピューター（Cray 1、Cray X-MP、Cray Y-MP）には、一般に「人口カウント」と呼ばれる非常に奇妙な命令があります。レジスタ内の1の数をカウントし、2つのバイナリワード間のハミング距離を効率的に計算するためと、PrCcLOSのベクトル化バージョンを実装するための両方に使用できます。この命令はNSAの標準的な命令と見なされ、ほとんどすべてのコンピューター契約に表示されます。

一方、驚くほど多くの一見複雑なシフトレジスタジェネレータがハッキングされています。そしてもちろん、NSAなどの軍事暗号解読機関によってハッキングされたそのようなジェネレータの数はさらに多くなります。

1.3。生成された疑似乱数のシーケンスPrCsLOSの線形の複雑さについて

多くの場合、ストリーム暗号はブロック暗号よりも解析が簡単です。たとえば、PgCsLOCベースのジェネレーターの分析に使用される重要なパラメーターは、線形の複雑さ、つまり線形の間隔です。これは、ジェネレータ出力をシミュレートできる最短のPrCsLOSの長さnとして定義されます。有限体上の有限オートマトンによって生成されたシーケンスは、有限の線形複雑さを持っています。 Berlekamp-Masseyアルゴリズムと呼ばれる単純なアルゴリズムでは、キーストリームの2nビットのみを調べることで、このPrCcLOCを決定できるため、線形の複雑さは重要です。目的のPrCsLOSを再作成することにより、ストリーム暗号を破ります。

このアイデアは、フィールドからリング、および出力シーケンスが奇数特性のフィールドの数値として扱われる場合に拡張できます。さらに拡張すると、線形複雑性プロファイルの概念が導入されます。これは、シーケンスが長くなるにつれて、シーケンスの線形複雑さを決定します。球形および二次の複雑さの概念もあります。いずれにせよ、線形の複雑さが高いことは必ずしも発電機の安全性を保証するものではありませんが、線形の複雑さが低いことは発電機の安全性が不十分であることを示していることを覚えておく必要があります。

1.4。生成された疑似乱数シーケンスPrCsLOSの相関独立性について

暗号学者は、いくつかの出力シーケンスの結果を非線形の方法で組み合わせることにより、高い線形の複雑さを得ようとします。ここでの危険は、1つ以上の内部出力シーケンス（多くの場合、個々のPrCsLOCの出力のみ）が共通のキーストリームによってリンクされ、線形代数を使用してカバーされない可能性があることです。多くの場合、このような対決は、相関対決または分割統治対決と呼ばれます。 Thomas Siegenthalerは、相関の独立性を正確に定義できること、および相関の独立性と線形の複雑さの間にはトレードオフがあることを示しました。

相関オープニングの主なアイデアは、ジェネレーターの出力とそのコンポーネントの1つの出力の間の相関関係を見つけることです。次に、出力シーケンスを観察することにより、この中間出力に関する情報を取得できます。この情報と他の相関関係を使用して、ジェネレーターがハッキングされるまで、他の中間出力に関するデータを収集することができます。

相関攻撃とそのバリエーション（高速相関攻撃など）は、多くのPgCsLOCベースのキーストリームジェネレーターに対して正常に使用されており、計算の複雑さと効率の間のトレードオフを提供します。

1.5。生成された疑似乱数のシーケンスを開く他の方法についてPgCsLOS

キーストリームジェネレータを壊す方法は他にもあります。線形整合性テストは、マトリックス手法を使用して暗号化キーのサブセットを見つけようとします。正しさに対する中途半端な一貫性の攻撃もあります。線形シンドロームアルゴリズムは、出力シーケンスのフラグメントを線形方程式として書き込む機能に基づいています。最良のアフィン近似攻撃と派生シーケンス攻撃があります。差分解読法と線形解読法は、ストリーム暗号にも適用できます。

2.疑似ランダムシーケンスジェネレータとしてのPrCsLOSのソフトウェア実装の説明

2.1アルゴリズムの一般化されたスキーム

2.2ソフトウェアモジュールとインターフェースの説明

下の図3は、プログラムウィンドウを示しています。

図プログラムインターフェース

メニューには次の機能があります。

[ファイル]-> [レポートの保存]

この関数は、PrCsLOSの初期状態、タップシーケンス、受信した疑似ランダムビットシーケンスの周期、シーケンス自体、および状態テーブルが書き込まれるレポートファイルを生成します。ファイルが正常に保存されると、保存が成功したことを示すメッセージが表示されます（図4）。レポートに推奨されるファイル拡張子は*です。 txt。

描く

ファイル->終了

この関数は、アプリケーションが確実に閉じられるようにします。

エスケープシーケンスを設定する

この関数は、ユーザーが画面フォームでチェックしたセルから値を読み取ることにより、タップシーケンスを生成します。その後、タップシーケンスの作成についてユーザーに通知します（図5）。タップシーケンスは、どのシフトレジスタフリップフロップがフィードバックを受け取るかを決定します。 XOR オフセットビットを形成します。デフォルトでは、最初のトリガーからのフィードバックは常にオンです。他の接続がない場合は、最下位ビットを最上位ビットの位置に変更して、左へのシフトが実行されます。

描く

初期値を設定する

この関数は、ウィンドウからユーザーが入力したレジスタの初期値を読み取ります編集 1で、指定された条件に従って入力された値をチェックします。入力された文字列は空ではなく（図6）、入力された文字列の長さは8（8ビット= 1バイト、図7）、入力された文字列にはゼロのみが含まれるか、または1つ（図8）、入力された文字列はゼロ以外です（図9）。それ以外の場合は、エラーメッセージが表示されます。ユーザーはエラーメッセージを修正して、ボタンをもう一度押す必要があります。チェックが成功すると、初期値が「初期」行の状態テーブルに書き込まれ、通知が発行されます（図10）。

描く

レジスタシフトを実行します

この関数は、シフトレジスタの動作をエミュレートします。順次256シフトを行うと、各シフトは疑似ランダムシーケンスの出力ビットとレジスタの新しい状態を生成します。レジスタの状態が最初の状態と等しくなるとすぐに、期間が計算され、フィールドに表示されますメモ 1つは疑似ランダムシーケンスを受信しました。

ヘルプ->バージョン情報

この関数は、プログラムと命令の簡単な説明を表示します（図11）。

描く

ヘルプ->作成者について

この関数は、プログラムの作成者に関する情報を表示します（図12）。

描く

2.3ユーザーマニュアル

まず、レジスタの初期状態を設定します。 8つの2進文字が含まれている必要があります。そうしないと、エラーメッセージが表示され、入力した値を修正する必要があります。メニュー項目「初期値の設定」を押します。
次に、レジスタフィードバックのチェックボックスをオンにします（タップシーケンス）。メニュー項目「タップシーケンスの設定」を押します。
次に、メニュー項目「シフトの登録」をクリックします。これを行う前に、必ず手順1と2を完了していることを確認してください。完了していないと、ソフトウェアエラーが発生します。
結果を受け取ったら、メニュー項目[ファイル]-> [レポートの保存]をクリックして結果を保存できます。これを行う前に、手順1〜3を完了していることを確認してください。完了していないと、ソフトウェアエラーが発生します。
ヘルプが必要な場合は、メニュー項目[ファイル]-> [バージョン情報]、[ファイル]-> [作成者について]をクリックしてください。
タップシーケンスの他の値とレジスタの初期状態でのレジスタの動作を確認するには、他のパラメータを入力して、手順1〜3の手順を順番に繰り返します。

結論

この論文では、RgCsLOSを疑似乱数ジェネレーターと見なしました。このプログラムは、線形フィードバックを備えたシフトレジスタの動作原理の視覚的なデモンストレーションとして機能します。 XOR 。その上で、ビットの疑似乱数シーケンスを形成する原理、レジスタの初期値と疑似乱数シーケンスの値の関係、タップシーケンス、および周期を調べることができます。結果として得られる疑似ランダムガンマは、別のソフトウェアアプリケーション（たとえば、ガンマ暗号のソフトウェア実装）で使用できます。

現在まで、これらのレジスタは独立した疑似乱数ジェネレータとして使用されていませんが、より複雑なデバイスの一部です。しかし、数学の新しい方向性を切り開いたのは彼らでした（有限体での原始多項式の検索、疑似乱数ジェネレーターを破るための数学的方法）。 RgCsLOSでの発電機の動作原理に関する知識がなければ、より複雑なデバイスの動作を理解することは不可能です。ハードウェアの実装が単純なため、テクノロジーで広く使用されています。 PrCsOSの研究により、これらのタイプのレジスタ（スライディング順列暗号、 DES 等。; EDS、ハッシュ関数）。

一般に、この分野の研究は、暗号解読および暗号解読者、コンピューターおよびデバイスの開発に真剣に拍車をかけ、また、他の多くの有用な機能（たとえば、巡回符号の修正）を実装することを可能にしました。

参考文献

シュナイアーブルース。応用暗号。プロトコル、アルゴリズム、C言語の原文。 -M。：Triumph、2002
ババッシュA.V. 現代の情報セキュリティの暗号化およびオートマトン理論的側面。第1巻-M。：Ed。センターEAOI、2009年。-414ページ。
E.S. セルマー。モノグラフ：「有限体における線形再帰」。ベルゲン大学、ノルウェー、1966年。
N.ZierlerとJ.Brillhart。「PrimitiveTrinomialsModulo 2について」、Journal of Information and Control、Vol。13No. 6 1968年12月、pp。541-544。
K.Kh. マイヤーとW.L.タックマン。「疑似ランダムコードは解読される可能性があります」、Electronic Designマガジン、no。 1972年11月23日。
J.L.マッセイ。「シフトレジスタの一般化とBose-Chowdhury-Hokvinghamコードのデコード」、情報理論に関するIEEEトランザクション、v。 IT-15、n 。 1、1969年1月、pp.122-127。
S.U. ゴロンブ。シフトレジスタシーケンス、サンフランシスコ、ゴールデンデー、1967年（Aigean Park Press、1982年に転載）。

附属書A

2を法とするいくつかの原始多項式の表

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

初期状態入力（IS）

入力検証

エラーメッセージの発行

タップシーケンスの設定

状態テーブルにIPを記録する

記録i -番目の状態レジスタと状態テーブルへの出力ビット

IS ==現在の状態

結果の保存

疑似ランダムシーケンス出力

出口

発売

はい

いいえ

線形フィードバックを備えたシフトレジスタでは、シフトレジスタ自体と挿入されたビットの値を計算する回路（またはサブルーチン）の2つの部分（モジュール）が区別されます。レジスタは関数セル（またはマシンワードのビットまたは複数のワード）で構成され、各セルには1ビットの現在の状態が格納されます。セルの数は、レジスタの長さと呼ばれます。ビット（セル）は通常、それぞれがビットを格納できる番号で番号が付けられ、計算されたビットがセルにプッシュされ、次に生成されたビットがセルから引き出されます。挿入されたビットの計算は通常、レジスタのシフトの前に実行され、シフトの後にのみ、計算されたビットの値がセルに配置されます。

シフトレジスタの周期は、繰り返しを開始する前の結果のシーケンスの最小の長さです。ビットセルのレジスタにはゼロ以外の状態が異なるだけなので、原則として、レジスタの周期はこの数を超えることはできません。レジスタの周期がこの数と等しい場合、そのようなレジスタは最大周期のレジスタと呼ばれます。

LFSRの場合、フィードバック関数は、レジスタのすべてまたは一部のビットの状態の線形ブール関数です。たとえば、2を法とする和またはその論理逆関数は、線形ブール関数（XOR演算、数式で示される）であり、このようなレジスタで最も頻繁に使用されます。

この場合、フィードバック関数の変数であるビットは通常呼び出されます 曲がる.

ハードウェア実装でのレジスタ制御は、シフトパルスを適用することによって実行されます（それ以外の場合は時計また 同期パルス）ソフトウェア内のすべてのセルに-フィードバック関数の計算とワードのビットシフトを含むプログラムサイクルを実行することによって。

各クロックティック中に、次の操作が実行されます。

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

したがって、論理演算XOR（排他的論理和）はフィードバック関数と見なされます。つまり、次のようになります。

原始多項式の性質

プロパティ

LFSRによって生成されるシーケンスのプロパティは、関連する多項式のプロパティと密接に関連しています。その非ゼロ係数はと呼ばれます 曲がる、およびレジスタの対応するセルは、フィードバック関数の引数の値を提供します。

線形の複雑さ

バイナリシーケンスの線形の複雑さは、LFSR操作の最も重要な特性の1つです。次の表記法を紹介しましょう。

意味

無限のバイナリシーケンスの線形の複雑さは番号と呼ばれ、次のように定義されます。

有限バイナリシーケンスの線形の複雑さは数値と呼ばれ、最短のLFSRの長さに等しく、最初の項としてを持つシーケンスを生成します。

線形複雑性プロパティ

バイナリシーケンスとします。それで：

相関の独立性

線形の複雑さを高めるために、暗号技術者は複数の出力シーケンスの結果を非線形に組み合わせようとします。この場合、危険なのは、1つ以上の出力シーケンス（多くの場合、個々のLFSRの出力でさえ）が共通のキーストリームによって接続され、線形代数を使用して開くことができることです。このような脆弱性に基づくハッキングは、 相関剖検。 Thomas Siegenthalerは、相関の独立性を正確に定義できること、および相関の独立性と線形の複雑さの間にはトレードオフがあることを示しました。

このハックの背後にある主なアイデアは、ジェネレーターの出力とその構成要素の1つの出力との間に何らかの相関関係を見つけることです。次に、出力シーケンスを観察することにより、この中間出力に関する情報を取得できます。この情報と他の相関関係を使用して、ジェネレーターがハッキングされるまで、他の中間出力に関するデータを収集することができます。

相関攻撃または高速相関攻撃などのバリエーションは、計算の複雑さと効率の間のトレードオフを伴う、多くの線形フィードバックシフトレジスタベースのキーストリームジェネレータに対して正常に使用されています。

例

ルジャンドル陪多項式を使用するLFSRの場合、生成されるシーケンスの形式はです。プロセスの開始前にシーケンスがレジスタに書き込まれるとすると、生成されたビットストリームの周期は次のシーケンスで7に等しくなります。

ステップ番号	州	生成されたビット
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

7番目のステップの内部状態が元の状態に戻ったため、次のステップから繰り返します。言い換えれば、シーケンスの周期は7に等しいことが判明しました。これは、多項式の原始性が原因で発生しました。

原始多項式を生成するためのアルゴリズム

レディテーブル

多項式の原始性の計算は、かなり複雑な数学的問題です。したがって、ジェネレーターの最大周期を提供するタップシーケンスの数をリストした既製のテーブルがあります。たとえば、32ビットシフトレジスタの場合、シーケンスがあります。つまり、新しいビットを生成するには、XOR関数を使用して31、30、29、27、25、および0番目のビットを合計する必要があります。 C言語でのこのようなLFSRのコードは次のとおりです。

Int LFSR（void）（static unsigned long S = 1; S =（（（（S >> 31）^（S >> 30）^（S >> 29）^（S >> 27）^（S >> 25）^ S）＆1）<< 31 ) | (S>> 1）; S＆1を返す; ）。

RSLOSジェネレーターのソフトウェア実装は、Cではなくアセンブラーで記述されている場合、非常に遅く、動作が速くなります。 1つの解決策は、16個のRLLSを並列に使用することです（特定のコンピューターのアーキテクチャーのワード長によっては32個）。このような方式では、ワードの配列が使用され、そのサイズはLFSRの長さに等しく、アレイワードの各ビットはそのLFSRを参照します。同じタップシーケンス番号が使用されている場合、これによりパフォーマンスが大幅に向上します。 [サンプルコードが必要] （参照：ビットスライス）。

ガロア構成

線形フィードバックシフトレジスタのガロア構成

フィードバックスキームも変更できます。この場合、ジェネレーターの暗号化強度は高くなりませんが、プログラムで実装する方が簡単です。タップシーケンスのビットを使用して新しい左端のビットを生成する代わりに、タップシーケンスの各ビットをジェネレーターの出力とXORし、このアクションの結果に置き換えます。その後、ジェネレーターの結果が新しい左端のビットになります。。 C言語では、次のようになります。

Int LFSR（void）（static unsigned long Q = 1; Q =（Q >> 1）^（Q＆1？0x80000057：0）; return Q＆1;）

利点は、すべてのXORが1回の操作で実行されることです。

最初に与えられたフィボナッチ構成とここで与えられたガロア構成は同じシーケンス（長さ2 32 -1）を与えるが、互いに位相がずれていることを証明できます。
ガロア構成でのLFSR関数への固定数の呼び出しのループは、フィボナッチ構成（Intel Corei5上のMSVS 2010コンパイラ）の約2倍の速度です。
ガロア構成では、フィードバックワードのビットの順序がフィボナッチ構成とは逆になっていることに注意してください。

ジェネレーターの例

ストップゴージェネレータ

ストップアンドゴー交流発電機

この発振器は、あるLFSRの出力を使用して、別のLFSRのクロック周波数を制御します。 RSLOS-2のクロック出力はRSLOS-1の出力によって制御されるため、時間t-1でのRSLOS-1の出力が1に等しい場合にのみ、RSLOS-2は時間tでその状態を変更できます。しかし、このスキームは相関関係の開始に抵抗しませんでした。

したがって、同じ考えに基づく改良された発電機が提案された。これは、ストップアンドゴーインターリーブジェネレーターと呼ばれます。長さの異なる3つのLFSRを使用します。 LFSR-1の出力が1に等しい場合、LFSR-2がクロックされ、LFSR-1の出力が0に等しい場合、LFSR-3がクロックされます。ジェネレータの出力は、RSLOS-2とRSLOS-3のモジュロ2の合計です。このジェネレーターは、周期が大きく、線形の複雑さが大きくなります。その著者は、RLOS-1の相関オープニングの方法も示しましたが、これはジェネレーターを大幅に弱めることはありません。

ゴルマンカスケード

Gollmann Cascadeは、stop-goジェネレーターの拡張バージョンです。これは一連のLFSRで構成され、各LFSRのタイミングは前のLFSRによって制御されます。時間tでのLFSR-1の出力が1の場合、LFSR-2がクロックされます。時間tでのLFSR-2の出力が1の場合、LFSR-3はクロックされます。最後のLFSRの出力は、ジェネレーターの出力です。すべてのLFSRの長さが同じで、nに等しい場合、k個のLFSRのシステムの線形複雑度はです。

このアイデアは単純であり、大きな周期、大きな線形の複雑さ、および優れた統計的特性を持つシーケンスを生成するために使用できます。ただし、残念ながら、「ロック」（ロックイン）と呼ばれる開口部の影響を受けやすくなっています。安定性を高めるために、少なくとも15のkを使用することをお勧めします。さらに、長いLFSRよりも短いLFSRを使用することをお勧めします。

スレッショルドジェネレータ

このジェネレーターは、可変数のシフトレジスターを使用して、以前のジェネレーターのセキュリティ問題を回避しようとします。理論的には、より多くのシフトレジスタを使用すると、暗号の複雑さが増します。これは、このジェネレータで行われました。

このジェネレータは多数のシフトレジスタで構成されており、その出力はメジャー化機能に供給されます。レジスタの出力のユニット数が半分を超える場合、ジェネレータはユニットを生成します。出力のゼロの数が半分を超える場合、ジェネレーターはゼロを生成します。ゼロと1の数を比較できるようにするには、シフトレジスタの数を奇数にする必要があります。生成されたシーケンスの周期が最大になるように、すべてのレジスタの長さは互いに素である必要があり、フィードバック多項式はプリミティブである必要があります。

3つのシフトレジスタの場合、ジェネレータは次のように表すことができます。

このジェネレーターは、しきい値ジェネレーターの線形がより複雑であることを除いて、Geffジェネレーターに似ています。その線形の複雑さは次のとおりです。

ここで、、は、1番目、2番目、および3番目のシフトレジスタの長さです。

その欠点は、各出力ビットがシフトレジスタの状態に関する情報を提供することです。正確には0.189ビットです。したがって、このジェネレータは相関の開始に抵抗しない可能性があります。

他のタイプ

自己間伐

自己減少型発電機は、独自の周波数を制御する発電機と呼ばれます。そのような発電機の2つのタイプが提案されています。最初のものは、線形フィードバックシフトレジスタと、シフトレジスタの出力値に応じてこのレジスタをクロックするいくつかの回路で構成されています。 LFSR出力が1に等しい場合、レジスタはd回クロックされます。出力がゼロの場合、レジスタはk回クロックされます。 2つ目はほとんど同じ設計ですが、わずかに変更されています。クロック回路では、0または1のチェックとして、出力信号自体ではなく、線形フィードバックを使用したシフトレジスタの特定のビットのXORが受信されます。残念ながら、この種の発電機は安全ではありません。

内積付きマルチレートオシレーター

このジェネレータは、異なるクロック周波数の線形フィードバックを備えた2つのシフトレジスタ（LFSR-1とLFSR-2）を使用します。 RLOS-2のクロック周波数はRLLS-1のd倍です。これらのレジスタの個々のビットは、AND演算と組み合わされます。次に、AND演算の出力がXORされます。出力シーケンスは、このXORブロックから取得されます。繰り返しますが、このジェネレーターは完全ではありません（線形整合性の開始に耐えられませんでした。-LFSR-1の長さ-LFSR-2の長さ、およびdがクロック周波数の比率である場合、ジェネレータは長さの出力シーケンスから取得できます）が、線形の複雑さが高く、統計的パフォーマンスに優れています。

フィードバックシフトレジスタシフトレジスタとシフトレジスタの2つの部分で構成されています フィードバック機能.

図19.フィードバックシフトレジスタ。

一般に、シフトレジスタは、リングまたはフィールドのいくつかの要素のシーケンスです。最も一般的に使用される少しシフトレジスタ。このようなレジスタの長さは、ビット数で表されます。ビットが取得されるたびに、レジスタ内のすべてのビットが1桁右にシフトされます。新しい最上位ビットは、レジスタ内の他のすべてのビットの関数として計算されます。通常、出力は最下位ビットです。シフトレジスタの周期は、出力シーケンスが繰り返されるまでの長さです。

最も単純なタイプのシフトレジスタは、線形フィードバックシフトレジスタ（LFSRまたはLRS）です。フィードバックは、レジスタの一部のビットに対する単純なXOR演算です。これらのビットのリストが定義されています 特性多項式と呼ばれる タップシーケンス。このスキームは時々呼ばれます フィボナッチ構成.

図20。フィボナッチ構成のLFOS。

LFSRのソフトウェア実装では、変更されたスキームが使用されます。タップシーケンスのビットを使用する代わりに、新しい有効ビットを生成するために、XOR演算が各ビットに対して実行され、ジェネレータの出力で古いものが置き換えられます。タップシーケンスのビット。この変更は時々呼ばれます ガロア構成.

図21。ガロア構成のRLOS。

n-ビットLFSRは2つのいずれかになります n–1つの内部状態。これは、理論的には、そのようなレジスタが2の周期を持つ疑似ランダムシーケンスを生成できることを意味します。 n– 1ビット（ゼロでのパディングは完全に無意味です）。 2つすべての通過 n–1つの内部状態は特定のタップシーケンスでのみ可能です。このようなレジスタは、最大周期のLFSRと呼ばれます。 LFSRの最大周期を確保するには、その特性多項式が 原生的モジュロ2。多項式の次数は、シフトレジスタの長さです。原始次数多項式 n-そうですね既約除数であるが除数ではない多項式 x d+1すべて d、2の約数です n– 1.（多項式について説明する場合、用語素数用語に置き換えられました 既約多項式）。図に示されているLFSRの特性多項式：

バツ 32 + バツ 7 + バツ 5 + バツ 3 + バツ 2 + バツ + 1

は2を法とする原始根です。このようなレジスタの周期は最大になり、232-1のすべての値が繰り返されるまで循環します。最も一般的に使用されるのは、間引きされた多項式です。いくつかの係数しかありません。最も人気のある三項式。

LFSRに基づくジェネレータの重要なパラメータは次のとおりです。 線形の複雑さ。それは長さとして定義されます nジェネレータ出力をシミュレートできる最短のLFSR。線形の複雑さは重要です。 Berlenkamp-Masseyアルゴリズム 2つだけチェックすることでそのようなLFSRを再現することが可能です nガンマビット。目的のLFSRの定義により、ストリーム暗号は実際に破られます。

フィードバックシフトレジスタは、シフトレジスタとフィードバック機能の2つの部分で構成されています（図1.2.1）。シフトレジスタはビットのシーケンスです。（ビット数はシフトレジスタの長さによって決まります。長さがnビットの場合、そのレジスタはnビットシフトレジスタと呼ばれます。）ビットを抽出する必要がある場合は常に、シフトレジスタのすべてのビットが右に1桁シフトしました。新しい左端のビットは、レジスタ内の他のすべてのビットの関数です。シフトレジスタの出力は1ビットで、通常は最下位ビットです。シフトレジスタの周期は、繰り返しを開始する前の結果のシーケンスの長さです。

米。 1.2.1。

暗号学者は、シフトレジスタベースのストリーム暗号が好きでした。デジタルハードウェアで簡単に実装できました。数学的理論について簡単に触れます。 1965年、ノルウェー政府の主任暗号研究者であるErnst Selmerは、シフトレジスタシーケンスの理論を開発しました。 NSAの数学者であるソロモンゴロムは、彼とセルマーの結果のいくつかを概説した本を書きました。

最も単純なタイプのフィードバックシフトレジスタは、線形フィードバックシフトレジスタ（LFSR）です（図1.2.2）。フィードバックは、レジスタ内のいくつかのビットのXORであり、これらのビットのリストはタップシーケンスと呼ばれます。このようなレジスタは、フィボナッチ構成と呼ばれることもあります。フィードバックシーケンスが単純なため、非常に高度な数学的理論を使用してLFSRを分析できます。暗号学者はシーケンスを分析するのが大好きで、これらのシーケンスは安全であるために十分にランダムであると確信しています。 LFSRは、他のシフトレジスタよりも暗号化で一般的に使用されます。

米。 1.2.2。

図について 1.2.3は、1番目と4番目のビットをタップした4ビットLFSRを示しています。値1111で初期化されている場合、レジスタを繰り返す前に、次の内部状態が発生します。

米。 1.2.3。 4

出力シーケンスは、最下位ビットの文字列になります。

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

nビットLFSRは、2n-1の内部状態のいずれかになります。これは、理論的には、このようなレジスタが2n-1ビットの周期の疑似ランダムシーケンスを生成できることを意味します。（内部状態の数と周期は2n-1です。これは、LFSRをゼロで埋めると、シフトレジスタがゼロの無限シーケンスを出力するためです。これはまったく役に立ちません。）特定のタップシーケンスでのみ、LFSRは循環します。すべての2n-1内部状態、このようなLFSRは、最大周期のLFSRです。結果の結果はM系列と呼ばれます。

特定のLFSRが最大周期を持つためには、タップシーケンスと定数1から形成される多項式が2を法とする原始でなければなりません。多項式の次数はシフトレジスタの長さです。次数nの原始多項式は、除数であるが2n-1の約数であるすべてのdのxd +1の約数ではない既約多項式です。

一般に、2を法とする特定の次数の原始多項式を生成する簡単な方法はありません。最も簡単な方法は、ランダムに多項式を選択し、それが原始であるかどうかを確認することです。簡単ではなく、ランダムに選択された数が素数であるかどうかを確認するのと少し似ていますが、多くの数学ソフトウェアパッケージでこれを行うことができます。

確かにすべてではありませんが、さまざまな次数の多項式の一部は2を法とする原始です。たとえば、表記（32、7、5、3、2、1、0）は、次の多項式が2を法とする原始であることを意味します。

x32 + x7 + x5 + x3 + x2 + x + 1

これは、最大周期のLFSRに簡単に一般化できます。最初の数値はLFSRの長さです。最後の数字は常に0であり、省略できます。 0を除くすべての数値は、シフトレジスタの左端から数えてタップシーケンスを指定します。つまり、次数の低い多項式の項は、レジスタの右端に近い位置に対応します。

例を続けると、（32、7、5、3、2、1、0）と書くことは、特定の32ビットシフトレジスタに対して、32、7、5、3、2番目のXORによって新しいビットが生成されることを意味します。、および最初のビットで、結果のLFSRは最大長になり、反復の前に232-1の値を循環します。

線形フィードバックシフトレジスタ。 フィードバック付き線形シフトレジスタ線形シフトレジスタの例