RSA共模攻击

攻击要求（已知 n、e1、e2、c1、c2）

# 题目内容
from gmpy2 import *
from Crypto.Util.number import *

flag  = '***************'

p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))

n = p*q
e1 = getPrime(32)
e2 = getPrime(32)
print()

flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('e1= ' +str(e1))
print('e2= '+str(e2))
print('n= '+str(n))

#flag1= 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
#flag2= 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
#e1= 3247473589
#e2= 3698409173
#n= 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313

直接根据已知条件进行共模攻击，脚本如下：

注意：libnum 、gmpy2 是第三方库，需要安装，直接命令行安装（pip install libnum,gmpy2）

import libnum
import gmpy2
def exp_def(e1,e2,c1,c2,n):
    s,s1,s2 = gmpy2.gcdext(e1, e2)
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)

n=103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313
e1=3247473589
e2=3698409173
c1=100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
c2=86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075

m=exp_def(e1,e2,c1,c2,n)
print(libnum.n2s(m))
# b'NSSCTF{xxxxx******xxxxx}'

这flag有点怪😥

当有两个以上的e和c时

当有两个以上的e 和c 时，可以通过判断 gcd(e1,e2,e3……,ek) 是否为 1，若为1 则可以拿两个 e 用上面的方法解出来。

否则需要求出满足 e1 x a1 + e2 x a2 + e3 x a3 +……+ ek x ak = 1 中的 a1~ak了，然后再计算

m = c₁^a1 x c₂^a2 x c₃^a3 x ……x c_n^ak ( mod n )

最后得出 明文 m 。