卷王杯-部分Crypto-wp 密码签到
密⽂
Y3NldHRfZl9jc2FyaF95b3Nwd2l0JTdCbW9qcCF1bCU3RA==
考点
base64
URL编码
栅栏密码
解密
base64
URL解码
栅栏密码爆破
真·简单·不卷·现代密码签到题⽬
from Crypto .Util .number import bytes_to_long
from secrets import p ,q ,r ,s ,t ,flag
n = p * q * r * s * t
e = 2
m = bytes_to_long (os .urandom (500) + flag )
c = pow (m ,e ,n )
print (p ,q ,r ,s ,t ,sep ='\n')
print (c )
'''
145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
'''考点rabin？有限域开⽅？
CRT（中国剩余定理）
分析1. e = 2⾸先想到的就是rabin攻击了，但是公钥n是由五个素数组成，所以不是⼀般的rabin；2. n = p * q * r * s * t 这么多参数，再加上⼀般的rabin解出来都有4个结果（虽然咱⽤的是有限域开⽅），那⽤⼀⽤CRT不过分吧； 3. 在模（）的条件下，对进⾏有限域开⽅，这样就有五个结果，再⽤中国剩余定理求出；
4. 实际情况中，对步骤3得出来的结果可能并⾮的结果，还有可能是（原理我也不知道，做题的时候发现做 不出来，然后去尝试试出来的）；
5. 1个素数对应2种结果，5个素数就种结果，分别CRT看看哪⾥有。
脚本感觉脚本写得丑爆了
p q ,r ,s ,t c m m mod p p −(m mod p )25flag
from Crypto.Util.number import*
from gmpy2 import*
dular import*
sidue_ntheory import nthroot_mod
e =2
p =14533236770094430374754891216011393919807805143602947796034896831591395666414369334722670260043860869393376813457528928 62832678107231378959031538290018262234464777998954932654225623489170122167900773957958612382573570351526878336390854157638 50743538206986781418939737511715957738982536382066693822159860701263
q =11666045825306760804406552331054723333773058390213375609547333939005773851070744790697118857721727486104737940401414017 81655696044044688977128468761084444683707091412193022916014086527420062681860597620871559331318373239526756279662998108918 05398890428420575425160696531236660480933905879208166090591482794763
r =15793172240285324542143627060991282326031373094128315285644464196940323864648256219053103839312408723255475474646460359 87173562555701660815015737273369772920594272203301690446116749735697669668384984532326427317379587917060869577622446869532 94662693939604300864961637325536379321027705854708492453330690705531
s =10097345168744951885474267377878326615899945107205860634822201879789114767595998361621000348447657761213448231199370167 72420077595569514943828330705633699642945448394336710870375961597538252490189506933692099279516677752670868961803957761501 88902057785214767230658487267587289809918132337927575673868568976679
t =939603450719482552338821216836507975121293338683514964688988347367704413987433007457033938383205879989536782542722454003 44928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554 858491264614271309608925634272282292964002897650355047792764365447
c =91445979203817748854429062573111494657022950572386009739735983050043915346187703630985650745413847719799317998783814392 64848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687 49738801840621404165727832385574990266175244879612251706192088055201134360860962288578761723875876939897200994957552625843 02826488170390912847963305853499577245226151051027359302589695621031122380201335870968263860281284718523772255253573489192 04333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312 84268760147811704041901346805998377727369919240877355180658145819732462006521052391346741418148087528020358014707778906380 88323564861972713766158832215582655910692237276075853132402436195155211806004351141311622725199491014640899354412517514266 83447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810 15885785946040682809019968332476095610568290257718928324648331468936557086221740733310324333669140142454870238787640922897 72784986912000282827442395120913731101117921772289798673185464627145212962569383746186362065657915417691382670807898424007 96973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299 68932520888226191846070883388840618791252734662891289492105973542093165695323656017890918058737258945692669021911417319320 2048332172538564489660440225377822914097420807957784201785024166011709377791129
assert isPrime(p)and isPrime(q)and isPrime(r)and isPrime(s)and isPrime(t)
x =[p,q,r,s,t]
y =[]
for i in x:
y.append(nthroot_mod(c,e,i))
y.append(i - nthroot_mod(c,e,i))
yy =[]
for i in range(32):
s =bin(i)[2:].rjust(5,'0')
yyy =[]
for j in range(5):
yyy.append(y[j*2+int(s[j])])
yy.append(yyy)
# print(yy)
for i in yy:
m = long_to_bytes(crt(x,i)[0])
if b'ctfshow'in m:
print(m)
'''
b'!Nb\x1bO\xc6\xd2\xfc\xa9\xe6PJ\xbf\\\xc2-\xe81\x85\x0cQ\x9e^\xc8.\xe4\xea\x186\xc0:\x14\xb9\xb2@d\x06\xd2\xe7\x07N8v\x13\'\x9d\x05-G)\x0b@\xd5 h9\x8b\xabDI\xd8\xb9\xf3\xc0\xb5i\x94\x181\x02@\x8e\xcc\x82\r%K\xffE(-@Dv%k\xa9y\xd8tS\x8f\xcf\xa7s\xf3\x8b\xa5\xcd\x7f\x02)LdW}S\xbd\xf3\xcf\x9cz o\xaevw$\xbf\x81\x8d\xbc\xdd\xc0\xc7p\xc1\xcb\xe5t\n\xfc\x99\xd1B\xf8~Cuq\xd7\x80\x1e\x97\x04\x05\x9a\xd6\xbe\xd61p\xd7U\xec\xc1#\xb1z\x0e\x04\x1 e\x8a\x89p\xa2FYZ-EZD)\xe2\x0b\xef\xd1\xf0\xe2\xd0\x0b\xcb\x18\x9c\xd0\x9em\xac\xf6"\xd2D\x91Z5)l\xd4\x86x\xd0{[\tzH\xae\x1b\x10\x18\x81(\x07\xa7 z\xa2\x88\xc2\xb0:\x92I\x95~\x0erD~\x93\x15}\x8b\x85\x96\xa0n\xb7\xc1\xf7(\x0f \xb4s\x06\xefe\x98
\xc3\xe8\xa4\xf7\xae\x8e9j\xa8\xb5@\x01\x10*\x80\x1 1\xf4\xeb\x98\x9a\xc0\xe1\xb5\x18\x9c\x02\x82_\xa3\x05\xb2\x11\'\xfd\xc0\x1a\xcd\xa2\x0b\x90y\x87$\xa3\xbb$<P\x85R\xecu\xe3\x91(_\'\x84kY5\x16\xb3\ xabCf\xa9\xfe\xe8\xb2\xe1\x0bM\xc9\xe8?U2\xcd\xcdS\x024\x07\x18*eL\x04u^RS[\x90\xb3\xc0\x99\x95\xe5\xab\x93\x8cGM\x9b\x18\xe6\xc4\xa1\x0c\xdc\ xbc{R\xca\x81\x1c\xb4\xc0\xb5\xf1\xb6\xeb\xd8\xa7\x8f\x0e \xbc\xdf\xf0\x85\x8bT\xa2\x96k\x1d5\xc0\xb8\x96\xdd\x95\xd2\x85y\xef\x13\xed\x87\xac\xc3\x a1\xe2\xd2\x90\x0e\x9e\xd0Z \xd9\xce\xa04\x92\xa6\xb5\xe9H\xb8,\xe4\xe92\xdc\x1a\x87\x94\xdc\x9bq\xee\x16\xda\xf4\x15=|i\xc2i9|\xd6\x89\x19\x19ij\xb 2\x0b\xc2E\x9d!Ey\xc0\x95\xea\x19\xa1\xb4g\xad\x94\xf9\xb6\xe5\x84\x80\xde\xd0\xe7G\xedR\x8d\x8d\x1c\x82g\xa9\xd2\x8a\xdc\xf0O\xe4\xd4\xe1\x9f\x7 f\tn\xb3\x8a5\x83\xbcctfshow{D0_y0u_R3aLly_Kn0w_Ra8IN_alg0RI7HM?}'
'''
概率RSA
题⽬描述
怎么说呢，算原题（Backdoor CTF 2018 题⽬ BIT-LEAKER）吧，看看吧
简单分析
之前做的时候并不知道是原题，后来看到，这个好像是偶数，然后就联想到了，之后就是RSA的LSB了。Least Significant Bit Oracle Attack （LSB Oracle Attack / Parity Oracle ）
适⽤情况：可以选择密⽂并泄露明⽂的最低位（奇偶性）。
假设存在⼀个oracle，能对给定密⽂进⾏解密并给出对应明⽂的奇偶信息，则我们只需要 次就能解密任意密⽂。在⼀次RSA加密中，明⽂为 ，模数为 ，加密指数为 ，密⽂为 。我们可以构造出
，
因为 的两倍可能⼤于 ，所以经过解密得到的明⽂是 。
我们还能够知道 的最低位lsb 是1还是0。 因为 是奇数，⽽ 是偶数，所以如果lsb 是0，说明 是偶数，没有超过，即 ，反之则 。举个例⼦就能明⽩ 是偶数，⽽ 是奇数。以此类推，构造密⽂$ c′′=((4^e)⋅c)%n$ 使其解密后为 ，判断 的奇偶性可以知道 和 的⼤⼩关系。所以我们就有了⼀个⼆分算法，可以在对数时间内将 的范围逼近到⼀个⾜够狭窄的空间。
来⾃不懂的可以两位⼤佬的博客，更详细
脚本
那篇博客中的脚本有些问题，本⽂已修正
交互时间较长，需要跑到，请耐⼼等待2∗(random .randint (1,10000))0和1log (N )m n e c c ′=((2)⋅e c )%n =((2)⋅e (m ))%n =e ((2⋅m ))%n e m n m ′=(2⋅m )%n m ′n 2⋅m (2⋅m )n m <2n m >2n
2%3=24%3=1m ′′=(4⋅m )%n m ′′4n m i = 1024
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议