exploit.py

from Crypto.Util.number  import *
from functools import reduce
import random
p = 0xfffffed83c17
phi = p - 1

def factor():
    c = phi
    res = []
    for i in range(2,152):
        e = 0
        while c % i == 0:
            c = c // i
            e +=  1
        if e:
            res.append((i,e))
    return res

counter = 0
def incr():
    global counter
    counter += 1
    if counter % 0x10 == 0:
        print("counter:",hex(counter))
    
memo = dict()

import subprocess

#cmd = ['python3', 'vuln.py']
cmd = ['nc','78.46.149.10','13373']
proc = subprocess.Popen(cmd, 
        stdout = subprocess.PIPE, stdin = subprocess.PIPE, universal_newlines = True)
one, target = proc.stdout.readline().split()

class G:
    def __init__(self, val):
        assert( type(val) == str)
        self.val = val

    def __add__(self, other):
        key = ('+',self.val, other.val)
        global proc
        if key in memo:
            return memo[key]
        incr()
        proc.stdin.write(' '.join(['mul',self.val, other.val]) + '\n')
        proc.stdin.flush()
        r = G(proc.stdout.readline().strip())
        # r = G((self.val * other.val) %p) 
        memo[key] = r
        return r
    def __mul__(self, other):
        key = ('*',self.val, other.val)
        global proc
        if key in memo:
            return memo[key]
        incr()
        proc.stdin.write(' '.join(['dhp',self.val, other.val]) + '\n')
        proc.stdin.flush()
        r = G(proc.stdout.readline().strip())
        # r = G((self.val * other.val) %p) 
        memo[key] = r
        return r

    def __pow__(self, k):
        key = ('**', self.val, k)
        if key in memo:
            return memo[key]
        c = One
        d = self
        k0 = k
        while k > 0:
            if k & 1:
                c = c * d
            d = d * d
            k = k // 2
        #assert( c.val == pow(self.val, k0, p))
        memo[key] = c
        return c

    def __eq__(self, other):
        return self.val == other.val
    def __repr__(self):
        return repr(self.val)

One = G(one)
Two = One + One
Eleven = pow(Two, 3) + Two + One

def logPower(g, h, pi, ei):
    x = 0
    ginv = pow(g, pow(pi, ei) - 1)
    assert( g * ginv  == One )
    gamma = pow(g, pow(pi, ei-1))
    #assert( pow(gamma, pi) == One )
    for k in range(ei):
        print(k)
        hk = pow(pow(ginv, x) * h, pow(pi, ei - 1 - k))
        #assert( pow(hk, pi) == One )
        dk = None
        for i in range(pi):
            if pow(gamma, i) == hk:
                dk = i
                break
        assert(dk is not None)
        #assert( pow(gamma, dk) == hk)
        x += pow(pi, k) * dk
    return x

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 * inverse(p, n_i) * p
    return sum % prod

assert( chinese_remainder( [3,5,7], [2,3,2]) == 23)


l = factor()
h = G(target)
g = Eleven

print("h", h)
print("factorize", l)
ns = []
xs = []
for (pi, ei) in l:
    ni = pow(pi, ei)
    d = phi // ni
    gi = pow(g, d) 
    hi = pow(h, d)
    #assert( pow(gi, ni) == One )
    #assert( pow(hi, ni) == One )
    xi = logPower(gi, hi, pi, ei)
    print("xi", xi)
    #assert( pow( gi, xi) == hi )
    ns.append( pow(pi,ei))
    xs.append( xi )
x = chinese_remainder(ns, xs)
y = pow(11, x, p)
print("x",x, "y",y)
proc.stdin.write(' '.join(['sol', str(y)]) + '\n')
proc.stdin.flush()
print(proc.stdout.read())
print(hex(counter))
"""
print( g, h, x , secret, phi, p)
assert( pow(g, x) == h  )
print(x, hex(counter))
"""