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.


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=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.