使用者:Blackbinary1024/RC5

Blackbinary1024/RC5

One round (two half-rounds) of the RC5 block cipher

在密碼學中， RC5 是一種因簡潔著稱的對稱分組加密算法。 由羅納德·維斯特於1994年設計， RC 代表"Rivest Cipher"，或者Ron's Code"(相較於 RC2 和 RC4). 高級加密標準 (AES)的候選算法之一RC6 是基於RC5的。

簡介

和許多加密方法不同，RC5允許可變的塊大小 (32、64或128 位)， 密鑰長度 (0至2040位)和加密輪數(0～255)。 最初建議選擇的參數是64位的塊大小，128位的密鑰和12輪加密。

RC5的一個關鍵特徵是使用基於數據的置換。RC5的其中一個目標是促進對於這類作為 原始密碼 的操作的研究和評估。 RC5也包括一些的取模加法和邏輯異或(XOR)運算. 這個加密的一般結構是類費斯妥網絡。 加密和解密程序可以用幾行代碼寫完。 然而密鑰的生成算法更為複雜。密鑰擴展使用了e和黃金比例代入一個單向函數，將所得值作為"我衣袖裡是空的"數字（即無任何來源依據的魔法數字）。 算法的誘人的簡潔性和基於數據的置換的特性，讓RC5吸引了眾多密碼研究人員將其作為研究對象。 RC5通常被記為RC5-w/r/b，w=字的大小（以bit為單位），r=加密輪數，b=密鑰的8位數的8位字節。

算法

RC5加密和解密都將隨機的密鑰擴展成2(r+1)個字，在加密和解密的過程中，這些字將會被按順序使用（而且每個字只使用一次）。以下的所有內容都來自Rivest的修訂後的RC5的論文

密鑰擴展

密鑰擴展算法將會在下面講解，首先以偽代碼表示，之後是用從參考資料中的論文附錄中直接複製的C語言代碼。

以下是論文中的命名方案，使用了這些變量名：

• w - 一個字的長度（以bit為單位)，通常是16、32或64。 加密以兩個字為單位進行。
• 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 在這裡以十六進制給出：
  • 對於 w =16: 0xB7E1
  • 對於 w =32: 0xB7E15163
  • 對於 w =64: 0xB7E151628AED2A6B
• Q_w -第二個魔法數字，定義為 $Odd((\phi -1)*2^{w})$其中Odd取最接近給定輸入的奇數， $\phi$ 是黃金比例，w 見上述定義。 對於共對於常見的w值，對應的P_w 在這裡以十六進制給出：
  • 對於 w =16:0x9E37
  • 對於 w =32:0x9E3779B9
  • 對於 w =64:0x9E3779B97F4A7C15

# Break K into words
# u = w / 8
c = ceiling( max(b, 1) / u )
# L is initially a c-length list of 0-valued w-length words
for i = b-1 down to 0 do:
    L[i/u] = (L[i/u] << 8) + K[i]
     
# Initialize key-independent pseudorandom S array
# S is initially a t=2(r+1) length list of undefined w-length words
S[0] = P_w
for i = 1 to t-1 do:
    S[i] = S[i-1] + Q_w
    
# The main key scheduling loop
i = j = 0
A = B = 0
do 3 * max(t, c) times:
    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

# return S

實例源碼由Rivest的RC5論文的附錄提供。這個代碼實現對應 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;
   
   for(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 - 要加密的明文的兩個字。

A = A + S[0]
B = B + S[1]
for i = 1 to r do:
    A = ((A ^ B) <<< B) + S[2 * i]
    B = ((B ^ A) <<< A) + S[2 * i + 1]

# The ciphertext block consists of the two-word wide block composed of A and B, in that order.
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;
}

解密

解密實際上就是直接把加密過程顛倒。 以下代碼展示了這個過程。

for i = r down to 1 do:
    B = ((B - S[2 * i + 1]) >>> A) ^ A
    A = ((A - S[2 * i]) >>> B) ^ B
B = B - S[1]
A = A - S[0]

return 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位塊)容易受到使用了2⁴⁴的選定的明文的差分攻擊。 18–20輪加密則被認為可以提供足夠的保護。

擁有其算法專利的公司RSA安全， 提供一系列的10 000美元的獎金作為破譯用RC5加密的密文的獎勵，但這些競賽已經在2007年5月停止。 其中的一部分已經在Distributed.net組織下利用分布式計算破解。 Distributed.net暴力破解了用56位和64位密鑰的RC5加密的密文，正在嘗試破解72位密鑰的密文；截至2018年2月，5.02%的密鑰空間已被遍歷。 以目前的速度，這將需要大約166年以測試的每一個可能的剩餘密鑰，以此才能保證項目的完成。 這項任務啟發了許多在集群計算領域的新興的開發研究。

參見

• Madryga
• Red Pike

外部連結

• Rivests的修訂文件，描述的密碼
• 維斯特的原始紙
• 掃描的進入密碼
• RSA實驗室的常見問題 — 什麼RC5和RC6?
• Helger Lipmaa的鏈接RC5

[[Category:使用过时图像语法的页面]]