0CTF – RSA? writeup

In this challenge, we are given a public key with public exponent e = 3 and public modulus N = 23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067. The ciphertext that we are supposed to decrypt is c = 2485360255306619684345131431867350432205477625621366642887752720125176463993839766742234027524.

Using e.g. msieve, this can be factored into three distinct prime factors:
p_1 = 26440615366395242196516853423447, p_2 = 27038194053540661979045656526063 and p_3 = 32581479300404876772405716877547.

First, we compute c_i = c \bmod p_i for all i = 1,2,3. Then, using PARI/GP, we execute the following operation factor(x^3 - Mod(c_i, p_i)) for each i.

For each such operation, we obtain a few roots:

L1 = [13065746773528615679127725156712, 19061253618972528384862766945681, 20754230340289340329043214744501]
L2 = [7421220485922146514530548901251]
L3 = [19177276190995540727122167162170, 19553467714697919836353088849918, 26432214695116292981336177743006]

Running a CRT for all possible combinations in [a,b,c] \leftarrow L1 x L2 x L3.

m = chinese_remainder(n, [-a,-b,-c])

we find the flag 0ctf{HahA!Thi5_1s_n0T_rSa~}.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s