交互ステップジェネレータ

暗号学において、交互ステップ生成器( ASG ) は、 3 つの線形フィードバック シフト レジスタに基づく、ストリーム暗号で使用される暗号疑似乱数生成器です。その出力は、3 番目の LFSR の出力に応じて交互にステップ (クロック) される 2 つの LFSR の組み合わせです。

このデザインは1987年に発表され、1989年にCGギュンターによって特許を取得しました。^{[1] [2]}

線形フィードバック シフト レジスタ(LFSR) は、統計的に言えば、優れた分布とシンプルな実装を備えた優れた疑似乱数ジェネレータです。ただし、出力が簡単に予測できるため、そのまま使用することはできません。

ASG は 3 つの線形フィードバック シフト レジスタで構成されており、便宜上、これらを LFSR0、LFSR1、LFSR2 と呼びます。レジスタの 1 つの出力によって、他の 2 つのうちどれを使用するかが決まります。たとえば、LFSR2 が 0 を出力する場合は LFSR0 がクロックされ、1 を出力する場合は LFSR1 がクロックされます。出力は、 LFSR0 と LFSR1 によって生成された最後のビットの排他的論理和です。3 つの LFSR の初期状態が重要です。

通常、LFSR は、非ゼロ状態にプリセットされた、異なるが近い次数の原始多項式を使用し、各 LFSR が最大長のシーケンスを生成するようにします。これらの仮定の下では、ASG の出力は明らかに長い周期、高い線形複雑性、および短いサブシーケンスの均等な分布を持ちます。

C 言語のコード例:

/* 16 ビットのおもちゃの ASG (実用には小さすぎます)。0 または 1 を返します。 */ 
unsigned ASG16toy ( void ) { static unsigned /* 少なくとも 16 ビットの符号なし型 */ lfsr2 = 0x8102 , /* 初期状態、16 ビット、0 であってはなりません */ lfsr1 = 0x4210 , /* 初期状態、15 ビット、0 であってはなりません */ lfsr0 = 0x2492 ; /* 初期状態、14 ビット、0 であってはなりません */ 

    
        
        
        

  /* LFSR2 は x^^16 + x^^14 + x^^13 + x^^11 + 1 を使用します */ 
lfsr2 = ( - ( lfsr2 & 1 )) & 0x8016 ^ lfsr2 >> 1 ;      

  if ( lfsr2 & 1 ) /* LFSR1 は x^^15 + x^^14 + 1 を使用します */ lfsr1 = ( - ( lfsr1 & 1 )) & 0x4001 ^ lfsr1 >> 1 ; else /* LFSR0 は x^^14 + x^^13 + x^^3 + x^^2 + 1 を使用します */ lfsr0 = ( - ( lfsr0 & 1 )) & 0x2C01 ^ lfsr0 >> 1 ; 
    
        
  
    
        

  戻り値( lfsr0 ^ lfsr1 ) & 1 ; }   

ASG はハードウェアで実装するのが非常に簡単です。特に、縮小ジェネレータや自己縮小ジェネレータとは異なり、出力ビットはクロックごとに生成されるため、一貫したパフォーマンスとタイミング攻撃に対する耐性が確保されます。

Shahram Khazaei、Simon Fischer、Willi Meier ^{[3]は、攻撃を実行するために必要な出力量と時間の複雑さとの間のさまざまなトレードオフを可能にするASGの}暗号解読法を提示しています。たとえば、漸近的複雑さとビット（3つのLFSRのうち最短のもののサイズ）などがあります。 ${\displaystyle O(L^{2}.2^{2L/3})}$${\displaystyle O(2^{2L/3})}$${\displaystyle L}$

• シュナイアー、ブルース。応用暗号学（p383-384）、第 2版、ジョン ワイリー アンド サンズ、1996 年。ISBN 0-471-11709-9