

BabyRSA - CrossCTF Quals 2018 (crypto)

Each time I asked for the flag, it gets encoded through RSA. I'm lucky I kept all the values.

out.txt.

Challenge

We're give a list of RSA n(modulus),e(exponent),c(ciphertext)

We notice that all the exponents are the same.

Vulnerability

RSA Algorithm

1. Firstly, 2 distinct primes are chosen, p and q
2. Calculate the modulus with n=pq
3. Calculate λ(n)=lcm(p-1,q-1)
4. Choose the exponent e such that 1<e<λ(n) and e and n are coprime
5. Calculate d=e-1 (mod λ(n))
6. Calculate the ciphertext c with c=m^e (mod n) Decryption is done with m=c^d (mod n)

Common prime factor attack

If the random prime generator is flawed, it could produce 2 prime numbers that are the same, and the message can easily be found by calculating p and q, however, every single pair of primes is coprime.

Low exponent attack

Another option is if c=m^e, we can just calculate m=c^1/e and we're done. This would require the exponent to be much smaller compared to the modulus.

Since we're given many pairs of c,n,e, we can use the Chinese Remainder Theorem to calculate m^e (mod n1*n2*n3...), then we can take the 257th root. This assumes message remains the same

Chinese remainder theorem

Let N be the product of all the modulus

Let N_i=N/n_i

Find integers M_i and m_i such that M_iN_i+m_in_i=1.

Now calculate C=Σc_iM_iM_i mod N

C=c_i mod n_i for all i

N is now much larger than 257, so we can just take C^1/e and we're done.

exploit

Flag:crossctf{Ha5tad_ch4ll3nGes_aRe_Gett1ng_b0riNg_n0w_Eh}