Rating:
# Escrime
## Challenge
We have 2 files: [escrime.py](escrime.py) and [out.txt](out.txt). The flag was split in half and each part was encrypted with different RSA key.
## Solution
> I didn't solve this challenge during the CTF.
Analyzing the given code, one can find that both RSA keys share a common prime512. And that primes have been chosen in this form:
After simple transformations one has:
So both n have prime512 as a common divisor. We can calculate it by geting 512-bit prime factor of `gcd`:
```python3
dividors = factor( gcd(n1-1,n2-1))
prime512 = next(filter(lambda v, p: len(bin(v)[2:]) == 512))
```
Going further:
as sum of primes is an even number, so we can divide it by 2
Now we should count bits. Known value (left side) has 1023 bits, prime512 has 512 bits. and
should have 256 bits, sum will have 257, division by 2 gives us 256 bits again. So
is a lot smaller than prime512. It can be skiped as the rest of division by prime512. We are here for integral values, after all:
Do we have to calculate further? To decrypt the flag, we need to find di. To find di, we need to have fii. And what is fii?
And we already have.
[Solution code](sol.py)
