RC4

1、初始化状态向量 S（256 个字节，用来作为密钥流生成种子 1）按照升序给每个字节赋值
2、初始密钥由用户输入，长度任意，如果长度小于 256 字节则进行轮转，直到填满，例如密钥是 12345，则填入的是 12345123451234512345…. 这个轮转过程得到的 256 个字节的向量 T 用来作为密钥流生成种子 2
3、密钥流的生成：假设明文长度 datalen = 1024 个字节则：

1
2
3
4
5
6
7
8
9
10
i=0;
j=0;
while(datalen--){
  i=(i+1) mod 256;
  j=(j+S[i]) mod 256;
  swap(S[i], S[j]);
  t=(S[i] + S[j]) mod 256;
  k=S[t];   //这里的k就是当前生成的密钥流的一位
  data[] = data[]^k;  //可以直接在这里加密，也可以把密钥流保存在数组中，最后运行异或运算
}

例题

hgame-week2 notRC4

题目：

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from hashlib import md5
from secret import flag
assert flag.startswith(b'hgame) and flag.endswith(b')

class Oo0:
    def __init__(self):
        self.O0 = [0] * 256
        self.Ooo = 0
        self.Ooo0 = [0] * 256
        for i in range(256):
            self.O0[i] = i
        self.oO0 = 0

    def OO0(self, oO0):
        l = len(oO0)
        for i in range(256):
            self.Ooo0[i] = oO0[i%l]
        for i in range(256):
            self.oO0 = ( self.oO0 + self.O0[i] + self.Ooo0[i] ) % 256
            self.O0[i], self.O0[self.oO0] = self.O0[self.oO0], self.O0[i]
        self.Ooo = self.oO0 = 0

    def OO0o(self, length):
        O = []
        for _ in range(length):
            self.Ooo = ( self.Ooo + 1 ) % 256
            self.oO0 = ( self.oO0 + self.O0[self.Ooo] ) % 256
            self.O0[self.Ooo], self.O0[self.oO0] = self.O0[self.oO0], self.O0[self.Ooo]
            t = ( self.O0[self.Ooo] + self.O0[self.oO0] ) % 256
            O.append( self.O0[t] )
        print(self.O0)
        return O

def xor(s1, s2):
    return bytes(map( (lambda x: x[0]^x[1]), zip(s1, s2) ))

def enc(msg):
    Oo0oO = Oo0()
    Oo0oO.OO0( md5(msg).digest()[:8] )
    O0O = Oo0oO.OO0o( len(msg) )
    return xor(msg, O0O)

print( enc(flag) )

# [157, 28, 118, 120, 251, 242, 69, 178, 165, 137, 115, 84, 250, 152, 56, 196, 191, 16, 71, 158, 1, 58, 233, 175, 214, 181, 42, 151, 255, 228, 38, 48, 186, 139, 201, 24, 30, 134, 162, 86, 187, 176, 121, 206, 153, 111, 161, 163, 26, 27, 14, 188, 96, 3, 52, 207, 57, 8, 145, 154, 238, 221, 85, 204, 66, 141, 143, 237, 113, 53, 218, 29, 177, 150, 87, 94, 183, 130, 200, 12, 182, 166, 205, 93, 252, 44, 77, 76, 55, 81, 208, 128, 6, 109, 156, 129, 103, 59, 105, 25, 75, 31, 164, 232, 132, 209, 159, 2, 194, 131, 116, 32, 19, 36, 4, 125, 108, 212, 170, 171, 248, 236, 126, 195, 174, 65, 215, 160, 91, 64, 172, 167, 13, 169, 68, 92, 20, 10, 142, 106, 23, 192, 67, 88, 253, 202, 184, 22, 249, 122, 62, 107, 123, 45, 148, 51, 100, 245, 190, 231, 220, 241, 213, 50, 70, 219, 39, 244, 82, 189, 37, 72, 119, 40, 234, 224, 80, 235, 18, 61, 198, 90, 60, 98, 95, 179, 54, 254, 74, 226, 180, 230, 211, 99, 239, 83, 144, 240, 34, 199, 35, 7, 210, 149, 112, 41, 101, 225, 168, 33, 63, 216, 79, 243, 17, 138, 97, 147, 11, 229, 222, 0, 9, 78, 49, 21, 155, 124, 135, 193, 197, 223, 5, 110, 246, 247, 104, 203, 89, 117, 140, 114, 136, 185, 15, 46, 173, 102, 73, 47, 217, 43, 146, 133, 127, 227]
# b'\x14\xe3s,\xcbq\xa8\xd1\x86\x12\xba\x9f\x88\xa9J}\xf5\xd8BF\x93x\x94\x8a\xdc\xdb\xa0\xb9O0SeJ^\xc7\xce\xcf\xe3\x1c\x10s\xe2\xb6\xceA\xfd\xd6\x87\x95W'

