RC5

RC5

RC5ブロック暗号の1ラウンド（2つの半ラウンド）
一般的な
デザイナー	ロン・リベスト
初版	1994
後継者	RC6、アケラレ
暗号の詳細
キーサイズ	0 ～ 2040 ビット (128 ビットを推奨)
ブロックサイズ	32、64、または128ビット（64ビットを推奨）
構造	フェイステル型ネットワーク
ラウンド	1-255 (当初提案されたのは12)
最高の公開暗号解読
12ラウンドのRC5（64ビットブロック）は、244個の選択平文を使用した差分攻撃に対して脆弱である。[ 1 ]

暗号学において、RC5 は対称鍵 ブロック暗号であり、そのシンプルさで知られています。1994年にロナルド リベストによって設計されました。 ^[2] RC は「Rivest Cipher」または「Ron's Code」の略です ( RC2とRC4を比較してください)。Advanced Encryption Standard (AES) の候補であるRC6 はRC5 に基づいています。

多くの方式とは異なり、RC5 には可変ブロック サイズ(32、64、または 128ビット)、キー サイズ(0 ～ 2040 ビット)、およびラウンド数 (0 ～ 255) があります。当初提案されたパラメータの選択肢は、64 ビットのブロック サイズ、128 ビットのキー、および 12 ラウンドでした。

