Skip to content

Schorr Signature

Schorr Signature

https://conduition.io/cryptography/schnorr/

Math

Single Signature

from ecc_lib import *
import hashlib
from cryptopals_lib import is_prime, int_byte_length, secure_rand_between, int_to_bytes, bytes_to_int, bXXencode


if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)

	### Create Nonce
	nonce = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod)
	nonce_point = nonce * Curve25519_Generator_Point
	print(f"Nonce: {nonce}")

	### generating random biased off of know values
	challenge = hashlib.sha256(nonce_point.compressed() + public_point.compressed() + message).digest()

	#Generate Signature
	signature = (bytes_to_int(challenge) * privateKey) + nonce % Curve25519_Generator_Point.curve.prime_mod
	print(f"Signature: s:{signature}, n:{nonce_point.compressed()}")

	#Check Signature
	check1 = signature * Curve25519_Generator_Point
	check2 = nonce_point + (bytes_to_int(challenge) * public_point)

	print(f"Valid: {check1 == check2}")
	assert check1 == check2

Multi Signature

from ecc_lib import *
import hashlib
from cryptopals_lib import is_prime, int_byte_length, secure_rand_between, int_to_bytes, bytes_to_int, bXXencode


if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair A
	private_KeyA, public_pointA = generate_KeyPair(Curve25519_Generator_Point)
	print(private_KeyA, public_pointA)

	#Generate KeyPair B
	private_KeyB, public_pointB = generate_KeyPair(Curve25519_Generator_Point)
	print(private_KeyB, public_pointB)

	#Generate KeyPair C
	private_KeyC, public_pointC = generate_KeyPair(Curve25519_Generator_Point)
	print(private_KeyC, public_pointC)

	# Generate Nonce A
	nonceA = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod)
	nonce_pointA = nonceA * Curve25519_Generator_Point
	print(f"Nonce: {nonceA}")

	# Generate Nonce B
	nonceB = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod)
	nonce_pointB = nonceB * Curve25519_Generator_Point
	print(f"Nonce: {nonceB}")

	# Generate Nonce C
	nonceC = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod)
	nonce_pointC = nonceC * Curve25519_Generator_Point
	print(f"Nonce: {nonceC}")

	#Compute aggerated Nonce Point
	aggregated_NoncePoint = nonce_pointA + nonce_pointB + nonce_pointC

	#Computer Aggerated Public Key
	aggregated_public_point = public_pointA + public_pointB + public_pointC	

	### generating random biased off of know values
	challenge = hashlib.sha256(aggregated_NoncePoint.compressed() + aggregated_public_point.compressed() + message).digest()

	#Generate Signature A
	signatureA = (bytes_to_int(challenge) * private_KeyA) + nonceA % Curve25519_Generator_Point.curve.prime_mod
	signatureB = (bytes_to_int(challenge) * private_KeyB) + nonceB % Curve25519_Generator_Point.curve.prime_mod
	signatureC = (bytes_to_int(challenge) * private_KeyC) + nonceC % Curve25519_Generator_Point.curve.prime_mod


	### Multi Signature
	aggregated_signature = signatureA + signatureB + signatureC
	print(f"Aggregated Signature: s:{aggregated_signature}, n:{aggregated_public_point.compressed()}")

	### Multi Signature Check
	#  s = (chal * privkey_a + nonce_a) + (chal * privkey_b + nonce_b) + (chal * privkey_c + nonce_c)
	#  s = (chal * privkey_a) + (chal * privkey_b) + (chal * privkey_c) + nonce_a + nonce_b + nonce_c
	#  s = chal * (privkey_a + privkey_b + privkey_c) + nonce_a + nonce_b + nonce_c


	#Check Individual Signatures
	check1 = signatureA * Curve25519_Generator_Point
	check2 = nonce_pointA + (bytes_to_int(challenge) * public_pointA)
	print(f"SignatureA Valid: {check1 == check2}")

	check1 = signatureB * Curve25519_Generator_Point
	check2 = nonce_pointB + (bytes_to_int(challenge) * public_pointB)
	print(f"SignatureB Valid: {check1 == check2}")

	check1 = signatureC * Curve25519_Generator_Point
	check2 = nonce_pointC + (bytes_to_int(challenge) * public_pointC)
	print(f"SignatureC Valid: {check1 == check2}")

	#Check Signature
	check1 = aggregated_signature * Curve25519_Generator_Point
	check2 = aggregated_NoncePoint + (bytes_to_int(challenge) * aggregated_public_point)

	print(f"Valid: {check1 == check2}")
	assert check1 == check2

Exploits

Multi-Signature Rogue Key Attack

The last person to exchange keys is able to generate a Public Key rouge_public_point = public_pointC - public_pointB - public_pointA that when aggerated to the multi signature is actually the public key that the last person actually has the private key for.

