ed25519.py

import hashlib

class Global(object):

	q = 2**255 - 19
	l = 2**252 + 27742317777372353535851937790883648493

	d = -4513249062541557337682894930092624173785641285191125241628941591882900924598840740
	bx = 15112221349535400772501151409588531511454012693041857206046113283949847762202
	by = 46316835694926478169428394003475163141307993866256225615783033603165251855960

def _sha256(m):
	return hashlib.sha256(m).digest()

def _hash(m):
	return hashlib.sha512(m).digest()

#
# use `pow(x, e, m)` instead
#

if 0:
	def exp_mod(x, e, m):
		if e == 0:
			return 1

		t = exp_mod(x, e/2, m)**2 % m
		if e & 1:
			t = (t*x) % m

		return t

def inv(x):
	return pow(x, Global.q-2, Global.q)

def square(x):
	return (x * x) % Global.q

def mult(x, y):
	return (x * y) % Global.q

def add(x, y):
	return (x + y) % Global.q

def edwards_add(x1, y1, z1, x2, y2, z2):
	# 11M + 1S + 6A

	A = mult(z1, z2)
	B = square(A)
	C = mult(x1, x2)
	D = mult(y1, y2)
	E = mult(d, mult(C, D))
	F = add(B, -E)
	G = add(B, E)
	H = add(C, D)

	x3 = mult(A, mult(F, add(mult(add(x1, y1), add(x2, y2)), -H)))
	y3 = mult(A, mult(G, H))
	z3 = mult(F, G)
	return x3, y3, z3

def edwards_double(x, y, z):
	# 3M + 4S + 6A

	sum2 = square(add(x, y))
	x2 = square(x)
	y2 = square(y)
	z2 = square(z)

	e = add(x2, y2)
	f = add(x2, -y2)
	j = add(add(z2, z2), f)

	x3 = mult(add(e, -sum2), j)
	y3 = mult(f, e)
	z3 = mult(f, j)
	return x3, y3, z3

def edwards_add_b(x, y, z):
	# 10M + 1S + 6A

	B = square(z)
	C = mult(x, Global.bx)
	D = mult(y, Global.by)
	E = mult(Global.d, mult(C, D))
	F = add(B, -E)
	G = add(B, E)
	H = add(C, D)

	x3 = mult(z, mult(F, add(mult(add(x, y), add(Global.bx, Global.by)), -H)))
	y3 = mult(z, mult(G, H))
	z3 = mult(F, G)
	return x3, y3, z3


#def scalar_multiply_recursive(e):
#	if e == 0:
#		return 0, 1
#
#	qx, qy = scalar_multiply_recursive(e/2)
#	qx, qy = edwards(qx, qy, qx, qy)
#	if e & 1:
#		qx, qy = edwards(qx, qy, bx, by)
#
#	return qx, qy


def scalar_multiply(e):

	mask, num_bits = 0, 0
	while e:
		mask = mask << 1 | (e & 1)
		e >>= 1
		num_bits += 1

	x, y, z = 0, 1, 1
	for n in xrange(num_bits):
		x, y, z = edwards_double(x, y, z)
		if mask & 1:
			x, y, z = edwards_add_b(x, y, z)
		mask >>= 1

	z_inv = inv(z)
	x = mult(x, z_inv)
	y = mult(y, z_inv)
	return x, y


def encode_int(y):
	bits = [(y >> i) & 1 for i in xrange(256)]
	return ''.join([
		chr(sum([bits[i * 8 + j] << j for j in xrange(8)]))
		for i in xrange(256/8)
	])


def encode_point(x, y):
	bits = [(y >> i) & 1 for i in xrange(256 - 1)] + [x & 1]
	return ''.join([
		chr(sum([bits[i * 8 + j] << j for j in xrange(8)]))
		for i in xrange(256/8)
	])


def bit(h, i):
	return (ord(h[i/8]) >> (i % 8)) & 1


def hint(m):
	h = _hash(m)
	return sum(2**i * bit(h, i) for i in xrange(512))


def multiply_and_encode(scalar):
	x, y = scalar_multiply(scalar)
	return encode_point(x, y)


class KeyPair(object):

	def __init__(self, sk):
		h = _hash(sk)
		a = 2**(256-2) + sum(2**i * bit(h, i) for i in xrange(3, 256-2))
		self.half = h[32:64]
		self.a = a
		self.pk = multiply_and_encode(a)

	def sign(self, m):
		r = hint(self.half + m)
		rp = multiply_and_encode(r)
		s = (r + hint(rp + self.pk + m) * self.a) % Global.l
		return rp + encode_int(s)


def to_hex(x):
	return ':'.join(ch.encode('hex') for ch in x)

seed = "wegusyduighdsjgm"
keys = KeyPair(seed)
print to_hex(keys.sign("fshgeytfsdyydtrsred"))