[Cryptohack] RSA (Monoprime, Square Eyes)

Monoprime

문제

왜 모든 사람들이 RSA를 위해 두 소수를 곱하는 데 집착합나요. 그냥 하나만 사용하는 게 어때요?

풀이

이번 문제의 Output.txt

먼저 n의 값이 factordb통해 알아보았다.

해당 숫자의 소수 상태

n의 상태는 P이고, n은 소수이다.

이때 오일러의 피함수를 보게 된다면

https://rkdxowhd98.tistory.com/135

단일 소수, 즉 모노프라임 인 경우의 오일러의 피함수의 작동원리가 n-1이기 때문에

개인키의 값은 n-1이다. 

from Crypto.Util.number import long_to_bytes

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

pri=n-1

key = pow(e, -1, pri) 

pt = pow(ct, key, n)
flag = long_to_bytes(pt)

print(flag)

플래그값은 crypto{0n3_pr1m3_41n7_pr1m3_l0l}이다.

 

Square Eyes

문제

2048비트 프라임을 받는 데 시간이 오래 걸려서 하나만 생성해서 두 번 사용했습니다. 💡만약 당신이 막히셨다면, 오일러의 피공식을 다시 한 번 보세요.

풀이

이번 문제의 Output.txt

일단 두 수로 나눠지지만 결과를 자세히 보면 두수가 같은걸 볼 수 있다.

문제에서 막히면 다시한번 오일러의 법칙을 보았다.

https://rkdxowhd98.tistory.com/135

작동원리에서 나오는 소수 P의 거듭제곱인 경우를 차용하자면

p=q이기 때문에

n=p^2, n은 p의 제곱이다.

그러면 2번의 거듭제곱인 상황의 오일러의 피함수를 차용하면

개인키는 p(p-1)이다.

이를 이용하여 문제를 푼다.

from Crypto.Util.number import long_to_bytes

p = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107 
e = 65537 
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
c = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896 #ciphertext

pri = p*(p-1)
key = pow(e, -1, pri) 

pt = pow(c, key, n)
flag = long_to_bytes(pt)

print(flag)

플래그값은 crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}이다