This turns the multi-signature solution into a single signature solution that is controlled by the attacker.

Note

The attacker wont actualy know the private key to the public key that they sent to the others.

from ecc_lib import *
import hashlib
from cryptopals_lib import is_prime, int_byte_length, secure_rand_between, int_to_bytes, bytes_to_int, bXXencode


if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair A
	private_KeyA, public_pointA = generate_KeyPair(Curve25519_Generator_Point)
	#print(private_KeyA, public_pointA)

	#Generate KeyPair B
	private_KeyB, public_pointB = generate_KeyPair(Curve25519_Generator_Point)
	#print(private_KeyB, public_pointB)

	#Generate KeyPair C
	private_KeyC, public_pointC = generate_KeyPair(Curve25519_Generator_Point)
	#print(private_KeyC, public_pointC)

	#Generate Shared Key pair
	rouge_public_point = public_pointC - public_pointB - public_pointA
	print(rouge_public_point)

	# Generate Nonce A
	nonceA = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod)
	nonce_pointA = nonceA * Curve25519_Generator_Point
	#print(f"Nonce: {nonceA}")

	# Generate Nonce B
	nonceB = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod)
	nonce_pointB = nonceB * Curve25519_Generator_Point
	#print(f"Nonce: {nonceB}")

	# Generate Nonce C
	nonceC = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod)
	nonce_pointC = nonceC * Curve25519_Generator_Point
	#print(f"Nonce: {nonceC}")

	#Compute aggerated Nonce Point
	aggregated_NoncePoint = nonce_pointA + nonce_pointB + nonce_pointC

	#Computer Aggerated Public Key
	aggregated_public_point = public_pointA + public_pointB + rouge_public_point

	print(f"Aggregated Point is Public point C: {aggregated_public_point == public_pointC}")
	assert aggregated_public_point == public_pointC

	### generating random baised off of know values
	challenge = hashlib.sha256(aggregated_NoncePoint.compressed() + aggregated_public_point.compressed() + message).digest()

	#Generate Signature A
	signatureA = (bytes_to_int(challenge) * private_KeyA) + nonceA % Curve25519_Generator_Point.curve.prime_mod
	signatureB = (bytes_to_int(challenge) * private_KeyB) + nonceB % Curve25519_Generator_Point.curve.prime_mod
	signatureC = (bytes_to_int(challenge) * private_KeyC) + nonceC % Curve25519_Generator_Point.curve.prime_mod
	#print(f"Signature: s:{signatureA}, n:{nonce_pointA.compressed()}")
	#print(f"Signature: s:{signatureB}, n:{nonce_pointB.compressed()}")
	#print(f"Signature: s:{signatureC}, n:{nonce_pointC.compressed()}")


	### Multi Signature
	aggregated_signature = signatureA + signatureB + signatureC
	print(f"Aggregated Signature: s:{aggregated_signature}, n:{aggregated_public_point.compressed()}")

	### Multi Signature Check
	#  s = (chal * privkey_a + nonce_a) + (chal * privkey_b + nonce_b) + (chal * privkey_c + nonce_c)
	#  s = (chal * privkey_a) + (chal * privkey_b) + (chal * privkey_c) + nonce_a + nonce_b + nonce_c
	#  s = chal * (privkey_a + privkey_b + privkey_c) + nonce_a + nonce_b + nonce_c


	#Check Indivisual Signatures
	check1 = signatureA * Curve25519_Generator_Point
	check2 = nonce_pointA + (bytes_to_int(challenge) * public_pointA)
	print(f"SignatureA Valid: {check1 == check2}")

	check1 = signatureB * Curve25519_Generator_Point
	check2 = nonce_pointB + (bytes_to_int(challenge) * public_pointB)
	print(f"SignatureB Valid: {check1 == check2}")

	check1 = signatureC * Curve25519_Generator_Point
	check2 = nonce_pointC + (bytes_to_int(challenge) * rouge_public_point)
	print(f"SignatureC Valid: {check1 == check2}")

	#Check Signature
	check1 = aggregated_signature * Curve25519_Generator_Point
	check2 = aggregated_NoncePoint + (bytes_to_int(challenge) * aggregated_public_point)

	print(f"Valid: {check1 == check2}")
	assert check1 == check2

To prevent this from happening you make each person in the signature validate that they know the secret key that they are using in the multi signature. This is done by signing some challenge and then verifying it with the attackers public key.

Duplicate nonces

If the nonce that generates the nonce_point is recovered by an attacker than it is possible to recover the private key. When 2 distinct messages are used, if they are the same message then no data is recovered because the signatures would be the same

\[ d = \dfrac{s_1 - s_2}{e_1 - e_2} \]