NSSCTF_[SWPUCTF 2021 新生赛]crypto2

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

题目

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

题目解析

本题基于RSA加密体系，提供了两个密文：

flag1

和

flag2

这两个密文是由相同的明文

m

和相同的模数

n

但使用了不同的公钥指数

e1

和

e2

加密生成的。 已知参数包括：

flag1 = pow(m, e1, n)

flag2 = pow(m, e2, n)

e1 = 3247473589

e2 = 3698409173

n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313

攻击机制

当使用相同模数

n

但不同公钥指数

e1

和

e2

对同一明文进行加密时，若

e1

和

e2

互质（即

gcd(e1, e2) = 1

），则可以通过扩展欧几里得算法来恢复明文。 根据扩展欧几里得算法，存在整数

s1

和

s2

满足以下等式： e1 × s1 + e2 × s2 = gcd(e1, e2) = 1 因此，我们可以通过以下方式计算明文： m = m^1 = m^(e1×s1 + e2×s2) = (m^e1)^s1 × (m^e2)^s2 = flag1^s1 × flag2^s2 (mod n)

解题步骤

1. 验证 e1 和 e2 是否互质：

gcd(e1, e2) = 1

确认它们互质，可以进行共用模数攻击。 2. 使用扩展欧几里得算法求解系数

s0, s1, s2 = gmpy2.gcdext(e1, e2)

得到：

s1 = 662456538

和

s2 = -583305491

3. 计算明文

m = pow(c1, s1, n) * pow(c2, s2, n) % n

注意：当

s2

为负数时，需计算

c2

模

n

的逆元。 4. 将数字转换为字节：

flag = long_to_bytes(m)

完整代码

from Crypto.Util.number import *
import gmpy2

# 给定参数
c1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
c2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
e1 = 3247473589
e2 = 3698409173
n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313

# 扩展欧几里得算法求系数
s0, s1, s2 = gmpy2.gcdext(e1, e2)
print(f"系数: s1 = {s1}, s2 = {s2}")

# 计算明文
if s1 < 0:
    c1 = gmpy2.invert(c1, n)
    s1 = -s1
if s2 < 0:
    c2 = gmpy2.invert(c2, n)
    s2 = -s2

m = pow(c1, s1, n) * pow(c2, s2, n) % n

# 转换为字节
flag = long_to_bytes(m)
print(flag.decode())

最终答案

最终的flag为： NSSCTF{xxxxx******xxxxx}

总结

共用模数攻击是针对RSA加密系统的一种攻击方法，当相同的明文使用相同的模数但不同的公钥指数加密时，如果这些公钥指数互质，则可以恢复出明文。这种攻击方式突显了在RSA应用中避免重复使用相同模数的重要性。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：SWP import Number decode encode