RC4

什么是RC4 ?

RC4加密算法是大名鼎鼎的RSA三人组中的头号人物Ron Rivest在1987年设计的密钥长度可变的流加密算法簇，之所以称其为簇，是由于其核心部分的S-box长度可为任意，但一般为256字节。

在密码学中，RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，因此也属于对称加密算法。所谓对称加密，就是加密和解密的过程是一样的。RC4是有线等效加密（WEP）中采用的加密算法，也曾经是TLS可采用的算法之一。

RC4已经成为一些常用的协议和标准的一部分，如1997年的WEP和2003/2004年无线卡的WPA; 和1995年的SSL，以及后来1999年的TLS。让它如此广泛分布和使用的主要因素是它不可思议的简单和速度，不管是软件还是硬件，实现起来都十分容易。

基本原理

对明文使用同一个密钥异或两次最后得到的是原文

  • 加密：原文和Keystream进行异或得到密文
  • 解密：密文和Keystream进行异或得到原文

img

流程图解

img

生成秘钥流（KeyStream）

从上图可以看出来，RC4加密原理很简单，只需要一个KeyStream与明文进行异或即可，密钥流的长度和明文的长度是对应的。RC4算法的的主要代码还是在于如何生成秘钥流。

密钥流的生成由两部分组成：

  1. KSA（the Key-Scheduling Algorithm)
  2. PRGA(the Pseudo-Random Generation Algorithm)

利用Key生成S盒——The key-scheduling algorithm (KSA)

1
2
3
4
5
6
7
8
9
10
11
/* 得到S-box */
int i = 0;
for (i = 0; i < 256; i++) {
    S[i] = i;
    T[i] = puc_key[i % key_length];
}
 
for (i = 0; i < 256; i++) {
    j = (j + S[i] + T[i]) % 256;
    swap_uchar(&S[i], &S[j]); //交换S[i]和S[j]
}

利用S盒生成密钥流——The pseudo-random generation algorithm(PRGA)

img

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 生成密钥流 Keystream */
int i = 0;
int j = 0;
int t = 0;
unsigned long k = 0;
 
for (k = 0; k < ul_data_length; k++) {
    i = (i + 1) % 256;
    j = (j + puc_sbox[i]) % 256;
    swap_uchar(&puc_sbox[i], &puc_sbox[j]);
    t = (puc_sbox[i] + puc_sbox[j]) % 256;
    puc_key_stream[k] = puc_sbox[t];
}

代码实现

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<stdio.h>
#include<string.h>
 
#define SBOX_LEN 256
 
#define rc4_encrypt rc4_crypt
#define rc4_decrypt rc4_crypt
 
static inline void swap_uchar(unsigned char *puc_x, unsigned char *puc_y)
{
    *puc_x = *puc_x ^ *puc_y;
    *puc_y = *puc_x ^ *puc_y;
    *puc_x = *puc_x ^ *puc_y;
}
 
void hexdump(unsigned char *puc_data, int length)
{
    int i = 0;
 
    for (i = 0; i < length; i++) {
        printf("%02X", puc_data[i]);
        if (i && (i + 1) % 16 == 0) {
            putchar('\n');
        }
    }
    printf("\n");
}
 
/**
 * 利用Key生成S盒
 * the Key-Scheduling Algorithm
 */
static void rc4_ksa(unsigned char *puc_sbox, unsigned char *puc_key, int key_length)
{
    int i = 0;
    int j = 0;
    char tmp[SBOX_LEN] = {0};
 
    for (i = 0; i < SBOX_LEN; i++) {
        puc_sbox[i] = i;
        tmp[i] = puc_key[i % key_length];
    }
 
    for (i = 0; i < SBOX_LEN; i++) {
        j = (j + puc_sbox[i] + tmp[i]) % SBOX_LEN;
        swap_uchar(&puc_sbox[i], &puc_sbox[j]); //交换puc_sbox[i]和puc_sbox[j]
    }
}
 
/**
 * 利用S盒生成密钥流
 * The pseudo-random generation algorithm(PRGA)
 */
