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.
We're give a list of RSA n(modulus),e(exponent),c(ciphertext)
We notice that all the exponents are the same.
- Firstly, 2 distinct primes are chosen, p and q
- Calculate the modulus with n=pq
- Calculate λ(n)=lcm(p-1,q-1)
- Choose the exponent e such that 1<e<λ(n) and e and n are coprime
- Calculate d=e-1 (mod λ(n))
- Calculate the ciphertext c with c=me (mod n) Decryption is done with m=cd (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=me, we can just calculate m=c1/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 me (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
Find integers Mi and mi such that MiNi+mini=1.
Now calculate C=ΣciMiMi mod N
C=ci mod ni for all i
N is now much larger than 257, so we can just take C1/e and we're done.