JHtC4BSK barsa

seed = 476283116406539741845175463956657874046958850596520333086272652099928678076182181180321  # backdoor_modulus
k = 1024
e = 65537
e_backdoor = 17
while True:
    p = random_nbit_prime(k/2)
    if gcd(e, p-1) == 1 and int(bin(p)[:k/4+32],2) < seed:
        break
qv = random_nbit_prime(k/2)
nv = p*qv
t = bin(nv)[:k/8]
u = bin(pi(seed, int(bin(p)[:k/4+32],2)))
u = '0'*(k/4+32 - len(u)) + u
l = bin(nv)[-(5*k)/8 + 32:]
n = int(t + u + l, 2)
q = n/p + 1 - ((n/p)%2)
while gcd(e, q-1) > 1 or not is_prime(q):
    m = random_nbit_integer(k/8-40)
    m += (1+(m%2)) / 2
    q = q^m
    n = p*q
d = modinv(e, (p-1)*(n/p-1))

#!/usr/bin/env python

import requests
from gmpy import gcd, invert, mpz, sqrt
from hashlib import sha256
from random import randint
import subprocess

print "Start"
url = 'http://jhtc4bsk.jhtc.pl:30902/'
seed = 476283116406539741845175463956657874046958850596520333086272652099928678076182181180321
e = 65537
enc_key = {}
sig_key = {}

#get keys modules
m = {}
auth = {}
c = {}
s = {}
c_hash = {}
for x in xrange(3):
    m[x] = 'gros23_huehue'+str(x)+str(randint(1,10000)) #have to be unique
    password = 'trolololo'
    auth[x] = requests.post(url+'register', data={'username':m[x], 'password':password}).cookies['auth']

    m[x] = mpz(m[x].encode('hex'), 16)
    c[x], s[x] = auth[x].split('--')
    c_hash[x] = mpz(sha256(c[x].decode('hex')).hexdigest(), 16)
    c[x] = mpz(c[x], 16)
    s[x] = mpz(s[x], 16)

enc_key['n'] = gcd(gcd(pow(m[1], e) - c[1], pow(m[2], e) - c[2]), pow(m[0], e) - c[0])
print "Encryption key modulus:", enc_key['n']
sig_key['n'] = gcd(gcd(pow(s[1], e) - c_hash[1], pow(s[2], e) - c_hash[2]), pow(s[0], e)- c_hash[0])
print "Signin key modulus:", sig_key['n']

#get private key of backdoor, seed == backdoor_modulus
e_backdoor = 17
p_backdoor = sqrt(seed)
d_backdoor = invert(e_backdoor,(p_backdoor-1)*p_backdoor)

#get 288 most significant bits of p
k = 1024
p_msb = bin(sig_key['n'])[2:][k/8:(3*k)/8 + 32]

#decrypt 288 msb of p
p_msb = pow(int(p_msb,2), d_backdoor, seed)
print "Signin key 288 msb of p:", bin(p_msb)[2:]

#compute whole p
p = mpz(subprocess.check_output(['sage', './partial_p.sage', str(sig_key['n']), str(p_msb)]))
print "Signin key p:", p
assert sig_key['n']%p == 0

#compute d
q = sig_key['n'] / p
sig_key['d'] = invert(mpz(e), mpz((p-1)*(q-1)))
print "Signin key d:", sig_key['d']

#cook cookie
m = int('admin'.encode('hex'), 16)
c = pow(m, e, enc_key['n'])
c = hex(c)[2:].strip('L')
s = pow(int(sha256(c.decode('hex')).hexdigest(),16), sig_key['d'], sig_key['n'])
s = hex(s)[2:].strip('L')
admin_cookie = c+'--'+s
print "Cookie:", admin_cookie

#get flag
resp = requests.get(url, cookies={'auth': admin_cookie})
print resp.text

#!/usr/bin/env sage
import sys

if len(sys.argv) < 2:
    print "Usage: ./partial_p n p_msb"
    sys.exit(1)

n = Integer(sys.argv[1])
p_msb = Integer(sys.argv[2])

pbits = p_msb.nbits()
p_msb = p_msb*2^(512-pbits)
PR.<x> = PolynomialRing(Zmod(n))
f = p_msb + x
#print '{} MSB bits of p is known'.format(pbits)

x0 = f.small_roots(X=2^(512-pbits), beta=0.4)[0]
print x0 + p_msb