目錄

共用素數，低加密指數攻擊，共模攻擊

?dp泄漏：

?公鑰分析：

維納攻擊 e很大

---

題目來源2022HGAME

import re from math import ceil from Crypto.Util.number import getPrime from libnum import s2n from secret import flagflag_parts = list(map(s2n, re.findall(rf".{{,{ceil(len(flag) / 3)}}}", flag)))print("# task1") m = flag_parts[0] e = 65537 p = getPrime(1024) q = getPrime(1024) r = getPrime(1024) n1 = p * q c1 = pow(m, e, n1) n2 = r * q c2 = pow(m, e, n2) print("e =", e) print("n1 =", n1) print("c1 =", c1) print("n2 =", n2) print("c2 =", c2)print("# task2") m = flag_parts[1] e = 7 p = getPrime(1024) q = getPrime(1024) n = p * q c = pow(m, e, n) print("e =", e) print("n =", n) print("c =", c)print("# task3") m = flag_parts[2] p = getPrime(1024) q = getPrime(1024) n = p * q e1 = getPrime(32) e2 = getPrime(32) c1 = pow(m, e1, n) c2 = pow(m, e2, n) print("n =", n) print("e1 =", e1) print("c1 =", c1) print("e2 =", e2) print("c2 =", c2) # task1 e = 65537 n1 = 14611545605107950827581005165327694782823188603151768169731431418361306231114985037775917461433925308054396970809690804073985835376464629860609710292181368600618626590498491850404503443414241455487304448344892337877422465715709154238653505141605904184985311873763495761345722155289457889686019746663293720106874227323699288277794292208957172446523420596391114891559537811029473150123641624108103676516754449492805126642552751278309634846777636042114135990516245907517377320190091400729277307636724890592155256437996566160995456743018225013851937593886086129131351582958811003596445806061492952513851932238563627194553 c1 = 965075803554932988664271816439183802328812013694203741320763105376036912584995031647672348468111310423680858101990670067065306237596121664884353679987689532305437801346923070145524106271337770666947677115752724993307387122132705797012726237073550669419110046308257408484535063515678066777681017211510981429273346928022971149411064556225001287399141306136081722471075032423079692908380267160214143720516748000734987068685104675254411687005690312116824966036851568223828884335112144637268090397158532937141122654075952730052331573980701136378212002956719295192733955673315234274064519957670199895100508623561838510479 n2 = 20937478725109983803079185450449616567464596961348727453817249035110047585580142823551289577145958127121586792878509386085178452171112455890429474457797219202827030884262273061334752493496797935346631509806685589179618367453992749753318273834113016237120686880514110415113673431170488958730203963489455418967544128619234394915820392908422974075932751838012185542968842691824203206517795693893863945100661940988455695923511777306566419373394091907349431686646485516325575494902682337518438042711296437513221448397034813099279203955535025939120139680604495486980765910892438284945450733375156933863150808369796830892363 c2 = 11536506945313747180442473461658912307154460869003392732178457643224057969838224601059836860883718459986003106970375778443725748607085620938787714081321315817144414115589952237492448483438910378865359239575169326116668030463275817609827626048962304593324479546453471881099976644410889657248346038986836461779780183411686260756776711720577053319504691373550107525296560936467435283812493396486678178020292433365898032597027338876045182743492831814175673834198345337514065596396477709839868387265840430322983945906464646824470437783271607499089791869398590557314713094674208261761299894705772513440948139429011425948090 # task2 e = 7 n = 14157878492255346300993349653813018105991884577529909522555551468374307942096214964604172734381913051273745228293930832314483466922529240958994897697475939867025561348042725919663546949015024693952641936481841552751484604123097148071800416608762258562797116583678332832015617217745966495992049762530373531163821979627361200921544223578170718741348242012164115593777700903954409103110092921578821048933346893212805071682235575813724113978341592885957767377587492202740185970828629767501662195356276862585025913615910839679860669917255271734413865211340126544199760628445054131661484184876679626946360753009512634349537 c = 10262871020519116406312674685238364023536657841034751572844570983750295909492149101500869806418603732181350082576447594766587572350246675445508931577670158295558641219582729345581697448231116318080456112516700717984731655900726388185866905989088504004805024490513718243036445638662260558477697146032055765285263446084259814560197549018044099935158351931885157616527235283229066145390964094929007056946332051364474528453970904251050605631514869007890625 # task3 n = 18819509188106230363444813350468162056164434642729404632983082518225388069544777374544142317612858448345344137372222988033366528086236635213756227816610865045924357232188768913642158448603346330462535696121739622702200540344105464126695432011739181531217582949804939555720700457350512898322376591813135311921904580338340203569582681889243452495363849558955947124975293736509426400460083981078846138740050634906824438689712748324336878791622676974341814691041262280604277357889892211717124319329666052810029131172229930723477981468761369516771720250571713027972064974999802168017946274736383148001865929719248159075729 e1 = 2519901323 c1 = 3230779726225544872531441169009307072073754578761888387983403206364548451496736513905460381907928107310030086346589351105809028599650303539607581407627819797944337398601400510560992462455048451326593993595089800150342999021874734748066692962362650540036002073748766509347649818139304363914083879918929873577706323599628031618641793074018304521243460487551364823299685052518852685706687800209505277426869140051056996242882132616256695188870782634310362973153766698286258946896866396670872451803114280846709572779780558482223393759475999103607704510618332253710503857561025613632592682931552228150171423846203875344870 e2 = 3676335737 c2 = 940818595622279161439836719641707846790294650888799822335007385854166736459283129434769062995122371073636785371800857633841379139761091890426137981113087519934854663776695944489430385663011713917022574342380155718317794204988626116362865144125136624722782309455452257758808172415884403909840651554485364309237853885251876941477098008690389600544398998669635962495989736021020715396415375890720335697504837045188626103142204474942751410819466379437091569610294575687793060945525108986660851277475079994466474859114092643797418927645726430175928247476884879817034346652560116597965191204061051401916282814886688467861

