ctfshow 密码挑战(下)

admin 2022年9月14日11:22:00CTF专场ctfshow 密码挑战(下)已关闭评论8 views19398字阅读64分39秒阅读模式

^o^

  1. from Crypto.Util.number import *

  2. from secret import n,o,_,flag

  3. return bytes_to_long(m)^o^pow(2,2**_,n)

  4. #(126176329335043454027341235009057683290541781096785538088437185779950106283534462102786883,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165185658681843519312254372108072512792854040590016772780908271525769845284796145687079308339,1138895128842708275167,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165145471041075065947806083270394708336810934202426175949363009508477208686445248781032485832)

运用费马小定理

因为2**_数有点大运算不出来,我们需要借助一些数学手段来化简

一开始没往分解n那里想,好家伙这个n还是可以分解的,分解出来之后求出phi

那么这个"2**_"就一定能分解成k*phi+t的形式  "_"这个字符不好看,我们换成e

2^{2^{e}}=2^{k*phi+t}\equiv2^{t} mod(n)

显然t=(2**e)%phi,

2**t%n用快速幂就很好求了

  1. from Crypto.Util.number import *

  2. n,o,_,c=(126176329335043454027341235009057683290541781096785538088437185779950106283534462102786883,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165185658681843519312254372108072512792854040590016772780908271525769845284796145687079308339,1138895128842708275167,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165145471041075065947806083270394708336810934202426175949363009508477208686445248781032485832)

  3. ps=[P1,P2,P3,P4,P5,P6,P7,P8,P9,P10]

