Skip to content

Instantly share code, notes, and snippets.

@terjanq
Last active December 9, 2018 14:14
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save terjanq/609364fb54554abfad1df47484d99116 to your computer and use it in GitHub Desktop.
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment