加密原理

RC4 是一种对称加密算法。与其他几种比较常见的流密码不同的是，RC4 不是对明文进行分组处理，而是以字节流的方式依次加密明文中的每一个字节，解密的时候也是依次对密文中的每一个字节进行解密。

RC4 算法的特点是算法简单，运行速度快，而且密钥长度是可变的，可变范围为 1-256Byte（8-2048Bit），在如今技术支持的前提下，当密钥长度为 128Bit 时，暴力搜索密钥就不可行了。所以，RC4 的密钥范围任然可以在今后相当长的时间里抵御暴力搜索密钥的攻击。

RC4加密算法的原理如下：

  1. 密钥调度算法（KSA）：在加/解密之前，需要使用一个密钥（Key）来初始化RC4算法的状态，生成一个有序的256字节的数组（S盒），用0-255装入长度256的S盒，用KSA打乱S盒。
  2. 伪随机数生成算法（PRGA）：然后使用生成的S盒数组，与明文依次进行异或操作（由于RC4是一个流加密算法，因此需要先对明文进行分组，每个明文分组的长度为S盒的长度，以此保证明文和密钥的长度相等）。
  3. 异或完成后即得到密文。

名词解释

密钥流：RC4 算法的关键是根据明文和密钥生成相应的密钥流，密钥流的长度和明文的长度是对应的，也就是说明文的长度是 500 字节，那么密钥流也是 500 字节。当然，加密生成的密文也是 500 字节，因为密文第 i 字节 = 明文第 i 字节 ^ 密钥流第 i 字节；

状态向量 S：长度为 256Byte，S[0],S[1]…S[255]。每个单元都是一个 Byte，算法运行的任何时候，S 都包括 0-255 的 8Bit 的排列组合，只不过值的位置发生了变换；

临时向量 T：长度也为 256Byte，每个单元也是一个 Byte。如果密钥的长度是 256Byte，就直接把密钥的值赋给 T，否则，轮转地将密钥的每个 Byte 赋给 T；

密钥 K：长度为 1-256Byte，注意密钥的长度（keylen）与明文长度、密钥流的长度没有必然关系，通常密钥的长度为 16Byte（128Bit）。

生成代码

KSA

1
2
3
4
5
6
7
def KSA(key):
    S=[i for i in range(256)]
    j=0
    for i in range(256):
        j=(j+S[i]+key[i%len(key)])%256
        S[i],S[j]=S[j],S[i]
    return S

KSA函数接收一个密钥key，首先将S盒按顺序填充为0~255，然后通过多次交换S盒中的元素，以打乱S盒的顺序。在实现中，使用一个索引i指向S盒的当前位置，另一个索引j取值为当前循环次数加上S[i]再加上key[i % len(key)]，在取模256后作为S盒的交换元素的索引。每次交换完元素，更新S盒的当前位置。最后 KSA函数返回打乱后的S盒。

PRGA

1
2
3
4
5
6
7
8
9
def PRGA(S):
    i=0
    j=0
    while True:
        i=(i+1)%256
        j=(j+S[i])%256
        S[i],S[j]=S[j],S[i]
        K=S[(S[i]+S[j])%256]
        yield K

PRGA函数接收一个打乱后的S盒，在循环中不断生成伪随机数流。

yield是Python中的一个关键字，它通常用于生成器函数中。生成器函数每次被调用时返回一个生成器对象，该对象可以用于迭代执行该函数中的代码，并在每次迭代时返回一个值。

yield的作用是将函数定义成一个生成器，它可以在函数中保存函数的内部状态，并且不会让函数的状态消失。在每次迭代中，yield关键字会暂停函数的执行并返回一个值，然后在下一次迭代时从暂停的位置继续执行。

在RC4算法中，yield K语句的作用是将每次PRGA生成的 K 作为一个伪随机数流的输出，并通过 yield 返回给调用者。

在循环中，生成器每轮都会生成一个随机数，此算法可以保证如果达到256次循环，那么S盒的每个元素都至少被交换过一次。

完整代码

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
def KSA(key):
    S=[i for i in range(256)]
    j=0
    for i in range(256):
        j=(j+S[i]+key[i%len(key)])%256
        S[i],S[j]=S[j],S[i]
    return S

def PRGA(S):
    i=0
    j=0
    while True:
        i=(i+1)%256
        j=(j+S[i])%256
        S[i],S[j]=S[j],S[i]
        K=S[(S[i]+S[j])%256]
        yield K

def RC4(key):
    S=KSA(key)
    return PRGA(S)

if __name__=="__main__":

    plain=b"this_is_a_flag_which_is_a_little_long"
    key=b"this_is_key"
    
    #encrypt:
    key_stream=RC4(key)
    c=[]
    for m in plain:
        c.append(m^next(key_stream))
    print(c)

    #decrypt:
    keystream=RC4(key)
    for ct in c:
        print(chr(ct^next(keystream)),end="")

对于使用yield作为生成器的函数，可以使用__iter__()方法返回迭代器对象本身，__next__()方法实现每次迭代时返回下一个值。

在Python 3中，next()函数已经默认使用__next__()方法，因此可以直接使用next()函数来获取迭代器中的下一个值。

加密代码的异或也可以写为m^key_stream.__next__()

总结：RC4函数将密钥作为输入，先使用KSA生成打乱后的S盒，再使用PRGA生成伪随机数流，从而实现RC4加密算法。