Public-Key Signatures and Key Exchange with Ed25519 and X25519

Lessons 1 to 4 used one shared secret key. Public-key cryptography splits the key in two: a private half you keep, and a public half you can give to anyone. This lesson covers the two things that split makes possible: signatures that anyone can verify, and two strangers agreeing on a secret key over an open network. Start a container with docker run --rm -it -v "$PWD":/work -w /work python:3.12-slim bash, then run pip install cryptography==50.0.2. The examples were run with Python 3.12.15 and cryptography 50.0.2. Every key is generated fresh on each run.

Sign with the private key, verify with the public one

A signature binds a message to the holder of a private key. Here a release is signed, and the verifier gets only the public key as PEM text.

# sign.py
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey

private_key = Ed25519PrivateKey.generate()       # demo-only: new key every run
public_key = private_key.public_key()

message = b"release v2.4.1 sha256=9b89376f..."
signature = private_key.sign(message)

pem = public_key.public_bytes(serialization.Encoding.PEM,
                              serialization.PublicFormat.SubjectPublicKeyInfo)
print(pem.decode().strip())
print("public key:", len(public_key.public_bytes_raw()), "bytes")
print("signature: ", len(signature), "bytes")

# the verifier only has the PEM text and the message
loaded = serialization.load_pem_public_key(pem)
print("verify:    ", loaded.verify(signature, message))

$ python sign.py
-----BEGIN PUBLIC KEY-----
MCowBQYDK2VwAyEAcDgvQH6cyzOD17TuD/VMg1v10Xk8VbA2cfGPu/XoCsY=
-----END PUBLIC KEY-----
public key: 32 bytes
signature:  64 bytes
verify:     None

The public key is 32 bytes, and the PEM adds a short header that names the algorithm. The signature is 64 bytes, however long the message is. The last line surprises people: verify returns None, not True. In this library, a valid signature returns nothing and an invalid one raises. So code that writes if key.verify(...): is wrong, but it’s also wrong safely: the check is never true, so it rejects everything instead of accepting everything.

One byte, or the wrong key, and verification fails

Now verify a changed message, and verify with someone else’s public key.

# verify_fail.py
from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey

signer = Ed25519PrivateKey.generate()
someone_else = Ed25519PrivateKey.generate()

message = b"release v2.4.1 sha256=9b89376f..."
signature = signer.sign(message)

checks = {
    "genuine":           (signer.public_key(), message),
    "one byte changed":  (signer.public_key(), message.replace(b"2.4.1", b"2.4.2")),
    "wrong public key":  (someone_else.public_key(), message),
}
for name, (pub, msg) in checks.items():
    try:
        pub.verify(signature, msg)
        print(f"{name:17} valid")
    except InvalidSignature:
        print(f"{name:17} InvalidSignature")

$ python verify_fail.py
genuine           valid
one byte changed  InvalidSignature
wrong public key  InvalidSignature

Changing 2.4.1 to 2.4.2 changes one byte, and verification fails. The signature covers every byte of the message. Verifying with the wrong public key fails too, which is the whole point: a signature proves which key made it. That’s what an HMAC can’t do. Anyone who can check an HMAC tag holds the same key and could have made the tag, but nobody can make an Ed25519 signature with only the public key. That’s why software releases, package registries, Git commits and TLS certificates use signatures.

Notice the trust problem this leaves: the verifier has to already know which public key is the right one. Lesson 6 solves that with certificates.

Two sides, one secret, nothing secret sent

X25519 is Diffie-Hellman key agreement on the same curve family. Each side sends a public key, and each combines the other’s public key with its own private key.

# exchange.py
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey

alice = X25519PrivateKey.generate()
bob = X25519PrivateKey.generate()

# only the public halves cross the network
alice_pub = alice.public_key()
bob_pub = bob.public_key()
print("alice sends:", alice_pub.public_bytes_raw().hex()[:32], "...")
print("bob sends:  ", bob_pub.public_bytes_raw().hex()[:32], "...")

alice_secret = alice.exchange(bob_pub)
bob_secret = bob.exchange(alice_pub)
print("alice computes:", alice_secret.hex()[:32], "...")
print("bob computes:  ", bob_secret.hex()[:32], "...")
print("equal:", alice_secret == bob_secret)

$ python exchange.py
alice sends: 94f6c538589b5c65a0ffbf75eaf2ee04 ...
bob sends:   fa069da440859cebec16ceb8b3a59583 ...
alice computes: f15fba66f07c9ba4ad98c0a79f488d20 ...
bob computes:   f15fba66f07c9ba4ad98c0a79f488d20 ...
equal: True

