1from hashlib import sha256
  2
  3# Ring Signatures
  4# bLSAG: Back’s Linkable Spontaneous Anonymous Group signatures
  5#
  6# A Rust implementation of this scheme can be found at:
  7# https://github.com/arnaucube/ring-signatures-rs
  8
  9def hashToPoint(a):
 10    # TODO use a proper hash-to-point
 11    h = sha256((str(a)).encode('utf-8'))
 12    r = int(h.hexdigest(), 16) * g
 13    return r
 14
 15def hash(R, m, A, B, q):
 16    h = sha256((
 17        str(R) + str(m) + str(A) + str(B)
 18        ).encode('utf-8'))
 19    r = int(h.hexdigest(), 16)
 20    return int(mod(r, q))
 21
 22def print_ring(a):
 23    print("ring of c's:")
 24    for i in range(len(a)):
 25        print(i, a[i])
 26    print("")
 27
 28class Prover:
 29    def __init__(self, F, g):
 30        self.F = F # Z_p
 31        self.g = g # elliptic curve generator
 32        self.q = self.g.order() # order of group
 33
 34    def new_key(self):
 35        self.w = int(self.F.random_element())
 36        self.K = self.g * self.w
 37        return self.K
 38
 39    def sign(self, m, R):
 40        # determine pi (the position of signer's public key in R
 41        pi = -1
 42        for i in range(len(R)):
 43            if self.K == R[i]:
 44                pi = i
 45                break
 46        assert pi>=0
 47
 48        a = int(self.F.random_element())
 49        r = [None] * len(R)
 50        # for i \in {1, 2, ..., n} \ {i=pi}
 51        for i in range(0, len(R)):
 52            if i==pi:
 53                continue
 54
 55            r[i] = int(mod(int(self.F.random_element()), self.q))
 56
 57        c = [None] * len(R)
 58        # c_{pi+1}
 59        pi1 = mod(pi + 1, len(R))
 60        c[pi1] = hash(R, m, a * self.g, hashToPoint(R[pi]) * a, self.q)
 61
 62        key_image = self.w * hashToPoint(self.K)
 63
 64        # do c_{i+1} from i=pi+1 to pi-1:
 65        for j in range(0, len(R)-1):
 66            i = mod(pi1+j, len(R))
 67            i1 = mod(pi1+j +1, len(R))
 68
 69            c[i1] = hash(R, m, r[i] * self.g + c[i] * R[i], r[i] * hashToPoint(R[i]) + c[i] * key_image, self.q)
 70
 71        # compute r_pi
 72        r[pi] = int(mod(a - c[pi] * self.w, self.q))
 73        print_ring(c)
 74
 75        return [c[0], r]
 76
 77def verify(g, R, m, key_image, sig):
 78    q = g.order()
 79    c1 = sig[0]
 80    r = sig[1]
 81    assert len(R) == len(r)
 82
 83    # check that key_image \in G (EC), by l * key_image == 0
 84    assert q * key_image == 0 # in sage 0 EC point is represented as (0:1:0)
 85
 86
 87    # for i \in 1,2,...,n
 88    c = [None] * len(R)
 89    c[0] = c1
 90    for j in range(0, len(R)):
 91        i = mod(j, len(R))
 92        i1 = mod(j+1, len(R))
 93        c[i1] = hash(R, m, r[i] * g + c[i] * R[i], r[i] * hashToPoint(R[i]) + c[i] * key_image, q)
 94
 95    print_ring(c)
 96    assert c1 == c[0]
 97
 98# Tests
 99import unittest, operator
100
101# ethereum elliptic curve
102p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
103a = 0
104b = 7
105F = GF(p)
106E = EllipticCurve(F, [a,b])
107GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
108GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
109g = E(GX,GY)
110n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
111h = 1
112q = g.order()
113assert is_prime(p)
114assert is_prime(q)
115assert g * q == 0
116
117
118class TestRingSignatures(unittest.TestCase):
119        def test_bLSAG_ring_of_5(self):
120                test_bLSAG(5, 3)
121        def test_bLSAG_ring_of_20(self):
122                test_bLSAG(20, 14)
123
124def test_bLSAG(ring_size, pi):
125        print(f"[bLSAG] Testing with a ring of {ring_size} keys")
126        prover = Prover(F, g)
127        n = ring_size
128        R = [None] * n
129
130        # generate prover's key pair
131        K_pi = prover.new_key()
132
133        # generate other n public keys
134        for i in range(0, n):
135            R[i] = g * i
136
137        # set K_pi
138        R[pi] = K_pi
139
140        # sign m
141        m = 1234
142        print("sign")
143        sig = prover.sign(m, R)
144
145        print("verify")
146        key_image = prover.w * hashToPoint(prover.K)
147        verify(g, R, m, key_image, sig)
148
149if __name__ == '__main__':
150        unittest.main()