writeup：
虽然题目变量名改的乱七八糟的，但是看 OO0o 还是能看出来这是 RC4 加密，OO0o 就是生成 k 的那个过程，最后返回的结果也是 k，O0 就是初始化状态向量 S，在题目的最后把 S 和密文打印了出来
因为 RC4 是异或加密的，明文与密文长度是一致的，密钥的长度也是一致的，flag 最后一个应该是“{”，所以可以通过 “{“ ^ “W” 来得到最后一轮的 k，看一下它在 S 中的位置就得到了 t，又因为 i 表示循环的此时，所以 i 也是已知的
根据 t=(S[i] + S[j]) mod 256; 可以推算出来 j = (t - S[i]) mod 256，这样交换 S[i] 和 S[j] 就把一部分 S 变回上一轮加密的样子了，
根据 j=(j+S[i]) mod 256; 得到上一轮的 j = (j - S[i]) mod 356，同时 i 的值只是减了个 1
这样我们有了 i、j，就能再确定上一轮的 t 的值了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
enc=b'\x14\xe3s,\xcbq\xa8\xd1\x86\x12\xba\x9f\x88\xa9J}\xf5\xd8BF\x93x\x94\x8a\xdc\xdb\xa0\xb9O0SeJ^\xc7\xce\xcf\xe3\x1c\x10s\xe2\xb6\xceA\xfd\xd6\x87\x95W'
s = [157, 28, 118, 120, 251, 242, 69, 178, 165, 137, 115, 84, 250, 152, 56, 196, 191, 16, 71, 158, 1, 58, 233, 175, 214, 181, 42, 151, 255, 228, 38, 48, 186, 139, 201, 24, 30, 134, 162, 86, 187, 176, 121, 206, 153, 111, 161, 163, 26, 27, 14, 188, 96, 3, 52, 207, 57, 8, 145, 154, 238, 221, 85, 204, 66, 141, 143, 237, 113, 53, 218, 29, 177, 150, 87, 94, 183, 130, 200, 12, 182, 166, 205, 93, 252, 44, 77, 76, 55, 81, 208, 128, 6, 109, 156, 129, 103, 59, 105, 25, 75, 31, 164, 232, 132, 209, 159, 2, 194, 131, 116, 32, 19, 36, 4, 125, 108, 212, 170, 171, 248, 236, 126, 195, 174, 65, 215, 160, 91, 64, 172, 167, 13, 169, 68, 92, 20, 10, 142, 106, 23, 192, 67, 88, 253, 202, 184, 22, 249, 122, 62, 107, 123, 45, 148, 51, 100, 245, 190, 231, 220, 241, 213, 50, 70, 219, 39, 244, 82, 189, 37, 72, 119, 40, 234, 224, 80, 235, 18, 61, 198, 90, 60, 98, 95, 179, 54, 254, 74, 226, 180, 230, 211, 99, 239, 83, 144, 240, 34, 199, 35, 7, 210, 149, 112, 41, 101, 225, 168, 33, 63, 216, 79, 243, 17, 138, 97, 147, 11, 229, 222, 0, 9, 78, 49, 21, 155, 124, 135, 193, 197, 223, 5, 110, 246, 247, 104, 203, 89, 117, 140, 114, 136, 185, 15, 46, 173, 102, 73, 47, 217, 43, 146, 133, 127, 227]
t=s.index(ord('}')^ord('W'))  #根据最后一位密钥，确定t
i=50  #根据密文长度确定i
sj = (t-s[i]) % 256  #根据t和s[i]算出s[j]
j=s.index(sj)   #根据s[j]在s中的位置算出j
s[j],s[i] = s[i],s[j]  #交换次序
j = (j-s[i])%256       #算出上一轮的j
i=i-1                  #算出上一轮的i
t = (s[i]+s[j])%256    #算出上一轮的 t
flag = "}"
while(i>0):
    flag += chr(s[t] ^ enc[i-1])   #s[t]就是k与密文异或得到明文
    s[j],s[i] = s[i],s[j]   #交换次序
    j = (j-s[i])%256        #拿到上一次的j
    i=i-1                   #拿到上一次的i
    t = (s[i]+s[j])%256     #拿到上一次的t
print(flag[::-1])    #因为顺序是反着的，所以要交换次序

LFSR