eddsa.py

# -*- mode: python; coding: utf-8 -*-
# Bugs in draft:
# + Indentation issues in Section 6.

import hashlib
class EdDSA:
    def encode():
        pass

    def __init__(self, phflag=0, ctx=None):
        self.phflag = phflag
        self.ctx = ctx
        self._x=0
        self._y=0

    def sign(msg, key, F=None, C=None):
        h = hashlib.sha512(key)
        self.dom2(F, C)

class Ed25519(EdDSA):
    # p = pow(2,255) - 19
    # d = -121665 * pow(121666, p - 2, p) % p
    # YP= 4 * pow(5, p - 2, p) % p
    # L = pow(2,252) + 27742317777372353535851937790883648493
    p = 57896044618658097711785492504343953926634992332820282019728792003956564819949L
    a = -1
    b = 256
    c = 3
    d = 37095705934669439343138083508754565189542113879843219016388785533085940283555L
    XP = 15112221349535400772501151409588531511454012693041857206046113283949847762202L
    YP = 46316835694926478169428394003475163141307993866256225615783033603165251855960L
    B = (XP, YP, 1, XP * YP % p)
    # BUG: Why L and not q like in the ed25519 paper
    L = 7237005577332262213973186563042994240857116359379907606001950938285454250989L

    def __init__(phflag=0, ctx=None):
        super(EdDSA, self).__init__(phflag=0)

    def dom2(x, y):
        return ""

    def PH(msg):
        return msg

    def curve25519(s, bx, by):
        pass

    def public_key(private):
        h = hashlib.sha512(key)
        s = 0
        for i in range(32)[::-1]:
            o = ord(h[i])
            if i == 0:
                o = o & 0xf8
            elif i == 31:
                o = (o & 0x7f) | 0x40
            s = (s<<8) + o
        x = s
        t = EdwardsPoint()
        t.x,t.y,t.z=XP, YP, 1
        # A=[s]B
        # A = self.curve25519(s, self.XP, self.YP)
        while x > 0:
            if (x % 2) > 0:
                r = r + s
            t = t.double()
            x = x // 2
        #
        return self.encode(A)

class Ed488(EdDSA):
    pass

def power(x, y, m):
    if (y == 0):
        return 1
    p = power(x, y/2, m) % m
    p = (p * p) % m
    return p if (y % 2 == 0) else (x * p) % m

def gcd(a, b):
    if (a == 0):
        return b
    return gcd(b % a, a)

def mod_inv(a, m):
    """
    http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
    """
    if (gcd(a, m) != 1):
        raise ValueError
    return pow(a, m - 2, m)

def string2int(s):
    ret = 0
    for c in s[::-1]:
        ret = (ret<<8) + ord(c)
    return ret

def on_curve(x,y): return ((y*y-x*x)-(1+d*x*x*y*y)) % P == 0

