RC4

RC4

RC4(來自Rivest Cipher 4的縮寫)是一種流加密演演算法,密鑰長度可變。它加解密使用相同的密鑰,因此也屬於對稱加密演演算法。RC4是有線等效加密(WEP)中採用的加密演演算法,也曾經是TLS可採用的演演算法之一。

簡介


RC4加密演演算法是大名鼎鼎的RSA三人組中的頭號人物Ron Rivest在1987年設計的密鑰長度可變的流加密演演算法簇。之所以稱其為簇,是由於其核心部分的S-box長度可為任意,但一般為256位元組。該演演算法的速度可以達到DES加密的10倍左右。

歷史


RC4是由羅納德·李維斯特在1987年開發出來的,雖然它的官方名是“Rivest Cipher 4”,但是首字母縮寫RC也可以理解為"Ron's Code"。
RC4開始時是商業密碼,沒有公開發表出來,但是在1994年9月份的時候,它被人匿名公開在了Cypherpunks郵件列表上,很快它就被發到了sci.crypt新聞組上,隨後從這傳播到了網際網路的許多站點。隨之貼出的代碼後來被證明是真實的,因為它的輸出跟取得了RC4版權的私有軟體的輸出是完全相同的。由於演演算法已經公開,RC4也就不再是商業秘密了,只是它的名字“RC4”仍然是一個註冊商標。RC4經常被稱作是“ARCFOUR”或者"ARC4"(意思是稱為RC4),這樣來避免商標使用的問題
RC4已經成為一些常用的協議和標準的一部分,如1997年的WEP和2003/2004年無線卡的WPA;和1995年的SSL,以及後來1999年的TLS。讓它如此廣泛分佈和使用的主要因素是它不可思議的簡單和速度,不管是軟體還是硬體,實現起來都十分容易。

破解


2015年,比利時魯汶大學的研究人員Mathy Vanhoef及Frank Piessens,公布了針對RC4加密演演算法的新型攻擊程式,可在75小時內取得cookie的內容。

原理


