糖醋小鸡块的blog
0%

misc趣题(二)

发表于 分类于 Valine：

又做到了一个包含misc与crypto的综合题，在这里记录一下我对这个问题的思考。

MISC.3

题目来源：CISG 2015

题目描述：

1
明文中含有flag这个单词。flag格式为flag{字符串}。

题目：

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
#!/usr/bin/python

from struct import pack
from struct import unpack

state = 0

def rand():
    global state
    state = (state * 1103515425 + 54321) & 0x3fffffff
    return state
    
def srand(seed):
    global state
    state = seed
    
def encrypt(data,key):
    srand(key)
    cipher = ""
    for c in data:
        cipher += pack("i",(ord(c)<<22) + rand())
    return cipher

def decrypt(data,key):
    srand(key)
    plain = ""
    for i in range(0,len(data),4):
        temp = unpack("i",data[i:i+4])[0] - rand()
        plain += chr(temp >> 22)
    return plain

def main():
    f1 = open("plaintext","rb")
    f2 = open("ciphertext","wb")
    data = f1.read()
    from secretfile import secretkey
    data = encrypt(data,secretkey)
    f2.write(data)

if __name__ == "__main__":
    main()

以及一个加密文件ciphertext，由于文件内容较大就不放在这里了。

先梳理一下题目的加密过程：

  • 从secretfile里取出secretkey，作为自己的伪随机数生成器的种子
  • 对于明文文件的每一个字符，将他们的ASCII码左移22位，并加上当前rand()生成的伪随机数，得到密文
  • 将密文用pack函数整合，按顺序写入ciphertext里。

所以，求解题目的突破口在于求解出密钥。而我搜索到的一篇wp讲了一种不错的思路：

CISG2015 MISC.3解析 (geekorz.com)

但是他其中的一句话引发了我的思考：

image-20230913142928566

他说，这个随机数生成算法并不同于普通的LCG，因为他最后一步是按位与运算，而不是模运算，所以就没有采用LCG的思路去求解本题。但是仔细思考就会发现，其实道理是完全一样的：

  • x & 0x3fffffff，表示的是取x的低三十位
  • x mod (0x3fffffff + 1)，表示的也是取x的低三十位

所以，某些按位与运算与模运算其实是等价的！因此我们可以利用下列代码，大大简化求解密钥key的过程：

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
from Crypto.Util.number import*
from struct import pack
from struct import unpack

state = 0

def rand():
    global state
    state = (state * 1103515425 + 54321) & 0x3fffffff
    return state
    
def srand(seed):
    global state
    state = seed
    
def encrypt(data,key):
    srand(key)
    cipher = ""
    for c in data:
        cipher += pack("i",(ord(c)<<22) + rand())
    return cipher

def decrypt(data):
    plain = []
    for i in range(0,len(data),4):
        temp = unpack("i",data[i:i+4])[0]
        plain.append(temp)
    return plain

def main():
    f1 = open("ciphertext","rb")
    data = decrypt(f1.read())
    for j in range(256):
        print("j =",j,":",end = " ")
        key = ((data[0] - (j<<22)) - 54321) * inverse(1103515425,(0x3fffffff + 1))
        print(key,end = "  ")
        srand(key)
        for i in data[0:40]:
            try:
                print(chr((i - rand()) >> 22),end = "")
            except:
                print("",end = "")
        print()

if __name__ == "__main__":
    main()

略微解释一下这段代码：

  • decrypt函数相较于给的附件中的decrypt函数作了简化，仅仅实现了unpack的功能，将密文转化为一个数字列表。
  • main函数用于爆破正确密钥。

如何爆破的呢？我们试想一下第一个密文数字data[0]的生成过程，此处假设第一个明文的ord值为j：

而其中rand()生成的值为：

而j仅有256种取值可能(更贴切的说，其实仅需要从可见字符范围内考虑)，因此我们生成所有可能的256个密钥，并解密前面四十个密文观测效果，看看哪个是真正的密钥，观测可知：

image-20230913145528744

可以看出j为105时，解出的密文看上去是正确的形式，因此我们取该密钥解密出全部内容，就得到了正确的文本：

1
2
...
+0lpfzK92vRhs6zyLUYE20n65i9s9GHFfw04XTb2BqKed1d35nuQX1hD5JRsou3m7dEEKGBIJCxUeAjPDgeixlQrAoZzFAlt541yJoyXxuEMGwaAqTXQlF+7pB/5S4vnZ85Lap2siP8q/jFYp87z7PXHmJ20opxy8yxnBsRPoWEs8glONXf1H+h4kkdTcCg+HfwGXqYrf0jyFBgAAAABJRU5ErkJggg==|flag is hidden in the above data It is a picture and you should base64decode it.

前面是一个很长的base64段，解码得到：

image-20230913145804385

大功告成！

flag：

flag{tHis_1s_YOUR_flaaaaag}

总结一下，本题最重要的一个点，就是发现模运算与按位与运算的等价性，从而能够使用LCG的解法解决题目。