PWNHUB-Crypto-easy_rsa

阅读量    138928 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

引言

上周做了PWNHUB公开赛的一道题,题目非常简单,不过其解法可以作为去年至今年不少比赛中一些题的非预期解。

 

easy_rsa

题目内容:

from Crypto.Util.number import *
import gmpy2

p = getPrime(256)
q = getPrime(256)
n = p**4 * q

e = 0x10001
phi = gmpy2.lcm(p - 1, q - 1)
print p,q,(p-1)*(q-1),phi
d = gmpy2.invert(e, phi)

dp = d % (p - 1)

flag = "flag test"
m = bytes_to_long(flag)

c = pow(m, e, n)

with open("task.txt", "wb") as f:
    f.write("p = " + str(p) + "n")
    f.write("dp = " + str(dp) + "n")
    f.write("c = " + str(c) + "n")

已知条件有:

e = 0x10001
p = 101929084299670546874377888313310032223878975126505177250899359089949344741757
dp = 65396861873942157177988639208356504492876743612299764912123170896046356221697
c = 6269384350208107136998483707011829394008587900457663571244788943036780209795770242310061468769349755061758139035007281850788012666607455148381884258167481858728622506286494019122798053786551166225594180741059049967989361825384394750684768329297786252047054319366274151496551274680273650028952994423859700579125146060211533750292355111530085730590032774664087174464270974719057122128137

和正常RSA的区别有两点:一是本题中n = p**4 * q而非p * q,这并不影响解密,如果知道pq的值一样可以计算n的欧拉函数 $phi(n) = (q-1)(p-1)p^3$;二是本题中不知道q的值,没有q就没法计算出n,所以就无法解密吗?答案是否定的,下面分析如何不使用q完成解密。

RSA加解密流程如下:

  1. 取大素数$p$和$q$,计算$n = pq$,计算$phi(n) = phi(p)phi(q)$;
  2. 取和$phi(n)$互质的公钥$e$,计算私钥$d$,满足$edequiv 1 pmod {phi(n)}$;
  3. 丢弃$p$和$q$,避免被他人获得进而计算出私钥;
  4. 加密:$c equiv m^e pmod n$;
  5. 解密:$m equiv c^d pmod n$.

由于

ed = kphi(n)+1

根据欧拉定理

a^{phi(n)} equiv 1 pmod n

c^d equiv m^{ed} equiv m^{kphi(n)+1} equiv m pmod n

(注意这不是严格的RSA正确性证明)

当知道n的一个因数(假定为p)的时候,令

cp equiv c pmod p

就有

cp equiv m^e pmod p

如果明文m不大于p,那么就可以在不需要q的情况下解密,流程如下:

  1. 计算$phi(p) = p-1$;
  2. 计算新的私钥$dp$,满足$e*dpequiv 1 pmod {phi(p)}$;
  3. 计算$m equiv cp^{dp} pmod p$.

同样由于欧拉定理保证了这样计算出的m是正确的

cp^{dp} equiv m^{edp} equiv m^{kphi(p)+1} equiv m pmod p

无论明文m是否大于p,上面的式子都是成立的,只是m大于p时得到是满足要求的最小m,这未必是我们想要的。

按照上面的思路,对于easy_rsa这道题,已知的最大的一个n的因数是$p^4$,解密流程如下:

  1. 计算$cp_4 equiv c pmod {p^4}$,得到cp4 = 92258417132703698867357242895362081798728266820359920406334628423217525720347162182976441142853919128328179377489269891965884679810815303646319951126042836844112032938227662314873014551126491592505083363734798620778161007996148756609856151255577919385049228825554966072197314543854674047083451882206834724547;
  2. 计算$phi(p^4) = (p-1)p^3$,得到phip4 = 107942504553034055189174912429558305583217343940542532622157501036333587105880669089428586204757543036635156859326713539152513944716055403225815788388551357468487200053249039484218446786105990107424723366865192526491061630182343408694770454246453879525773269493047346660305044734430034813341844797241874083308;
  3. 计算新的私钥$dp_4$,满足$e*dp_4equiv 1 pmod {phi(p^4)}$,得到dp4=8874288028621198549815744208164245395461724661666587817083244817183657587721211606479411972950144832405972582786095374352712897052506317234244708604872281520976075100888136850038436170156386082652614698577439573565067672664639307353821859521795222590061589270618720780715070586525306736260217278293776302865;
  4. 计算$m equiv cp_4^{dp_4} pmod {p^4}$,得到m=13040004482819946222025247183339497391242477745471686520134579858183906354823232897647456893;
  5. 转成字符串,得到flag{473c6e6a2d6a46b5b38331cdee4b3192}.

