ACJT2000 group signature scheme¶

from algorithms.euclidean import gcd, inverse

def safe_prime(n):
    """
    Return a safe prime p in [n/2, n],
    i.e., such that (p-1)/2 is also a prime.
    """
    while True:
        p = random_prime(n, lbound=n/2)
        if Integer((p-1)/2).is_prime():
            return p

def is_QRroot(a, n):
    """
    Assuming n = pq,
    return True if a^2 has order (p-1)(q-1)/4.
    """
    return gcd(a+1, n) == 1 and gcd(a-1, n) == 1

def is_QR(a, p, q):
    """
    Return True if a is a quadratic residue
    modulo n = (2*p+1) * (2*q+1) of order p*q.
    """
    n = (2*p+1) * (2*q+1)
    return is_QRroot(a, n) and pow(a, p*q, n) == 1

def find_QR(n):
    """
    Assuming n = pq, where p and q are safe primes,
    find an element of order (p-1)(q-1)/4.
    """
    while True:
        a = randint(2, n-2)
        if is_QRroot(a, n):
            return Integer(a^2 % n)

def find_element(n):
    """
    Find an element in Z^*_n.
    """
    while True:
        x = randint(2, n-1)
        if gcd(x, n) == 1:
            return Integer(x)

class ACJTParams:
    """
    A class for parameters of the ACJT group signature scheme.
    """

    def __init__(self, H, e, k, lp, lm1=None, lm2=None, gm1=None, gm2=None):
        """
        Object constructor.
        """
        self.H = H
        self.e = e
        self.k = k
        self.lp = lp
        llm2 = 4 * self.lp
        if lm2 is None:
            self.lm2 = llm2 + 1
        else:
            assert lm2 > llm2
            self.lm2 = lm2
        llm1 = self.e * (self.lm2 + self.k) + 2
        if lm1 is None:
            self.lm1 = floor(llm1) + 1
        else:
            assert lm1 > llm1
            self.lm1 = lm1
        lgm2 = self.lm1 + 2
        if gm2 is None:
            self.gm2 = lgm2 + 1
        else:
            assert gm2 > lgm2
            self.gm2 = gm2
        lgm1 = self.e * (self.gm2 + self.k) + 2
        if gm1 is None:
            self.gm1 = floor(lgm1) + 1
        else:
            assert gm1 > lgm1
            self.gm1 = gm1

        self.pgm1 = 2 ^ self.gm1
        self.pgm2 = 2 ^ self.gm2
        self.plm1 = 2 ^ self.lm1
        self.plm2 = 2 ^ self.lm2
        self.plp = 2 ^ self.lp
        self.pg1 = 2 ^ ceil(self.e * (self.gm1 + 2*self.lp + self.k + 1))
        self.pg2 = 2 ^ ceil(self.e * (self.gm2 + self.k))
        self.pl2 = 2 ^ ceil(self.e * (self.lm2 + self.k))
        self.plk = 2 ^ ceil(self.e * (2*self.lp + self.k))

    def prove_discrete_log(self, values, bases, logs, n, lm=None, X=0):
        """
        Provide a zero-knowledge proof of the fact that
        the values can be expressed as a product of the elements in bases
        raised to the corresponding exponents in logs modulo n.
        """
        assert len(values) == len(bases)
        assert all(len(bb) == len(logs) for bb in bases)
        assert all(v == prod(pow(b, x, n) for b, x in zip(bb, logs)) % n for v, bb in zip(values, bases))
        if lm is None:
            lm = 4 * self.lp
        l = 2^(ceil(self.e * (lm + self.k))) - 1
        tt = [randint(-l, l) for _ in logs]
        c = self.H(*sum([[v, prod(pow(b, t, n) for b, t in zip(bb, tt)) % n] + bb for v, bb in zip(values, bases)], []))
        return (c, ) + tuple(t - c*(x-X) for t, x in zip(tt, logs))

    def verify_discrete_log(self, values, bases, proof, n, lm=None, X=0):
        """
        Verify the proof of the discrete logarithm.
        """
        assert len(values) == len(bases)
        assert all(len(bb) + 1 == len(proof) for bb in bases)
        if lm is None:
            lm = 4 * self.lp
        l = 2^(ceil(self.e * (lm + self.k)) + 1) - 1
        c = proof[0]
        ss = proof[1:]
        return all(-l <= s <= l for s in ss) and \
            c == self.H(*sum([[v, prod(pow(b, s - c*X, n) for b, s in zip(bb, ss)) * pow(v, c, n) % n] + bb
                              for v, bb in zip(values, bases)], []))

    def verify(self, pubkey, m, sig):
        """
        Verify the signature of the given message.
        """
        n, a, a0, y, g, h = pubkey
        c, s1, s2, s3, s4, T1, T2, T3 = sig
        return -2*self.pg2 < s1 < 2*self.pg2 and -2*self.pl2 < s2 < 2*self.pl2 and \
            -2*self.pg1 < s3 < 2*self.pg1 and -2*self.plk < s4 < 2*self.plk and \
            c == self.H(g, h, y, a0, a, T1, T2, T3,
                        Integer(pow(a0, c, n) * pow(T1, s1 - c * self.pgm1, n) /
                                (pow(a, s2 - c * self.plm1, n) * pow(y, s3, n)) % n),
                        Integer(pow(T2, s1 - c * self.pgm1, n) / pow(g, s3, n) % n),
                        Integer(pow(T2, c, n) * pow(g, s4, n) % n),
                        Integer(pow(T3, c, n) * pow(g, s1 - c * self.pgm1, n) * pow(h, s4, n) % n), m)

    def verify_opening(self, pubkey, m, sig, A, proof):
        """
        Verify that the signer has been correctly identified.
        """
        assert self.verify(pubkey, m, sig)
        n, a, a0, y, g, h = pubkey
        c, s1, s2, s3, s4, T1, T2, T3 = sig
        return self.verify_discrete_log([y, T1 / A % n], [[g], [T2]], proof, n)

