Schnorr Protocol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import random

def generate_random_value(n):
    """Generates a random value in the range [1, n-1]"""
    return random.randrange(1, n)

def mod_pow(base, exponent, modulus):
    """Calculates (base^exponent) % modulus efficiently"""
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

def prover(secret, generator, modulus, challenge):
    """Prover's actions in the Schnorr Protocol"""
    r = generate_random_value(modulus)
    commitment = mod_pow(generator, r, modulus)
    response = (r + challenge * secret) % modulus
    return commitment, response

def verifier(commitment, response, generator, modulus, public_key, challenge):
    """Verifier's actions in the Schnorr Protocol"""
    verification = mod_pow(generator, response, modulus)
    check = (commitment * mod_pow(public_key, challenge, modulus)) % modulus
    return verification == check

# Example usage (non-interactive)
secret = 1234  # Example secret
generator = 5  # Example generator
modulus = 2147483647  # Prime modulus
public_key = mod_pow(generator, secret, modulus)

verifier_challenge = 233 # Example verifier challenge
print('Verifier challenge:', verifier_challenge)

commitment, response = prover(secret, generator, modulus, verifier_challenge)
if verifier(commitment, response, generator, modulus, public_key, verifier_challenge):
    print("Proof successful!")
else:
    print("Proof failed!")