secret.sage

from sage.all import *

def lagrange_delta(u,S):
  d = 1
  var("x")
  for j in S:
    if j == u: continue
    d *= (x-j)/(u-j)
  return d

def eval_poly(ex, u):
  return sum([x * u ^ y for x,y in ex.coefficients()])

def get_random():
  return ZZ.random_element(2**256)

def genpoly(rank, m):
  expr = m
  var("x")
  for i in xrange(1, rank):
    expr += get_random() * x ** i
  return expr

def encrypt(n, m):
  rank = n
  ex = genpoly(rank, ZZ(m))

  keys = []
  for i in xrange(n):
    r = get_random()
    t = (r, eval_poly(ex, r))
    keys.append(t)

  return keys

def decrypt(keys):
  keys = dict(keys)
  ex = 0
  for x in keys.keys():
    ex += keys[x] * lagrange_delta(x, keys.keys())
  print "[+] Constructed Polynomial :", ex.expand().simplify()
  return ex.coefficients()[0][0]

m = encrypt(16, int("test_message".encode("hex"), 16))
print m

print ("%x"%int(decrypt(m))).decode("hex")