import hashlib

def H(*largs):
    """
    Compute the MD5 hash of the input as an integer.
    """
    return Integer(hashlib.md5(str(list(largs)).encode()).hexdigest(), 16)

pars = ACJTParams(H, 1.1, 128, 128)

class ACJTJoinTranscript:
    """
    A class representing an ACJT join protocol transcript.
    """
    pass

class ACJTGroupManager:
    """
    A class representing the ACJT group manager.
    """

    def __init__(self, pars):
        """
        Object constructor.
        """
        self.pars = pars
        p = safe_prime(self.pars.plp)
        q = safe_prime(self.pars.plp)
        self.p = (p-1)/2
        self.q = (q-1)/2
        self.n = p * q
        self.a = find_QR(self.n)
        self.a0 = find_QR(self.n)
        self.g = find_QR(self.n)
        self.h = find_QR(self.n)
        self.x = find_element(self.p * self.q)
        self.y = Integer(pow(self.g, self.x, self.n))
        self.members = {}
        self.certificates = {}

    def public_key(self):
        """
        Return the group public key.
        """
        return (self.n, self.a, self.a0, self.y, self.g, self.h)

    def secret_key(self):
        """
        Return the group manager's secret key.
        """
        return (self.p, self.q, self.x)

    def join_init(self, name, msg):
        """
        Respond to joining initiation.
        """
        assert name not in self.members
        client = self.members[name] = ACJTJoinTranscript()
        client.C1, client.C1_proof1 = msg
        assert is_QR(client.C1, self.p, self.q)
        assert self.pars.verify_discrete_log([client.C1], [[self.g, self.h]], client.C1_proof1, self.n)
        client.alpha = Integer(randint(1, self.pars.plm2 - 1))
        client.beta = Integer(randint(1, self.pars.plm2 - 1))
        return (client.alpha, client.beta)

    def join_gen(self, name, msg):
        """
        Generate the group member's exponent.
        """
        client = self.members[name]
        client.C2, client.C2_proof1, client.C2_proof2, client.C1_proof2 = msg
        assert is_QR(client.C2, self.p, self.q)
        assert self.pars.verify_discrete_log([client.C2], [[self.a]], client.C2_proof1, self.n,
                                             self.pars.lm2, self.pars.plm1)
        assert self.pars.verify_discrete_log([Integer(client.C2 / pow(self.a, self.pars.plm1, self.n) % self.n)],
                                             [[self.a]], client.C2_proof2, self.n, self.pars.lm2)
        assert self.pars.verify_discrete_log([Integer(pow(client.C1, client.alpha, self.n) *
                                                      pow(self.g, client.beta, self.n) % self.n)],
                                             [[self.g, self.h]], client.C1_proof2, self.n, 2 * self.pars.lm2 + 1)
        client.e = random_prime(self.pars.pgm1 + self.pars.pgm2 - 1, lbound=self.pars.pgm1 - self.pars.pgm2 + 1)
        d = inverse(client.e, 4 * self.p * self.q)
        client.A = Integer(pow(client.C2 * self.a0, d, self.n))
        self.certificates[client.A] = name
        return (client.A, client.e)

    def open(self, m, sig):
        """
        Identify the signer of the signature sig to the message m.
        """
        assert self.pars.verify(self.public_key(), m, sig)
        c, s1, s2, s3, s4, T1, T2, T3 = sig
        A = Integer(T1 / pow(T2, self.x, self.n) % self.n)
        proof = self.pars.prove_discrete_log([self.y, T1 / A % self.n], [[self.g], [T2]], [self.x], self.n)
        return (self.certificates[A], A, proof)
        