Both sides arrive at the same 32-byte secret, but it never crossed the network: only the two public keys did. Someone who records both public keys can’t compute the secret without one of the private keys. This is how TLS 1.3 and SSH agree on session keys. Because these keys are generated fresh for each session and then thrown away, recording traffic today and stealing a server’s long-term key later doesn’t reveal past sessions. That property is called forward secrecy.

From shared secret to encryption key

A raw Diffie-Hellman output isn’t uniformly random, so it shouldn’t be used directly as an AES key. Pass it through HKDF first.

# derive_key.py
import os
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

def session_key(shared: bytes) -> bytes:
    return HKDF(algorithm=hashes.SHA256(), length=32, salt=None,
                info=b"demo-chat v1 session key").derive(shared)

alice, bob = X25519PrivateKey.generate(), X25519PrivateKey.generate()
k_alice = session_key(alice.exchange(bob.public_key()))
k_bob = session_key(bob.exchange(alice.public_key()))

nonce = os.urandom(12)
ct = AESGCM(k_alice).encrypt(nonce, b"meet at 10", None)
print("bob reads:", AESGCM(k_bob).decrypt(nonce, ct, None))

$ python derive_key.py
bob reads: b'meet at 10'

Alice encrypts with her derived key, and Bob decrypts with his. That only works because both derived exactly the same AES-256 key. The info string labels the purpose, so the same shared secret can safely produce separate keys for separate jobs, such as one per direction. This is a sketch of the idea, not a protocol to deploy. Real protocols also authenticate the exchange and bind it to a transcript. Use TLS (lesson 7) or a vetted library such as libsodium’s crypto_box, rather than assembling these pieces yourself.

Practice

1. Sign the same message twice. Is an Ed25519 signature the same each time? Compare it with ECDSA on P-256, and check that both ECDSA signatures still verify.

# deterministic.py
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

msg = b"release v2.4.1"
ed = Ed25519PrivateKey.generate()
print("Ed25519 same signature twice:", ed.sign(msg) == ed.sign(msg))

p256 = ec.generate_private_key(ec.SECP256R1())
s1 = p256.sign(msg, ec.ECDSA(hashes.SHA256()))
s2 = p256.sign(msg, ec.ECDSA(hashes.SHA256()))
print("ECDSA   same signature twice:", s1 == s2)
p256.public_key().verify(s1, msg, ec.ECDSA(hashes.SHA256()))
p256.public_key().verify(s2, msg, ec.ECDSA(hashes.SHA256()))
print("both ECDSA signatures verify")

$ python deterministic.py
Ed25519 same signature twice: True
ECDSA   same signature twice: False
both ECDSA signatures verify

2. Authenticate the key exchange. A plain X25519 exchange agrees a key with whoever answered. Have a server sign its ephemeral X25519 public key with a long-term Ed25519 key the client already trusts. Then show that a substituted public key is refused.

# signed_exchange.py
from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey

server_id = Ed25519PrivateKey.generate()          # long-term; client already trusts it
trusted = server_id.public_key()

eph = X25519PrivateKey.generate()                 # fresh for this session
eph_pub = eph.public_key().public_bytes_raw()
sig = server_id.sign(eph_pub)                     # server signs what it sends

swapped = X25519PrivateKey.generate().public_key().public_bytes_raw()

for name, offered in [("genuine", eph_pub), ("substituted", swapped)]:
    try:
        trusted.verify(sig, offered)
        print(f"{name:12} key accepted")
    except InvalidSignature:
        print(f"{name:12} InvalidSignature, handshake aborted")

$ python signed_exchange.py
genuine      key accepted
substituted  InvalidSignature, handshake aborted

3. Compare sizes with RSA. Generate an RSA-3072 key and a PSS signature, and compare the public key and signature sizes with Ed25519. Both offer roughly 128-bit security.

# rsa_compare.py
import time
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import ed25519, padding, rsa

msg = b"release v2.4.1"
start = time.perf_counter()
rsa_key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
rsa_ms = (time.perf_counter() - start) * 1000
rsa_sig = rsa_key.sign(msg, padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                                        salt_length=padding.PSS.MAX_LENGTH), hashes.SHA256())
ed_key = ed25519.Ed25519PrivateKey.generate()

der = serialization.Encoding.DER, serialization.PublicFormat.SubjectPublicKeyInfo
print(f"RSA-3072: keygen {rsa_ms:5.0f} ms, public key {len(rsa_key.public_key().public_bytes(*der))} B,"
      f" signature {len(rsa_sig)} B")
print(f"Ed25519:  public key {len(ed_key.public_key().public_bytes(*der))} B,"
      f" signature {len(ed_key.sign(msg))} B")

$ python rsa_compare.py
RSA-3072: keygen    24 ms, public key 422 B, signature 384 B
Ed25519:  public key 44 B, signature 64 B