1. 题目信息
附件中包含一个Python脚本sm.py，3个文本文件。
2. 分析
读完一遍sm.py后，可以确定解题的思路是先由ps与r解出bchoose，再由bchoose按照同样的过程计算出密钥key，最后进行AES解密求出flag。首先看生成r的代码：
r=0
for i in range(512):
if bchoose[i]=='1':
r=r^ps[i]
即(r=sum_{i=1}^{512} extrm{bchoose[i]}cdot extrm{ps[i]})(此处的加法是异或)；虽然生成方式类似背包加密，但是由于ps具有很好的性质，我们不使用破解背包加密的方法来解此题；我们来分析生成ps的gen512num函数：
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)。接下来，(roplus ( extrm{bchoose[j]}cdot extrm{ps[j]})=sum_{i eq j} extrm{bchoose[i]}cdot extrm{ps[i]})，在{ps[i]| i( eq)j}中，只有1个数倒数第2位为1，同理，可推断出bchoose的第k位(记order[k]=2)，直到推断出bchoose所有位。
3. 解题
实现的Python脚本如下：
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('
')[:-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()
程序运行结果如下：
$ python solve.py
flag{shemir_alotof_in_wctf_fun!}