RC5 の重要な特徴は、データ依存回転の使用です。RC5 の目標の 1 つは、このような操作を暗号プリミティブとして研究および評価することを促進することでした。^[要出典] RC5 は、多数のモジュラー加算と排他的論理和 (XOR)で構成されます。アルゴリズムの一般的な構造は、RC2 に似たFeistelのようなネットワークです。暗号化および復号化ルーチンは、数行のコードで指定できます。ただし、キー スケジュールはより複雑で、eと黄金比の両方の 2 進展開を「秘密の数字」のソースとして使用して、基本的に一方向の関数を使用してキーを拡張します。アルゴリズムの魅力的な単純さとデータ依存回転の目新しさにより、RC5 は暗号解読者にとって魅力的な研究対象となっています。^{[誰によると? RC5は} 基本的に RC5-w/r/b と表記されます。ここで、w はビット単位のワード サイズ、r はラウンド数、b はキーのバイト数です。

RC5 暗号化と復号化はどちらもランダム キーを 2(r+1) ワードに拡張し、暗号化と復号化のプロセス中に順番に (それぞれ 1 回だけ) 使用されます。以下はすべて、Rivest の RC5 に関する改訂論文からの引用です。^[3]

キー拡張アルゴリズムは、最初に疑似コードで、次に参考文献の付録から直接コピーした C コードの例で、以下に示されます。

論文の命名規則に従って、次の変数名が使用されます。

• w – ワードの長さ（ビット単位）。通常は 16、32、または 64 です。暗号化は 2 ワード ブロックで行われます。
• u = w /8 – バイト単位でのワードの長さ。
• b – キーの長さ（バイト単位）。
• K[] – キー。バイト配列として扱われます（0 ベースのインデックスを使用）。
• c – キーの長さ（単語単位）（b = 0 の場合は 1）。
• L[] – キーのスケジュール中に使用される一時的な作業配列。キーをワード単位で初期化します。
• r – データを暗号化するときに使用するラウンド数。
• t = 2( r +1) – 必要なラウンドサブキーの数。
• S[] – ラウンドサブキーワード。
• P _w – 最初のマジック定数。Odd(( e − 2)  ×  2 ^w )として定義されます。ここで、Oddは与えられた入力に最も近い奇数、eは自然対数の底、w は上で定義されています。wの一般的な値については、関連するP _wの値が16 進数で次のように示されます。
  • w = 16の場合: 0xB7E1
  • w = 32の場合: 0xB7E15163
  • w = 64の場合: 0xB7E151628AED2A6B
• Q _w – 2 番目の魔法定数。Odd ((𝜙 − 1)  ×  2 ^w )と定義されます。ここで、Oddは与えられた入力に最も近い奇数です。𝜙は黄金比で、w は上で定義されています。wの一般的な値については、関連するQ _wの値が16 進数で次のように示されます。
  • w = 16の場合: 0x9E37
  • w = 32の場合: 0x9E3779B9
  • w = 64の場合: 0x9E3779B97F4A7C15

# K を単語に分割します
# u = w / 8 
c  =  ceiling ( max ( b ,  1 )  /  u ) 
# L は最初、長さ c で値が 0 の w 長単語のリストです
for  i  =  b - 1 から 0まで do : L [ i / u ] = ( L [ i / u ] <<< 8 ) + K [ i ] 
              
     
# キーに依存しない疑似乱数 S 配列を初期化します
# S は初期値で長さが 2(r+1) の未定義の w 長ワードのリストです
S [ 0 ]  =  P_w 
for  i  =  1  to  t - 1  do : 
    S [ i ]  =  S [ i  -  1 ]  +  Q_w
    
# メインキースケジューリングループ
i  =  j  =  0 
A  =  B  =  0 
3 * max ( t , c )回実行します 。A = S [ i ] = ( S [ i ] + A + B ) <<< 3 B = L [ j ] = ( L [ j ] + A + B ) <<< ( A + B ) i = ( i + 1 ) % t j = ( j + 1 ) % c    
              
                
          
          

# Sを返す

サンプル ソース コードは、RC5 に関する Rivest の論文の付録から提供されています。実装は、w = 32、r = 12、b = 16 で動作するように設計されています。

void RC5_SETUP ( unsigned char * K ) { // w = 32、r = 12、b = 16 // c = max(1、ceil(8 * b/w)) // t = 2 * (r+1) WORD i 、j 、k 、u = w / 8 、A 、B 、L [ c ]; for ( i = b -1 、L [ c -1 ] = 0 ; i != -1 ; i -- ) L [ i / u ] = ( L [ i / u ] << 8 ) + K [ i ]; for ( S [ 0 ] = P 、i = 1 ; i < t ; i ++ ) S [ i ] = S [ i -1 ] + Q ; ( A = B = i = j = k = 0 ; k < 3 * t ; k ++ , i = ( i + 1 ) % t , j = ( j + 1 ) % c ) { A = S [ i ] = ROTL ( S [ i ] + ( A + B ), 3 ); B = L [ j ] = ROTL ( L [ j ] + ( A + B ), ( A + B ) ); } }   

   
   
   
            
   
             
            
   
             
          
   
                              
   
               
                 
   

暗号化には、単純な関数を数回実行する必要があります。セキュリティのニーズと時間的な考慮に応じて、12 ラウンドまたは 20 ラウンドが推奨されるようです。上記で使用した変数の他に、このアルゴリズムでは次の変数が使用されます。

• A、B -暗号化される平文ブロックを構成する 2 つの単語。

A  =  A  +  S [ 0 ] 
B  =  B  +  S [ 1 ] 
i = 1の場合 、A = ( ( A ^ B ) <<< B ) + S [ 2 * i ] B = ( ( B ^ A ) <<< A ) + S [ 2 * i + 1 ]     
              
                

# 暗号文ブロックは、A と B の順序で構成された 2 ワード幅のブロックで構成されます。
return  A ,  B

Rivest が示した C コードの例は次のとおりです。

void RC5_ENCRYPT ( WORD * pt , WORD * ct ) { WORD i , A = pt [ 0 ] + S [ 0 ], B = pt [ 1 ] + S [ 1 ]; for ( i = 1 ; i <= r ; i ++ ) { A = ROTL ( A ^ B , B ) + S [ 2 * i ]; B = ROTL ( B ^ A , A ) + S [ 2 * i + 1 ]; } ct [ 0 ] = A ; ct [ 1 ] = B ; }    

              
   
          
   
             
               
   
        

復号化は、暗号化プロセスを逆順に行う非常に単純なものです。以下の疑似コードは、そのプロセスを示しています。

 i  =  r から 1まで 実行します: B = (( B - S [ 2 * i + 1 ]) >>> A ) ^ A A = (( A - S [ 2 * i ]) >>> B ) ^ B B = B - S [ 1 ] A = A - S [ 0 ] 
                
              
    
    

 A 、 Bを返す

Rivest が示した C コードの例は次のとおりです。

void RC5_DECRYPT ( WORD * ct , WORD * pt ) { WORD i , B = ct [ 1 ], A = ct [ 0 ]; for ( i = r ; i > 0 ; i -- ) { B = ROTR ( B - S [ 2 * i + 1 ], A ) ^ A ; A = ROTR ( A - S [ 2 * i ], B ) ^ B ; } pt [ 1 ] = B - S [ 1 ]; pt [ 0 ] = A - S [ 0 ]; }    

      
   
          
   
               
             
   
   
            

12ラウンドのRC5（64ビットブロック）は、244個の選択された平文を使用した差分攻撃に対して脆弱です^。 [ 1 ] ¹⁸～20ラウンドが十分な保護として提案されています。

これらの課題の多くは、 Distributed.netが主催する分散コンピューティングを使用して取り組まれてきました。Distributed.netは、56ビットおよび64ビットのキーで暗号化されたRC5メッセージを総当たり攻撃し、2002年11月3日から72ビットのキーの解読に取り組んできました。 ^[4] 2023年7月26日の時点で、キースペースの10.409％が検索されており、その日に記録されたレートに基づくと、キースペースの100％を完了するには59年強かかります。^[5]このタスクは、クラスターコンピューティングの分野で多くの新しい斬新な開発に影響を与えました。^[6]

RSA Securityは、このアルゴリズムの特許（現在は失効）を保有しており^{[7]、 RC5で暗号化された}暗号文を解読した人に1万ドルの賞金を出すコンテストを開催していたが、このコンテストは2007年5月をもって中止された。^[4]その結果、distributed.netが賞金を出すことにした。優勝鍵を発見した個人には1,000ドル、チーム（該当する場合）には1,000ドル、フリーソフトウェア財団には2,000ドルが支払われる。^[8]

• マドリガ
• レッドパイク

• リベストの暗号を説明した改訂版論文
• リベストの原論文
• SCANの暗号エントリ
• RSA Laboratories FAQ — RC5 と RC6 とは何ですか?
• Helger Lipmaa の RC5 のリンク