简介
RC4 算法是一种流密码,它与之前学习的 MD5,SHA,HMAC,DES 等有根本区别,先与分组加密 DES 做个对比吧:
| 特性 | 分组加密(DES) | 流密码(RC4) |
|---|
| 处理方式 | 固定大小分组(如 64 位) | 逐位或逐字节 |
| 加密方式 | 分组加密 | 与伪随机密钥流异或 |
| 算法结构 | Feistel 网络/SPN | 伪随机数生成器 |
| 密钥流 | 固定 | 依赖于密钥和状态 |
核心思想:RC4 生成一个伪随机的密钥流,然后与明文进行逐字节异或操作得到密文
算法步骤
下面以具体的例子来演示 RC4 加密:“password”,密钥:“secret”
RC4 算法分为两个主要阶段:
密钥调度算法
目的是用一个可变长度的密钥,初始化一个 256 字节的状态向量 S
先来看一下代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
| def KSA(key):
# 1. 初始化S盒：S = [0, 1, 2, ..., 255]
S = list(range(256))
j = 0
key_length = len(key)
# 2. 用密钥打乱S盒
for i in range(256):
j = (j + S[i] + key[i % key_length]) % 256
# 交换S[i]和S[j]
S[i], S[j] = S[j], S[i]
return S
|
具体到运算中是什么样子呢?
输入密钥:“secret”(ASCII: 115, 101, 99, 114, 101, 116)
初始化 S 盒
1
| S[0] = 0, S[1] = 1, S[2] = 2, ..., S[255] = 255
|
打乱过程(演示一下前几步):
1
2
3
4
5
6
7
8
9
| i=0: j = (0 + S[0] + key[0]) % 256 = (0 + 0 + 115) % 256 = 115
交换 S[0] 和 S[115]：S[0]=115, S[115]=0
i=1: j = (115 + S[1] + key[1]) % 256 = (115 + 1 + 101) % 256 = 217
交换 S[1] 和 S[217]：S[1]=217, S[217]=1
i=2: j = (217 + S[2] + key[2]) % 256 = (217 + 2 + 99) % 256 = 62
交换 S[2] 和 S[62]：S[2]=62, S[62]=2
...
|
最终就得到了打乱的 S 盒:
1
| S = [115, 217, 62, 123, 245, ...] # 完全打乱的顺序
|
伪随机生成算法
利用打乱后的 S 盒生成伪随机的密钥流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def PRGA(S):
i = 0
j = 0
while True:
i = (i + 1) % 256
j = (j + S[i]) % 256
# 交换S[i]和S[j]
S[i], S[j] = S[j], S[i]
# 生成密钥流字节
t = (S[i] + S[j]) % 256
key_byte = S[t]
yield key_byte
|
明文:“password”（ASCII: 70 61 73 73 77 6F 72 64）
生成密钥流 (PRGA)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| i = 0, j = 0
第1个密钥字节：
i = (0 + 1) % 256 = 1
j = (0 + S[1]) % 256 = (0 + 217) % 256 = 217
交换 S[1] 和 S[217]：S[1]=1, S[217]=217
t = (S[1] + S[217]) % 256 = (1 + 217) % 256 = 218
密钥字节 = S[218] = （假设为）0x3A
第2个密钥字节：
i = (1 + 1) % 256 = 2
j = (217 + S[2]) % 256 = (217 + 62) % 256 = 23
交换 S[2] 和 S[23]：S[2]=123, S[23]=62
t = (S[2] + S[23]) % 256 = (123 + 62) % 256 = 185
密钥字节 = S[185] = （假设为）0xF7
...
|
这就生成了一个完整的密钥流了
1
| 密钥流: 3A F7 85 2C 91 DE 4B 6C
|
加解密过程
加密和解密是使用的相同的操作
1
2
3
4
5
6
7
8
9
10
11
12
13
| def rc4_process(key, data):
# 初始化S盒
S = KSA(key)
# 生成密钥流
key_stream = PRGA(S)
# 逐字节异或
result = bytearray()
for byte in data:
key_byte = next(key_stream)
result.append(byte ^ key_byte)
return bytes(result)
|
加密:将得到的密钥流和明文进行异或
1
2
3
| 明文: 70 61 73 73 77 6F 72 64
密钥流: 3A F7 85 2C 91 DE 4B 6C
异或: 4A 96 F6 5F E6 B1 39 08
|
解密:同理,将得到的密文与密钥流进行异或,就能够得到明文
1
2
3
| 密文: 4A 96 F6 5F E6 B1 39 08
密钥流: 3A F7 85 2C 91 DE 4B 6C
异或: 70 61 73 73 77 6F 72 64
|
完整的代码实现
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
| class RC4:
def __init__(self, key):
"""用给定密钥初始化RC4"""
self.S = list(range(256))
self.i = 0
self.j = 0
self._ksa(key)
def _ksa(self, key):
"""密钥调度算法"""
j = 0
key_length = len(key)
for i in range(256):
j = (j + self.S[i] + key[i % key_length]) % 256
self.S[i], self.S[j] = self.S[j], self.S[i]
def _prga(self):
"""伪随机生成算法（生成一个字节）"""
self.i = (self.i + 1) % 256
self.j = (self.j + self.S[self.i]) % 256
self.S[self.i], self.S[self.j] = self.S[self.j], self.S[self.i]
t = (self.S[self.i] + self.S[self.j]) % 256
return self.S[t]
def process(self, data):
"""加密或解密数据"""
result = bytearray()
for byte in data:
key_byte = self._prga()
result.append(byte ^ key_byte)
return bytes(result)
def rc4_main():
# 测试数据
key = b"secret"
plaintext = b"password"
print(f"密钥: {key.hex()}")
print(f"明文: {plaintext.hex()}")
# 加密
rc4 = RC4(key)
ciphertext = rc4.process(plaintext)
print(f"密文: {ciphertext.hex()}")
# 解密（使用相同密钥重新初始化）
rc4_decrypt = RC4(key)
decrypted = rc4_decrypt.process(ciphertext)
print(f"解密: {decrypted.hex()}")
print(f"验证: {decrypted == plaintext}")
if __name__ == "__main__":
rc4_main()
|