In this challenge, we are given a public key with public exponent and public modulus The ciphertext that we are supposed to decrypt is

Using e.g. msieve, this can be factored into three distinct prime factors:

, and .

First, we compute for all . Then, using PARI/GP, we execute the following operation `factor(x^3 - Mod(c_i, p_i))`

for each .

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]`

`L1 x L2 x L3`

.

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

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

.

Advertisements