buuctf-RSA1

最近被問到這道題，現在網上的答案可能有點問題，因為大多數看這道題的都是新人，在這里寫一個新的wp。

治多網站制作公司哪家好，找創(chuàng)新互聯建站！從網頁設計、網站建設、微信開發(fā)、APP開發(fā)、響應式網站開發(fā)等網站項目制作，到程序開發(fā)，運營維護。創(chuàng)新互聯建站自2013年創(chuàng)立以來到現在10年的時間，我們擁有了豐富的建站經驗和運維經驗，來保證我們的工作的順利進行。專注于網站建設就選創(chuàng)新互聯建站。
題目：

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)))

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

新聞標題：buuctf-RSA1-創(chuàng)新互聯
網址分享：http://jinyejixie.com/article4/decoie.html

成都網站建設公司_創(chuàng)新互聯，為您提供App開發(fā)、網站建設、云服務器、網站設計、網站維護、網站設計公司

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