かせへの道：フグについてシンプルかつ明確

「バギーの成長はフグの胃から離れます。 危険が現れると、水や空気で満たされ、魚は風船のように見えます

棘が突き出ている。 球状の状態は、魚をほとんど不死身にします。 ただし、十分に大きな捕食者がそのようなボールを飲み込もうとすると、スタックします

後に死ぬ捕食者ののどに」



ウィキペディア、無料​​の百科事典。



1993年末までに、暗号の世界では非常に厄介な状況が発生しました。 DES対称暗号化アルゴリズムは、弱い56ビットキーで、大失敗に近く、既存のものも

当時、クフ、REDOC II、IDEAなどの代替品は特許によって保護されていました

無料で使用することはできません。 当時RSA Securityによって開発されたRC2およびRC4アルゴリズムには、ライセンスプロセスも必要でした。 そして一般的に、政府機関や大企業内の暗号化業界は

Skipjackなどの秘密のアルゴリズムを使用するようになりました。



一定の真空がありました。 死にかけているDESよりも暗号化された暗号化アルゴリズムが必要でしたが、同時にそれを使用する権利に制限はありませんでした。



そして彼は現れました。



1994年、ケンブリッジのFast Software Encryptionワークショップ、およびその後のコンピュータサイエンスのレクチャーノート（＃809、1994）で、Bruce Schneierは、Blowfishという名前のブロック暗号アルゴリズムを発表しました。



このアルゴリズムの特徴は、DESよりも高度な暗号化安定性（最大448ビットの可変キー長の使用を含む）、高い暗号化/復号化速度（置換テーブルの生成による）、そしてもちろん、目標。



1994年のBruce Schneierによるアーカイブのオリジナル記事：

ブロック暗号II、ブルースシュナイアー（ページの下部）：

新しい可変長キーの説明、64ビットブロック暗号（Blowfish）。 191-204



またはPDF

はじめに

BlowFishは、可変長キーを使用する64ビットブロック暗号アルゴリズムです。 これは、1993年に暗号化と情報セキュリティの分野で有名な専門家であるBruce Schneierによって開発されました。



一般的な場合、アルゴリズムは2つの段階で構成されます-キーの拡張とソースデータの暗号化/復号化。







キー拡張の段階で、元のキーはラウンドキーの行列（P）に変換されます。

合計4168バイトの置換マトリックス（S、置換ボックス）（または置換）。 おそらく、この「拡張子」（448ビットから4168バイト）が名前の選択を説明しています

Blowfishアルゴリズム。



データ暗号化、およびラウンドキーと置換のマトリックスの作成は、Feistelネットワークを使用して行われます。Feistelネットワークは16ラウンドで構成されています。 したがって、キー拡張とデータ暗号化の段階を詳細に検討する前に、前述のFeistelネットワークが何であるかを決定する必要があります。



このプロセスでは、C ++のBlowfishアルゴリズムに従ってエンコーダーのプログラムコードを実装します。 高レベル言語（C / C ++ / Haskell / Perl / ...など）の既製の実装がページで利用可能

ブルース・シュナイアーのサイトにソースコードがあります。

Feistel Network

1971年、DES Corporationの「ゴッドファーザー」であるIBM CorporationのHorst Feistelは、後に一般名「Lucifer」と呼ばれるさまざまな暗号化アルゴリズムを実装する2つのデバイスを開発しました。 これらのデバイスの1つで、彼は後にFeistel Networkと呼ばれる回路を使用しました。 このネットワークは、Feistelセルと呼ばれる特定の繰り返し（繰り返し）構造です。







ネットワークの原理は非常に簡単です。

1. ソースデータは、固定長のブロックに分割されます（通常、2の累乗の倍数-64ビット、128ビット）。 ソースデータのブロックの長さが暗号のビット長よりも短い場合、ブロックは何らかの既知の方法で補完されます。
   
   
   
   
2. ブロックは、「左」L ₀と「右」R _0の 2つの等しいサブブロックに分割され_ます 。
   
   64ビット容量の場合、それぞれ32ビットの長さを持つ2つのブロック。
   
   
   
   
3. 「左サブブロック」L _0は 、キーP _0に応じて、反復関数F （L ₀ 、P ₀ ）によって変更されます_。
   
   その後、「右サブブロック」R ₀とモジュロ2（XOR）が追加され_ます 。
   
   
   
   
