BabyRSA2 - CrossCTF Quals 2018 (crypto)
Each time I asked for the flag, it gets encoded through RSA.... again... I'm lucky I kept all the values... AGAIN!
We're give a list of RSA n(modulus),e(exponent),c(ciphertext)
We notice that all the modulus 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 modulus attack
Since pq mod n=(p mod n)(q mod n)mod n and ma mb=mab, if we can find numbers x1x2... such that Σxiei=1, then we can calculate m1, assuming all the messages are the same.
Bézout's identity states that if x and y are coprime, then integers a,b exists such that ax+by=1, however, all our exponents share common prime factors, even any 4 exponents share a common factor. However, all 5 exponents do not share a common factor, thus, it is possible to find x1x2... such that Σxiei=1.
We can use the extended Euclidean algorithm, however, the numbers resulting from it could be pretty huge, so the equation is evaluated by Mathematica, giving us x=[3239,237,735,556,-6676]. For negative numbers, we can calculate the inverse modulo pretty quickly, and evaluating Πmxiei (mod n) gives us the flag.