經典題型，分別考察了三種RSA攻擊方法.

共用素數，低加密指數攻擊，共模攻擊（兩次n一樣

from math import gcd import gmpy2 from gmpy2 import invert from libnum import n2s, xgcd # task1 n1 n2 共用素數 e = 65537 n1 = 14611545605107950827581005165327694782823188603151768169731431418361306231114985037775917461433925308054396970809690804073985835376464629860609710292181368600618626590498491850404503443414241455487304448344892337877422465715709154238653505141605904184985311873763495761345722155289457889686019746663293720106874227323699288277794292208957172446523420596391114891559537811029473150123641624108103676516754449492805126642552751278309634846777636042114135990516245907517377320190091400729277307636724890592155256437996566160995456743018225013851937593886086129131351582958811003596445806061492952513851932238563627194553 c1 = 965075803554932988664271816439183802328812013694203741320763105376036912584995031647672348468111310423680858101990670067065306237596121664884353679987689532305437801346923070145524106271337770666947677115752724993307387122132705797012726237073550669419110046308257408484535063515678066777681017211510981429273346928022971149411064556225001287399141306136081722471075032423079692908380267160214143720516748000734987068685104675254411687005690312116824966036851568223828884335112144637268090397158532937141122654075952730052331573980701136378212002956719295192733955673315234274064519957670199895100508623561838510479n2 = 20937478725109983803079185450449616567464596961348727453817249035110047585580142823551289577145958127121586792878509386085178452171112455890429474457797219202827030884262273061334752493496797935346631509806685589179618367453992749753318273834113016237120686880514110415113673431170488958730203963489455418967544128619234394915820392908422974075932751838012185542968842691824203206517795693893863945100661940988455695923511777306566419373394091907349431686646485516325575494902682337518438042711296437513221448397034813099279203955535025939120139680604495486980765910892438284945450733375156933863150808369796830892363 c2 = 11536506945313747180442473461658912307154460869003392732178457643224057969838224601059836860883718459986003106970375778443725748607085620938787714081321315817144414115589952237492448483438910378865359239575169326116668030463275817609827626048962304593324479546453471881099976644410889657248346038986836461779780183411686260756776711720577053319504691373550107525296560936467435283812493396486678178020292433365898032597027338876045182743492831814175673834198345337514065596396477709839868387265840430322983945906464646824470437783271607499089791869398590557314713094674208261761299894705772513440948139429011425948090 q = gcd(n1, n2) p = n1 // q r = n2 // q print(n2s(pow(c1, int(invert(e, (p - 1) * (q - 1))), n1)).decode(), end = "") # print(n2s(pow(c2, int(invert(e, (r - 1) * (q - 1))), n2)).decode(), end = "") # task2 低加密指數攻擊 n =14157878492255346300993349653813018105991884577529909522555551468374307942096214964604172734381913051273745228293930832314483466922529240958994897697475939867025561348042725919663546949015024693952641936481841552751484604123097148071800416608762258562797116583678332832015617217745966495992049762530373531163821979627361200921544223578170718741348242012164115593777700903954409103110092921578821048933346893212805071682235575813724113978341592885957767377587492202740185970828629767501662195356276862585025913615910839679860669917255271734413865211340126544199760628445054131661484184876679626946360753009512634349537 e = 7 c = 10262871020519116406312674685238364023536657841034751572844570983750295909492149101500869806418603732181350082576447594766587572350246675445508931577670158295558641219582729345581697448231116318080456112516700717984731655900726388185866905989088504004805024490513718243036445638662260558477697146032055765285263446084259814560197549018044099935158351931885157616527235283229066145390964094929007056946332051364474528453970904251050605631514869007890625 print(n2s(int(gmpy2.iroot(c, e)[0])).decode(), end = "")# task3 共模攻擊 n = 18819509188106230363444813350468162056164434642729404632983082518225388069544777374544142317612858448345344137372222988033366528086236635213756227816610865045924357232188768913642158448603346330462535696121739622702200540344105464126695432011739181531217582949804939555720700457350512898322376591813135311921904580338340203569582681889243452495363849558955947124975293736509426400460083981078846138740050634906824438689712748324336878791622676974341814691041262280604277357889892211717124319329666052810029131172229930723477981468761369516771720250571713027972064974999802168017946274736383148001865929719248159075729e1 = 2519901323 c1 = 3230779726225544872531441169009307072073754578761888387983403206364548451496736513905460381907928107310030086346589351105809028599650303539607581407627819797944337398601400510560992462455048451326593993595089800150342999021874734748066692962362650540036002073748766509347649818139304363914083879918929873577706323599628031618641793074018304521243460487551364823299685052518852685706687800209505277426869140051056996242882132616256695188870782634310362973153766698286258946896866396670872451803114280846709572779780558482223393759475999103607704510618332253710503857561025613632592682931552228150171423846203875344870 e2 = 3676335737 c2 = 940818595622279161439836719641707846790294650888799822335007385854166736459283129434769062995122371073636785371800857633841379139761091890426137981113087519934854663776695944489430385663011713917022574342380155718317794204988626116362865144125136624722782309455452257758808172415884403909840651554485364309237853885251876941477098008690389600544398998669635962495989736021020715396415375890720335697504837045188626103142204474942751410819466379437091569610294575687793060945525108986660851277475079994466474859114092643797418927645726430175928247476884879817034346652560116597965191204061051401916282814886688467861s1, s2, _ = xgcd(e1, e2) if s1 < 0:s1 = -s1c1 = int(invert(c1, n)) if s2 < 0:s2 = -s2c2 = int(invert(c2, n)) print(n2s(pow(c1, s1, n) * pow(c2, s2, n) % n).decode())

