RC5
在密碼學中,RC5是一種因簡潔著稱的對稱分組加密演算法。由羅納德·李維斯特於1994年設計,[2]「RC」代表「Rivest Cipher」,或者「Ron's Code」(相較於RC2和RC4)。RC6演算法是基於RC5的。
![]() RC5區塊加密法的一輪(兩個半輪) | |
概述 | |
---|---|
設計者 | 羅納德·李維斯特 |
首次發布 | 1994 |
繼承演算法 | RC6,Akelarre |
密碼細節 | |
金鑰長度 | 0至2040位(建議128位元) |
分組長度 | 32,64或128位元(建議64位元) |
結構 | 類費斯妥網路 |
重複回數 | 1-255(原先建議12輪) |
最佳公開破解 | |
12輪RC5(64位元塊大小)可用244選擇明文進行差分攻擊。[1] |
簡介
編輯和許多加密方法不同,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=金鑰的位元組數。
演算法
編輯RC5加密和解密都將隨機的金鑰擴充成2(r+1)個字,在加密和解密的過程中,這些字將會被按順序使用(而且每個字只使用一次)。以下的所有內容都來自Rivest的修訂後的RC5的論文[3]
金鑰擴充
編輯金鑰擴充演算法將會在下面講解,首先以虛擬碼表示,之後是用從參考資料中的論文附錄中直接複製的C語言代碼。
以下是論文中的命名方案,使用了這些變數名:
- w - 一個字的長度(以bit為單位),通常是16、32或64。加密以兩個字為單位進行。
- u=w/8-一個字的長度,以位元組為單位。
- b-金鑰的長度,位元組為單位。
- K[]-金鑰,可以看作是一個由位元組資料組成的陣列(下標從0開始)。
- c - 金鑰的長度,以字為單位(如果b=0,取1).
- L[] - 一個在金鑰生成的臨時陣列,用來按字初始化金鑰
- r - 加密的輪數。
- t=2(r+1) - 需要的輪加密的子金鑰個數。
- S[] - 偽隨機S陣列。
- Pw - 第一個魔法數字,定義為 ,其中Odd取最接近給定輸入的奇數,e 為自然對數的底數,w 見上述定義。對於常見的w值,對應的Pw 在這裡以十六進制給出:
- 對於 w =16: 0xB7E1
- 對於 w =32: 0xB7E15163
- 對於 w =64: 0xB7E151628AED2A6B
- Qw -第二個魔法數字,定義為 其中Odd取最接近給定輸入的奇數, 是黃金比例,w 見上述定義。對於共對於常見的w值,對應的Pw 在這裡以十六進制給出:
- 對於 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位元塊)容易受到使用了244的選定的明文的差分攻擊。[1] 18–20輪加密則被認為可以提供足夠的保護。
擁有其演算法專利的公司RSA安全,[4] 提供一系列的10,000美元的獎金作為破譯用RC5加密的密文的獎勵,但這些競賽已經在2007年5月停止。其中的一部分已經在Distributed.net組織下利用分散式計算破解。Distributed.net暴力破解了用56位和64位元金鑰的RC5加密的密文,正在嘗試破解72位金鑰的密文;截至2018年2月,5.02%的金鑰空間已被遍歷。以目前的速度,這將需要大約166年以測試的每一個可能的剩餘金鑰,以此才能保證專案的完成。[5]這項任務啟發了許多在叢集計算領域的新興的開發研究。[6]
參見
編輯參考資料
編輯- ^ 1.0 1.1 Biryukov A.和Kushilevitz E.(1998年)。改進的密碼分析的RC5的。EUROCRYPT1998年。
- ^ Rivest, R. L. The RC5 Encryption Algorithm (pdf). Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e: 86–96. 1994 [2018-10-02]. (原始內容存檔 (PDF)於2007-04-17).
- ^ 存档副本 (PDF). [2018-09-27]. (原始內容存檔 (PDF)於2018-09-21).
- ^ Rivest, R. L, "Block Encryption Algorithm With Data Dependent Rotation", 美國專利第5,724,428號, issued on 3 March 1998.
- ^ RC5-72/项目的总体统计数据. [2018-09-27]. (原始內容存檔於2018-10-09).
- ^ Archived copy. [2014-10-28]. (原始內容存檔於2014-10-28).