# 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!

## Challenge

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

We notice that all the modulus 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=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.

exploit

Flag:`crossctf{RSA_Challenges_Are_Too_Easy}`