得到最后

hgame{RsA@hAS!a&VArIETYof.AttacK^mEThodS^whAT:other!AttACK|METHOdS~do@you_KNOW}

?dp泄漏：

一直e? n c 但是n特別大，而且已知dp

import gmpy2def getd(n,e,dp):for i in range(1, e):if ((e * dp -1 ) % i == 0):p = (e * dp - 1) // i + 1if (n % p != 0):continueq = n // pphin = (p - 1) * (q - 1)d = gmpy2.invert(e, phin)return de = 65537 n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113 dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657 c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751 d = getd(n,e,dp) m = pow(c,d,n) flag = bytes.fromhex(hex(m)[2:]) print(flag)

?公鑰分析：

公鑰解析：

分析得到n 和 e?，下面就是常規操作

from Crypt with open('./pub.key','r') as f:key = RSA.import_key(f.read()) e = key.e n = key.n print('e = %d\nn = %d'%(e,n))# p q e 得 d p = 285960468890451637935629440372639283459 q = 304008741604601924494328155975272418463 phi = (p-1)*(q-1) d = inverse(e,phi) print('d =',d)key = rsa.PrivateKey(n,e,d,q,p) with open("flag.enc.txt","rb") as f: f = f.read()print(rsa.decrypt(f,key))

維納攻擊 e很大

