本文主要是介绍[CISCN 2018]sm,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
1.题目
3.解题
4.参考
1.题目
题目链接
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
import hashlib
from random import randint
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 psdef run():choose=getPrime(512)ps=gen512num()print "gen over"bchoose=bin(choose)[2:]r=0bchoose = "0"*(512-len(bchoose))+bchoosefor i in range(512):if bchoose[i]=='1':r=r^ps[i]flag=open("flag","r").read()key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))aes_obj = AES.new(key, AES.MODE_ECB)ef=aes_obj.encrypt(flag).encode("base64")open("r", "w").write(str(r))open("ef","w").write(ef)gg=""for p in ps:gg+=str(p)+"\n"open("ps","w").write(gg)run()
附件:ef、ps、r
2.分析
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
import hashlib
from random import randint
def gen512num():order=[]while len(order)!=512:tmp=randint(1,512)if tmp not in order:order.append(tmp)#产生1~512的序列ps=[]for i in range(512):p=getPrime(512-order[i]+10)#根据order获得一个对应的素数pre=bin(p)[2:][0:(512-order[i])]+"1"#取素数的前512-order[i]位,加1之后就能够明确保证每一位的最后一个1的位置ps.append(int(pre+"0"*(512-len(pre)),2))#剩余位置(512-)补0#加到集合中去return psdef run():choose=getPrime(512)#获取一个512位的随机素数来作为chooseps=gen512num()#得到对应的序列了print "gen over"#完成准备bchoose=bin(choose)[2:]#获取2进制版本数r=0bchoose = "0"*(512-len(bchoose))+bchoose#bchoose前面完全补充0,共512位for i in range(512):if bchoose[i]=='1':r=r^ps[i]#根据choose来确定r是否与ps[i]异或flag=open("flag","r").read()#读取flag信息key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))#choose,哪个随机素数被转化为bytes后又被转化为MD5,又被按照16进制转化为了整数,然后又转化为了bytesaes_obj = AES.new(key, AES.MODE_ECB)#获取aes加密对象ef=aes_obj.encrypt(flag).encode("base64")#ef里储存flagopen("r", "w").write(str(r))open("ef","w").write(ef)#输出efgg=""for p in ps:gg+=str(p)+"\n"open("ps","w").write(gg)#ps是被完全输出
run()
题目把ps全部给了,r是最终异或的结果,那么我们的问题就是根据r和ps把choose求出,然后利用内置的AES加密方式进行解密即可,解密方法有两种,一种是根据代码寻找突破口进行解密,一种是使用sage进行矩阵解密
3.解题
第一种:
我们注意gen512num函数:
order=[]while len(order)!=512:tmp=randint(1,512)if tmp not in order:order.append(tmp)#产生1~512的序列ps=[]for i in range(512):p=getPrime(512-order[i]+10)#根据order获得一个对应的素数pre=bin(p)[2:][0:(512-order[i])]+"1"#取素数的前512-order[i]位,加1之后就能够明确保证每一位的最后一个1的位置ps.append(int(pre+"0"*(512-len(pre)),2))#剩余位置(512-)补0#加到集合中去return ps
所以得到的ps必然是一个末尾0的个数分别是0~511的数组,说明ps中每一个数的最后一个1的位置都不一样
还原choose:
上面这个特性可以帮助顺利我们反推choose,举例来说,假如最后一个值1为1,则它必定是来自最后一个1的位置相同的那个数,我们将目前的数异或上对应的ps数,就能够消除这个数对前面的数的影响了,然后就能够让对choose的求解推进一位
求解代码如下:
f = open("...", 'r')
ps = f.readlines()
psn = []
pos = []
for i in ps:psn.append(int(i))t1 = int(i)t2 = 0while(t1 % 2 == 0):t1 >>= 1t2 += 1pos.append(512 - t2)
r = 6753785483255906709117615805253027649453460653974415214642466102672301763943358839905575042938258141827000621474498066533397472809407687579125519939754658
m = list('0' * 512)
for i in range(511, -1, -1):if ((r >> (511 - i)) % 2 == 1):r ^= psn[pos.index(i + 1)]#找到对应的那个进行异或的位置m[pos.index(i + 1)] = '1'#置为1
choose = int(''.join(m), 2)
然后进行AES求解:
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
import hashlib
from random import randint
import base64key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))f2 = open("...", 'r')
c = f2.read()
c = base64.b64decode(c)
aes = AES.new(key, AES.MODE_ECB)
flag = aes.decrypt(c)
print(flag)#b'flag{shemir_alotof_in_wctf_fun!}'
第二种,使用sage进行求解:
原问题可以看作:
A代表choose,B代表ps中的512个数,C是代表最终给出的r,即异或结果
sage中模2意义的加能够满足异或运算的要求,自己动动笔应该能发现
故我们可以使用以下的方程来求解:
这个问题在sage中是十分易求的
代码如下:
#please run in sagemathfrom Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
import base64ps = open("...",'r').readlines()
c = []
for i in ps:c.append(int(i.strip()))
A=[]
for i in c:A.append([int(x) for x in bin(i)[2:].zfill(512)])
r = 6753785483255906709117615805253027649453460653974415214642466102672301763943358839905575042938258141827000621474498066533397472809407687579125519939754658
B = [int(x) for x in bin(r)[2:].zfill(512)]
A = matrix(GF(2),A)
B = matrix(GF(2),B)
key = B*A.inverse()
li = []
for i in key[0]:li.append(bin(i)[2:])
choose = int(''.join(li), 2)
k=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))
aes=AES.new(k,AES.MODE_ECB)
flag_enc='5eFo3ANg2fu9LRrFktWCJmVvx6RgBFzd0R8GXQ8JD78='flag_enc=base64.b64decode(flag_enc)
flag=aes.decrypt(flag_enc)
print(flag)
4.参考
文章1
文章2
这篇关于[CISCN 2018]sm的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!