static void rc4_prga(unsigned char *puc_sbox, unsigned char *puc_key_stream, unsigned long ul_data_length)
{
    int i = 0;
    int j = 0;
    int t = 0;
    unsigned long k = 0;
 
    for (k = 0; k < ul_data_length; k++) {
        i = (i + 1) % SBOX_LEN;
        j = (j + puc_sbox[i]) % SBOX_LEN;
        swap_uchar(&puc_sbox[i], &puc_sbox[j]);
        t = (puc_sbox[i] + puc_sbox[j]) % SBOX_LEN;
        /* 为了更清晰理解rc4算法流程，此处保存keystream，不直接进行XOR运算 */
        puc_key_stream[k] = puc_sbox[t];
    }
}
 
/* 加解密 */
void rc4_crypt(unsigned char *puc_data, unsigned char *puc_key_stream, unsigned long ul_data_length)
{
    unsigned long i = 0;
 
    /* 把PRGA算法放在加解密函数中可以不需要保存keystream */
    for (i = 0; i < ul_data_length; i++) {
        puc_data[i] ^= puc_key_stream[i];
    }
}
 
int main(int argc, char *argv[])
{
    unsigned char sbox[SBOX_LEN] = {0};
    char key[SBOX_LEN] = {"abcdefghijklmnopqrstuvwxyz"}; //秘钥内容随便定义
    char data[512] = "lsRJ@.0 lvfvr#9527";
    unsigned char puc_keystream[512] = {0};
    unsigned long ul_data_length = strlen(data);
 
    printf("key=%s, length=%d\n\n", key, strlen(key));
    printf("Raw data string:%s\n", data);
    printf("Raw data hex:\n");
    hexdump(data, ul_data_length);
 
    /* 生成S-box */
    rc4_ksa(sbox, (unsigned char *)key, strlen(key));
 
    /* 生成keystream并保存,S-box也会被更改 */
    rc4_prga(sbox, puc_keystream, ul_data_length);
 
    printf("S-box final status:\n");
    hexdump(sbox, sizeof(sbox));
 
    printf("key stream:\n");
    hexdump(puc_keystream, ul_data_length);
 
    /* 加密 */
    rc4_encrypt((unsigned char*)data, puc_keystream, ul_data_length);
 
    printf("cipher hexdump:\n");
    hexdump(data, ul_data_length);
 
    /* 解密 */
    rc4_decrypt((unsigned char*)data, puc_keystream, ul_data_length);
 
    printf("decypt data:%s\n", data);
 
    return 0;
}

运行示例：

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
┌──(shelmean㉿ubuntu)-[~/rc4]
└─$ ./rc4
key=abcdefghijklmnopqrstuvwxyz, length=26
 
Raw data string:lsRJ@.0 lvfvr#9527
Raw data hex:
6C73524A402E30206C76667672233935
3237
S-box final status:
0F6F831DDB7F1C9C918760EB3B2FF7B3
3F49485A942603DEA95F463386711A55
DC6DF03D05975EAA41D94E2DAF135059
09ED42C69847067BCCB75BD7747D0C4D
2B0E844F9A516853527311354C77219E
FD179F02297C18A06A7572BF2CC5A108
E1F8E7A819C0DFA28DFF8FD262D4BAAD
6E3CA34476340B048CA580E5F4B42A20
2232FA153090EECB9B56A600EFB2A7A4
2EF5C1E3AEF93882B0B6B87E376C668E
541F7925144585C8C4963AC9B5B1248A
E4F11E16B9E289E8CD3EEC23D19D694A
BDC28BFED0FCABCA7057F30DEAE901C7
ACE067BB27BE9293E66139F25D120ABC
2831CED3FBD55CCF9995436436C3D681
58DA65DD1B781063D807F66B404B887A
 
key stream:
2393B785D3C35D48248588D0C0159423
1EEA
cipher hexdump:
4FE0E5CF93ED6D6848F3EEA6B236AD16
2CDD
decypt data:lsRJ@.0 lvfvr#9527