事实上这个大小的m,取n的一个较小因子$p^2$就可以计算出来,读者可以自己计算。

截至本文完成官方 writeup 尚未公开,个人感觉上面的解法应该属于预期解法,因为这个题目流程比较简单。相对应的,去年至今年的一些比赛中出现了一些流程复杂的题目,比如不公开RSA的en,解题时需要使用各种技巧才能获得计算 flag 的全部要素。如果出题人对m的选择不合适,那么只需要获取部分要素即可计算 flag,工作量大大减少。下面以 De1CTF2019 的 Baby_RSA 为例应用上面的解法。

De1CTF2019 Baby_RSA

题目内容:

import binascii
from data import e1,e2,p,q1p,q1q,hint,flag

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)

ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))

flag=int(binascii.hexlify(flag),16)
q1=q1p
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

下面是官方 writeup 的解法:

本题主要考察RSA的基础知识和常见攻击方式,涉及共模攻击、小指数攻击等。首先通过共模攻击等到p,再通过小指数攻击得到e1,e2,然后使用yafu分解大数得到q1且可解出没有任何用处的hint。然后是以flag为明文的加密,这里的加密不满足e和φ互素,因此虽然知道p,q,但无法直接解密,需要稍做操作。

事实上本题的m实在太小了,只需要通过低加密指数小明文攻击得到e2,配合已知的q2解密即可获得flag,流程如下:

  1. 使用低加密指数小明文攻击得到e2:
for i in range(200000):
    if gmpy.root(ce2+n*i,3)[1]==1:
        res=gmpy.root(ce2+n*i,3)[0]
        e2=res-tmp
        break
  1. 对于c2==pow(flag,e2,p*q2),已知c2e2和模数的一个因子q2,使用上面提到的方法求解:
    1. 计算$cq_2 equiv c_2 pmod {q_2}$,得到cq2 = 59300156834807239400438883971989389252055541087043532702584370751329717945886481828760106720813999920356009388325503241306598798800976100279870403310753783824524984677363752808090507086013354386506648468559181712840654544329520704859572275231884385619243419604881680998090642805788985141920716229101651471742;
    2. 计算$phi(q_2) = q_2-1$,得到phiq2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959512;
    3. 计算新的私钥$dq_2$(注意这里$phi(q_2)$和$e_2$不互素,令$e=frac{2}{e_2}$),满足$e*dq_2equiv 1 pmod {phi(q_2)}$,得到dp4=108137817394146015594852058734005451132800899677885557426197929598594956463991870282326331929409200590023700635072220450512097663569826867921816998060051238124409538827828378297268506047977115344663749598582163852149601763815400251995770809704407725376150671432757304162027361685807036201740059635743897815877;
    4. 计算$m^2 equiv cq_2^{dq_2} pmod {q_2}$,再开方得到m=3597756982424788530654510857179372044113434920098110365668160220641544533784058353001736221836299987936893;
    5. 转成字符串,得到de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}.

flag: de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}.

 

结语

n的因子较大且部分已知,而明文又较小的时候常常可以应用上面的方法完成解密。师傅们如果要出类似题目建议先对明文进行填充,这样这种非预期解法就无法进行(比如NCTF-2019-easyRSA)。

 

参考

  1. easy_rsa:https://pwnhub.cn/publicgamedetail/25
  2. Baby_RSA: https://github.com/De1ta-team/De1CTF2019/blob/master/writeup/crypto/Baby%20Rsa/README_zh.md
分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多