^o^
from Crypto.Util.number import *
from secret import n,o,_,flag
return bytes_to_long(m)^o^pow(2,2**_,n)
#(126176329335043454027341235009057683290541781096785538088437185779950106283534462102786883,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165185658681843519312254372108072512792854040590016772780908271525769845284796145687079308339,1138895128842708275167,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165145471041075065947806083270394708336810934202426175949363009508477208686445248781032485832)
运用费马小定理
因为2**_数有点大运算不出来，我们需要借助一些数学手段来化简
一开始没往分解n那里想，好家伙这个n还是可以分解的，分解出来之后求出phi
那么这个"2**_"就一定能分解成k*phi+t的形式 "_"这个字符不好看，我们换成e
显然t=(2**e)%phi,
2**t%n用快速幂就很好求了
from Crypto.Util.number import *
n,o,_,c=(126176329335043454027341235009057683290541781096785538088437185779950106283534462102786883,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165185658681843519312254372108072512792854040590016772780908271525769845284796145687079308339,1138895128842708275167,22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165145471041075065947806083270394708336810934202426175949363009508477208686445248781032485832)
ps=[P1,P2,P3,P4,P5,P6,P7,P8,P9,P10]
rsa-rsa-rsa-rsa
from Crypto.Util.number import bytes_to_long
number = bytes_to_long(os.urandom(bits // 8))
return gmpy2.next_prime(number)
p, q = [genPrime(700), genPrime(1400)]
keyA = (p * q, gmpy2.powmod(e, -1, (p - 1) * (q - 1)))
p, q, r = [genPrime(700) for i in range(3)]
keyB = (p * q * r, gmpy2.powmod(e, -1, (p - 1) * (q - 1) * (r - 1)))
p, q = [genPrime(700) for i in range(2)]
keyC = (p * q * r, gmpy2.powmod(e, -1, (p - 1) * (q - 1) * (r - 1)))
p, q = [genPrime(700) for i in range(2)]
keyD = (p * q * q, gmpy2.powmod(e, -1, (p - 1) * (q - 1) * q))
key = [keyA, keyB, keyC, keyD]
print('Pubkey:\n', n, d % (2**1050))
flag = pow(flag, e, n)
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
pub1=1932038554996040104455315883223718472713346303330978743187996729621529739811658796197488223680412961958556887967491813511917170439647307828115472638585061826614468592481442868170090215351305925734264287520730497594994002140743068998862077851863298594873771123822744767803224906340976228342363101074033729879279238569509131400285857667919295999183513229060721575824944210340220184232383953260959482459809500905579066796423460415005468731499877425631734048522986804875919132786153939377820467381744176688418461727816693147502213213443376334599763827118508992087636947292972915017881722657189677917877434729457682857780869117786951
df1=5912397705121717556140784657839641276560016575788920678668312850282756456341071738849340091721631088367775989603962369060157436838599496513280991842470122870570378689158520323429323908937960430964492381345224198651911458858050453721123669314789402584706012298518271648142729102770808241490823703064903677427178678987
pub2=3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591
df2=6868327978266104802989981973163703169084555636189784576185238791210063194494388661448473806872716472633244760268088234379444819398858802986829208689016378717268858566806477769143597241086404105945418733687540225015490422345056492001144261514258758982987176876603622870246393409441550222724784227760607803005148775595
pub3=10917617097027265819941199316245708170664160322239112396992379752685149315630190490833569034344683693982148527246306753579034132187820876052547216920239096359749160292797938505063486556690953030692992535714104625710877777307612335669496734575845403728813048203197554540098183478830776569082345496253038419373074472138418756601605374254337538019930772982193317933908317697869554266829969870439418941090745812562872389999750219688406179614975768418558172158692416388137635116617826776163051924280348502765388774834534253485204220529953203590706632081252443788723009621033253377031581260077729777730562359860834341986687191557500091
df3=710016105956319812070196605372318197237647995205776902826343969564168786127883195056045540440980051252709799006465642410089439983838848338421298134182240503034311901611777832870887544745630013027374872143628363811646853589142393730120315860912598068353846852210199572425834904863374715504479538347687533932269822763
pub4=6258481099173792024819474693106946368509556265824075910806389420555433719530245040141261998807861113767884111671342271029919841711711451328448935904736886474775877276202237359977901024567156613869337571238366773386318181308244237935111072607256271603656248526102492009598490205120638143923415224899689908073058800131284179621374129893525361577639595306070201323091432351719890284142312117565661804884081697597556630696419503309791419750920380224952740990294316717474919958301157249871723798444410218228692985548446454088523506882711893486354157312740234878194977819815946236879045967624220542070450161828690568738574846066444577281
df4=2806980746913087054428141202947110250935818433820162370601349094569030624334740692976405122418159297203918181430168687556227936388861062069029464526241058280610192563178711275063698079728866019927374256044090494931048809359682558905005574381364419252965309956377206006737941726025977314039045950483033199847327597975
for k in range(1, e+1):
results = solve_mod([e*d0*X == k*n*X - k*n - k*X^3 + k*X^2 + X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, n)
n = 1932038554996040104455315883223718472713346303330978743187996729621529739811658796197488223680412961958556887967491813511917170439647307828115472638585061826614468592481442868170090215351305925734264287520730497594994002140743068998862077851863298594873771123822744767803224906340976228342363101074033729879279238569509131400285857667919295999183513229060721575824944210340220184232383953260959482459809500905579066796423460415005468731499877425631734048522986804875919132786153939377820467381744176688418461727816693147502213213443376334599763827118508992087636947292972915017881722657189677917877434729457682857780869117786951
d = 5912397705121717556140784657839641276560016575788920678668312850282756456341071738849340091721631088367775989603962369060157436838599496513280991842470122870570378689158520323429323908937960430964492381345224198651911458858050453721123669314789402584706012298518271648142729102770808241490823703064903677427178678987
print ("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = find_p(d, kbits, e, n)
def find_p(d0, kbits, e, n,nr,r):
for k in range(453, e+1):
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)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, n)
n = 3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591
d = 6868327978266104802989981973163703169084555636189784576185238791210063194494388661448473806872716472633244760268088234379444819398858802986829208689016378717268858566806477769143597241086404105945418733687540225015490422345056492001144261514258758982987176876603622870246393409441550222724784227760607803005148775595
r = 304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421
nr= 10280851260215661228721812462963362751712222846615159271176460150024460899889060011839049156272187978734750111466693198507334216014735049652210072336103990004734797548185140459346864858092641582238977098760137091308415257893039163570833557699872569238432957187705939647075081298171268840155684240469629342929338154014455920953821984340392691337122078847544315282119393193599870233623910796032620112968699887881053905771
print ("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = find_p(d, kbits, e, n,nr,r)
def find_p(d0, kbits, e, n,nr,r):
for k in range(954, e+1):
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)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, n)
n = 10917617097027265819941199316245708170664160322239112396992379752685149315630190490833569034344683693982148527246306753579034132187820876052547216920239096359749160292797938505063486556690953030692992535714104625710877777307612335669496734575845403728813048203197554540098183478830776569082345496253038419373074472138418756601605374254337538019930772982193317933908317697869554266829969870439418941090745812562872389999750219688406179614975768418558172158692416388137635116617826776163051924280348502765388774834534253485204220529953203590706632081252443788723009621033253377031581260077729777730562359860834341986687191557500091
d = 710016105956319812070196605372318197237647995205776902826343969564168786127883195056045540440980051252709799006465642410089439983838848338421298134182240503034311901611777832870887544745630013027374872143628363811646853589142393730120315860912598068353846852210199572425834904863374715504479538347687533932269822763
r = 304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421
nr= 35837962510180211518739008508644670008508667561776978160000807897435989769911480223712286499260808430327562390622287416536598634173604649768013260998489914721294637524833887494512686007396277800372765374682627993376125107197072381672013102161175243830211550848334487290501423410007471628165449933315178136849963102436935876274207879116427567865644803603036493064397884335415944564405624233572462190128612652848535681271
print ("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = find_p(d, kbits, e, n,nr,r)
def find_p(d0, kbits, e, n):
for k in range(1, e+1):
results = solve_mod([e*d0*X == k*X*n-k*X^2-k*n+k*X+X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, n)
n = 6258481099173792024819474693106946368509556265824075910806389420555433719530245040141261998807861113767884111671342271029919841711711451328448935904736886474775877276202237359977901024567156613869337571238366773386318181308244237935111072607256271603656248526102492009598490205120638143923415224899689908073058800131284179621374129893525361577639595306070201323091432351719890284142312117565661804884081697597556630696419503309791419750920380224952740990294316717474919958301157249871723798444410218228692985548446454088523506882711893486354157312740234878194977819815946236879045967624220542070450161828690568738574846066444577281
d = 2806980746913087054428141202947110250935818433820162370601349094569030624334740692976405122418159297203918181430168687556227936388861062069029464526241058280610192563178711275063698079728866019927374256044090494931048809359682558905005574381364419252965309956377206006737941726025977314039045950483033199847327597975
print ("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = find_p(d, kbits, e, n)
经过尝试，我们第一组求出的(n//p)%p=0，也就是符合n=p*q^2的情况，需要额外的处理一下。
exp：
from Crypto.Util.number import *
p4=229782170356713062468972304393709379094316943698419478525981146932427182787492098685170334709792151681685720031899018156464090680098352465417019872712876175440775435102270646688599316590098647561179829270883511
p1=186079707137273465727675663354548663388763576891443804945762882210015522639159070344380918794954577846453340173341959614261104488023331542246865274934338579422558024826431114568051002726599530299533854413652469
p2=84253476920558313940284411534839962364259949303445575587617755576147327229203410142719895961164289376147645554721469805789834633759260461347621987612111401103785636823305071611334925049589472170807910976464643
p3=166570905321608297661831854827833393060362746089021714201716629457191577315158726231346411502629041992795147629736275151823594909118106836548293984236347141516025623306168674772455281310505638221738671396307729
n1=1932038554996040104455315883223718472713346303330978743187996729621529739811658796197488223680412961958556887967491813511917170439647307828115472638585061826614468592481442868170090215351305925734264287520730497594994002140743068998862077851863298594873771123822744767803224906340976228342363101074033729879279238569509131400285857667919295999183513229060721575824944210340220184232383953260959482459809500905579066796423460415005468731499877425631734048522986804875919132786153939377820467381744176688418461727816693147502213213443376334599763827118508992087636947292972915017881722657189677917877434729457682857780869117786951
n2=3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591
n3=10917617097027265819941199316245708170664160322239112396992379752685149315630190490833569034344683693982148527246306753579034132187820876052547216920239096359749160292797938505063486556690953030692992535714104625710877777307612335669496734575845403728813048203197554540098183478830776569082345496253038419373074472138418756601605374254337538019930772982193317933908317697869554266829969870439418941090745812562872389999750219688406179614975768418558172158692416388137635116617826776163051924280348502765388774834534253485204220529953203590706632081252443788723009621033253377031581260077729777730562359860834341986687191557500091
n4=6258481099173792024819474693106946368509556265824075910806389420555433719530245040141261998807861113767884111671342271029919841711711451328448935904736886474775877276202237359977901024567156613869337571238366773386318181308244237935111072607256271603656248526102492009598490205120638143923415224899689908073058800131284179621374129893525361577639595306070201323091432351719890284142312117565661804884081697597556630696419503309791419750920380224952740990294316717474919958301157249871723798444410218228692985548446454088523506882711893486354157312740234878194977819815946236879045967624220542070450161828690568738574846066444577281
c=4863472644674217870502565424693713184000486927536995099651919590240866271469253214344182197334842137507506086858073884082195321114866653889949375924127756080834433032454456087411507323678798402153608823661022078160023141062260191255620270915331691502139415828179122879192294099884444457864136735926806260011876510858736421882145300532909608975279197160825647548849553174913916658119199697996174288038879828745214652265872117421930778762203853307243931789294163101430752597851152391642867666313642265617715322464199460030394197177929755093316075034884004768661209784916266357741690678348488199658622049287166258613947571770322996041
d1=gmpy2.invert(e,p1*(p1-1)*(q1-1))
r=304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421
d2=gmpy2.invert(e,(p2-1)*(q2-1)*(r-1))
d3=gmpy2.invert(e,(p3-1)*(q3-1)*(r-1))
#print(gmpy2.iroot(q4,2))
d4=gmpy2.invert(e,(p4-1)*(q4-1))
EasyBits
搬一下大佬wp，我算法设计能力欠缺，最后一步遍历a是真的不会写，递归好难搞
思路就是分解n然后找到所有可能的a，此处要遍历因子之间所有相乘的可能性
factors= [11, 11, 48449, 59123, 8694766963, 69630045151, 103388070465146659, 444180493923722421083, 30585433443292955619949165033, 1603284485789102527932517130294371239263, 544595079558994543939523656419724930553860455113812380055988020817]
c = 257341678671014174901705941161725480777217699326282679647327740348082868304405278349012885595624093813001761459371505300727815357112995028183296998092408041699940235629702457970518156536007414219436741641
from Crypto.Util.number import *
def convert_to_base(x, base):
res.append(x % base)
def check_base(cur_a, cur_b):
for base_0 in range(2, 10):
for base_1 in range(2, 10):
arr_0 = convert_to_base(cur_a, base_0)
arr_1 = convert_to_base(cur_b, base_1)
if min(arr_0) == 1 and max(arr_0) == base_0 - 1 and min(arr_1) == 1 and max(arr_1) == base_1 - 1:
if (sum(arr_0) + sum(arr_1)) % 8 == 0 and (len(arr_0) == len(arr_1) or len(arr_0) == len(arr_1) + 1):
arr_0 = arr_0[::-1]
arr_1 = arr_1[::-1]
s = ''
for i in range(len(arr_1)):
s += '0' * arr_0[i] + '1' * arr_1[i]
if (len(arr_0) == len(arr_1) + 1):
s += '0' * arr_0[-1]
m = int(s, 2)
if b'flag{' in long_to_bytes(m):
print(long_to_bytes(m))
break
if (cur_pos == len(factors)):
cur_b = c // cur_a
check_base(cur_a, cur_b)
dfs(cur_pos + 1, cur_a * factors[cur_pos])
HardLCG涉及到了新知识，另开一篇博客慢慢学
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论