ed25519 chaumian blind signatures

blindsig.py

from scalar import Scalar
from ed25519 import G, KeyPair, challenge
from group_element import GroupElement

class IssuerSession(object):

    def __init__(self, kp):
        self.x = kp.x
        self.P = kp.P
        self.k = Scalar.random()
        self.R = self.k * G

    def public_key(self):
        return self.P

    def public_nonce(self):
        return self.R

    def sign(self, challenge):
        return self.k + challenge * self.x


class UserSession(object):

    def __init__(self, P, R):
        self.a = Scalar.random()
        self.b = Scalar.random()
        self.R = R + self.a * G + self.b * P
        self.P = P

    def challenge(self, m):
        return challenge(self.R, self.P, m) + self.b

    def signature(self, s):
        return self.R.serialize() + (s + self.a).serialize()


if __name__ == "__main__":
    keys = KeyPair.random()

    issuer = IssuerSession(keys)
    user = UserSession(
        issuer.public_key(),
        issuer.public_nonce()
    )

    message = str.encode('blind message')
    e = user.challenge(message)
    s = issuer.sign(e)
    sig  = user.signature(s)

    print(keys.verify(sig, message))

ed25519.py

import hashlib
import os

from field_element import *
from group_element import *
from scalar import *

#------------------------------------------------------------------------------

G = GroupElement(
    FieldElement(15112221349535400772501151409588531511454012693041857206046113283949847762202),
    FieldElement(46316835694926478169428394003475163141307993866256225615783033603165251855960)
).to_projective()

#------------------------------------------------------------------------------

class KeyPair(object):

    def sign(self, m):
        k = Scalar.hash(self.prefix + m)
        R = k * G
        e = challenge(R, self.pk, m)
        s = k + e * self.x
        return R.serialize() + s.serialize()

    def verify(self, sig, m):
        rb = sig[:32]
        s = Scalar.deserialize(sig[32:])
        e = challenge(rb, self.pk, m)
        res = s * G - e * self.P
        return (res.serialize() == rb)

    @staticmethod
    def from_seed(sk):
        h = _hash(sk)
        x = int.from_bytes(h[:32], "little")
        x &= (1 << 254) - 8
        x |= (1 << 254)

        self = KeyPair()
        self.prefix = h[32:64]
        self.x = Scalar(x)
        self.P = self.x * G
        self.pk = self.P.serialize()
        return self

    @staticmethod
    def random():
        sk = os.urandom(32)
        return KeyPair.from_seed(sk)

#------------------------------------------------------------------------------

class VerificationKey(object):

    def verify(self, R, s, m):
        rb = R.serialize()
        e = challenge(rb, self.pk, m)
        res = s * G - e * self.P
        return (res.serialize() == rb)

    @staticmethod
    def from_point(point):

        self = KeyPair()
        self.P = point
        self.pk = self.P.serialize()
        return self

#------------------------------------------------------------------------------

def challenge(R, P, M):

    if (type(R) == GroupElementProjective):
        R = R.serialize()

    if (type(P) == GroupElementProjective):
        P = P.serialize()

    return Scalar.hash(R + P + bytes(M))

#------------------------------------------------------------------------------

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

field_element.py

class FieldElement(object):

	q = 2**255 - 19

	def __init__(self, x):
		self.x = x

	def __add__(self, other):
		return FieldElement((self.x + other.x) % self.q)

	def __sub__(self, other):
		return FieldElement((self.x - other.x) % self.q)

	def __mul__(self, other):
		return FieldElement((self.x * other.x) % self.q)

	def __neg__(self):
		return FieldElement(self.q - self.x)

	def __str__(self):
		return str(self.x)

	def __and__(self, other):
		return self.x & other

	@staticmethod
	def invert(t):
		return FieldElement(pow(t.x, FieldElement.q - 2, FieldElement.q))

	@staticmethod
	def square(x):
		return FieldElement((x * x) % FieldElement.q)

group_element.py

from field_element import FieldElement

