Problem: [SWPUCTF 2021 新生赛]crypto2
思路
- 由代码可知明文flag用两个公钥分别加密了两次，用共模攻击解密即可
EXP
- 具体攻击代码
from base64 import encode
from gmpy2 import *
from Crypto import*
from Crypto.Util.number import long_to_bytes
n=gmpy2.mpz(input("输入n:"))
E1=gmpy2.mpz(input("请输入公钥1："))
E2=gmpy2.mpz(input("请输入公钥2："))
flag1=gmpy2.mpz(input("请输入密文1："))
flag2=gmpy2.mpz(input("请输入密文2："))
def extgcd(e1,e2):
if (e20):
return (e1,1,0) #返回值e1即为最大公约数，1和0分别为扩展欧几里得算法中的系数
elif e10:
return (e2,0,1) #判断e1是否为0，若为0则返回e2及系数0和1
else:g,x1,y1=extgcd(e2,e1%e2) #递归实现扩展欧几里得算法得出最大公约数
x=y1 #实现x，y的更新
y=x1-(e1//e2)*y1
return(g,x,y)
def isprim1(g):
if(g!=1):
return 1
return 0
g,e1,e2=extgcd(E1,E2)
if(isprim1(g)):
print("E1与E2互质，可以进行下一步")
else:print("E1与E2不互质！！！")
if(e1<0):
e1=-e1
flag1=gmpy2.invert(gmpy2.mpz(flag1),gmpy2.mpz(n))
flag=gmpy2.mul(gmpy2.powmod(flag1,e1,n),gmpy2.powmod(flag2,e2,n)) #powmod=pow(base,exp,mod)实现 (baseexp)%mod
if(e2<0):
e2=-e2
flag2=gmpy2.invert(gmpy2.mpz(flag2),gmpy2.mpz(n))
flag=gmpy2.mul(gmpy2.powmod(flag1,e1,n),gmpy2.powmod(flag2,e2,n)) #powmod=pow(base,exp,mod)实现 (baseexp)%mod
else:
flag=gmpy2.mul(gmpy2.mpz(flag1),gmpy2.mpz(flag2))
flag =gmpy2.mpz(flag)
flag=gmpy2.powmod(flag,gmpy2.mpz(1),gmpy2.mpz(n))
print("解密成功！")
print("flag的整数形式为："+str(flag))
print("flag的字节串形式为："+(str(long_to_bytes(flag))))
总结
- 对该题的考点总结