# Easy RSA 2 Writeup
### ISITDTU Quals 2019 - crypto 919 - 16 solves
> Let's continue with RSA
#### Observations
The problem is to crack [multi-prime RSA](http://cacr.uwaterloo.ca/techreports/2006/cacr2006-16.pdf). Modulus `n` and private key exponenet `d` are generated by the following code.
```pythonp1 = getPrime(512)p2 = gmpy2.next_prime(p1)q1 = getPrime(512)q2 = gmpy2.next_prime(q1)n = p1 * p2 * q1 * q2phi = (p1 - 1) * (p2 - 1) * (q1 - 1) * (q2 - 1)d = gmpy2.invert(e,phi)```
As the code says, all the values of primes `p1`, `p2`, `q1`, `q2` are very close to each other, which means value of `p1 * p2` and `q1 * q2`, `p1 * q2` and `p2 * q1` are also very close. Let `c` be the difference between those two values
#### Vulnerability: factors are too close!
`n`'s bit length is 2047. There is a high chance that `c` differs less then `{4 * N}^{1 / 4}` from `sqrt{N}`, `n` can be factored by using [fermat factorization method](https://en.wikipedia.org/wiki/Fermat%27s_factorization_method). By factoring `n`, I got all the values of `p1 * q1`, `p1 * q2`, `p2 * q1`, `p2 * q2`. By calculating greatest common divisor with `p1 * q1` and `p1 * q2`, I can recover `p1`!. All the other factors can be recovered by using a similar manner. Now it is straigtforward. Calculate `phi` and `d` and get the flag. I get the flag:
```ISITDTU{C0ngratu1ati0ns_Attack_RSA_Multi_prim3!!!!}```
I think my solution is unintended since I didn't use the values below. Wondering how to solve the challenge using these information...
```pythonk1 = pow(p1 + q2, e, n)k2 = pow(p2 + q1, e, n)```
Code for parameter generation: [task.py](task.py)
Parsed parameters: [config.py](config,py)
Exploit code: [solve.py](solve.py)