Link to this headingEdward 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.

Link to this headingKey Generation

Link to this headingSigning 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 }

Link to this headingImplementation

Link to this headingVerifying 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}

Calculate the hash from the public key, R and the message.

h = hash(R + pubKey + msg) \pmod{q}


Using the Random, hash and public key provided generate a candidate for the signature canadate

s_1 = (R + h * pubKey) \pmod{q}


Make Comparison using the provided signature

-p_1 = s * G
Compare p_1 and p_2

P1 == P2



Link to this headingImplementation
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
Link to this headingMath 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