來之不易的warm_up嗚嗚嗚嗚，新學(xué)到了幾個知識點(diǎn)：Rabin算法與這個題中左移的逆運(yùn)算以及e和φ（n）不互素
題目
from Crypto.Util.number import *
from encode import KEY
q=getPrime(1024)
p=getPrime(1024)
r=getPrime(1024)
s=getPrime(1500)
e1=125794
e2=42373
n1=p*q
n2=p*r
n3=p*q*s
c1=pow(s,e1,n1)
Key=int(KEY.encode('hex'),16)
key_encode=pow(Key,e2,n3)
with open("enc","a")as f:
f.write("c1: "+str(c1)+"\n")
f.write("n1: "+str(n1)+"\n")
f.write("n2: "+str(n2)+"\n")
f.write("key_encode: "+str(key_encode)+"\n")
from flag import flag
import os
KEY = os.urandom(len(flag))
dec=int(flag.encode('hex'),16)
assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)
#enc: 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809
題目分析
先說個大概思路，后邊有詳細(xì)的分析和知識點(diǎn)記錄
①通過求n1,n2的公因數(shù)我們可以求出p批糟，進(jìn)一步分解得到q和r
②從 key_encode=pow(Key,e2,n3)可以看出要想求出key我們必須知道n3，而n3=p*q*s所以我們要通過第一個e和φ（n）不互素類型的RSA求出s
③通過推算可以推導(dǎo)出m * *2 與 c * * b_d同余
④使用rabin算法，算出四個解伟众，長度為1500bit的即為s
⑤知道s后，解出一個由三個素?cái)?shù)組成的RSA召廷，求出key
⑥key和給出的enc異或凳厢，再進(jìn)行后續(xù)的位操作，即可得到flag
新學(xué)習(xí)到的知識點(diǎn)
e與φ（n）不互素
學(xué)習(xí)戳
推導(dǎo)過程
2159F283E9C0A9BB07475D60797CE006.jpg
Rabin算法
學(xué)習(xí)戳
由上面的推斷竞慢，e=2,使用Rabin算法
推導(dǎo)過程
c ≡ m^2 (mod n)
rabin1.png
rabin2.png
優(yōu)化
之前計(jì)算擴(kuò)展歐幾里得算法ap+bq=gcd(a,b)中a和b先紫，一直用自己寫的，現(xiàn)在才知道a=invert(p,q)``b=invert(q,p)
位運(yùn)算
assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)
這里有一個陷阱筹煮，因?yàn)閙ask全是1泡孩，按位與可以省略....我之前沒發(fā)現(xiàn)這個，還一直想著怎么逆
我們把解出的key和enc異或寺谤，得到現(xiàn)在的dec
原來的dec與原來的dec左移200位得到現(xiàn)在的dec
左移.jpg
由于左移后后200位為0仑鸥，所以現(xiàn)在dec的后200位即為原dec后200位
再從原dec后200位取出后135位，與現(xiàn)在dec前135位異或变屁，即為原dec的前135位
代碼
from gmpy2 import *
from Crypto.Util.number import *
import exgcdmoni
n1=15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2=16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
c1=9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855
e1=125794
e2=42373
key_encode=154190230043753146353030548481259824097315973300626635557077557377724792985967471051038771303021991128148382608945680808938022458604078361850131745923161785422897171143162106718751785423910619082539632583776061636384945874434750267946631953612827762111005810457361526448525422842867001928519321359911975591581818207635923763710541026422076426423704596685256919683190492684987278018502571910294876596243956361277398629634060304624160081587277143907713428490243383194813480543419579737033035126867092469545345710049931834620804229860730306833456574575819681754486527026055566414873480425894862255077897522535758341968447477137256183708467693039633376832871571997148048935811129126086180156680457571784113049835290351001647282189000382279868628184984112626304731043149626327230591704892805774286122197299007823500636066926273430033695532664238665904030038927362086521253828046061437563787421700166850374578569457126653311652359735584860062417872495590142553341805723610473288209629102401412355687033859617593346080141954959333922596227692493410939482451187988507415231993
enc=17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809
p=gcd(n1,n2)
q=n1//p
phin=(p-1)*(q-1)
b=gcd(e1,phin)
a=e1//b
b_d=invert(a,phin)
c1=pow(c1,b_d,n1)
a,b=exgcdmoni.exgcd(p,q)
r=pow(c1,(p+1)//4,p)
s=pow(c1,(q+1)//4,q)
x1=(a*p*s+b*q*r)%n1
x2=n1-x1
x3=(a*p*s-b*q*r)%n1
x4=n1-x3
s=x3
phin1=(p-1)*(q-1)*(s-1)
d=invert(e2,phin1)
key=pow(key_encode,d,p*q*s)
dec=bin(key^enc)[2:]
dec2=dec[135:]
dec1=bin(int(dec[:135],2)^int(dec2[65:],2))[2:]
dec=int(dec1+dec2,2)
print(long_to_bytes(dec))
