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进行异或得到原文

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

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

KSA（the Key-Scheduling Algorithm)
PRGA(the Pseudo-Random Generation Algorithm)
利用Key生成S盒——The key-scheduling algorithm (KSA)

得到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)

图片来源：https://www.biaodianfu.com/rc4.html

/* 生成密钥流 Keystream */

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];
}

代码实现
#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;
}