safecurve.py

#!/usr/bin/env python3

"""
this code is a cleaned version of http://ed25519.cr.yp.to/python/ed25519.py for python3

code released under the terms of the GNU Public License v3, copyleft 2015 yoochan
"""

import collections
import hashlib
import os

Point = collections.namedtuple('Point', ['x', 'y'])

key_mask = int.from_bytes(b'\x3F' + b'\xFF' * 30 + b'\xF8', 'big', signed=False)


class Ed25519():
    length = 256

    def __init__(self):
        self.q = 2 ** 255 - 19
        self.l = 2 ** 252 + 27742317777372353535851937790883648493
        self.d = -121665 * self.inverse(121666)

        self.i = pow(2, (self.q - 1) // 4, self.q)

        self.B = self.point(4 * self.inverse(5))

    def to_hash(self, m):
        return hashlib.sha512(m).digest()

    def from_bytes(self, h):
        """ pick 32 bytes, return a 256 bit int """
        return int.from_bytes(h[0:self.length // 8], 'little', signed=False)

    def to_bytes(self, k):
        return k.to_bytes(self.length // 8, 'little', signed=False)

    def as_key(self, h):
        return 2 ** (self.length - 2) + (self.from_bytes(h) & key_mask)

    def secret_key(self):
        """ pick a random secret key """
        m = os.urandom(1024)
        h = self.to_hash(m)
        k = self.as_key(h)
        return self.to_bytes(k)

    def public_key(self, sk):
        """ compute the public key from the secret one """
        h = self.to_hash(sk)
        a = self.as_key(h)
        c = self.outer(self.B, a)
        return self.point_to_bytes(c)

    def inverse(self, x):
        return pow(x, self.q - 2, self.q)

    def sign(self, message, secret_key, public_key):
        s_h = self.to_hash(secret_key)
        s_d = self.as_key(s_h)

        m_h = self.to_hash(s_h[self.length // 8:self.length // 4] + message)
        m_d = self.from_bytes(m_h)

        R = self.outer(self.B, m_d)

        r_h = self.to_hash(self.point_to_bytes(R) + public_key + message)
        r_d = m_d + self.from_bytes(r_h) * s_d

        return self.point_to_bytes(R) + self.to_bytes(r_d % self.l)

    def verify(self, message, signature, public_key):
        r_b = signature[0:self.length // 8]
        r_h = self.to_hash(r_b + public_key + message)
        r_d = self.from_bytes(r_h)

        s_d = self.from_bytes(signature[self.length // 8:self.length // 4])
        b_j = self.outer(self.B, s_d)

        P = self.bytes_to_point(public_key)
        p_j = self.outer(P, r_d)

        R = self.bytes_to_point(r_b)

        return b_j == self.inner(R, p_j)

    def recover(self, y):
        """ given a value y, recover the preimage x """
        p = (y * y - 1) * self.inverse(self.d * y * y + 1)
        x = pow(p, (self.q + 3) // 8, self.q)
        if (x * x - p) % self.q != 0:
            x = (x * self.i) % self.q
        if x % 2 != 0:
            x = self.q - x
        return x

    def point(self, y):
        """ given a value y, recover x and return the corresponding P(x, y) """
        return Point(self.recover(y) % self.q, y % self.q)

    def is_on_curve(self, P):
        return (P.y * P.y - P.x * P.x - 1 - self.d * P.x * P.x * P.y * P.y) % self.q == 0

    def inner(self, P, Q):
        """ inner product on the curve, between two points """
        x = (P.x * Q.y + Q.x * P.y) * self.inverse(1 + self.d * P.x * Q.x * P.y * Q.y)
        y = (P.y * Q.y + P.x * Q.x) * self.inverse(1 - self.d * P.x * Q.x * P.y * Q.y)
        return Point(x % self.q, y % self.q)

    def outer(self, P, n):
        """ outer product on the curve, between a point and a scalar """
        if n == 0:
            return Point(0, 1)
        Q = self.outer(P, n // 2)
        Q = self.inner(Q, Q)
        if n & 1:
            Q = self.inner(Q, P)
        return Q

    def point_to_bytes(self, P):
        return (P.y + ((P.x & 1) << 255)).to_bytes(self.length // 8, 'little')

    def bytes_to_point(self, b):
        i = self.from_bytes(b)
        y = i % 2 ** (self.length - 1)
        x = self.recover(y)
        if (x & 1) != ((i >> (self.length - 1)) & 1):
            x = self.q - x
        return Point(x, y)


if __name__ == '__main__':
    def hexit(s):
        return ''.join("{0:02X}".format(i) for i in reversed(s))


    ecc = Ed25519()

    alice_sk = b'alicealicealicealicealicealiceal'  # ecc.secret_key()
    alice_pk = ecc.public_key(alice_sk)

    assert (hexit(alice_pk) == 'AFA095BF733298216D0E88A0F2A4FEB15E5FEB73E7FA7522B67594FD2EF770D6')

    message = 'foo bar'.encode('utf8')
    signature = ecc.sign(message, alice_sk, alice_pk)

    import cProfile

    cProfile.run("ecc.sign(message, alice_sk, alice_pk)")

    assert (ecc.verify(message, signature, alice_pk))
    cProfile.run("ecc.verify(message, signature, alice_pk)")

    print("code test: OK")