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)

Original writeup (https://github.com/death-of-rats/CTF/blob/master/2022/securinets/Escrime/Readme.md).