from Crypto.PublicKey import DSA
from sympy import isprime, mod_inverse
import random
import hashlib

def generate_DSA_key():
    key = DSA.generate(1024)
    p, q = key.p, key.q
    assert (p-1) % q == 0

    a = (p-1) // q
    h = random.randint(2, p-2)
    g = pow(h, a, p)

    return key, g

def find_hash(m):
    if isinstance(m, int):
        m = str(m)
    mstr = m.encode()
    hash_value = hashlib.sha1(mstr).digest()
    return int.from_bytes(hash_value, 'big') % q

def sign_message(message, key, g):
    H = find_hash(message)
    x = random.randint(1, key.q-1)
    y = pow(g, x, key.p)

    k = random.randint(1, key.q-1)
    r = pow(g, k, key.p) % key.q

    s = (mod_inverse(k, key.q) * (H + x * r)) % key.q

    return r, s

def verify_signature(message, r, s, key, g):
    H = find_hash(message)
    w = mod_inverse(s, key.q)
    u1 = (H * w) % key.q
    u2 = (r * w) % key.q

    v = ((pow(g, u1, key.p) * pow(key.y, u2, key.p)) % key.p) % key.q

    return v == r

# Example usage
key, g = generate_DSA_key()
message = "attack tomorrow!"
r, s = sign_message(message, key, g)
verification_result = verify_signature(message, r, s, key, g)
print("Verification Result:", verification_result)