[羊城杯 2020]GMC

題目

from Crypto.Util.number import getPrime,bytes_to_long,getRandomNBitInteger from secret import flag from gmpy2 import gcddef gmc(a, p):if pow(a, (p-1)//2, p) == 1:return 1else:return -1def gen_key():[gp,gq] = [getPrime(512) for i in range(2)]gN = gp * gqreturn gN, gq, gpdef gen_x(gq,gp):while True:x = getRandomNBitInteger(512)if gmc(x,gp) ^ gmc(x,gq) == -2:return xdef gen_y(gN):gy_list = []while len(gy_list) != F_LEN:ty = getRandomNBitInteger(768)if gcd(ty,gN) == 1:gy_list.append(ty)return gy_listif __name__ == '__main__':flag = bin(bytes_to_long(flag))[2:]F_LEN = len(flag)N, q, p = gen_key()x = gen_x(q, p)y_list = gen_y(N)ciphertext = []for i in range(F_LEN):tc = pow(y_list[i],2) * pow(x,int(flag[i])) % Nciphertext.append(tc)with open('./output.txt','w') as f:f.write(str(N) + '\n')for i in range(F_LEN):f.write(str(ciphertext[i]) + '\n')

解題

程序如何加密的還是挺容易看出來的，關鍵就是怎么逆過去了。。。

from Crypto.Util.number import * def isqr(x,p):if p==1 or x==1:return 1sgn=1while x%2==0:x=x//2if p%8==3 or p%8==5:sgn=-sgnif x<p:_tmp=pp=xx=_tmpif x%4==3 and p%4==3 :sgn=-sgnreturn sgn*isqr(x%p,p) n,s=0,[] fp=open("output.txt","r") n=int(fp.readline()) while True:try:a=int(fp.readline())s.append(a)except:break assert len(s)+1==304 ans="" for i in s:if(isqr(i,n)==1):ans+='0'else:ans+='1' print(long_to_bytes(int(ans,2)))

參考代碼

運行得到：b'GWHT{876db950c1424a8e49d50cdcc0b3a86e}'

答案

flag{876db950c1424a8e49d50cdcc0b3a86e}

總結

以上是生活随笔為你收集整理的[羊城杯 2020]GMC的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。