Skip to content

Instantly share code, notes, and snippets.

@odzhan

odzhan/schnorr1.py

Last active September 15, 2024 05:50
Show Gist options
  • Save odzhan/82a709860678cf48bb10d4d93a6ef138 to your computer and use it in GitHub Desktop.
Save odzhan/82a709860678cf48bb10d4d93a6ef138 to your computer and use it in GitHub Desktop.
Download ZIP
Schnorr Digital Signatures
Raw
schnorr1.py
'''
Schnorr Digital Signature Scheme based on paper:
Efficient Signature Generation by Smart Cards, published in March 1991 by Claus-Peter Schnorr
'''
from random import randint
import sympy
import hashlib
def generate_safe_prime(bits):
"""Generate a safe prime number with the specified number of bits."""
while True:
q = sympy.randprime(2**(bits-1), 2**bits)
p = 2*q + 1
if sympy.isprime(p):
return p, q
def find_primitive_root(p, q):
"""Find a primitive root of p with order q."""
for alpha in range(2, p):
if pow(alpha, q, p) == 1 and pow(alpha, 1, p) != 1:
return alpha
raise ValueError("No primitive root found")
def hash_function(x, m):
"""One-way hash function h(x, m)"""
data = str(x) + m
hash_value = hashlib.sha256(data.encode()).hexdigest()
return int(hash_value, 16)
# Initialize the Key Authentication Center (KAC)
def init_kac():
p, q = generate_safe_prime(140)
alpha = find_primitive_root(p, q)
private_key = sympy.randprime(1, p-1)
public_key = pow(alpha, private_key, p)
published_info = {
"p": p,
"q": q,
"alpha": alpha,
"hash_function": "SHA-256",
"public_key": public_key
}
return published_info, private_key
# Run the KAC initialization
published_info, private_key = init_kac()
p = published_info['p']
q = published_info['q']
alpha = published_info['alpha']
s = randint(1, q - 1) # Private key
v = pow(alpha, q - s, p) # Public key
# Signing
message = "Test message"
r = randint(1, q - 1)
x = pow(alpha, r, p)
e = hash_function(x, message) % q
y = (r + s * e) % q
# Verification
x_prime = (pow(alpha, y, p) * pow(v, e, p)) % p
e_prime = hash_function(x_prime, message) % q
assert e == e_prime
print("Signature verified successfully!")
Raw
schnorr2.py
import hashlib
import secrets
# q is a prime number. p is a safe prime 2q+1 (2*0x897036e085d45b4876b672bda7a6b12887d+1)
p = 0x112e06dc10ba8b690ed6ce57b4f4d62510fb
q = 0x897036e085d45b4876b672bda7a6b12887d
alpha = 0x3
# Hash function
def H(data):
return int(hashlib.sha256(data.encode()).hexdigest(), 16)
# Key generation
def generate_keys():
x = secrets.randbelow(q - 1) + 1 # private key in range [1, q-1]
y = pow(alpha, x, p) # public key
return x, y
# Signature generation
def sign(M, x):
k = secrets.randbelow(q - 1) + 1 # random k in range [1, q-1]
r = pow(alpha, k, p)
e = H(str(r) + M) % q
s = (k - x * e) % q
return r, s
# Signature verification
def verify(M, r, s, y):
e = H(str(r) + M) % q
rv = (pow(alpha, s, p) * pow(y, e, p)) % p
ev = H(str(rv) + M) % q
return e == ev
# Loop to generate and verify 4096 signatures
invalid_signatures = []
for i in range(4096):
message = f"Hello, Schnorr! {i}"
x, y = generate_keys() # Generate keys
r, s = sign(message, x) # Sign the message
is_valid = verify(message, r, s, y) # Verify the signature
if not is_valid:
invalid_signatures.append((message, r, s, y))
# Print only the invalid signatures
for message, r, s, y in invalid_signatures:
print(f"Message: {message}")
print(f"Public key: {y}")
print(f"Signature: (r: {r}, s: {s})")
print(f"Signature valid: False")
Raw
schnorrx.py
'''
On the Security of the Schnorr Signature Scheme and DSA against Related-Key Attacks
p = 338838876847395647379062259034510725087309079458130429395598701614954101959771782493853012277736067589418883702085154063382854154039640105020306250881237456936972474326849394416770970798676668499998174472506130506145276115066321013502844563275110388662428396162280028683823243729257125833722043618224773168907
q = 169419438423697823689531129517255362543654539729065214697799350807477050979885891246926506138868033794709441851042577031691427077019820052510153125440618728468486237163424697208385485399338334249999087236253065253072638057533160506751422281637555194331214198081140014341911621864628562916861021809112386584453
g = 3
https://2ton.com.au/safeprimes/
'''
import hashlib
import random
from sympy import isprime
import sympy
def find_safe_prime(bits):
"""Generate a safe prime number with the specified number of bits."""
while True:
q = sympy.randprime(2**(bits-1), 2**bits)
p = 2*q + 1
if sympy.isprime(p):
return p, q
def find_primitive_root(p, q):
"""Find a primitive root of p with order q."""
for alpha in range(2, p):
if pow(alpha, q, p) == 1 and pow(alpha, 1, p) != 1:
return alpha
raise ValueError("No primitive root found")
def modular_inverse(a, p):
return pow(a, p - 2, p)
def generate_keys(bits=1024):
#p, q = find_safe_prime(bits)
#g = find_primitive_root(p, q)
p = 0x894289e84e6266cc334f6ae862b938befc5b52da5060d136a1fc1faf6122172438233f42400445de676e2988d56218628074db0d75f78427418c2ca49308e205c60e4606185e0e0ae2092cf92890e65909b74ce48ed869818feb17b21cb3e0f6b027a23c7faf815c55f82278e87b2313e71e641024ca5a23c65bfc89a974c6b8dab7b14aa7a34ce45d1bf7de05649a0266a28fbcf785b960e093a9dcf38e04859e0a69bede048064056c23ae0bcffd6dc2a3f861258617321c7c5fd203bceb843c6417ceee70b6b3aaf9cbd587df8012dd6df6290430911b2bb1b80dad24d9e0255a50e6bf67d2c23655052479fcc0dbb301e25ad8c9d0d32d1498104fdf22440194e7b654ad9c411b46ec9c70a55ed27be08fcebe1525b8ce6b0cbb4324f9e1511fb61f5714db758a1a4a3c80daed4046ecab4f90dcd4b7c3526ed62bea054ff714db993393dfcf4b3de44c71c7c7a40bc25235d1e05816211096a0eabd6c025e92deb1c516dc0de3d40e6c2f943608e8c76c01dcd1e228838c831f848cc67b5c20eef51721475aef1e7b0f52a6de055db74f4d8b293e574f70924944d773ea37ed0939eeaae162b741a1ad173ec78a57509086a8781c4359a97c15e003f51c1a5f5d6934ee03c9ccdacc61b95859c3065cec455374e6a6415032daa8a197ca58173e83fb0023e73bdad6a66a36503ba0047cd9543b8a7d92ca0181209f81eb
q = 0x44a144f42731336619a7b574315c9c5f7e2da96d2830689b50fe0fd7b0910b921c119fa1200222ef33b714c46ab10c31403a6d86bafbc213a0c6165249847102e30723030c2f07057104967c9448732c84dba672476c34c0c7f58bd90e59f07b5813d11e3fd7c0ae2afc113c743d9189f38f320812652d11e32dfe44d4ba635c6d5bd8a553d1a6722e8dfbef02b24d01335147de7bc2dcb07049d4ee79c70242cf0534df6f02403202b611d705e7feb6e151fc3092c30b990e3e2fe901de75c21e320be777385b59d57ce5eac3efc0096eb6fb148218488d95d8dc06d6926cf012ad28735fb3e9611b2a82923cfe606dd980f12d6c64e869968a4c0827ef912200ca73db2a56ce208da3764e3852af693df047e75f0a92dc6735865da1927cf0a88fdb0fab8a6dbac50d251e406d76a0237655a7c86e6a5be1a9376b15f502a7fb8a6dcc99c9efe7a59ef22638e3e3d205e1291ae8f02c0b10884b50755eb6012f496f58e28b6e06f1ea073617ca1b047463b600ee68f11441c6418fc246633dae10777a8b90a3ad778f3d87a9536f02aedba7a6c5949f2ba7b84924a26bb9f51bf6849cf75570b15ba0d0d68b9f63c52ba84843543c0e21acd4be0af001fa8e0d2faeb49a7701e4e66d6630dcac2ce1832e7622a9ba735320a8196d5450cbe52c0b9f41fd8011f39ded6b53351b281dd0023e6caa1dc53ec96500c0904fc0f5
g = 3
x = random.randint(1, q - 1)
y = pow(g, x, p)
H = lambda m: int(hashlib.sha512(m).hexdigest(), 16) % q
return x, (y, H), p, q, g
def int_to_bytes(value):
return value.to_bytes((value.bit_length() + 7) // 8, byteorder='big')
def sign(message, sk, p, q, g):
x = sk # x = secret key
t = random.randint(1, q - 1) # generate random t
r = pow(g, t, p)
psi = pow(g, x, p)
H = lambda m: int(hashlib.sha512(m).hexdigest(), 16) % q
h = H(message + int_to_bytes(r) + int_to_bytes(psi))
s = (t + (x * h)) % q
return (h, s)
def verify(message, signature, vk, p, q, g):
y, H = vk
h, s = signature
# Calculate r' = g^s * y^(-h) mod p
#r_prime = (pow(g, s, p) * modular_inverse(pow(y, h, p), p)) % p
r_prime = (pow(g, s, p) * pow(y, -h, p)) % p
h_prime = H(message + int_to_bytes(r_prime) + int_to_bytes(y))
return h == h_prime
# Loop to generate and verify 4096 signatures
invalid_signatures = []
for i in range(32):
message = f"Hello, Schnorr! {i}"
message = message.encode()
sk, vk, p, q, g = generate_keys()
#print(f"p : {p}")
#print(f"q : {q}")
#print(f"g : {g}")
r, s = sign(message, sk, p, q, g)
is_valid = verify(message, (r, s), vk, p, q, g)
if not is_valid:
invalid_signatures.append((message, r, s, vk))
# Print only the invalid signatures
for message, r, s, y in invalid_signatures:
print(f"Message: {message}")
print(f"Public key: {y}")
print(f"Signature: (r: {r}, s: {s})")
print(f"Signature valid: False")
print("OK")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment