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. 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:

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

The detailed proof can be found in this blog post (highly recommand to read all four parts carefully).

Script

#!/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

flag{thats_the_twinning_pin_to_win}