| # imports
|
| import random
|
| import math
|
|
|
| def large_random(n):
|
| return random.randrange(2**(n-1)+1, 2**n)
|
|
|
| def is_prime(n):
|
| for i in range(2, int(math.sqrt(n)) + 1):
|
| if n % i == 0:
|
| return False
|
| return True
|
|
|
| def large_prime(n):
|
| while True:
|
| lr = large_random(n)
|
| if is_prime(lr): return lr
|
|
|
| p = large_prime(32)
|
|
|
| # p = 283
|
| q = 47
|
| g = 60
|
| x = 24
|
| k = 15
|
| y = pow(g, x, p)
|
| print(f"y: {y}\n")
|
|
|
| def hash(M):
|
| sum = 0
|
| for i in M:
|
| sum += ord(i)
|
| return sum%10000007
|
|
|
| def sign(M):
|
| r = pow(g, k, p) % q
|
| s = ( (hash(M) + x*r) * pow(k, -1, q) ) % q
|
| print(f"r: {r}, s: {s}")
|
| return (r, s)
|
|
|
| def verify(M, r1, s1):
|
| w = pow(s1, -1, q)
|
| u1 = (hash(M) * w) % q
|
| u2 = (r1 * w) % q
|
| v = ( ( g**u1 * y**u2 ) % p ) % q
|
| print(f"g: {g}, w: {w}, u1: {u1}, u2: {u2}, v: {v}")
|
| return v
|
|
|
| print(">>> Test case 1")
|
| r, s = sign("abcdf")
|
| v = verify("abcdf", r, s)
|
| if v==r: print("Verified\n")
|
|
|
| print(">>> Test case 2")
|
| r_new, s_new = sign("abcdefguyhgfdgfdgfdgfdhjgfdskgfdk")
|
| v_new = verify("abcdf", r_new, s_new)
|
| print("Verified") if v_new==r_new else print("Not verified")
|
|
|
| print(f"Large number: {large_prime(32)}")
|