# Public domain.

import random
import hashlib
import sys

b = 128
l = 2**256-189
sys.setrecursionlimit(2000)

def inthash(s):
  return int(hashlib.sha512(s).hexdigest(),16) % l

numadds = 0

class groupelt:
  def __init__(self):
    self.x = 0
  def __init__(self,x):
    self.x = x % l
  def __add__(a,b):
    if a.x == 0: return b
    if b.x == 0: return a
    global numadds
    numadds += 1
    return groupelt(a.x + b.x)
  def __neg__(a):
    return groupelt(-a.x)
  def __sub__(a,b):
    if a.x == 0: return -b
    if b.x == 0: return a
    if a.x == b.x: return groupelt(0)
    global numadds
    numadds += 1
    return groupelt(a.x - b.x)
  def __mul__(a,b):
    if b < 0:
      return a * (-b)
    elif b >= l:
      return a * (b % l)
    elif b == 0:
      return groupelt(0)
    elif b & 1:
      return a + (a + a) * (b >> 1)
    else:
      return (a + a) * (b >> 1)

B = groupelt(1000003)

def signedmessage(M):
  secretkey = random.randrange(l)
  publickey = B * secretkey
  A = publickey.x
  r = random.randrange(l)
  R = (B * r).x
  h = inthash(str(R) + str(A) + M)
  S = (r + h * secretkey) % l
  return [R,S,A,M]

def isvalid(sm):
  R,S,A,M = sm[0],sm[1],sm[2],sm[3]
  h = inthash(str(R) + str(A) + M)
  return (B * S).x == (groupelt(R) + groupelt(A) * h).x

def benchmark(verifybatch,n):
  sm = [signedmessage(str(i)) for i in range(n)]
  valid = [True for i in range(n)]
  numforgeries = 0
  
  while True:
    t1 = numadds
  
    v = verifybatch(sm)
    if v != valid: print "wrong results! " + str(valid) + " vs. " + str(v)
    
    t2 = numadds
    print "%.3f" % (float(t2-t1)/(n*b)),"*nb additions; b=",b,"bits security; n=",n,"signatures;",numforgeries,"forgeries"
  
    if numforgeries == n: return
  
    forge = random.randrange(n)
    while not valid[forge]: forge = random.randrange(n)
    sm[forge][3] = sm[forge][3] + "x"
    valid[forge] = False
    numforgeries += 1