Mình sẽ tiếp tục writeup với chuỗi bài crypto và cụ thể là RSA. Khi đụng đến RSA thì thường sẽ liên quan đến rất nhiều toán.

Tổng quan về RSA:

• Chọn 2 số nguyên tố rất lớn đặt là p và q là private key. Lấy n = p*q.
• Ta có hàm phi Euler của n, đặt là $phi(n) = (p-1)*(q-1) = x$ và với mọi số a bất kỳ, có $a**(k*x + 1) = a [mod n]$.
• Lấy c = m**e % n với e là public key, thường lấy e = 65537.
• Lấy d = e**(-1) % x => $e*d = 1 [mod x] = k*x + 1$. => $c**d = m**(e*d) = m**(k*x + 1) = m [mod n]$

Nếu ta biết được p hoặc q thì có thể giải được mã.

Đề hôm nay mình lấy từ cuộc thi sơ khảo SVATTT 2020 (có biến tấu một chút. Hình 1 và 2).

(
m_nbits = 319
n = 9564131924902545901229274881252226809665751938593881897849244749742473615225998938327163080228568253235299742784176021290228707395737554742733574684770257881366142706501059192856478671033321009078083854176613518013122548818414875496421060745931135004174406703579716530954447002026717475428585993180489555581572291766024667155896792319593048199744311978251088730868674307952209546492025657067514433212327294382884275175934313191280083450601028526323224645724170422428751929823746664817524739993877648665694134479982528598562100633707757938927224900224158554215288213710497645041130649002956091989756837161169175898429430317776783277722303299444806945014131679834149675567514570617160325228009340896421785193685458757709540951949468624745115813743182104555047957882263249414978981224957049647055993951854696827273225544092112981750222706861308258580999201944498850076453579882899826576316769604961584247223475766384643316202128483783855340556186877387707693550779470299333605364382331250291343233427489080286582866042160879317104031362953079730565769364787623257517966874656371049923625491370616366113703735181720416656753262672964550263614387036343294400043405000263148819023775933828914531516729420212658406868430697
c = 1899354127260715821953252263762446310844237821079863391093999279593694527931512744666683459833721463364634679861512180085320915903389928877688677295967753625422821236103603782134067590862363039172666970011601464150892714147673543316655815662554230583831141956688007201435128652970502780380443853740721674176708563415531114673404558170440440418183080357829515620469926566119468419374078953845690342897387975791792567964964045910673333368756576779302355740848815451470562451026788115185748637656020841524580065022515301742634290865479706600320435834353248301462547869526349055097196073746093752608850632115592439854136538920596409330362592615551794550679416109099505367004740467387373443461180568447289312286311514285856860366976780670631284197463554838378376324127571873940240865456053918878005104689100469672039261164118743704103070710798509037355686694781210745746847919455639392263761984948468425667006773795451289193758599571212550483768151371709383789624571387137704120863783848280990047390490060628117098204036487406103992000250070636728534826523451189423447981863435038495348280791905481888836955154287237596036805975947172865620675968407489214270949567915882249860203441788389362945762023885951303836147089225
a = 2259868424430992779737974612523021901136890334141560509226560651538369544583125520613575379238057619332848580441586402076729451653050155143503083215953933938398494491695837346508237265557589168220008733253358033213950567442173192056784194516593367031337413429733320431505411894713387139521336101632645371933101624147322110277470599002182292322444420628962756152541465051208684827791745329343936297327518805376300927166044802772428416871109217370178798108686388050818877383107929391629288134849711835358388298394165355780751651104677618561423208956714797761645023501713640164755310317371914225696796910881822600082020283974023540779153101410951277066058387736803094464083239622823952138312029584080854076891506981502325882512202725485670791268767908384440104317230056476432185514645394346057969658530921377698027368066723640030269500977296834006305695918713223486724460057634208651937764181465980190668676554827758545655990191064884011885600191494401685396927396758563338386913616341848735575363216975409577298411313580395925847824019949040206507594032776635030900817407455671484246092466205473901283669111638804758896895256739320449178460915110103473636513695565203650615502479754069208222119427842225197664989223674
b = 9448983124422734405676523416851681867532776411826736608517798714734361097227539112067062063325328791408557896769480774287457143041062048297440681359375770886649722167882247477131831751165141065763649026777474664744910030404305809041667258509417505416773630573437531243780251091398820828852936579823933490374027524853781115198491652939854014405487274962234819933151629711404287472588787199844431341213916151903289626075299981490204532030371618554231855804623531695752568033667119047335699142612176035342788733397108470052661110641968817547252851461947953556331930227203105694782351400316312758272026831344868498468426920485261835444052433634085934306946519411478735112251106041292917047215405965010387836233898282176296914986207987544576762395835243541453368573359175322765647733052494183835052629632007990675292980467031406629562617153956707851660903917323914131446218750713695768677231165272457673922270176941091528375459673379741567199491549138996843009707379727147134069458999630666255181788827020559056038647937092890352371395907010642620685745321855010890834764832258727374983807953642535401378652948196896944707006400175597598981022930375445044230401115463856665810255875145003116813873716203472885187213721508
)

Nếu quen toán thì cách giải khá là đơn giản. Chúng ta sẽ leak số p từ hai số a và b đã cho. Ta có hình 3. Sau khi leak được private key sẽ giải mã được (hình 4).