题目信息

附件中包含一个Python脚本sm.py，3个文本文件。

分析

读完一遍sm.py后，可以确定解题的思路是先由ps与r解出bchoose，再由bchoose按照同样的过程计算出密钥key，最后进行AES解密求出flag。首先看生成r的代码：

1
2
3
4
r=0
for i in range(512):
    if bchoose[i]=='1':
        r=r^ps[i]

即$r=\sum_{i=1}^{512}\textrm{bchoose[i]}\cdot \textrm{ps[i]}$(此处的加法是异或)；虽然生成方式类似背包加密，但是由于ps具有很好的性质，我们不使用破解背包加密的方法来解此题；我们来分析生成ps的gen512num函数：

1
2
3
4
5
6
7
8
9
10
11
12
def gen512num():
    order=[]
    while len(order)!=512:
        tmp=randint(1,512)
        if tmp not in order:
            order.append(tmp)
    ps=[]
    for i in range(512):
        p=getPrime(512-order[i]+10)
        pre=bin(p)[2:][0:(512-order[i])]+"1"
        ps.append(int(pre+"0"*(512-len(pre)),2))
    return ps

order是1,2,…,512的一个随机的排列，对ps[i]:首先生成一个长度为512-order[i]+10的素数，去掉此素数的最后10位，同时在尾部追加一个二进制位1，最后在后面填充0使得长度为512；我们首先考虑生成r的最后1个二进制位，ps中只有1个数最后1位为1，其余数最后1位均为0，那么最后1位为1的数如果没有“加入”异或运算，那么r的最后1位一定为0，否则，一定为1，这样我们通过r的最后1位就可以推断出bchoose的第j位(记order[j]=1)。接下来，$r\oplus (\textrm{bchoose[j]}\cdot \textrm{ps[j]})=\sum_{i\neq j}\textrm{bchoose[i]}\cdot \textrm{ps[i]}$，在{ps[i]| i$\neq$j}中，只有1个数倒数第2位为1，同理，可推断出bchoose的第k位(记order[k]=2)，直到推断出bchoose所有位。

解题

实现的Python脚本如下：

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
from base64 import b64decode
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes

def cal_k():
    with open('ps','r') as f:
        ps=[long(x) for x in f.read().split('\n')[:-1]]
    with open('r','r') as f:
        r=long(f.read())
    pbits=[bin(x).rfind('1')-2 for x in ps]
    bc=['0']*512
    for le in range(512):
        ind=pbits.index(511-le)
        tt=bin(r)[2:].rjust(512,'0')[511-le]
        if tt=='1':
            bc[ind]='1'
            r^=ps[ind]
    return long(''.join(bc),2)

def solve():
    with open('ef','rb') as f:
        ef=b64decode(f.read())
    key=long_to_bytes(int(md5(long_to_bytes(cal_k())).hexdigest(),16))
    aes_obj = AES.new(key, AES.MODE_ECB)
    return aes_obj.decrypt(ef)

if __name__=='__main__':
    print solve()

程序运行结果如下：

1
2
$ python solve.py
flag{shemir_alotof_in_wctf_fun!}