Christmas CTF 2016 Stupid RSA

rsa.py

from pwn import *


import threading
from gmpy2 import *
import random, string

#======================================================================================
# function "xgcd" tackes positive integers a, b as input
# and return a triple (g, x, y), such that ax + by = g = gcd(a, b).
def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

# An application of extended GCD algorithm to finding modular inverses:
def mulinv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n
# - https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
#=====================================================================================

def GeneratePrime(Base, randomST):
    while True:
        k1 = mpz_urandomb(randomST, 1023)
        k2 = k1 + mpz_urandomb(randomST, 1023)

        #Add Random Number to Bignumber, then find next prime number
        p1 = next_prime(Base+k1)
        p2 = next_prime(Base+k2)
        #Prime Checking
        if is_prime(p1, 100) and is_prime(p2, 100):
            return [p1, p2]

def GenerateKeys(p, q):
    e = 65537
    n = p * q
    pin = (p-1)*(q-1)
    d = mulinv(e, pin)
    return [e, d, n]




randomST = random_state()
BaseNumber = (mpz(2) ** mpz(2048)) + mpz_urandomb(randomST, 512)
p, q = GeneratePrime(BaseNumber, randomST)
PublicKey, PrivateKey, N = GenerateKeys(p, q)
r = remote('52.175.158.46', 40002)
r.recvuntil(' : ')
c = int(r.recvline())
print c
r.recvuntil(' : ')
e = int(r.recvline())
print e
r.recvuntil(' : ')
n = int(r.recvline())
print n
assert n == N
result = pow(c, PrivateKey, N)
print result
r.sendline(str(result))
r.interactive()