背景 #

RC4加密算法 由 RSA Security 的 Ron Rivest 于 1987 年设计，为密钥长度可变的流加密算法。

该算法一开始作为商业秘密存在，但在1994年被逆向并公开，因为 RSA Security 从来就没有正式发布过这个算法，所以也被叫做ARC4（Alleged RC4-所谓的RC4）。

RC4算法的具有实现相对简单，运行速度快，支持变长密钥，不需要填充，对数据长度没有限制等特点，曾广泛应用于 SSL/TLS 协议和 WEP/WPA 协议，现已证实不安全不建议使用。

流加密（Stream Cipher）是一种对称加密算法。

它以字节（Byte）或比特（Bit）为单位连续加密数据，通过生成一个与明文等长的密钥流（Keystream），然后将明文和密钥流进行按位或按字节的异或（XOR）操作，得到密文。由于 XOR 具有可逆性，解密时使用相同的密钥流即可恢复原文。

算法介绍 #

原理 #

RC4算法的原理基于伪随机数流和异或运算。

具体来说，它首先需要一个密钥K，密钥K的长度可以是5到256字节不等。通过密钥编排算法（KSA, Key Scheduling Algorithm）对密钥进行处理，生成 S 盒数组（为0-255的一个全排列，即 0 到 255 的某种打乱顺序），用于增加生成密钥流的非线性、不可预测性。

然后，通过生成伪随机数流（Keystream）并将伪随机数流与明文进行异或运算，从而得到密文（这个过程中 S 盒数组会不断被修改）。解密过程则是将密文与相同的伪随机数流进行异或运算，以恢复出明文。

实现 #

算法主要分为以下2个步骤：

• Key-scheduling algorithm(KSA)：初始化S盒数组
• Pseudo-random generation algorithm (PRGA)：生成伪随机数流

KSA #

首先，S 盒数组首先初始化为恒等排列identity permutation.

for i from 0 to 255
    S[i] := i
endfor

然后，使用密钥 K 对 S 盒进行256轮迭代的重新排列

j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

经过这一步，S 盒变成了密钥相关的一个0-255的全排列，不同密钥生成的S 盒不同。

PRGA #

生成伪随机数流。

每次加密时通过交换 S[i] 和 S[j] 使得 S 盒在加密过程中不断变化。每次从 S 盒中取出的密钥流字节 K = S[(S[i] + S[j]) % 256] （0-255的一个数）是不可预测的。

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    t := (S[i] + S[j]) mod 256
    K := S[t]
    output K
endwhile

持续输出不可预测的介于0-255数（字节）构成伪随机数流 K[i]，和明文的字节逐一异或可得密文。

题目 #

TODO