1from hashlib import sha256
 2
 3# Ring Signatures
 4# bLSAG: Back’s Linkable Spontaneous Anonymous Group signatures
 5
 6def hashToPoint(a):
 7    # TODO use a proper hash-to-point
 8    h = sha256((str(a)).encode('utf-8'))
 9    r = int(h.hexdigest(), 16) * g
10    return r
11
12def hash(R, m, A, B, q):
13    h = sha256((
14        str(R) + str(m) + str(A) + str(B)
15        ).encode('utf-8'))
16    r = int(h.hexdigest(), 16)
17    return int(mod(r, q))
18
19def print_ring(a):
20    print("ring of c's:")
21    for i in range(len(a)):
22        print(i, a[i])
23    print("")
24
25class Prover(object):
26    def __init__(self, F, g):
27        self.F = F # Z_p
28        self.g = g # elliptic curve generator
29        self.q = self.g.order() # order of group
30
31    def new_key(self):
32        self.w = int(self.F.random_element())
33        self.K = self.g * self.w
34        return self.K
35
36    def sign(self, m, R):
37        # determine pi (the position of signer's public key in R
38        pi = -1
39        for i in range(len(R)):
40            if self.K == R[i]:
41                pi = i
42                break
43        assert pi>=0
44
45        a = int(self.F.random_element())
46        r = [None] * len(R)
47        # for i \in {1, 2, ..., n} \ {i=pi}
48        for i in range(0, len(R)):
49            if i==pi:
50                continue
51
52            r[i] = int(mod(int(self.F.random_element()), self.q))
53
54        c = [None] * len(R)
55        # c_{pi+1}
56        pi1 = mod(pi + 1, len(R))
57        c[pi1] = hash(R, m, a * self.g, a * hashToPoint(R[pi]), self.q)
58
59        key_image = self.w * hashToPoint(self.K)
60
61        # do c_{i+1} from i=pi+1 to pi-1:
62        #  for j in range(0, len(R)-1):
63        for j in range(0, len(R)-1):
64            i = mod(pi1+j, len(R))
65            i1 = mod(pi1+j +1, len(R))
66
67            c[i1] = hash(R, m, r[i] * self.g + c[i] * R[i], r[i] * hashToPoint(R[i]) + c[i] * key_image, self.q)
68
69        # compute r_pi
70        r[pi] = int(mod(a - c[pi] * self.w, self.q))
71        print_ring(c)
72
73        return [c[0], r]
74
75def verify(g, R, m, key_image, sig):
76    q = g.order()
77    c1 = sig[0]
78    r = sig[1]
79    assert len(R) == len(r)
80
81    # check that key_image \in G (EC), by l * key_image == 0
82    assert q * key_image == 0 # in sage 0 EC point is interpreted as (0:1:0)
83
84
85    # for i \in 1,2,...,n
86    c = [None] * len(R)
87    c[0] = c1
88    for j in range(0, len(R)):
89        i = mod(j, len(R))
90        i1 = mod(j+1, len(R))
91        c[i1] = hash(R, m, r[i] * g + c[i] * R[i], r[i] * hashToPoint(R[i]) + c[i] * key_image, q)
92
93    print_ring(c)
94    assert c1 == c[0]