class ACJTGroupMember:
    """
    A class representing a group member.
    """

    def __init__(self, name, gm):
        """
        Object constructor.
        """
        self.name = name
        self.pars = gm.pars
        self.n, self.a, self.a0, self.y, self.g, self.h = gm.public_key()

    def join_init(self):
        """
        Initiate group joining.
        """
        self.xx = Integer(randint(1, self.pars.plm2 - 1))
        self.r = Integer(randint(1, self.n^2 - 1))
        self.C1 = Integer(pow(self.g, self.xx, self.n) * pow(self.h, self.r, self.n) % self.n)
        C1_proof1 = self.pars.prove_discrete_log([self.C1], [[self.g, self.h]], [self.xx, self.r], self.n)
        return (self.C1, C1_proof1)

    def join_gen(self, msg):
        """
        Generate personal private key.
        """
        self.alpha, self.beta = msg
        assert 1 <= self.alpha < self.pars.plm2
        assert 1 <= self.beta < self.pars.plm2
        self.x = self.pars.plm1 + (self.alpha * self.xx + self.beta) % self.pars.plm2
        self.C2 = Integer(pow(self.a, self.x, self.n))
        C2_proof1 = self.pars.prove_discrete_log([self.C2], [[self.a]], [self.x], self.n, self.pars.lm2, self.pars.plm1)
        C2_proof2 = self.pars.prove_discrete_log([Integer(self.C2 / pow(self.a, self.pars.plm1, self.n) % self.n)],
                                                 [[self.a]], [self.x - self.pars.plm1], self.n, self.pars.lm2)
        C1_proof2 = self.pars.prove_discrete_log([Integer(pow(self.C1, self.alpha, self.n) *
                                                          pow(self.g, self.beta, self.n) % self.n)], [[self.g, self.h]],
                                                 [self.alpha * self.xx + self.beta, self.alpha * self.r],
                                                 self.n, 2 * self.pars.lm2 + 1)
        return (self.C2, C2_proof1, C2_proof2, C1_proof2)

    def join_verify(self, msg):
        """
        Verify the correctness of the exponent.
        """
        self.A, self.e = msg
        return pow(self.a, self.x, self.n) * self.a0 % self.n == pow(self.A, self.e, self.n)

    def sign(self, m):
        """
        Produce a group signature of the message m.
        """
        w = Integer(randint(0, self.pars.plp^2 - 1))
        T1 = Integer(self.A * pow(self.y, w, self.n) % self.n)
        T2 = Integer(pow(self.g, w, self.n))
        T3 = Integer(pow(self.g, self.e, self.n) * pow(self.h, w, self.n) % self.n)
        r1 = Integer(randint(-self.pars.pg2+1, self.pars.pg2-1))
        r2 = Integer(randint(-self.pars.pl2+1, self.pars.pl2-1))
        r3 = Integer(randint(-self.pars.pg1+1, self.pars.pg1-1))
        r4 = Integer(randint(-self.pars.plk+1, self.pars.plk-1))
        d1 = Integer(pow(T1, r1, self.n) / (pow(self.a, r2, self.n) * pow(self.y, r3, self.n)) % self.n)
        d2 = Integer(pow(T2, r1, self.n) / pow(self.g, r3, self.n) % self.n)
        d3 = Integer(pow(self.g, r4, self.n))
        d4 = Integer(pow(self.g, r1, self.n) * pow(self.h, r4, self.n) % self.n)
        c = H(self.g, self.h, self.y, self.a0, self.a, T1, T2, T3, d1, d2, d3, d4, m)
        s1 = r1 - c * (self.e - self.pars.pgm1)
        s2 = r2 - c * (self.x - self.pars.plm1)
        s3 = r3 - c * self.e * w
        s4 = r4 - c * w
        return (c, s1, s2, s3, s4, T1, T2, T3)