# Public domain. import sys import random import signatures import doublescalarmult c = 5 twoc = 2**c # XXX: tune c and twoc for b def digits(n): result = [] while n != 0: nk = n % twoc n /= twoc if nk + nk >= twoc: nk -= twoc n += 1 result.append(nk) return result def multiscalarmult(scalars,points): s = [digits(n) for n in scalars] words = max([len(d) for d in s]) needmultiples = [0] * len(scalars) for j in range(len(scalars)): for i in range(len(s[j])): if s[j][i] > needmultiples[j]: needmultiples[j] = s[j][i] if -s[j][i] > needmultiples[j]: needmultiples[j] = -s[j][i] multiples = [False,points] for i in range(2,2**c): newmultiples = [i <= needmultiples[j] and points[j] + multiples[i - 1][j] for j in range(len(points))] multiples.append(newmultiples) result = signatures.groupelt(0) for i in reversed(range(words)): for j in range(c): result = result + result for j in range(len(scalars)): if len(s[j]) > i: digit = s[j][i] if digit > 0: result = result + multiples[digit][j] elif digit < 0: result = result - multiples[-digit][j] return result 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]))