#!/usr/bin/env python # coding: utf-8 # # ACJT2000 group signature scheme # # We present the group signature scheme given by Ateniese, Camenisch, Joye and Tsudik in their paper [*A Practical and Provably Secure Coalition-Resistant Group Signature Scheme*](https://www.ics.uci.edu/~gts/paps/acjt00.pdf). # # Let us first give some auxiliary functions. # In[1]: 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) # ## Scheme parameters # # Let us now set the scheme parameters. # In[2]: 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) # In[3]: 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) # ## Key generation # # George, the group manager, can now generate his secret key together with the group public key. # In[4]: 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) # In[5]: set_random_seed(0) george = ACJTGroupManager(pars) print("Public key: {}".format(george.public_key())) print("Secret key: {}".format(george.secret_key())) # Note that the group manager should also provide a proof that $n$ really is a product of two safe primes, see [Camenisch & Michels](http://www.brics.dk/RS/98/29/BRICS-RS-98-29.pdf). # # ## Joining the group # # Alice now wants to join the group. She performs the following protocol with George over an authenticated and encrypted channel. # In[6]: 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) # In[7]: alice = ACJTGroupMember("Alice", george) alice_join_send1 = alice.join_init() print("Alice sends {} to George".format(alice_join_send1)) # In[8]: alice_join_recv1 = george.join_init(alice.name, alice_join_send1) print("George sends {} to Alice".format(alice_join_recv1)) # In[9]: alice_join_send2 = alice.join_gen(alice_join_recv1) print("Alice sends {} to George".format(alice_join_send2)) # In[10]: alice_join_recv2 = george.join_gen(alice.name, alice_join_send2) print("George sends {} to Alice".format(alice_join_recv2)) # In[11]: alice.join_verify(alice_join_recv2) # ## Signing # # Alice can now sign a message $m$ on behalf of the group. # In[12]: m = 2 sig = alice.sign(m) sig # ## Verifying # # Anyone in possession of the group public key can verify that the signature was created by a group member. # In[13]: pars.verify(george.public_key(), m, sig) # ## Opening # # Only the group manager can identify the signer. # In[14]: signer, A, proof = george.open(m, sig) (signer, A, proof) # Anyone can now verify that the signer was correctly identified. # In[15]: pars.verify_opening(george.public_key(), m, sig, A, proof)