blind_solution.py

#!/usr/bin/env python2
# encoding: utf-8
from pwn import *
from Crypto.Util.number import long_to_bytes


def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
 
    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1



maxN = 151


host, port = '78.46.149.10 13373'.split(' ')
port = int(port)


if args['REMOTE']:
    conn = remote(host, port)
else:
    conn = process('./vuln.py')


def mul(x, y):
    x = long_to_bytes(x).rjust(16, '\x00').encode('hex')
    y = long_to_bytes(y).rjust(16, '\x00').encode('hex')

    conn.sendline('mul {} {}'.format(x, y))
    return int(conn.recvline().strip(), 16)

def inv(x):
    x = long_to_bytes(x).rjust(16, '\x00').encode('hex')
    conn.sendline('inv {}'.format(x))
    return int(conn.recvline().strip(), 16)

def dhp(x, y):
    x = long_to_bytes(x).rjust(16, '\x00').encode('hex')
    y = long_to_bytes(y).rjust(16, '\x00').encode('hex')

    conn.sendline('dhp {} {}'.format(x, y))
    return int(conn.recvline().strip(), 16)

def solve(x):
    conn.sendline('sol {}'.format(x))
    conn.interactive()
    return conn.recvline().strip()

memoize = {}

def _dhp(x,y):
    if x*y in memoize:
        return memoize[x*y]
    res = dhp(x, y)
    memoize[x*y] = res
    return res


def _pow(x, y):
    res = enc1
    while y > 0:
        if y & 1:
            res = _dhp(res, x)
        y /= 2
        x = _dhp(x, x)
    return res


g = 5
p = 0xfffffed83c17   


factors = [13**4, 2, 3**2, 7, 47, 103, 107, 151]

factors_divided = [140737478663691, 31274995258598, 40210708189626, 9855220662, 5988828879306, 2732766575994, 2630607077826, 1864072565082]

# 281474957327382: 2 3 3 7 13 13 13 13 47 103 107 151


enc1, ency = conn.recvline().strip().split()
enc1 = int(enc1, 16)
ency = int(ency, 16)


values = [0, enc1] # encrypted values [1, 300]

# print(enc1, ency)
log.info(hex(enc1))
log.info(hex(ency))


print "Filling precalculated"
for i in range(2, maxN):
    values.append( mul( values[-1], values[1] ) )

print "Finished precalculated"


E = lambda x: values[x]

 
xq_arr = []
found13 = False

for q in factors:
    ypow = _pow(ency, (p-1)//q)
    for xq in xrange(min(maxN, q)):
        if  ypow == _pow(_pow(E(5), (p-1)//q), xq):
            print "Found for %s: %s" % (q, xq)
            if q == 13**4:
                found13 = True
            xq_arr.append(xq)
            break
    if q == 13**4 and not found13:
        print("not found for 13, exiting")
        exit(1)


x = chinese_remainder(factors, xq_arr)
# print x

print solve(pow(5, x, p))




# czyli jak dobrze rozumiem algorytm
# to y^( (p-1)/q ) dla q ktore jest dzielnikiem (p-1) jest rowne g^(x_q * (p-1)/q) gdzie g to generator Zp* a x_q = x mod q
# tak?
# mozna wtedy bruteforcowac latwo x_q
# i z CRT odzyskać x