import random
from sympy import isprime
p, q = (1279, 71)
assert (p – 1) % q == 0
assert isprime(p) == True
assert isprime(q) == True
a = (p – 1) // q
h = random.randint(2, p – 2)
# generator g
g = pow(h, a, p)
# Private Key & Public Key Calculation
# Alice’s private key
x = random.randint(1, q – 1)
# Alice’s public key
y = pow(g, x, p)
# Sign a Message
H = 17
# Random Integer
k = random.randint(1, q – 1)
r = pow(g, k, p) % q
s = (pow(k, -1, q) * (H + x * r)) % q
assert r != 0 and s != 0
# Verification
w = pow(s, -1, q)
u1 = (H * w) % q
u2 = (r * w) % q
checkpoint = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
assert checkpoint == r