# Twinning

## Topics

- RSA twin primes

## Analysis

The challenge name suggests that this RSA cryptosystem is weak under **twin primes** attack. To verify this fact, you can connect to the server multiple times and query the factors of the given `n` from [factordb](http://factordb.com/). This challenge could be done manually, but let's still automate it for learning purposes.

The nice thing about twin primes is that we don't even need to factor anything. The factors `p` and `q` satisfy the following elementary equations:

```plaintext
p = abs(int(sqrt(n + 1)) - 1)
q = abs(int(-sqrt(n + 1)) - 1)
```

The detailed proof can be found in [this blog post](https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-4/) (highly recommand to read all four parts carefully).

## Script

```python
#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import inverse, long_to_bytes
from math import sqrt

#--------setup--------#

host, port = "jh2i.com", 50013

#--------interact--------#

r = remote(host, port)

# read data
data = r.readuntil("What is the PIN?\n").decode().split()

# parse data
data[12] = data[12].strip("()").split(",")
e, N = int(data[12][0]), int(data[12][1])
c = int(data[-5])

# compute twin primes
p = abs(int(sqrt(N + 1)) - 1)
q = abs(int(-sqrt(N + 1)) - 1)

# rsa
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = str(pow(c, d, N))

# print flag
r.sendline(m)
log.info(r.readall().decode())
```

## Flag

```plaintext
flag{thats_the_twinning_pin_to_win}
```