Based on Xuan Yu’s instant kill ctfshow-RSA

Table of Contents

babyrsa

easyrsa1

easyrsa2

easyrsa3

easyrsa4

easyrsa5

easyrsa6

---

The RSA algorithm is an asymmetric encryption algorithm. Different from the symmetric encryption algorithm, the RSA algorithm has two different keys, one is the public key and the other is the private key.

Common ones in CTF include: broadcast attack, common mode attack, Wiener attack, non-mutual mode attack

babyrsa

Importing e p q c successfully calculated the private key, but an error occurred when calculating the plain text.

Here we also need to fill in n, n=p*q, and use Python to calculate it.

Calculate plaintext after importing n

plain text to character

flag{b4by_R5A}

You can also use scripts to help understand the principles

import gmpy2
import binascii
e=65537
p = 1040468357126640647791947349742711856355389278898806119299319397110013015616822701779316229746427899209189025633612933454 34055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873 283332371986860194245739423508566783663380619142431820861051179
q = 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120 35449798794591102117084245755218288013364271130722707213381225334112983041615845049925821696787985758156538089078839506813003 3931180395926482431150295880926480086317733457392573931410220501
c = 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589 87383097330189852364474495154534540457846617672503029042164934493695248025490293941721514820573573075480846735163994347481628 09802304470974446824892230544995241979097198573005971574060750692043150227038944662261795076270708354282260865097677467593538 22302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989 680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,p*q)

print(binascii.unhexlify(hex(m)[2:]))

Run out of flag{b4by_R5A}

easyrsa1

importenc

First decompose n

Import p q to calculate the private key

Compute plaintext

Convert plain text to characters and get the flag

flag{fact0r_sma11_N}

easyrsa2

There are two public keys n and they are not mutually prime. We can directly find the greatest common factor of these two numbers to obtain p and q.

Import e and c and solve for the private key (you can use any one of the ciphertext c)

Explanation of the text, an error is also reported here

Use script to solve

import gmpy2
import binascii
e=65537
n1 = 236865639255375777530472290407542829533522217241544953906873588777753801476051524555379885634907169438725175932128583261 46811511103311865753018329109314623702207073882884251372553225986112006827111351501044972239272200616871716325265416115038890 80511482931511195031918318959128382179323799904442788793453683581352674875961296310337780308990066250939956981978557149282811 24373126592298798061687588436032488236298218510537754586519339521839884821639500392484872704538882884275403055428241799517344 12044985364866532124803746008139763081886781361488304666575456680411806505094963425401175510416864929601220556158569443747
c1 = 162748414223789761394460782826898119391141740806482454071194519203564908810413303814740022407058841033519066268223118999 75800846804242094953030780612051228489046483192196465887209940192492798634629810153294837247478239915137141724788863067032900 44871781158393304147301058706003793357846922086994952763485999282741595204008663847963539422096343391464527068599046946279309 03721285993130333550745514600139032655066853166549324529383900983246866839082028266498406639905140322799006803222638222217347 8078505888238749583237980643698405005689247922901342204142833875409505180847943212126302482358445768662608278731750064815

n2 = 222576053205255840781808890735232239739241929843538471371646051869566296759389295853863923276720655243381764024964140140 83816446508860530887742583338880317478862512306633061601510404960095143941320847160562050524072860211772522478494742213643890 02744399218336267897042604676563094664433909314913914338875279493280695658988450356917522685041927109533679845623889900988310 07935157445799458544814301948793607653462364180193846440952572428116293931644024982610660773393048752122508979184204278140001 42751282805980632089867108525335488018940091698609890995252413007073725850396076272027183422297684667565712022199054289711
c2 = 274260069544183655946955370283109837594864191540910697615784037797812391200739875362346111265979620991886698548047191139 33627977536244795376468025104204150394618321180188490305806752498175769268583635416831357772393220027418201459442861091720662 59843766755795255913189902403644721138554935991439893850589677849639263080528599197595705927535430942463184891689410078059090 16649701719 6424586116535915712965147141775026549870636328195690774259990189286665844641289108474834973710730426105047318959307995062
p = gmpy2.gcd(n1,n2)
q = n1 // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c1,d,n1)
print(binascii.unhexlify(hex(m)[2:]))

Run to get flag{m0_bv_hv_sv}

easyrsa3

Import e1,e2,n1,n2,c1,c2

Carry out a common module attack (note that the two n’s are the same, only enter them once otherwise an error will be reported)

plain text to character

flag{sh4r3_N}

easyrsa4

Here e is very small, it should be a small exponential attack

After importing, perform a small exponential attack and convert the plain text into characters.

flag{Sm4ll_eee}

easyrsa5

Import e, n, c and perform Wiener attack

Convert plain text to characters to get flag

flag{very_biiiiig_e}

easyrsa6

First decompose n

These five numbers are all prime numbers, also called Fermat numbers. We have already performed Fermat decomposition before.

Here we import e as 65537, import the ciphertext c, and import the decomposed p and q

The private key can be calculated

Continue to calculate the plaintext

Convert plain text to characters

flag{ p & amp;q_4re_t00_c1o5ed}