4. 加算の結果は、次のラウンドの入力データの左半分になる新しい左サブブロックL ₁に割り当てられ、「左サブブロック」L _0は 、右半分になる新しい右サブブロックR ₁に変更なし_で割り当てられます。
   
   
   
   
5. この操作は、あるステージから別のステージに移動しながらn-1回繰り返され、ラウンドキー（P ₀ 、P ₁ 、P ₂など）が変化します。nは、使用されるアルゴリズムのラウンド数です。

復号化プロセスは、ラウンドキーが逆の順序で使用されることを除いて、暗号化プロセスに似ています。



Blowfishアルゴリズムに戻ります。



一般に、Blowfish暗号化アルゴリズムはFeistelネットワークですが、ラウンドキーを生成および使用するいくつかの機能を備えています（P ₀ 、P ₁ ...）。



まず、Blowfishアルゴリズムの反復関数Fは、入力を受け取って32ビット数（DWORD）を出力する「ブラックボックス」のようなものだとしましょう。



この場合、32ビットのラウンドキーPn：

1. ソースキーからの規則に従って計算されます（最大448ビット長）。
2. 反復関数Fの引数ではありません。
3. 「左ブロック」にモジュロ2（XOR）を直接追加します。
   
   この操作の結果は、関数Fの着信32ビット引数です。

Blowfishアルゴリズムでは、暗号化中に（Feistelネットワーク内で）16ラウンドが実行され、最後のラウンドの左右の出力ブロックに17番目と18番目のキーが追加されます。 可能なキーの長さを決定するため、このラウンド数が選択されました。



しかし、ここで注意深い読者は疑問を抱くかもしれません：それぞれ32ビットの長さを持つ18個のラウンドキーが使用される場合、最終的に576ビット（18キー×32ビット）の長さのキーを取得します。 Blowfishのソースキーの長さが最初は448ビットに制限されているのはなぜですか？



答えは簡単です-制限はありません。 576ビットまでのキーを使用できます。 しかし！ この制限は、アルゴリズムのセキュリティと暗号の安定性を観察するための要件に基づいて行われました。



C ++でBlowfishアルゴリズムのFeistelネットワークを実装しましょう。

