buuctf-RSA1
最近被问到这道题，现在网上的答案可能有点问题，因为大多数看这道题的都是新人，在这里写一个新的wp。
治多网站制作公司哪家好，找
创新互联建站！从网页设计、网站建设、微信开发、APP开发、
响应式网站开发等网站项目制作，到程序开发，运营维护。
创新互联建站自2013年创立以来到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选
创新互联建站。
题目：
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
网上答案基本都是同一种形式，核心代码为：m = (((m1-m2)*I)%p)*q+m2。其实推导是没问题的，但是真正起作用的只有m2，因为m1 = m2，所以后面的推到没有任何意义。
m1、m2或者说mp、mq就是m。
wp：
根据费马小定理：
RSA解密原理：
根据上面对于dp的定义：
所以我们可以得到结论：
from Crypto.Util.number import *
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
m = pow(c, dp, p)
print(long_to_bytes(m))
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
m = pow(c, dq, q)
print(long_to_bytes(m))
以上是wp。
推广到一般情况：
如果m >p 或者 m >q的情况又如何呢？这里自己写了一道差不多的题目，m满足上述情况。
task.py:
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
e = getPrime(256)
print(f"p = %d" %p)
print(f"q = %d" %q)
print(f"e = %d" %e)
flag = b'Hello_world_I_am_coming_soon_Please_Waiting_for_me_Thank_you_very_Much!'
d = inverse(e, (p - 1) * (q - 1))
dp = d % (p - 1)
dq = d % (q - 1)
print(f"dp = %d" %dp)
print(f"dq = %d" %dq)
m = bytes_to_long(flag)
n = p * q
c = pow(m, e, n)
print(f"c = %d" %c)
'''
p = 6926931481661163158206322888609703633942281936041380098286251687188506967049414186037659658699187264906821810864635760898979690990756966551278021578998291
q = 12998690832506339440015053745748265344656526216265161654959849049366323002124065092154594716191578843135977811678682838871858697526858995984329380419980913
e = 71128804286988599007039290915038713271044413888167730003577897256139934935941
dp = 6148889404402536590508011446935790843614514839697585326158290024496841220326631544116014497689044476534601498480223872263477602191884044930126752836047231
dq = 9493121201048858715333174956142964789148065600348765586344609365888884217574018356225202124154002902916927219527185254432280397558121173773344086749082285
c = 78375263660593211120584078796453000342814240208394759659717637470351553783389111880446991272503062126743438797053252454888827540106185629197886465642880244388047960613996334135707469056334135130788403395848687900303886160920202526479321695441298525541071076842525224671835263271188257203429419770213288719223
'''
根据上述理论：
这里就可以用中国剩余定理(CRT)来解答了。
简单来说，如果除数互相互素，我们知道除数的集合及其余数的集合，那我们可以利用中国剩余定理来求出被除数。这里我们知道余数的集合是{mp，mq}，除数的集合是{p, q}，被除数就是m。
exp:
from Crypto.Util.number import *
from gmpy2 import *
#中国剩余定理CRT
#aList是余数，mList是n的集合。
def CRT(aList, mList):
M = 1
for i in mList:
M = M * i #计算M = ∏ mi
#print(M)
x = 0
for i in range(len(mList)):
Mi = M // mList[i] #计算Mi
Mi_inverse = invert(Mi, mList[i]) #计算Mi的逆元
x += aList[i] * Mi * Mi_inverse #构造x各项
x = x % M
return x
p = 6926931481661163158206322888609703633942281936041380098286251687188506967049414186037659658699187264906821810864635760898979690990756966551278021578998291
q = 12998690832506339440015053745748265344656526216265161654959849049366323002124065092154594716191578843135977811678682838871858697526858995984329380419980913
e = 71128804286988599007039290915038713271044413888167730003577897256139934935941
dp = 6148889404402536590508011446935790843614514839697585326158290024496841220326631544116014497689044476534601498480223872263477602191884044930126752836047231
dq = 9493121201048858715333174956142964789148065600348765586344609365888884217574018356225202124154002902916927219527185254432280397558121173773344086749082285
c = 78375263660593211120584078796453000342814240208394759659717637470351553783389111880446991272503062126743438797053252454888827540106185629197886465642880244388047960613996334135707469056334135130788403395848687900303886160920202526479321695441298525541071076842525224671835263271188257203429419770213288719223
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
print(long_to_bytes(m1))
print(long_to_bytes(m2))
print("=======================================")
m = CRT([m1, m2], [p, q])
test = long_to_bytes(m)
print(test)
d = inverse(e, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, p * q)))
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
名称栏目：buuctf-RSA1-创新互联
本文地址：
http://cdkjz.cn/article/decoie.html