def recover_x(xs, y):
    # x = ± sqrt((y*y - 1)/(d*y*y + 1))
    p = Ed25519.p
    modp_sqrt_m1 = pow(2, (p-1) // 4, p)
    d = Ed25519.d
    y2 = y * y
    x2 = (y2 - 1) * pow(d * y2 + 1, p-2, p)
    if x2 == 0:
        if xs:
            return None
        else:
            return 0
    x = pow(x2, (p+3) // 8, p)
    if (x * x - x2) % p != 0:
        x = x * modp_sqrt_m1 % p
    if (x * x - x2) % p != 0:
        return None
    if (x & 1) != xs:
        x = p - x
    return x

def add_point(P,Q):
    p = (2**255 -19)
    A = (P[1]-P[0])*(Q[1]-Q[0])
    B = (P[1]+P[0])*(Q[1]+Q[0])
    C = 2 * P[3] * Q[3] * Ed25519.d
    D = 2 * P[2] * Q[2]
    E = B-A
    F = D-C
    G = D+C
    H = B+A
    return (E*F % p, G*H % p, F*G % p, E*H % p)

def double_point(P):
    p = (2**255 -19)
    A=P[0]*P[0]
    B=P[1]*P[1]
    Ch=P[2]*P[2];
    C=Ch+Ch
    H=A+B
    XYS=P[0]+P[1]
    E=H-XYS*XYS
    G=A-B
    F=C+G
    # BUG: no (mod p) in the draft
    return (E*F % p, G*H % p, F*G % p, E*H % p)

def mul_point(s, P):
    Q = (0, 1, 1, 0)
    while s > 0:
        # BUG: not a constant time algorithm
        if s & 1:
            Q = add_point(P, Q)
        P = double_point(P)
        s >>= 1
    return Q

def from_be(s):
    """
    http://stackoverflow.com/questions/444591/convert-a-string-of-bytes-into-an-int-python
    """
    return sum(ord(c) << (i * 8) for i, c in enumerate(s[::-1]))

def from_le(s):
    """
    http://stackoverflow.com/questions/444591/convert-a-string-of-bytes-into-an-int-python
    """
    return sum(ord(c) << (i * 8) for i, c in enumerate(s))

secret = "9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60"
public = "d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a"
signature = "e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b"

def secret_expand(secret):
    h = hashlib.sha512(secret).digest()
    # BUG: Section 5.1.5: Which are "the lower 32 bytes"? 0 through 31?
    s = from_le(h[0:Ed25519.b // 8])
    s &= (1 << 255) - 8
    s |= (1 << 254)
    return (s, h[Ed25519.b // 8:])

def secret_to_public(secret):
    (s, t) = secret_expand(secret)
    A = mul_point(s, Ed25519.B)
    return compress(A)

def decompress(s):
    y = from_le(s)
    xs = y >> 255
    y &= (1 << 255) - 1
    x = recover_x(xs, y)
    if x is None:
        raise ValueError
    return (x, y, 1, x*y % Ed25519.p)

def compress(P):
    mod_invp_Z = mod_inv(P[2], Ed25519.p)
    x = P[0] * mod_invp_Z % Ed25519.p
    y = P[1] * mod_invp_Z % Ed25519.p
    y |= (x & 1) << 255
    s = ""
    for i in range(Ed25519.b // 8):
        s += chr(y & 0xff)
        y >>= 8
    return s

print "%s (sec)" % secret
print "%s (pub)" % public

pub = secret_to_public(secret.decode('hex')).encode('hex')
print "%s (public key %s)\n" % (pub, "OK" if pub == public else "ERR")

class EdwardsPoint:
    def __add__(self, y):
        pass
    def init_point(self,x,y):
        self.x=x
        self.y=y
        self.z=1
        self.t
    def double(self):
        tmp=EdwardsPoint()
        tmp.init_point(0,1)
        A=self.x*self.x
        B=self.y*self.y
        Ch=self.z*self.z
        C=Ch+Ch
        H=A+B
        xys=self.x+self.y
        E=H-xys*xys
        G=A-B
        F=C+G
        tmp.x,tmp.y,tmp.z,tmp.t=E*F,G*H,F*G,E*H
        return tmp

def equal_point(P, Q):
    if (P[0] * Q[2] - Q[0] * P[2]) % Ed25519.p != 0:
        return False
    if (P[1] * Q[2] - Q[1] * P[2]) % Ed25519.p != 0:
        return False
    return True

def verify(msg, key, sig, ctx=None, phflag=None):
    # sB = R + H(R, A, M)A
    Rs,S = sig[:Ed25519.b // 8], sig[Ed25519.b // 8:]
    R = decompress(Rs)
    A = decompress(key)
    s = from_le(S)
    k = from_le(hashlib.sha512(Rs + key + msg).digest()) % Ed25519.L
    kA = mul_point(k, A)
    sB = mul_point(s, Ed25519.B)
    return equal_point(sB, add_point(R, kA))

def sign(msg, key, ctx=None, phflag=None):
    (s, pfx) = secret_expand(key)
    r = from_le(hashlib.sha512(pfx + msg).digest()) % Ed25519.L
    R = compress(mul_point(r, Ed25519.B))
    A = compress(mul_point(s, Ed25519.B))
    k = from_le(hashlib.sha512(R + A + msg).digest()) % Ed25519.L
    s = (r + k * s) % Ed25519.L
    S = ""
    for i in range(Ed25519.b // 8):
        S += chr(s & 0xff)
        s >>= 8
    return R + S

print "%s (sig)" % signature
sig = sign("", secret.decode('hex')).encode('hex')
print "%s (signature %s)" % (sig, "OK" if sig == signature else "ERR")
print "(verify %s)\n" % ("OK" if verify("", public.decode('hex'), signature) else "ERR")

secret = "4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb"
public = "3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c"
message = "\x72"
signature = "92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00"

print "%s (sig)" % signature
sig = sign(message, secret.decode('hex')).encode('hex')
print "%s (signature %s)" % (sig, "OK" if sig == signature else "ERR")
print "(verify %s)\n" % ("OK" if verify(message, public.decode('hex'), signature.decode('hex')) else "ERR")