import gmpy2 import hashlibdef transform(x, y): # 使用輾轉相處將分數 x/y 轉為連分數的形式res = []while y:res.append(x // y)x, y = y, x % yreturn resdef continued_fraction(sub_res):numerator, denominator = 1, 0for i in sub_res[::-1]: # 從sublist的后面往前循環denominator, numerator = numerator, i * numerator + denominatorreturn denominator, numerator # 得到漸進分數的分母和分子，并返回# 求解每個漸進分數 def sub_fraction(x, y):res = transform(x, y)res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res))))) # 將連分數的結果逐一截取以求漸進分數return resdef get_pq(a, b, c): # 由p+q和pq的值通過維達定理來求解p和qpar = gmpy2.isqrt(b * b - 4 * a * c) # 由上述可得，開根號一定是整數，因為有解x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)return x1, x2def wienerAttack(e, n):for (d, k) in sub_fraction(e, n): # 用一個for循環來注意試探e/n的連續函數的漸進分數，直到找到一個滿足條件的漸進分數if k == 0: # 可能會出現連分數的第一個為0的情況，排除continueif (e * d - 1) % k != 0: # ed=1 (mod φ(n)) 因此如果找到了d的話，(ed-1)會整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)continuephi = (e * d - 1) // k # 這個結果就是 φ(n)px, qy = get_pq(1, n - phi + 1, n)if px * qy == n:p, q = abs(int(px)), abs(int(qy)) # 可能會得到兩個負數，負負得正未嘗不會出現d = gmpy2.invert(e, (p - 1) * (q - 1)) # 求ed=1 (mod φ(n))的結果，也就是e關于 φ(n)的乘法逆元dreturn dprint("該方法不適用")n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471 e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085 d = wienerAttack(e, n) print("d=", d)

費馬定理：

同p?

兩輪加密 共用同一個p ，所以用gcd()算法求最大公約數可以得到q值

給了三組加密的參數和明密文，其中題目很明確地能告訴你這三組的明文都是一樣的，并且e都取了一個較小的數字

import gmpy2 import libnumdef CRT(data):sum = 0m = 1for n in data:m = m*n[0]for n,c in data:m1 = m/nmr = gmpy2.invert(m1,n)sum = sum+mr*m1*creturn sum%mN1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5) c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5) N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5) c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5) N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5) c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5) e = 3n = [N1,N2,N3] c = [c1,c2,c3] data = zip(n,c) m_e = CRT(data) m = gmpy2.iroot(m_e,e)[0] print libnum.n2s(m)

總結

以上是生活随笔為你收集整理的crypto-RSA的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。