ISITDTU CTF - Simple RSA

simple_rsa.py

from Crypto.Util.number import *
import random
flag = 'Hidden'
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        #raise Exception('modular inverse does not exist')
        print "aaa"
    else:
        return x % m
def next_prime(n):
    num = n + 1
    while True:
        if isPrime(num):
            return num
        num += 1
p = random.randint(1<<251,1<<252)
i = 10
p = next_prime(p)
p1 = next_prime(p*10)
p2 = next_prime(p1*10)
p3 = next_prime(p2*10)

N = p*p1*p2*p3
e = 65537
c = pow(bytes_to_long(flag),e,N)
print c
#153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
print N
#603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231

solve_rsa.py

from Crypto.Util.number import *
from gmpy2 import *

c = 153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
N = 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231

brute_start = int(iroot(N/1000000,4)[0])
i = 1
while True:
	p = brute_start + i
	if N % p == 0:
		print p
		break
	p = brute_start - i
	if N % p == 0:
		print p
		break
	i += 1

# Took from SO
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

print p
p1 = next_prime(p*10)
p2 = next_prime(p1*10)
p3 = next_prime(p2*10)

phi = (p-1)*(p1-1)*(p2-1)*(p3-1)
e = 65537
d = modinv(e,phi)

print long_to_bytes(pow(c,d,N))