# Public domain. import sys import heapq import random import signatures import doublescalarmult def multiscalarmult(scalars,points): x = zip([-n for n in scalars],points) heapq.heapify(x) while len(x) > 1: np1 = heapq.heappop(x) np2 = heapq.heappop(x) n1,p1 = -np1[0],np1[1] n2,p2 = -np2[0],np2[1] p2 += p1 n1 -= n2 if n1 > 0: heapq.heappush(x,(-n1,p1)) heapq.heappush(x,(-n2,p2)) np1 = heapq.heappop(x) n1,p1 = -np1[0],np1[1] return p1 * n1 def verifybatch(smvector): results = [] randomizers = [random.randrange(2**signatures.b) for i in range(len(smvector))] points = [signatures.B] scalars = [0] for i in range(len(smvector)): sm = smvector[i] R,S,A,M = sm[0],sm[1],sm[2],sm[3] h = signatures.inthash(str(R) + str(A) + M) points.append(signatures.groupelt(R)) scalars.append(randomizers[i]) points.append(signatures.groupelt(A)) scalars.append((h * randomizers[i]) % signatures.l) scalars[0] = (scalars[0] - S * randomizers[i]) % signatures.l if multiscalarmult(scalars,points).x == 0: return [True] * len(smvector) for sm in smvector: R,S,A,M = sm[0],sm[1],sm[2],sm[3] h = signatures.inthash(str(R) + str(A) + M) checkR = doublescalarmult.doublescalarmult(S,signatures.B,(-h) % signatures.l,signatures.groupelt(A)) results.append(R == checkR.x) return results signatures.benchmark(verifybatch,int(sys.argv[1]))