void swap(unsigned long *a, unsigned long *b) { unsigned long temp; if (a && b) { temp = *a, *a = *b, *b = temp; } } void blowfish_encrypt_block(blowfish_ctx *ctx, unsigned long *high, unsigned long *low) { int i; for (i = 0; i < 16; i++) { *high ^= ctx->p[i]; *low ^= F(ctx, *high); swap(low, high); } swap(low, high); *low ^= ctx->p[16]; *high ^= ctx->p[17]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

キー拡張（爆破！）

Blowfishアルゴリズムの準備段階は、重要な拡張段階です。 この段階のプロセスでは、ラウンドキーのマトリックスPnと置換マトリックスが構築されます。それぞれが256個の32ビット要素で構成される4つのSボックス（置換ボックス）置換ブロックです。







これらの行列の要素は、Blowfishアルゴリズムについて前述したFeistelネットワークを使用して暗号化（計算）されます。 したがって、BlowfishアルゴリズムのFeistelネットワークが使用されます。

• ソースデータの暗号化/復号化。
• ラウンドキーマトリックスと置換マトリックスを生成します（つまり、キー拡張）。

生成されたラウンドキーマトリックスと置換マトリックスは、その後使用されます

暗号化/復号化の過程で。



キー拡張プロセスが処理されます

18×32（P ₁ 、P ₂ ...）+ 4×256×32（S ₁ —S ₄ ）= 33344ビットまたは4168バイトのデータ。



この場合、（18（Pn）+ 4×256（S ₁ —S ₄ ））/ 2 = 521がFeistelネットワークの完全な反復に対して実行されます。



これはすべて非常に時間がかかる操作であり、それがBlowfishアルゴリズムの理由です

頻繁にキーを変更する必要がある場合はお勧めしません。



キー拡張アルゴリズムについて説明します。

1. 「誠実な番号」を選択します（または、「袖の番号を上げない」）。 これは、最初は繰り返しシーケンスを含まない既知の数値です。 これは、たとえばアルゴリズム（バックドア）に抜け穴を作成するなど、「悪意のある」目標を追求せずに開発者が定数を選択したことを示すために行われます。
   
   
   
   Blowfishは通常、PI番号を誠実な番号として使用します。 PI番号の値の16進表現は計算しませんが、既製のソリューションを使用します： PI番号の仮数の8366桁の16進数 。
   
   
   
   
2. PI番号の仮数の値は、ラウンドキーのマトリックス（FIXED_P）および置換マトリックス（FIXED_S）を埋めるために使用されます。
   
   
   
   

    typedef struct _blowfish_ctx { unsigned long p[18]; unsigned long sbox[4][256]; } blowfish_ctx; const unsigned int FIXED_S[4][256] = { { 0xD1310BA6, 0x98DFB5AC, 0x2FFD72DB, 0xD01ADFB7, 0xB8E1AFED, 0x6A267E96, 0xBA7C9045, 0xF12C7F99, 0x24A19947, 0xB3916CF7, 0x0801F2E2, 0x858EFC16, 0x636920D8, 0x71574E69, 0xA458FEA3, 0xF4933D7E, 0x0D95748F, 0x728EB658, 0x718BCD58, 0x82154AEE, 0x7B54A41D, 0xC25A59B5, 0x9C30D539, 0x2AF26013, ....        .... 0xB74E6132, 0xCE77E25B, 0x578FDFE3, 0x3AC372E6 } }; const unsigned long FIXED_P[] = { 0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344, 0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89, 0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C, 0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917, 0x9216D5D9, 0x8979FB1B };
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   
   
   
3. 各ラウンドキーPn（P ₁ 、P ₂ ...）の値は、元のキーKの対応する要素とモジュロ2（XOR）で加算されます。たとえば、ラウンドキーP _1の XOR
   
   元のキーKの最初の32ビットを使用して、元のキーKの2番目の32ビットを使用してP _2のようになります。 元のキーKがすべてのラウンドキーの長さ（576ビット）よりも短い場合は、それ自体を連結します。
   
   あなたと：KK、KKKなど。
   
   
   
   

    for(i = 0, k = 0; i < 18; i++) { for(j = 0, long_key = 0; j < 4; j++, k++) { long_key = (long_key << 8) | key[k % key_len]; } ctx->p[i] ^= long_key; }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   
   
   
4. 次に、ラウンドキーの行列と置換行列の要素を暗号化（新しい値を計算）する必要があります。 これを行うには、実装したBlowfishのFeistelネットワークアルゴリズムを使用します。
   
   
   
   
   1. 現在のラウンドキーP 1〜P ₁₈と置換行列S 1〜S ₄ （置換行列については以下で正確に説明します）を使用して、64ビットのゼロシーケンス0x00000000 0x00000000を暗号化し、P ₁とP _2に結果を書き込みます。 。
      
      
      
      
   2. P ₁とP ₂は、ラウンドキーと置換行列の変更された値で暗号化され、結果はそれぞれP ₃とP _4に書き込まれます。
      
      
      
      
   3. 暗号化は、すべてのラウンドキーP 1〜P ₁₈および置換行列S 1〜S _4の要素_が変更されるまで続きます。
      
      
      
      つまり 最終的に、（18 Pn + 4×256（S ₁ —S ₄ ））/ 2 = 521の繰り返しに対するBlowfishアルゴリズムのFeistelネットワーク計算の結果を取得する必要があります。 反復ごとに、ラウンドキーの行列または順列の行列の要素に対して2つの新しい値をすぐに計算するため、2で割った。
   
   
   
   
   

    for (i = 0, k = 0, l = 0; i < 18; i++) { blowfish_encrypt_block(ctx, (unsigned long*)&k, (unsigned long*)&l); ctx->p[i] = k; ctx->p[++i] = l; } for (i = 0; i < 4; i++) { for (j = 0; j < 256; j++) { blowfish_encrypt_block(ctx, (unsigned long*)&k, (unsigned long*)&l); ctx->sbox[i][j] = k; ctx->sbox[i][++j] = l; } }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

この時点で、Blowfishアルゴリズムの準備段階（キーの拡張）が完了しました。 しかし、暗号化/復号化段階を見る前に、BlowfishアルゴリズムのFeistelネットワークの反復内で各ラウンドで実行される「ブラックボックス」 -関数Fを開いてみましょう。

反復（ラウンド）関数

ラウンド関数または反復関数（使用されるFeistelネットワーク全体に共通であるため）は非常に単純であり、置換行列に対していくつかの論理演算のみを使用します。 当初、Horst FeistelはLuciferの開発時に、順列の行列に単純な線形回路を備えた電子ユニットの使用を想定していました。







だから：

1. 着信32ビットブロックは4つの8ビットブロックに分割されます。それらをX ₁ 、X ₂ 、X ₃ 、X ₄と呼びましょう
   
   （上の図を参照）。
   
   
   
   
2. それぞれは、置換テーブルS 1〜S ₄の配列のインデックスです。
3. S ₁ [X ₁ ]とS ₂ [X ₂ ]の値が2 ^32を法として加算され、結果が加算されます
   
   2（XOR）とS ₃ [X ₃ ]を法とし、最後にS ₄ [X ₄ ]を2 ^32を法として合計します。
4. 計算の結果は、関数F（X ₁ -X ₄ ）の値になります。

関数式：





すべてが非常に簡単です。 この関数は、S 1〜S ₄置換マトリックスを使用して、着信32ビットのデータを置換マトリックスからの値に線形に変換します。 そして意味自体

マトリックスでは、置換は以前に検討した主要な拡張段階で計算されます。



C ++での関数の実装：

 unsigned long F(blowfish_ctx *ctx, unsigned long x) { return ((ctx->sbox[0][(x >> 24) & 0xFF] + ctx->sbox[1][(x >> 16) & 0xFF]) ^ ctx->sbox[2][(x >> 8) & 0xFF]) + ctx->sbox[3][(x) & 0xFF]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、ソースデータを暗号化するプロセスに進みましょう。

ソースデータの暗号化/復号化

サプライズ！ 実際、ソースデータの暗号化および復号化アルゴリズムはすでに検討済みです。 問題は、最初に気づいたように、データの暗号化/復号化、および前述のラウンドキーのマトリックスと置換マトリックスの作成が、Blowfishアルゴリズムに考慮されたFeistelネットワークを使用して行われることです。



つまり ソフトウェアの実装では、ソースデータの暗号化プロセス全体が、キー拡張の段階での暗号化プロセスとの類推によって構築されます。 つまり ソースデータの64ビットごとにblowfish_encrypt_block関数（Feistelネットワークの実装）を繰り返し実行することを表します。 ラウンドキーP（P ₁ 、P ₂ 、hellip）および置換行列S 1〜S ₄は、それぞれFeistelネットワークおよびこのネットワーク内の関数Fの入力パラメーターです。







その結果、Blowfishアルゴリズムで暗号化または復号化アルゴリズムを要約すると、

その後、次の手順を実行します。

1. Feistelネットワークのラウンドキー用に18個の要素の配列と、それぞれ256個の要素の4つの置換行列を選択します。
   
   
   
   
2. 選択した配列にPI番号の仮数値を入力します。
   
   
   
   
3. 反復XORを作成します。Pi= Pi XOR Ki（Piはラウンドキー、Kiはソースキー）。
   
   
   
   
4. Feistelネットワークを使用してラウンドキーと置換マトリックスを暗号化します（置換マトリックスはネットワーク内の関数の入力パラメーターとして使用され、ネットワーク内のラウンドキーはラウンドキーマトリックスから取得されます）。
   
   
   
   
5. また、Feistelネットワークを使用して、64ビットのソースデータブロックを暗号化/復号化します。
   
   
   
   

すべてがシンプルです。

まとめ

親愛なる読者。 複雑なことを簡単な言葉で説明することは非常に困難です。



このテキストを書き始める前に、私は開発者の代わりに身を置いてみました。

議論したBlowfishアルゴリズムを研究しようとする人。



そこで、このアルゴリズムを理解するのに十分な完全性を備えたドキュメントをネットワーク上で見つけることにしました。 その結果、私はもちろんウィキペディアのページ、フォーラム、そしてさまざまな用語集に到達しました。 しかし、そこに提示された説明を読むと、しばしば答えよりも多くの質問が生じました。



これらすべてのことから、例とともに簡単かつ同時に詳細な説明が有用であり、需要があるという意見で私を確認しました。 したがって、私はできる限り「すべてを棚に置く」ことを試みました。 しかし、私はそれをどれだけうまくやった-あなたを判断します。



ありがとう

心から、AB



PS続行する予定です...