RC4演演算法的原理很簡單,包括初始化演演算法(KSA)和偽隨機子密碼生成演演算法(PRGA)兩大部分。假設S-box的長度為256,密鑰長度為Len。先來看看演演算法的初始化部分(用C代碼表示):
其中,參數1是一個256長度的char型數組,定義為:unsigned char sBox[256];
參數2是密鑰,其內容可以隨便定義:char key[256];
參數3是密鑰的長度,Len=strlen(key);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void rc4_init(unsigned char*s,unsigned char*key, unsigned long Len)
{
int i=0,j=0;
//char k[256]={0};
unsigned char k[256]={0};
unsigned char tmp=0;
for(i=0;i<256;i++) {
s[i]=i;
k[i]=key[i%Len];
}
for(i=0;i<256;i++) {
j=(j+s[i]+k[i])%256;
tmp=s[i];
s[i]=s[j];//交換s[i]和s[j]
s[j]=tmp;
}
}
在初始化的過程中,密鑰的主要功能是將S-box攪亂,i確保S-box的每個元素都得到處理,j保證S-box的攪亂是隨機的。而不同的S-box在經過偽隨機子密碼生成演演算法的處理后可以得到不同的子密鑰序列,將S-box和明文進行xor運算,得到密文,解密過程也完全相同。
再來看看演演算法的加密部分(用C代碼表示):
其中,參數1是上邊rc4_init函數中,被攪亂的S-box;
參數2是需要加密的數據data;
參數3是data的長度.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void rc4_crypt(unsigned char*s,unsigned char*Data,unsigned long Len)
{
int i=0,j=0,t=0;
unsigned long k=0;
unsigned char tmp;
for(k=0;k
{
i=(i+1)%256;
j=(j+s[i])%256;
tmp=s[i];
s[i]=s[j];//交換s[x]和s[y]
s[j]=tmp;
t=(s[i]+s[j])%256;
Data[k]^=s[t];
}
}
最後,在main函數中,調用順序如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main()
{
unsigned char s[256]={0},s2[256]={0};//S-box
char key[256]={"justfortest"};
char pData[512]="這是一個用來加密的數據Data";
unsigned long len=strlen(pData);
int i;
printf("pData=%s\n",pData);
printf("key=%s,length=%d\n\n",key,strlen(key));
rc4_init(s,(unsigned char*)key,strlen(key));//已經完成了初始化
printf("完成對S[i]的初始化,如下:\n\n");
for(i=0;i<256;i++)
{
printf("%02X",s[i]);
if(i&&(i+1)%16==0)putchar('\n');
}
printf("\n\n");
for(i=0;i<256;i++)//用s2[i]暫時保留經過初始化的s[i],很重要的!!!
{
s2[i]=s[i];
}
printf("已經初始化,現在加密:\n\n");
rc4_crypt(s,(unsigned char*)pData,len);//加密
printf("pData=%s\n\n",pData);
printf("已經加密,現在解密:\n\n");
//rc4_init(s,(unsigned char*)key,strlen(key));//初始化密鑰
rc4_crypt(s2,(unsigned char*)pData,len);//解密
printf("pData=%s\n\n",pData);
return0;
}
因此最終的完整程序是:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//程序開始
#include
#include
typedef unsigned longULONG;
void rc4_init(unsigned char*s, unsigned char*key, unsigned long Len)
{
int i = 0, j = 0;
char k[256] = { 0 };
unsigned char tmp = 0;
for (i = 0; i<256; i++)
{
s[i] = i;
k[i] = key[i%Len];
}
for (i = 0; i<256; i++)
{
j = (j + s[i] + k[i]) % 256;
tmp = s[i];
s[i] = s[j];//交換s[i]和s[j]
s[j] = tmp;
}
}
void rc4_crypt(unsigned char*s, unsigned char*Data, unsigned long Len)
{
int i = 0, j = 0, t = 0;
unsigned long k = 0;
unsigned char tmp;
for (k = 0; k
{
i = (i + 1) % 256;
j = (j + s[i]) % 256;
tmp = s[i];
s[i] = s[j];//交換s[x]和s[y]
s[j] = tmp;
t = (s[i] + s[j]) % 256;
Data[k] ^= s[t];
}
}
int main()
{
unsigned char s[256] = { 0 }, s2[256] = { 0 };//S-box
char key[256] = { "justfortest" };
char pData[512] = "這是一個用來加密的數據Data";
unsigned long len = strlen(pData);
int i;
printf("pData=%s\n", pData);
printf("key=%s,length=%d\n\n", key, strlen(key));
rc4_init(s, (unsigned char*)key, strlen(key));//已經完成了初始化
printf("完成對S[i]的初始化,如下:\n\n");
for (i = 0; i<256; i++)
{
printf("%02X", s[i]);
if (i && (i + 1) % 16 == 0)putchar('\n');
}
printf("\n\n");
for (i = 0; i<256; i++)//用s2[i]暫時保留經過初始化的s[i],很重要的!!!
{
s2[i] = s[i];
}
printf("已經初始化,現在加密:\n\n");
rc4_crypt(s, (unsigned char*)pData, len);//加密
printf("pData=%s\n\n", pData);
printf("已經加密,現在解密:\n\n");
//rc4_init(s,(unsignedchar*)key,strlen(key));//初始化密鑰
rc4_crypt(s2, (unsigned char*)pData, len);//解密
printf("pData=%s\n\n", pData);
return 0;
}
//程序完

應用安全


由於RC4演演算法加密是採用的xor,所以,一旦子密鑰序列出現了重複,密文就有可能被破解。關於如何破解xor加密,請參看Bruce Schneier的Applied Cryptography一書的1.4節Simple XOR,在此我就不細說了。那麼,RC4演演算法生成的子密鑰序列是否會出現重複呢?由於存在部分弱密鑰,使得子密鑰序列在不到100萬位元組內就發生了完全的重複,如果是部分重複,則可能在不到10萬位元組內就能發生重複,因此,推薦在使用RC4演演算法時,必須對加密密鑰進行測試,判斷其是否為弱密鑰。
而且,根據目前的分析結果,沒有任何的分析對於密鑰長度達到128位的RC4有效,所以,RC4是目前最安全的加密演演算法之一,大家可以放心使用!