Skip to content

EdDSA

Edward curve Digital Signature Algorithm (EdDSA)

  • Small Key size
  • Small Signature size (2 * key_size)
  • High security level

Differences between ECDSA and EdDSA:
- There is a different but similar signing structure
- There are some Security Benefits
- The full Message Public key is included rather than just the x value. This removes two possible Points that can be accepted. Point P and the point -P.
- The Random value is specific to the private key and message. Making it deterministic.
- The signature makes it almost impossible to recover the secret key from a bad random.

Key Generation

from ecc_lib import *
import hashlib
from cryptopals_lib import bytes_to_int, int_to_bytes

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

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

Signing a Message

  1. Generate the privKey and publicKey
    • privKey = hash(seed)
    • pubKey = privKey * G
  2. Generate a secret integer from the private key and message
    • r = hash(privKey + msg) mod q
  3. Generate the Random Public Integer
    • R = r * G
  4. Generate the Hash
    • h = hash(R + pubKey + msg) mod q
  5. Generate the public signature
    s = (r + h * privKey) mod q
  6. Return the signature { R, s }

Implementation

from ecc_lib import *
import hashlib
from cryptopals_lib import bytes_to_int, int_to_bytes


### EdDSA
def eddsa_sign(privateKey, curve_generator, message, hash_obj=hashlib.sha256):
	#Derive Information
	curve = curve_generator.curve
	order = curve.order
	public_key = curve_generator * privateKey

	#Generate a Random Number hashed from the private key and the message
	hashed_secret_key  = hash_obj(int_to_bytes(privateKey)).digest()
	hashed_message_int = bytes_to_int(hash_obj(hashed_secret_key + message).digest()) % order

	#Generate Random and make a new Point
	message_publickey = curve_generator * hashed_message_int

	#Calculate the hash of the public Information
	# Message_PublicKey | Sender_PublicKey | Message
	hash_output_int = bytes_to_int(hash_obj( message_publickey.compressed() + public_key.compressed() + message).digest()) % order

	#Generate S
	s = (hashed_message_int + ( hash_output_int * privateKey)) % order 

	return {"message_key":message_publickey.compressed(), "signature":s}


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

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)
	#1118376335731908256068732195467137787275566017941934643723748303483550337980 Curve25519: x=31592139095823145743735521290207490847011069353785999562280993997344601755653, y=21673586675302998803223294955405643770844065999969499514651060183576782057508

	#Generate Signature
	signature = eddsa_sign(privateKey, Curve25519_Generator_Point, message)
	print(signature)
	#{'message_key': b'\x02\x19\xebq\x90\x93\xa7\x0e\xe8\xff\xb5\x8f\xca\x85\xc9\xfd\xc8sP\xa4g;\xcf\xa3cgI\xb7\x99@x\x9e\x8d', 'signature': 4635426480053735016845786485222519126656916118819117425364207333976983427746}
	

	#Check Signature
	verify = eddsa_verify(public_point, message, signature, Curve25519_Generator_Point)
	print(verify)
	#True

Verifying a Message

Comparison Identity:

\[ p_1 = s * G = (r + h * privKey) \pmod{q} * G = (r * G) + (h * privKey * G ) \pmod{q} = R + h * (privKey * G ) \pmod{q} = R + h * pubKey \pmod{q} \]

  1. Calculate the hash from the public key, R and the message.
    • h = hash(R + pubKey + msg) \pmod{q}
  2. Using the Random, hash and public key provided generate a candidate for the signature canadate
    • s_1 = (R + h * pubKey) \pmod{q}
  3. Make Comparison using the provided signature
    -p_1 = s * G
  4. Compare p_1 and p_2
    • P1 == P2

Implementation

from ecc_lib import *
import hashlib
from cryptopals_lib import bytes_to_int, int_to_bytes

def eddsa_verify(public_key, message, signature_obj, curve_generator, hash_obj=hashlib.sha256):
	#Derive Information
	curve = curve_generator.curve
	order = curve.order
	message_publickey = Point(point_x=None, point_y=None, curve=curve_generator.curve).decompress(signature_obj["message_key"])

	#Calculate Point 1 from the signature["signature"] int
	test_point1 = curve_generator * signature_obj["signature"] 

	#Calculate the hash of the public Information
	# Message_PublicKey | Sender_PublicKey | Message
	hash_output_int = bytes_to_int(hash_obj( signature_obj["message_key"] + public_key.compressed() + message).digest()) % order

	#R' = (h * s1) * G + (r * s1) * pubKey
	test_point2 = (message_publickey + ( public_key * hash_output_int)) 

	#Because of the way this is checked there are two possible public keys. The one that is used and the negative point
	return test_point1 == test_point2

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

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)
	#1118376335731908256068732195467137787275566017941934643723748303483550337980 Curve25519: x=31592139095823145743735521290207490847011069353785999562280993997344601755653, y=21673586675302998803223294955405643770844065999969499514651060183576782057508

	#Generate Signature
	signature = eddsa_sign(privateKey, Curve25519_Generator_Point, message)
	print(signature)
	#{'message_key': b'\x02\x19\xebq\x90\x93\xa7\x0e\xe8\xff\xb5\x8f\xca\x85\xc9\xfd\xc8sP\xa4g;\xcf\xa3cgI\xb7\x99@x\x9e\x8d', 'signature': 4635426480053735016845786485222519126656916118819117425364207333976983427746}	

	#Check Signature
	verify = eddsa_verify(public_point, message, signature, Curve25519_Generator_Point)
	print(verify)
	#True

Math Proof

Point 1 Identities:

\[ \begin{aligned} P_1 &= s * G \\ P_1 &= (r + h * privKey) * G \mod{q} \\ P_1 &= (r *G) + (h * privKey) * G \mod{q} \\ P_1 &= R + (h * privKey) * G \mod{q} \\ P_1 &= R + h * (privKey * G) \mod{q} \\ P_1 &= R + h * (pubKey) \mod{q} \\ P_1 &= R + h * pubKey \mod{q} \\ \end{aligned} \]

Point 2 Identities:

P2 = R + h * pubKey