縮小ジェネレータ

暗号学において、縮小生成器はストリーム暗号で使用することを目的とした擬似乱数生成器の一種である。これは、ドン・コッパースミス、ヒューゴ・クラウチク、イシャイ・マンスールによって1993年にCrypto誌で発表された。^[1]

シュリンクジェネレータは、2 つの線形フィードバックシフトレジスタを使用します。1 つはAシーケンスと呼ばれ、出力ビットを生成し、もう 1 つはSシーケンスと呼ばれ、その出力を制御します。AとSの両方がクロックされます。S ビットが 1 の場合、 Aビットが出力されます。Sビットが 0 の場合、Aビットは破棄され、何も出力されず、レジスタは再度クロックされます。これには、ジェネレータの出力レートが不規則に変化し、S の状態を暗示するという欠点があります。この問題は、出力をバッファリングすることで克服できます。LFSR によって生成されたランダムシーケンスは、セキュアシステムにおける予測不可能性を保証することはできず、そのランダム性を向上させるさまざまな方法が提案されています^[2]

この単純さにもかかわらず、フィードバック多項式が秘密である場合、網羅的探索よりも優れた攻撃は現在のところ知られていない。しかし、フィードバック多項式が既知である場合、最もよく知られている攻撃はA・Sビット未満の出力を必要とする。^[3]

バリエーションとしては、自己収縮ジェネレータがあります。

Pythonでの実装

この例では、2 つの Galois LFRS を使用して出力疑似ランダムビットストリームを生成します。Python コードを使用して、ファイルまたは任意のバイトストリームを暗号化および復号化できます。

#!/usr/bin/env python3

インポート システム

# ---------------------------------------------------------------------------- 
# Crypto4o 関数はここから始まります
# ----------------------------------------------------------------------------


クラス GLFSR : 
"""ガロア線形フィードバック シフト レジスタ。"""    

    def  __init__ ( self ,  polynom ,  initial_value ): 
        print  "polynom 0x %Xを使用します。初期値: 0x %X 。"  %  ( polynom ,  initial_value )

        self.polynom = polynom | 1 self.data = initial_value tmp = polynom self.mask = 1    
          
          
          

         tmp  !=  0の場合: 
            tmp & self.mask ! = 0の場合 : tmp ^ = self.mask    
                  

             tmp  ==  0の場合:
                中断

            自己.マスク <<=  1

    def  next_state ( self ): 
        self . data  <<=  1

        戻り値 =  0

         self.data & self.mask ! = 0の場合: retval = 1 self.data ^ = self.polynom    
              
              

         戻り値を返す


クラス SPRNG : 
    def  __init__ ( self 、 polynom_d 、 init_value_d 、 polynom_c 、 init_value_c ): 
        print  "GLFSR D0: " 、
        self . glfsr_d  =  GLFSR ( polynom_d 、 init_value_d ) 
        print  "GLFSR C0: " 、
        self . glfsr_c  =  GLFSR ( polynom_c 、 init_value_c )

    def  next_byte ( self ):
        バイト =  0
        ビット位置 =  7

         trueの場合: 
            bit_d  =  self.glfsr_d.next_state ( ) bit_c = self.glfsr_c.next_state ( )
              

             bit_c  !=  0の場合: 
                bit_r  =  bit_d
                バイト |=  bit_r  <<  bitpos

                ビット位置 -=  1

                 bitpos  <  0の場合: 
                    break

        戻り バイト


# ---------------------------------------------------------------------------- 
# Crypto4o 関数はここで終了します
# ----------------------------------------------------------------------------


 main () の
    定義: prng  =  SPRNG ( 
        int ( sys . argv [ 3 ],  16 ), 
        int ( sys . argv [ 4 ],  16 ), 
        int ( sys . argv [ 5 ],  16 ), 
        int ( sys . argv [ 6 ],  16 ), 
    )

    open  ( sys . argv [ 1 ], "rb" )をfとして、open ( sys . argv [ 2 ], "wb" )をgとして実行し、trueの場合、input_ch = f . read ( 1 )       
         
              

             input_ch  ==  ""の場合:
                中断

            random_ch  =  prng.next_byte ( ) & 0xFF g.write ( chr ( ord ( input_ch ) ^ random_ch ) )  
              


 __name__  ==  "__main__"の場合: 
    main ()

参照

FISH、縮小ジェネレータ原理に基づく（安全でない）ストリーム暗号
交互ステップ生成器、類似のストリーム暗号

参考文献

^ D. Coppersmith、H. Krawczyk、Y. Mansour、「縮小ジェネレータ」、CRYPTO '93: Proceedings of the 13th annual international cryptology conference on Advances in cryptology、(ニューヨーク、ニューヨーク、米国)、pp. 22–39、Springer-Verlag New York、Inc.、1994
^ Poorghanad, A. 他「進化的手法を用いた高品質疑似乱数の生成」IEEE、DOI: 10.1109/CIS.2008.220。
^ Caballero-Gil, P. 他「縮小ジェネレータに対する新たな攻撃戦略」Journal of Research and Practice in Information Technology、第 1 巻、331 ～ 335 ページ、2008 年 12 月。

[1] D. Coppersmith、H. Krawczyk、Y. Mansour、「縮小ジェネレータ」、CRYPTO '93: Proceedings of the 13th annual international cryptology conference on Advances in cryptology、(ニューヨーク、ニューヨーク、米国)、pp. 22–39、Springer-Verlag New York、Inc.、1994

[2] Poorghanad, A. 他「進化的手法を用いた高品質疑似乱数の生成」IEEE、DOI: 10.1109/CIS.2008.220。

[3] Caballero-Gil, P. 他「縮小ジェネレータに対する新たな攻撃戦略」Journal of Research and Practice in Information Technology、第 1 巻、331 ～ 335 ページ、2008 年 12 月。