# RSA
- Đọc thông tin về `RSA` và các cách tấn công tại [đây](https://hackmd.io/7FSbyXYrRPaceCCrP8XdeA)
## STARTER

**RSA Starter 1**
- Challenge này không có gì khó cả ta chỉ cần sử dụng `pow()` của Python để giải quyết.

print(pow(101, 17, 22663))


**RSA Starter 2**
- Challenge này cho ta $(p, q, m, e)= (17, 23, 12, 65537)$ và yêu cầu ta tìm `c`. Với $c \equiv m^e mod(n)$ $(n= pq)$

(p, q, m, e)= (17, 23, 12, 65537)
print(pow(m, e, p*q))


**RSA Starter 3**
- Challenge này yêu cầu ta tính $\phi(n)$ với $(p, q)= (857504083339712752489993810777, 1029224947942998075080348647219)$
- Ta có $\phi(n)= (p- 1)(q- 1)$

(p, q)= (857504083339712752489993810777, 1029224947942998075080348647219)
print((p- 1)*(q- 1))


**RSA Starter 4**
- Challenge này yêu cầu ta tính `d` dựa vào yếu tố đã cung cấp.
- Ta biết rằng $d= e^{-1} mod(\phi(n))$.

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e= 65537
phi= (p- 1)*(q- 1)
d= pow(e, -1, phi)
print(d)


**RSA Starter 5**
- Challenge nay yêu cầu ta tìm thông tin bị encrypt dựa vào các yếu tố đã cung cấp.
- Ta biết $c \equiv m^e mod(n)$ và $m \equiv c^d mod(n)$
- Sử dụng factordb để phân tích n.

n= 882564595536224140639625987659416029426239230804614613279163
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e= 65537
c= 77578995801157823671636298847186723593814843845525223303932
phi= (p- 1)*(q- 1)
d= pow(e, -1, phi)
print(pow(c, d, n))


**RSA Starter 6**
- Chall cho ta flag là: crypto{Immut4ble_m3ssag1ng} và yêu cầu ta sử dụng nó là c với SHA256.
- Decode theo RSA ta thu được con số đó là flag ta cần submit.

from Crypto.Util.number import *
from hashlib import sha256
n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
c = b"crypto{Immut4ble_m3ssag1ng}"
c = sha256(c).hexdigest()
c = int(c, 16)
m = pow(c, d, n)
print(m)

## PRIMES PART 1

**Factoring**
- Challenge cho ta số n yêu cầu ta phân tích và flag là số được phân tích ra nhỏ hơn.
- Ta sử dụng [tool](http://www.factordb.com/)

**Inferius Prime**
- Challenge cho ta một bài thuần RSA bình thường với lỗ hỏng là n tương đối nhỏ có thể phân tích ra được

from Crypto.Util.number import *
p, q = 752708788837165590355094155871, 986369682585281993933185289261
n, phi = p * q, (p - 1) * (q - 1)
e = 3
d = pow(e, -1, phi)
ct = 39207274348578481322317340648475596807303160111338236677373
print(long_to_bytes(pow(ct, d, n)))


**Monoprime**
- Challenge có đặt ra câu hỏi là tại sao phải dùng 2 số nguyên tố p, q để tạo n mà không phải là một số?
- Đây chính là gợi ý làm bài cho ta khi mà n challenge cung cấp không thể phân tích một cách nhanh chóng. Hoặc có thể n chính là số nguyên tố.

from Crypto.Util.number import *
n=171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e= 65537
ct= 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  
phi= n- 1
d= pow(e, -1, phi)
decode =pow(ct, d, n)
print(long_to_bytes(decode))


**Square Eyes**
- Challenge cung cấp cho ta $n= x^2$. Nên $p= q= \sqrt{x}$

from math import *
N=535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e=65537
c=222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p= q= isqrt(N)
phi= p*(p-1)
d= pow(e, -1, phi)
flag= pow(c, d, N)
flag= hex(flag)[2:]
flag= bytes.fromhex(flag)
print(flag)


**Manyprime**
- Challenge này cho ta n được tạo thành từ nhiều số nguyên tố khác nhau mà không phải 2 số như RSA ta thường gặp.
- Tuy nhiên ta vẫn decrypt như bình thường.

from Crypto.Util.number import *
N= 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e= 65537
ciphertext= 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
factor = (9282105380008121879, 9303850685953812323, 9389357739583927789, 10336650220878499841, 10638241655447339831, 11282698189561966721, 11328768673634243077, 11403460639036243901, 11473665579512371723, 11492065299277279799, 11530534813954192171, 11665347949879312361, 12132158321859677597, 12834461276877415051, 12955403765595949597, 12973972336777979701, 13099895578757581201, 13572286589428162097, 14100640260554622013, 14178869592193599187, 14278240802299816541, 14523070016044624039, 14963354250199553339, 15364597561881860737, 15669758663523555763, 15824122791679574573, 15998365463074268941, 16656402470578844539, 16898740504023346457, 17138336856793050757, 17174065872156629921, 17281246625998849649)
phi = 1
for prime in factor:
    phi *= (prime - 1)
d = inverse(e, phi)
flag = pow(ciphertext, d, N)
print(long_to_bytes(flag))

## PUBLIC EXPONENT

**Salty**
- Challenge này cho ta giá trị của $e= 1$. Điều này khiến cho $c= m$ nếu $m< n$ do cách encrypt là: $c \equiv m^e mod(n)$.
- Thật vậy, sau khi decrypt theo suy đoán ta có:

from Crypto.Util.number import *
ct= 44981230718212183604274785925793145442655465025264554046028251311164494127485
flag= long_to_bytes(ct)
print(flag)


**Modulus Inutilis**
- Challenge này tương đối giống với challene `Salty` chỉ khác chỉ số $e= 3$ thay vì $e= 1$. Nên ta cũng có dự đoán như bài `Salty`.
- Thật vậy ta có:

from Crypto.Util.number import *
from sage import *
ct= 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
ct= pow(ct, 1/3)
flag= long_to_bytes(ct)
print(flag)


**Everything is Big**
- Đọc source challenge ta thấy điều kiện của d giống với điều kiện của `Wiener attack`. Ta sẽ sử dụng `Wiener attack`.
- Sử dụng tool trên [dcode.fr](https://www.dcode.fr/). Ta thu được flag.
- Theo tool thông báo thì challenge này được decrypt bằng `Wiener attack` đúng như ta dự đoán.

**Crossed Wires**
- Kịch bản của challenge là cung cấp cho ta:
- Key riêng của bản thân gồm (N, d).
- Key của từng thành viên khác gồm (N, e). Với các giá trị của N giống nhau.
- Encrypt. Đây là flag sau khi bị mã hóa.
- Kịch bản này khá giống với kịch bản mà tôi đã nhắc tới trong phần [Common modulus](https://hackmd.io/7FSbyXYrRPaceCCrP8XdeA?view#Common-modulus).
- Dựa vào kịch bản đó và các thông tin về key của các thành viên khác ta decrypt.
- Tuy nhiên sau khi thử decrypt tôi nhận ra nó khác là khó khăn. Ta sẽ thử brute d của từng thành viên xem cipher đó ứng với key nào.

from Crypto.Util.number import *
import math
from gmpy2 import next_prime
from factordb.factordb import *
my_key =  (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
friend_keys = [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
cipher =  20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
fator = FactorDB(my_key[0])
fator.connect()
[p, q] = fator.get_factor_list()
phi = (p-1)*(q-1)
for e in friend_keys:
    d = pow(e[1], -1, phi)
    cipher = pow(cipher, d, my_key[0])
    print(d)
    
print(long_to_bytes(cipher))


**Everything is Still Big**
- Bài này tương đối giống với bài `Everything is Big` nên ta sẽ thử giải tương tự.
- Vẫn là `Wiener attack`.

**Endless Emails**
- Chall cho ta 7 bộ số c, n, e. Với e là số nhỏ là 3. Từ e ta có thể đoán được rằng $c= m^3$.
- Từ chall ta định hướng rằng sử dụng Thặng dư Trung Hoa để giải quyết.

from Crypto.Util.number import*
from itertools import *
import gmpy2
n = [14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021, 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123, 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147, 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961, 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823, 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263, 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897]
c = [6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225, 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172, 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153, 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577, 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805, 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749, 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144]
e= 3
for i, j, k in combinations(range(7), 3):
    N=n[i]*n[j]*n[k]
    N1=N//n[i]
    N2=N//n[j]
    N3=N//n[k]
    u1 = inverse(N1, n[i]) 
    u2 = inverse(N2, n[j])
    u3 = inverse(N3, n[k])
    M = (c[i]*u1*N1 + c[k]*u3*N3 + c[j]*u2*N2) % N
    m = long_to_bytes(gmpy2.iroot(M, e)[0])
    if b'crypto{' in m:
        print(m.decode()) 

## PRIMES PART 2

**Infinite Descent**
- Challenge cho ta 2 số q, p khá gần nhau nên ta sẽ sử dụng `Fermat attack`.

import math

def isqrt(n):
    # Hàm tính căn bậc hai với tối ưu hóa
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def fermat(n):
    # Trường hợp đặc biệt khi n là số chẵn
    if n % 2 == 0:
        return 2, n // 2

    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(b2)

    # Số lần lặp tối đa để tránh vòng lặp vô hạn
    max_iterations = 10000
    count = 0

    while b*b != b2:
        a += 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1

        if count > max_iterations:
            raise Exception("Không thể phân tích sau {} lần lặp".format(max_iterations))

    p = a + b
    q = a - b
    assert n == p * q
    return p, q

def main():
    n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
    p, q = fermat(n)
    print("p =", p)
    print("q =", q)
    
    phi= (p-1)*(q-1)
    c= 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
    e= 65537
    d= pow(e, -1, phi)
    flag= long_to_bytes(pow(c, d, n))
    print(flag)
from Crypto.Util.number import *
if __name__ == '__main__':
    main()


**Marin's Secrets**
- Challenge tạo 2 số nguyên tố Mersenne p, q (Số nguyên tố có dạng 2^x- 1).
- Challenge này ta có thể brute force tìm p, q được tuy nhiên n bài này ta có thể phân tích ra được nên ta sẽ phân tích ra.

from Crypto.Util.number import *
p= 2**2203- 1
q= 2**2281- 1
n= 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457 
e= 65537
c= 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
phi= (p- 1)*(q- 1)
d= pow(e, -1, phi)
flag= pow(c, d, n)
print(long_to_bytes(flag))


**Fast Primes**
- Challenge này ta chỉ chú ý vào cách lấy dữ liệu trong file pem và cách giải mã bằng key (PKSC1) để có được cipher.

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
f = open('key_17a08b7040db46308f8b9a19894f9f95.pem', 'rb')
key = RSA.import_key(f.read())
p = 51894141255108267693828471848483688186015845988173648228318286999011443419469
q = 77342270837753916396402614215980760127245056504361515489809293852222206596161
phi = (p - 1) * (q - 1)
c = "249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28"
c = bytes.fromhex(c)
d = pow(key.e, -1, phi)
key = RSA.construct((key.n, key.e, d))
print(key)
cipher = PKCS1_OAEP.new(key)
print(cipher)
plaintext = cipher.decrypt(c)
print(plaintext)


**Ron was Wrong, Whit is Right**
- Challenge này giống với challenge trước có điều phải brute force 50 file.

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from factordb.factordb import FactorDB
for i in range(1, 51):
    with open(f"{i}.pem", 'r') as f:
        key = RSA.importKey(f.read())
        print(key.exportKey)
    with open(f"{i}.ciphertext", "r") as a:
        c = a.read() 
    try:
        f = FactorDB(key.n)
        f.connect()
        [p, q] = f.get_factor_list()
    except:
        continue
    phi= (p-1)*(q-1)
    d = pow(key.e, -1, phi)
    c = bytes.fromhex(c)
    print(c)
    key = RSA.construct((key.n, key.e, d))
    cipher = PKCS1_OAEP.new(key)
    plaintext = cipher.decrypt(c)
    print(plaintext)


**RSA Backdoor Viability**
- Challenge cho ta số n tương đối lớn tuy nhiên ta vẫn có thể phân tích được.

from Crypto.Util.number import *
n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
p, q= 20365029276121374486239093637518056591173153560816088704974934225137631026021006278728172263067093375127799517021642683026453941892085549596415559632837140072587743305574479218628388191587060262263170430315761890303990233871576860551166162110565575088243122411840875491614571931769789173216896527668318434571140231043841883246745997474500176671926153616168779152400306313362477888262997093036136582318881633235376026276416829652885223234411339116362732590314731391770942433625992710475394021675572575027445852371400736509772725581130537614203735350104770971283827769016324589620678432160581245381480093375303381611323, 34857423162121791604235470898471761566115159084585269586007822559458774716277164882510358869476293939176287610274899509786736824461740603618598549945273029479825290459062370424657446151623905653632181678065975472968242822859926902463043730644958467921837687772906975274812905594211460094944271575698004920372905721798856429806040099698831471709774099003441111568843449452407542799327467944685630258748028875103444760152587493543799185646692684032460858150960790495575921455423185709811342689185127936111993248778962219413451258545863084403721135633428491046474540472029592613134125767864006495572504245538373207974181
d = pow(e,-1,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))


## PADDING

**Bespoke Padding**
- Ta hãy lưu ý hàm `pad`. Hàm `pad` tạo ra flag sau khi pad có dạng $a*m+b$.

def pad(self, flag):
    m = bytes_to_long(flag)
    a = random.randint(2, self.N)
    b = random.randint(2, self.N)
    return (a, b), a*m+b

- Nếu ta nhận $2c$ từ sever thì ta có tìm được flag dựa trên hàm pad bằng cách sau:
$$c_1= (a_1*m+ b_1)^e\ mod(n)$$ $$c_2= (a_2*m+ b_2)^e\ mod(n)$$
- Suy ra:
$$f_1 = (a_1 * x + b_1)^e -c_1= 0\ mod(n)$$ $$f_2 = (a_2 * x + b_2)^e -c_2= 0\ mod(n)$$
- Từ đây ta lấy GCD của $f_1, f_2$ ta sẽ thu được flag.

from Crypto.Util.number import *
e= 11

a_1= 6133949050067298652891732285984333303205886210575004621136848221222454831779179003828611829548864663815867688083465174208816477085582792026188922174233905828433287848668574845437461702664346937261585270626340172370780680003395792106649367480603907049240029161494435194360164757573384671538154469918106480070712691085237639934288182708107804530829289241733936248431993890629287273486150107897566379160112558305222611473065075096743008063283247415141512161829045242032212064229662894195804704297672964972529064417673809490268144760343544049618944111116634597194926940369629655119925307413185090097688170606958149354689
a_2= 7278785479563032076217372072478742163364049824278768817708658539903270801518023918779895024210989090568888582542582028348751831998235566278679075968947304679463797091642616235215918791594086892519762887573526177721228321027998145000676784949384486383189382747358758605172729318456799653632946876183374507963226949217817331545873550195930672166037942897507485968085193822595973021183244604458728496591545129243629668129874493063684878566877787164097805379016723297283531538348963053417588765471733847436676493331556656065503288601539158075473859738637224074087760270097903016780901069285201197512947712289007266196707
b_1= 9352131218175100321164720090910986400556184443794247937348484058659896415785140745758020988686002306831017115068548953239537917488841522253652922320320125123116273465716166431335982785772308121928197374194732384981297361045160326980834900334397492639583189210996397884942589307527272465344179155938112056419275364552206064201461462237744416724470640086722918524780890206023893535248274843719019319174705722911510807506933906382371748754819022430617415606426106834375637197806550831016627055105814918321017229359923792672743647391693743743146123885618196972610006428693421113080228906125510192850255877516140039461221
b_2= 11865578230563836828698440198808365763838529641027242368774648502528146025373884077636188559268558983553029345861005341892039509480861763747979370373285951032460886690599396504316564191297695866749350530719433597835530131842462394478691215454748422031274496715144914840581803915484205642237754397897135762963222557911979900760257412637291140293429425584155306979638319333273918692229160775503948430456548824596794763502666041465085282983358829082798254649239371165290718210100917096913199025417082399562485589742852045161633752465618786410930009837407350953986601362316013361870446096677995658906011118890837646662268
c_1= 4009779869087029255297463436169552204922655636486739641149158955611853474961823388440774560168088903319163374734746559193431012002310033134294928687790281560060480278406902405647710065437968470791144020214948251589802521673538106673520329593966117133035500642791160363872942530392478032603543815079749621272066298793745754177453129785264105576254533858055814555411033650580409676947102291490308738562451861962318065135790387510758132221037279295861267324464183809432424228112569670498250666299553720115811684942009389793137881124508986193925796993330600220816337487839592275984075100028603123399027888744446526336084
c_2= 9470532791192518339116567612452125668634254427593345077890928811136489095569332157070928187542877325732220962249094478185997114006520013646928161539356773555658138326485644749570751397752591877370804493367197391523565979494997776864514990972954373896156187161882821335142611778824885021617291630987368379239885737958813946409618414749366178178723492300258314121332637553715297423542857436720797021700415618429608435119251524740781833903275242120949797821323535018136881667998526942979724320776350568534803754580045582204197786249574712490746093947342307493799702810358608122422901511340954397692865671624257606048446
n_1= 12758089942147422526562581670640799437693626559720177948335448952480177040540092993839347305858716346620139258915118063052676763720502105839408081236315999453600215894689204755604040046196929147256570353306444785675709648665073725546856388899081456336370619470129424251159530163067693045543606732567681940633785188718453572053164778456198151034369543964342556284175816763267598187050376096124192024564750249854263088738800589356974410853869051058877431888385737390248624865065793387454497794541374321909982888533632248244348081428001135536261135254237936156340896691103352539883828862927723394248037465576852490432707
n_2= 12758089942147422526562581670640799437693626559720177948335448952480177040540092993839347305858716346620139258915118063052676763720502105839408081236315999453600215894689204755604040046196929147256570353306444785675709648665073725546856388899081456336370619470129424251159530163067693045543606732567681940633785188718453572053164778456198151034369543964342556284175816763267598187050376096124192024564750249854263088738800589356974410853869051058877431888385737390248624865065793387454497794541374321909982888533632248244348081428001135536261135254237936156340896691103352539883828862927723394248037465576852490432707
P.<x> = PolynomialRing(Zmod(n_1))

f1 = (a_1 * x + b_1)**e -c_1
f2 = (a_2 * x + b_2)**e -c_2

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a.monic()


m = long_to_bytes(int(-gcd(f1, f2).coefficients()[0]))
print(m)


**Null or Never**
- Chall này ta có được len của flag, và ta biết được dạng của flag.

Flag: b'crypto{???????????????????????????????????}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

- Với 57 bytes `0`. Ta sẽ sử dụng `Coppersmith's attack`, cụ thể hơn là `Stereotyped messages`.

from Crypto.Util.number import *
msg= "crypto{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"
msg = msg.encode()
msg = msg.replace(b"X",b"\x00")
msg=  msg + b'\x00' * (100 - len(msg))
msg = bytes_to_long(msg)
n= 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
c= 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
P.<x> = PolynomialRing(Zmod(n))
f= (msg+ x*((2**8)**58))**3 -c
f= f.monic()
x= f.small_roots(epsilon=1/20)
long_to_bytes(int(x[0]))


## SIGNATURES PART 1

**Signing Server**
- Challenge ta chỉ cần gửi ngược lại `C` là có được flag.

from pwn import *
import json

r = remote("socket.cryptohack.org", 13374)
r.recvline()
r.sendline(json.dumps({'option': 'get_secret'}))
data = json.loads(r.recvline().decode())
ciphertext = data['secret'][2:]
r.sendline(json.dumps({'option': 'sign', 'msg': ciphertext}).encode())
data = json.loads(r.recvline().decode())
print(data)
r.close()


**Let's Decrypt**
- Máy chủ xác minh chữ ký không chính xác bằng cách so sánh trực tiếp thông điệp được tính toán với chữ ký được cung cấp.
- Điều này cho phép giả mạo chữ ký bằng cách thao tác với mod(N) trong phương trình xác minh.
- Ta chọn e= 1 cho dễ.

**Blinding Light**
- Challenge này ta vận dụng kiến thức về kỹ thuật `Blinding`.
$$r^e mod(N)$$
- Với challenge này tôi chọn $r= 3$.
$$C_1= (3^eM)\ mod(N)$$ $$=>M_1= C_1^d\ mod(N)= 3^{ed}M^d\ mod(N)$$
- $verified= c^e\ mod(N)=$ ADMIN_TOKEN, với ADMIN_TOKEN= "admin=True"= 459922107199558918501733.

from Crypto.Util.number import *
from pwn import *
from json import *
r = remote('socket.cryptohack.org', 13376)
r.recvline()
r.sendline(dumps({"option": "get_pubkey"}))
recv = loads(r.recvline())
x = 459922107199558918501733
N = int(recv["N"], 16)
e = int(recv["e"], 16)
sign = (pow(3, e)* x) % N
r.sendline(dumps({"option": "sign", "msg": hex(sign)[2:]}))
recv = loads(r.recvline())
msg = int(recv["msg"], 16)
signature = int(recv["signature"], 16)
r.sendline(dumps({"option": "verify", "msg": hex(x)[2:],"signature": hex(signature* pow(3, -1, N) % N)[2:] }))
print(r.recvline())

## SIGNATURES PART 2

**Vote for Pedro**
- Từ source code ta biết được sever sẽ cho ta flag khi mà ta thỏa điều kiện của hàm sau:

 elif your_input['option'] == 'vote':
            vote = int(your_input['vote'], 16)
            verified_vote = long_to_bytes(pow(vote, ALICE_E, ALICE_N))

            # remove padding
            vote = verified_vote.split(b'\00')[-1]

            if vote == b'VOTE FOR PEDRO':
                return {"flag": FLAG}
            else:
                return {"error": "You should have voted for Pedro"}

- Chall yêu cầu chúng ta tìm một số nguyên x sao $x^3\ mod(n)$ tương đương với giá trị của "VOTE FOR PEDRO". Ta sẽ lợi dụng rằng n của chall rất lớn để tạo 1 số x thỏa mãn.
- Ta sẽ tìm x với code sau:

from sage.all import *
msg = bytes_to_long(b'VOTE FOR PEDRO')
modulus = 256**15
Zmod_n = Zmod(modulus)
x_candidates = Zmod_n(msg).nth_root(3, all=True)
for x in x_candidates:
    if x**3 == msg:
        print(hex(x))
        break

- Sau khi có x ta gửi lên sever và thu được flag.