class GroupElementProjective(object):

    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z

    def __add__(self, other):
        # 11M + 1S + 6A

        A = self.z * other.z
        B = A * A
        C = self.x * other.x
        D = self.y * other.y
        E = _d * (C * D)
        F = B - E
        G = B + E
        H = C + D

        x = A * F * ((self.x + self.y) * (other.x + other.y) - H)
        y = A * G * H
        z = F * G
        return GroupElementProjective(x, y, z)

    def __sub__(self, other):
        return self + (-other)

    def __neg__(self):
        return GroupElementProjective(-self.x, self.y, self.z)

    def __str__(self):
        return "({x}, {y}, {z})".format(x = str(self.x), y = str(self.y), z = str(self.z))

    def double(self):
        # 3M + 4S + 6A

        sum2 = (self.x + self.y) * (self.x + self.y)
        x2 = self.x * self.x
        y2 = self.y * self.y
        z2 = self.z * self.z

        e = x2 + y2
        f = x2 - y2
        j = z2 + z2 + f

        self.x = (e - sum2) * j
        self.y = f * e
        self.z = f * j

    def serialize(self):
        return GroupElement.from_projective(self).serialize()

    @staticmethod
    def zero():
        return GroupElementProjective(
            FieldElement(0),
            FieldElement(1),
            FieldElement(1),
        )

class GroupElement(object):

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        res = self.to_projective() + other.to_projective()
        return GroupElement.from_projective(res)

    def __sub__(self, other):
        res = self.to_projective() + (-other).to_projective()
        return GroupElement.from_projective(res)

    def __neg__(self):
        return GroupElement(-self.x, self.y)

    def __str__(self):
        return "({x}, {y})".format(x = str(self.x.x),y = str(self.y.x))

    def to_projective(self):
        return GroupElementProjective(self.x, self.y, FieldElement(1))

    def serialize(self):
        return int.to_bytes(self.y.x | ((self.x.x & 1) << 255), 32, "little")

    @staticmethod
    def deserialize(s):
        y = int.from_bytes(s, "little")
        sign = y >> 255
        y &= (1 << 255) - 1
        x = _recover_x(FieldElement(y), sign)
        return GroupElement(x, y)

    @staticmethod
    def from_projective(p):
        inverse = FieldElement.invert(p.z)
        x = p.x * inverse
        y = p.y * inverse
        return GroupElement(x, y)


_q = FieldElement.q
_d = FieldElement(37095705934669439343138083508754565189542113879843219016388785533085940283555)
_eye = FieldElement(pow(2, (_q - 1) // 4, _q))

def _recover_x(y, sign):

    y2 = y * y
    x2 = (y2 - FieldElement(1)) * FieldElement.invert(_d * y2 + FieldElement(1))

    x = FieldElement(pow(x2.x, (_q + 3) // 8, _q))
    if (x * x != x2):
        x *= _eye

    if (x & 1) != sign:
        x = -x

    return x

scalar.py

import hashlib
import random
from group_element import GroupElementProjective, GroupElement


class Scalar(object):

	l = 2**252 + 27742317777372353535851937790883648493

	def __init__(self, value):
		if (type(value) == Scalar):
			self.x = value.x
		else:
			self.x = value

	def __add__(self, other):
		return Scalar((self.x + other.x) % self.l)

	def __sub__(self, other):
		return Scalar((self.x - other.x) % self.l)

	def __mul__(self, other):
		t = type(other)
		if (t == GroupElementProjective):
			return _scalar_multiply(self.x, other)
		elif (t == GroupElement):
			return GroupElement.from_projective(scalar_multiply(self.x, other.to_projective()))
		elif (t == Scalar):
			return Scalar(self.x * other.x)
		else:
			pass

	def __mod__(self, other):
		return Scalar(self.x % other)

	def __str__(self):
		return str(self.x)

	@staticmethod
	def hash(m):
		h = hashlib.sha512(m).digest()
		return Scalar(int.from_bytes(h, "little") )

	@staticmethod
	def random():
		return Scalar(random.randint(1, Scalar.l - 1))

	def serialize(self):
	    return int.to_bytes(self.x, 32, "little")

	@staticmethod
	def deserialize(s):
		return Scalar(int.from_bytes(s, "little"))


def _scalar_multiply(scalar, point):

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

	zero = GroupElementProjective.zero()
	res = zero
	for _ in range(num_bits):
		res.double()
		res = res + point if (mask & 1) else res + zero
		mask >>= 1

	return res