# 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:
```plaintextp = 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 python3from pwn import *from Crypto.Util.number import inverse, long_to_bytesfrom math import sqrt
#--------setup--------#
host, port = "jh2i.com", 50013
#--------interact--------#
r = remote(host, port)
# read datadata = r.readuntil("What is the PIN?\n").decode().split()
# parse datadata[12] = data[12].strip("()").split(",")e, N = int(data[12][0]), int(data[12][1])c = int(data[-5])
# compute twin primesp = abs(int(sqrt(N + 1)) - 1)q = abs(int(-sqrt(N + 1)) - 1)
# rsaphi = (p - 1) * (q - 1)d = inverse(e, phi)m = str(pow(c, d, N))
# print flagr.sendline(m)log.info(r.readall().decode())```
## Flag
```plaintextflag{thats_the_twinning_pin_to_win}```