rc4 笔记

发表于 本文字数： 1.9k 阅读时长 ≈ 2 分钟
rc4 的简要笔记

RC4 原理

简述

在密码学中，RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，因此也属于对称加密算法，属于 Feistel 密码结构。

但不同于DES的是，RC4不是对明文进行分组处理，而是字节流的方式依次加密明文中的每一个字节，解密的时候也是依次对密文中的每一个字节进行解密。

流密码

定义：流密码是对称密码算法，从明文输入流逐位或逐字节产生密文输出。

实例：使用最广泛的流密码是RC4。

流密码结构：

流密码结构图

流密码类似于”一次一密”，不同的是”一次一密”使用的是真正的随机数流，而流密码使用的是伪随机数流。

设计流密码的主要因素：

  1. 加密序列的周期要长，若出现重复的周期过短，容易被破解
  2. 密钥流应该尽可能地接近真正随机数流的特征
  3. 密钥长度要长，以避免琼穷举攻击

算法逻辑结构

密钥流的生成

算法关键变量

  1. 密钥流：RC4算法的关键是根据明文和密钥生成相应的密钥流，密钥流的长度和明文的长度是对应的，也就是说明文的长度是500字节，那么密钥流也是500字节。当然，加密生成的密文也是500字节，因为密文第i字节=明文第 i 字节 ^ 密钥流第 i 字节；
  2. 状态向量S：长度为256，S[0],S[1].....S[255]。每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换；
  3. 临时向量T：长度也为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给T，否则，轮转地将密钥的每个字节赋给T；
  4. 密钥K：长度为1-256字节，注意密钥的长度与明文长度、密钥流的长度没有必然关系，通常密钥的长度趣味16字节（128比特）。

算法描述

  1. 初始化状态向量S

    给S的元素依次初始化0~255

  2. 初始化临时向量T

    若密钥K长度小于256字节，则进行轮转填充状态向量T

  3. 对状态向量S进行置换操作

    按照以下规则打乱状态向量S

    1
    2
    3
    4
    5
    6
    j = 0;
    for (i = 0; i < 256; i++)
    {
        j = (j + S[i] + T[i]) mod 256;
        swap(S[i], S[j]);
    }

    处理后，状态向量S几乎带有一定的随机性

  4. 密钥流的生成

    1
    2
    3
    4
    5
    6
    7
    8
    9
    i, j = 0;
    for (r = 0; r < dataLength; r++)
    {
    	i = (i + 1) mod 256;
    	j = (j + S[i]) mod 256;
    	swap(S[i], S[j]);
    	t = (S[i] + S[j]) mod 256;
    	z[r] = S[t]
    }

    其中 z[r] 为每一位的密钥流

  5. 加解密

    1
    2
    3
    4
    for (i = 0; i < dataLength; i++)
    {
    	data[i] ^= z[i];
    }

C++ 实现

其中 S 必须为 char S[256]

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
void rc4_init(char* S, char* K, size_t len)
{
	char T[256];
	size_t i, j;
	char t;
	// 初始化状态向量S与临时向量T
	for (i = 0; i < 256; ++i)
	{
		S[i] = i;
		T[i] = K[i % len];
	}

	// 对状态向量S进行置换操作
	j = 0;
	for (i = 0; i < 256; ++i)
	{
		j = (j + T[i] + S[i]) % 256;

		// swap(S[i], S[j]);
		t = S[i];
		S[i] = S[j];
		S[j] = t;
	}
}

void rc4(char* S, char* data, size_t len)
{
	size_t i = 0, j = 0;
	char t;
	for (size_t r = 0; r < len; r++)
	{
		i = (i + 1) % 256;
		j = (j + S[i]) % 256;

		// swap(S[i], S[j]);
		t = S[i];
		S[i] = S[j];
		S[j] = t;

		t = (S[i] + S[j]) % 256;
		data[r] ^= t;
	}
}

Python 实现

1
2
3
4
5
6
7
8
9
import base64
from Crypto.Cipher import ARC4

data = "mg6CITV6GEaFDTYnObFmENOAVjKcQmGncF90WhqvCFyhhsyqq1s="
key = "carol"

rc4 = ARC4.new(key.encode())
res = rc4.decrypt(base64.b64decode(data))
print(res)