rsa-rsa-rsa-rsa

  1. from Crypto.Util.number import bytes_to_long

  2. number = bytes_to_long(os.urandom(bits // 8))

  3. return gmpy2.next_prime(number)

  4. p, q = [genPrime(700), genPrime(1400)]

  5. keyA = (p * q, gmpy2.powmod(e, -1, (p - 1) * (q - 1)))

  6. p, q, r = [genPrime(700) for i in range(3)]

  7. keyB = (p * q * r, gmpy2.powmod(e, -1, (p - 1) * (q - 1) * (r - 1)))

  8. p, q = [genPrime(700) for i in range(2)]

  9. keyC = (p * q * r, gmpy2.powmod(e, -1, (p - 1) * (q - 1) * (r - 1)))

  10. p, q = [genPrime(700) for i in range(2)]

  11. keyD = (p * q * q, gmpy2.powmod(e, -1, (p - 1) * (q - 1) * q))

  12. key = [keyA, keyB, keyC, keyD]

  13. print('Pubkey:\n', n, d % (2**1050))

  14. flag = pow(flag, e, n)

  15. print('Final encrypted:\n', flag)

加密代码很好看懂,重点是   d % (2**1050) 是给出了d的低1050位,看到取余就应该想到给出多少低位,看到取余就应该想到给出低位,看到取余就应该想到给出低位!我说三遍,省得我总是记不住! 

给出低位之后,考虑Partial Key Exposure attack,这个攻击中的脚本不是一成不变的,根据n的因子的不同需要提前拟定好要爆破的方程。

下面给出第四组求d的方法(需要跑老久了,这一组k=1028的时候解出来p),其他三组同理

根据  ed=k*phi+1可以给出下面公式

n=pqq

ed=kq(p - 1)(q - 1)+1

ed=kn-kpq-kq^2+kq+1

edq=knq-kn-kq^3+kq^2+q  ……(3)

下面求出四组公钥的p

  1. pub1=1932038554996040104455315883223718472713346303330978743187996729621529739811658796197488223680412961958556887967491813511917170439647307828115472638585061826614468592481442868170090215351305925734264287520730497594994002140743068998862077851863298594873771123822744767803224906340976228342363101074033729879279238569509131400285857667919295999183513229060721575824944210340220184232383953260959482459809500905579066796423460415005468731499877425631734048522986804875919132786153939377820467381744176688418461727816693147502213213443376334599763827118508992087636947292972915017881722657189677917877434729457682857780869117786951

  2. df1=5912397705121717556140784657839641276560016575788920678668312850282756456341071738849340091721631088367775989603962369060157436838599496513280991842470122870570378689158520323429323908937960430964492381345224198651911458858050453721123669314789402584706012298518271648142729102770808241490823703064903677427178678987

  3. pub2=3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591

  4. df2=6868327978266104802989981973163703169084555636189784576185238791210063194494388661448473806872716472633244760268088234379444819398858802986829208689016378717268858566806477769143597241086404105945418733687540225015490422345056492001144261514258758982987176876603622870246393409441550222724784227760607803005148775595

  5. pub3=10917617097027265819941199316245708170664160322239112396992379752685149315630190490833569034344683693982148527246306753579034132187820876052547216920239096359749160292797938505063486556690953030692992535714104625710877777307612335669496734575845403728813048203197554540098183478830776569082345496253038419373074472138418756601605374254337538019930772982193317933908317697869554266829969870439418941090745812562872389999750219688406179614975768418558172158692416388137635116617826776163051924280348502765388774834534253485204220529953203590706632081252443788723009621033253377031581260077729777730562359860834341986687191557500091

  6. df3=710016105956319812070196605372318197237647995205776902826343969564168786127883195056045540440980051252709799006465642410089439983838848338421298134182240503034311901611777832870887544745630013027374872143628363811646853589142393730120315860912598068353846852210199572425834904863374715504479538347687533932269822763

  7. pub4=6258481099173792024819474693106946368509556265824075910806389420555433719530245040141261998807861113767884111671342271029919841711711451328448935904736886474775877276202237359977901024567156613869337571238366773386318181308244237935111072607256271603656248526102492009598490205120638143923415224899689908073058800131284179621374129893525361577639595306070201323091432351719890284142312117565661804884081697597556630696419503309791419750920380224952740990294316717474919958301157249871723798444410218228692985548446454088523506882711893486354157312740234878194977819815946236879045967624220542070450161828690568738574846066444577281

  8. df4=2806980746913087054428141202947110250935818433820162370601349094569030624334740692976405122418159297203918181430168687556227936388861062069029464526241058280610192563178711275063698079728866019927374256044090494931048809359682558905005574381364419252965309956377206006737941726025977314039045950483033199847327597975

  9. def find_p(d0, kbits, e, n):

  10. for k in range(1, e+1):

  11. results = solve_mod([e*d0*X == k*n*X - k*n - k*X^3 + k*X^2 + X], 2^kbits)

  12. for x in results:

  13. p0 = ZZ(x[0])

  14. p = partial_p(p0, n)

  15. n = 1932038554996040104455315883223718472713346303330978743187996729621529739811658796197488223680412961958556887967491813511917170439647307828115472638585061826614468592481442868170090215351305925734264287520730497594994002140743068998862077851863298594873771123822744767803224906340976228342363101074033729879279238569509131400285857667919295999183513229060721575824944210340220184232383953260959482459809500905579066796423460415005468731499877425631734048522986804875919132786153939377820467381744176688418461727816693147502213213443376334599763827118508992087636947292972915017881722657189677917877434729457682857780869117786951

  16. d = 5912397705121717556140784657839641276560016575788920678668312850282756456341071738849340091721631088367775989603962369060157436838599496513280991842470122870570378689158520323429323908937960430964492381345224198651911458858050453721123669314789402584706012298518271648142729102770808241490823703064903677427178678987

  17. print ("lower %d bits (of %d bits) is given" % (kbits, nbits))

  18. p = find_p(d, kbits, e, n)

  19. def find_p(d0, kbits, e, n,nr,r):

  20. for k in range(453, e+1):

  21. results = solve_mod([e*d0*X == k*X*n-k*X*nr-k*n-k*X^2*r+k*X^2+k*nr+k*X*r-k*X+X], 2^kbits)

  22. for x in results:

  23. p0 = ZZ(x[0])

  24. p = partial_p(p0, n)

  25. n = 3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591

  26. d = 6868327978266104802989981973163703169084555636189784576185238791210063194494388661448473806872716472633244760268088234379444819398858802986829208689016378717268858566806477769143597241086404105945418733687540225015490422345056492001144261514258758982987176876603622870246393409441550222724784227760607803005148775595

  27. r = 304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421

  28. nr= 10280851260215661228721812462963362751712222846615159271176460150024460899889060011839049156272187978734750111466693198507334216014735049652210072336103990004734797548185140459346864858092641582238977098760137091308415257893039163570833557699872569238432957187705939647075081298171268840155684240469629342929338154014455920953821984340392691337122078847544315282119393193599870233623910796032620112968699887881053905771

  29. print ("lower %d bits (of %d bits) is given" % (kbits, nbits))

  30. p = find_p(d, kbits, e, n,nr,r)

  31. def find_p(d0, kbits, e, n,nr,r):

  32. for k in range(954, e+1):

  33. results = solve_mod([e*d0*X == k*X*n-k*X*nr-k*n-k*X^2*r+k*X^2+k*nr+k*X*r-k*X+X], 2^kbits)

  34. for x in results:

  35. p0 = ZZ(x[0])

  36. p = partial_p(p0, n)

  37. n = 10917617097027265819941199316245708170664160322239112396992379752685149315630190490833569034344683693982148527246306753579034132187820876052547216920239096359749160292797938505063486556690953030692992535714104625710877777307612335669496734575845403728813048203197554540098183478830776569082345496253038419373074472138418756601605374254337538019930772982193317933908317697869554266829969870439418941090745812562872389999750219688406179614975768418558172158692416388137635116617826776163051924280348502765388774834534253485204220529953203590706632081252443788723009621033253377031581260077729777730562359860834341986687191557500091

  38. d = 710016105956319812070196605372318197237647995205776902826343969564168786127883195056045540440980051252709799006465642410089439983838848338421298134182240503034311901611777832870887544745630013027374872143628363811646853589142393730120315860912598068353846852210199572425834904863374715504479538347687533932269822763

  39. r = 304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421

  40. nr= 35837962510180211518739008508644670008508667561776978160000807897435989769911480223712286499260808430327562390622287416536598634173604649768013260998489914721294637524833887494512686007396277800372765374682627993376125107197072381672013102161175243830211550848334487290501423410007471628165449933315178136849963102436935876274207879116427567865644803603036493064397884335415944564405624233572462190128612652848535681271

  41. print ("lower %d bits (of %d bits) is given" % (kbits, nbits))

  42. p = find_p(d, kbits, e, n,nr,r)

  43. def find_p(d0, kbits, e, n):

  44. for k in range(1, e+1):

  45. results = solve_mod([e*d0*X == k*X*n-k*X^2-k*n+k*X+X], 2^kbits)

  46. for x in results:

  47. p0 = ZZ(x[0])

  48. p = partial_p(p0, n)

  49. n = 6258481099173792024819474693106946368509556265824075910806389420555433719530245040141261998807861113767884111671342271029919841711711451328448935904736886474775877276202237359977901024567156613869337571238366773386318181308244237935111072607256271603656248526102492009598490205120638143923415224899689908073058800131284179621374129893525361577639595306070201323091432351719890284142312117565661804884081697597556630696419503309791419750920380224952740990294316717474919958301157249871723798444410218228692985548446454088523506882711893486354157312740234878194977819815946236879045967624220542070450161828690568738574846066444577281

  50. d = 2806980746913087054428141202947110250935818433820162370601349094569030624334740692976405122418159297203918181430168687556227936388861062069029464526241058280610192563178711275063698079728866019927374256044090494931048809359682558905005574381364419252965309956377206006737941726025977314039045950483033199847327597975

  51. print ("lower %d bits (of %d bits) is given" % (kbits, nbits))

  52. p = find_p(d, kbits, e, n)

经过尝试,我们第一组求出的(n//p)%p=0,也就是符合n=p*q^2的情况,需要额外的处理一下。

exp:

  1. from Crypto.Util.number import *

  2. p4=229782170356713062468972304393709379094316943698419478525981146932427182787492098685170334709792151681685720031899018156464090680098352465417019872712876175440775435102270646688599316590098647561179829270883511

  3. p1=186079707137273465727675663354548663388763576891443804945762882210015522639159070344380918794954577846453340173341959614261104488023331542246865274934338579422558024826431114568051002726599530299533854413652469

  4. p2=84253476920558313940284411534839962364259949303445575587617755576147327229203410142719895961164289376147645554721469805789834633759260461347621987612111401103785636823305071611334925049589472170807910976464643

  5. p3=166570905321608297661831854827833393060362746089021714201716629457191577315158726231346411502629041992795147629736275151823594909118106836548293984236347141516025623306168674772455281310505638221738671396307729

  6. n1=1932038554996040104455315883223718472713346303330978743187996729621529739811658796197488223680412961958556887967491813511917170439647307828115472638585061826614468592481442868170090215351305925734264287520730497594994002140743068998862077851863298594873771123822744767803224906340976228342363101074033729879279238569509131400285857667919295999183513229060721575824944210340220184232383953260959482459809500905579066796423460415005468731499877425631734048522986804875919132786153939377820467381744176688418461727816693147502213213443376334599763827118508992087636947292972915017881722657189677917877434729457682857780869117786951

  7. n2=3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591

  8. n3=10917617097027265819941199316245708170664160322239112396992379752685149315630190490833569034344683693982148527246306753579034132187820876052547216920239096359749160292797938505063486556690953030692992535714104625710877777307612335669496734575845403728813048203197554540098183478830776569082345496253038419373074472138418756601605374254337538019930772982193317933908317697869554266829969870439418941090745812562872389999750219688406179614975768418558172158692416388137635116617826776163051924280348502765388774834534253485204220529953203590706632081252443788723009621033253377031581260077729777730562359860834341986687191557500091

  9. n4=6258481099173792024819474693106946368509556265824075910806389420555433719530245040141261998807861113767884111671342271029919841711711451328448935904736886474775877276202237359977901024567156613869337571238366773386318181308244237935111072607256271603656248526102492009598490205120638143923415224899689908073058800131284179621374129893525361577639595306070201323091432351719890284142312117565661804884081697597556630696419503309791419750920380224952740990294316717474919958301157249871723798444410218228692985548446454088523506882711893486354157312740234878194977819815946236879045967624220542070450161828690568738574846066444577281

  10. c=4863472644674217870502565424693713184000486927536995099651919590240866271469253214344182197334842137507506086858073884082195321114866653889949375924127756080834433032454456087411507323678798402153608823661022078160023141062260191255620270915331691502139415828179122879192294099884444457864136735926806260011876510858736421882145300532909608975279197160825647548849553174913916658119199697996174288038879828745214652265872117421930778762203853307243931789294163101430752597851152391642867666313642265617715322464199460030394197177929755093316075034884004768661209784916266357741690678348488199658622049287166258613947571770322996041

  11. d1=gmpy2.invert(e,p1*(p1-1)*(q1-1))

  12. r=304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421

  13. d2=gmpy2.invert(e,(p2-1)*(q2-1)*(r-1))

  14. d3=gmpy2.invert(e,(p3-1)*(q3-1)*(r-1))

  15. #print(gmpy2.iroot(q4,2))

  16. d4=gmpy2.invert(e,(p4-1)*(q4-1))

EasyBits

搬一下大佬wp,我算法设计能力欠缺,最后一步遍历a是真的不会写,递归好难搞

思路就是分解n然后找到所有可能的a,此处要遍历因子之间所有相乘的可能性

  1. factors= [11, 11, 48449, 59123, 8694766963, 69630045151, 103388070465146659, 444180493923722421083, 30585433443292955619949165033, 1603284485789102527932517130294371239263, 544595079558994543939523656419724930553860455113812380055988020817]

  2. c = 257341678671014174901705941161725480777217699326282679647327740348082868304405278349012885595624093813001761459371505300727815357112995028183296998092408041699940235629702457970518156536007414219436741641

  3. from Crypto.Util.number import *

  4. def convert_to_base(x, base):

  5. res.append(x % base)

  6. def check_base(cur_a, cur_b):

  7. for base_0 in range(2, 10):

  8. for base_1 in range(2, 10):

  9. arr_0 = convert_to_base(cur_a, base_0)

  10. arr_1 = convert_to_base(cur_b, base_1)

  11. if min(arr_0) == 1 and max(arr_0) == base_0 - 1 and min(arr_1) == 1 and max(arr_1) == base_1 - 1:

  12. if (sum(arr_0) + sum(arr_1)) % 8 == 0 and (len(arr_0) == len(arr_1) or len(arr_0) == len(arr_1) + 1):

  13. arr_0 = arr_0[::-1]

  14. arr_1 = arr_1[::-1]

  15. s = ''

  16. for i in range(len(arr_1)):

  17. s += '0' * arr_0[i] + '1' * arr_1[i]

  18. if (len(arr_0) == len(arr_1) + 1):

  19. s += '0' * arr_0[-1]

  20. m = int(s, 2)

  21. if b'flag{' in long_to_bytes(m):

  22. print(long_to_bytes(m))

  23. break

  24. if (cur_pos == len(factors)):

  25. cur_b = c // cur_a

  26. check_base(cur_a, cur_b)

  27. dfs(cur_pos + 1, cur_a * factors[cur_pos])

HardLCG涉及到了新知识,另开一篇博客慢慢学

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年9月14日11:22:00
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  ctfshow 密码挑战(下) http://cn-sec.com/archives/1294423.html