**Tags:** rsa crypto

Rating:

# 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}

```