# Twinning

The name of the challenge is a subtle hint towards Twin primes, i.e. the RSA primes `p`

and `q`

being twin primes, at a difference of two.

How does that help?

We can now easily factor `n`

since we have another relation, namely

```
q = p + 2 and
p*q = N
q^2 - q*p = N
( q - 1 )^2 = N + 1
q = sqrt( N + 1 ) + 1
p = sqrt( N + 1 ) - 1
```

One can easily solve a quadratic equation to find `p`

Once `p`

and `q`

are found, rest is a piece of cake

Although the time was not a concern, I still wrote a small script

```
from pwn import remote
import gmpy2
import re
HOST, PORT = "jh2i.com", 50013
REM = remote(HOST, PORT)
data = REM.recvuntil(b'What is the PIN?')
print(data.decode())
e_n = re.search(b'(\d+),(\d+)',data)
e = int(e_n[1])
n = int(e_n[2])
PIN = int(re.search(b'is (\d+)',data)[1])
def factor(n,e):
a = gmpy2.iroot(n+1,2)[0]
phi = (a-2)*(a)
return gmpy2.invert(e,phi) # returns d
DECRYPTED_PIN = pow(PIN, factor(n,e), n)
REM.sendline(str(DECRYPTED_PIN).encode())
print(REM.recvline().decode())
print(REM.recvline().decode())
print(REM.recvline().decode())
```

### flag{thats_the_twinning_pin_to_win}

PREVIOUSCTFs-2020