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