Digital Signatures in Python: ECDSA vs EdDSA vs RSA-PSS, Nonce Reuse Attacks, and RFC 6979

Why Learn Digital Signatures?

A digital signature gives you three guarantees at once: authenticity (the message really came from this sender), integrity (it was not modified in transit), and non-repudiation (the signer cannot later deny signing). TLS server certificates, JWTs (ES256 / RS256), SSH host-key authentication, signed Git commits, Bitcoin and Ethereum transactions, and OS code signing all rest on signatures. Almost all trust in modern infrastructure is built on top of them.

Signatures are an application of public-key cryptography. They lean on the same hard problems as RSA (integer factorization) and elliptic curve cryptography (ECC) (the elliptic curve discrete logarithm problem, ECDLP), but now to produce a tag that only the private-key holder can create and anyone can verify with the public key. This article lays out the general signature model and the security notion (EUF-CMA), compares the three workhorse schemes — ECDSA, EdDSA (Ed25519), and RSA-PSS — with equations, and then implements a from-scratch educational ECDSA in Python that we actually run to confirm sign → verify → tamper detection. For a map of the whole field, see the Cryptography Roadmap.

The Signature Model

A signature scheme is a triple of algorithms \((\mathsf{Gen}, \mathsf{Sign}, \mathsf{Verify})\) .

1. Key generation \(\mathsf{Gen}\) : produce a key pair \((sk, pk)\) . The signing key \(sk\) is secret; the verification key \(pk\) is public.
2. Signing \(\mathsf{Sign}(sk, m) \to \sigma\) : produce a signature \(\sigma\) over message \(m\) .
3. Verification \(\mathsf{Verify}(pk, m, \sigma) \to \{0, 1\}\) : check whether \((m, \sigma)\) is valid under \(pk\) .

Correctness requires that honestly generated signatures always verify:

The hash-and-sign paradigm

Real schemes do not sign the message \(m\) directly. They first compress it with a cryptographic hash \(H\) into a fixed-length digest \(e = H(m)\) , then sign that. This is hash-and-sign:

It buys three things:

• Arbitrary-length messages: the signature math only handles a fixed-size input (an integer below \(N\) for RSA, below the order \(n\) for ECDSA); the hash absorbs any length.
• Performance: even a huge file needs just one hash and one signing operation.
• Security separation: if \(H\) is collision-resistant, the scheme’s security reduces to signing a short digest. Conversely, breaking \(H\) breaks the signature — as in the 2008 rogue-CA attack that exploited MD5 collisions.

SHA-256 and SHA-512 are today’s defaults. You can inspect digests with the hash generator tool.

Signatures vs MACs — Non-Repudiation

A MAC (Message Authentication Code) such as HMAC — also used in AES / ChaCha20 AEAD — also protects integrity. But a MAC and a digital signature differ in a fundamental way.

The decisive difference is non-repudiation. Because the sender and receiver share the same HMAC key, the receiver can forge the same tag — so they cannot prove to a third party that the sender produced it. With a digital signature, only the private-key holder can sign, and anyone with the public key can verify. That lets you prove “this party signed this” to a court or any third party, which is exactly why PKI certificates and e-contracts use signatures. See also zero trust security and the security certifications post.

The Security Notion: EUF-CMA

What “secure” means for a signature scheme is pinned down by EUF-CMA (Existential Unforgeability under Chosen-Message Attack). Consider this game against an adversary \(\mathcal{A}\) :

1. The challenger runs \(\mathsf{Gen}\) and hands \(pk\) to \(\mathcal{A}\) .
2. \(\mathcal{A}\) may query a signing oracle on any messages \(m_1, m_2, \dots\) of its choice and receive \(\sigma_i = \mathsf{Sign}(sk, m_i)\) (this is the chosen-message part).
3. Finally \(\mathcal{A}\) tries to output a valid signature \(\sigma^\*\) on a fresh message \(m^\*\) it never queried.

If this probability is negligible, the scheme is EUF-CMA secure. “Existential” is the strongest bar: the adversary loses even if it forges any one fresh signature, not a specific chosen message. RSA-PSS, ECDSA, and Ed25519 are all provably EUF-CMA secure under appropriate assumptions (the RSA assumption, ECDLP, and the random-oracle model). What breaks that guarantee in practice is implementation error — like the ECDSA nonce reuse below, which violates the proof’s premises and enables forgery.

ECDSA: Elliptic Curve Digital Signature Algorithm

ECDSA is the signature scheme over ECC, used across TLS certificates, SSH, Bitcoin, and Ethereum. Fix the domain parameters: prime field \(\mathbb{F}_p\) , base point \(G\) , order \(n\) .

Key generation:

• Choose a private key \(d \in [1, n-1]\) at random.
• Public key \(Q = dG\) (via scalar multiplication).

Signing — for message digest \(e = H(m)\) :

1. Pick a nonce \(k \in [1, n-1]\) .
2. Compute \(R = kG\) and \(r = R_x \bmod n\) (retry if \(r = 0\) ).
3. Compute the following (retry if \(s = 0\) ). The signature is \((r, s)\) .

Verification — check \((r, s) \in [1, n-1]\) and:

Correctness follows by substitution. From \(s = k^{-1}(e + rd)\) we get \(k = w e + w r d = u_1 + u_2 d\) , so

and the \(x\) -coordinate matches \(r\) .

Nonce reuse and bias are fatal

The single biggest pitfall in ECDSA is the nonce \(k\) . It must be uniformly random and secret per signature; any leakage recovers the private key instantly.

(a) Reusing k: sign two different messages \(m_1, m_2\) with the same \(k\) and \(r\) is shared:

Subtract to get \(s_1 - s_2 = k^{-1}(e_1 - e_2)\) , hence

so both the nonce \(k\) and the private key \(d\) are fully exposed. In 2010, Sony’s PlayStation 3 used a constant \(k\) for its ECDSA code signing; fail0verflow / geohot extracted the signing key and could forge valid signatures for arbitrary code.

(b) Biased k: you do not even need full reuse. If the top bits of \(k\) are biased or partially known, a lattice attack (solving the Hidden Number Problem with LLL / BKZ) recovers \(d\) from a handful of signatures. Weak RNGs and imperfect constant-time code have leaked keys this way repeatedly.

RFC 6979: deterministic nonces

RFC 6979 eliminates this structural risk with deterministic ECDSA: derive \(k\) from the private key \(d\) and the digest \(H(m)\) via HMAC-DRBG instead of an RNG.

Now (1) the same \((d, m)\) always gives the same \(k\) while different messages get cryptographically independent \(k\) — no reuse, no bias; and (2) security no longer depends on RNG quality, so even low-entropy embedded devices are safe. Signatures become reproducible, which also simplifies testing. Modern ECDSA (OpenSSL, cryptography, Bitcoin libraries) uses RFC 6979. “Hedged” variants additionally mix in randomness to resist fault injection.

EdDSA / Ed25519

EdDSA (Edwards-curve Digital Signature Algorithm), and specifically Ed25519 (over the twisted Edwards form of Curve25519 with SHA-512), fixes ECDSA’s weaknesses by design. It is the default signature for SSH, Signal, WireGuard, TLS 1.3, and Git.

Key generation: hash the secret seed \(sk\) with SHA-512; clamp the first 32 bytes into the scalar \(a\) and keep the second 32 bytes as a “prefix” \(\mathrm{pre}\) . Public key \(A = aB\) (with base point \(B\) ).

Signing — for message \(M\) :

The signature is \((R, S)\) — 64 bytes total. Verification: check \(8 S B \overset{?}{=} 8 R + 8 H(R \| A \| M) A\) .

The crucial point: Ed25519’s \(r\) — the analogue of ECDSA’s nonce \(k\) — is derived deterministically from the secret prefix and the message (Eq. 11), with no RNG involved at all. Consequently:

• Nonce reuse and bias are structurally impossible — RFC 6979’s idea is baked into the scheme itself.
• High misuse resistance — Curve25519’s constant-time Edwards arithmetic resists side channels, and invalid-curve attacks are ruled out by design.
• Fast — friendly to batch verification and fast fixed-base multiplication; often faster than ECDSA at equal security.

For a curve-based signature in any new protocol, Ed25519 is the 2026 default. ECDSA remains where you need existing compatibility — TLS certificate chains, Bitcoin’s secp256k1, and so on.

RSA Signatures: PKCS#1 v1.5 vs RSA-PSS

RSA can sign too. Naively, apply the private exponent \(d\) to the digest (the “decrypt” operation) and undo it with the public exponent \(e\) :

But “textbook RSA signatures” are forgeable, so the padding scheme is what actually matters. There are two standards.

PKCS#1 v1.5

RSA PKCS#1 v1.5 signatures (as in JWT RS256) prepend a fixed padding string and a hash-algorithm identifier (an ASN.1 DigestInfo) before exponentiating. It is deterministic and simple, but because the padding is structured, sloppy verifiers have allowed the Bleichenbacher signature forgery (BB'06): with public exponent \(e=3\) and a verifier that does not strictly check padding, an attacker could fabricate a signature just by taking a cube root. It also has no tight security reduction, so it is “not formally guaranteed secure.” Yet it is still everywhere — JWT RS256, older TLS certificates, and countless legacy systems.

RSA-PSS

RSA-PSS (Probabilistic Signature Scheme) (JWT PS256) is the Bellare–Rogaway probabilistic padding: it mixes in a random salt so each signature differs, stretches the hash with MGF1, applies EMSA-PSS encoding, and then exponentiates.

Why PSS is preferred:

• Provable security: a tight EUF-CMA reduction to the RSA assumption in the random-oracle model. v1.5 has no such guarantee.
• Robustness via salt: being probabilistic, the same message yields a different signature each time, closing off attacks that target deterministic padding.
• Standards direction: NIST FIPS 186-5, TLS 1.3, and modern PKI recommend or require PSS.

For any new RSA signature, choose PSS. PKCS#1 v1.5 should be treated as legacy, kept only for backward compatibility.

Comparing the Three Schemes

Rules of thumb:

• New projects: prefer Ed25519. If you need curve compatibility or existing PKI, use ECDSA (P-256).
• Where RSA is mandatory (HSMs, old CAs): use RSA-PSS, avoid v1.5.
• Verification-heavy workloads (clients validating many certs): RSA verification is a cheap \(e = 65537\) exponentiation and can win.
• Cryptocurrency: Bitcoin and Ethereum sign with ECDSA over secp256k1 (Bitcoin also adopted Schnorr with Taproot).

As a concrete case, OAuth 2.0 / OIDC JWTs use the algorithm identifiers RS256 (RSA v1.5), PS256 (RSA-PSS), ES256 (P-256 ECDSA), and EdDSA (Ed25519).

Python Implementation

1. From-scratch educational ECDSA (verified by running it)

We implement ECDSA over the tiny curve \(y^2 = x^3 + 2x + 2 \pmod{17}\) with base point \(G = (5, 1)\) (order \(n = 19\) ). It transcribes Eqs. (4)–(6) directly and uses double-and-add for scalar multiplication. This code was actually run to confirm sign → verify → tamper detection, plus private-key recovery from nonce reuse.

import hashlib

# --- curve over a small prime field: y^2 = x^3 + 2x + 2 over F_17 ---
p = 17
a, b = 2, 2
G = (5, 1)   # base point
n = 19       # order of G (this point has order 19)
O = None     # point at infinity


def ec_add(P, Q):
    """point addition on the curve (inverse via pow(x, -1, p))"""
    if P is O:
        return Q
    if Q is O:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O  # P + (-P) = O
    if P == Q:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p  # tangent
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p         # chord
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)


def scalar_mult(k, P):
    """double-and-add: kP in O(log k) point operations"""
    R, Q = O, P
    while k:
        if k & 1:
            R = ec_add(R, Q)
        Q = ec_add(Q, Q)
        k >>= 1
    return R


def hash_to_int(msg):
    return int.from_bytes(hashlib.sha256(msg).digest(), "big") % n


def sign(d, msg, k):
    """signing: s = k^{-1}(e + rd) mod n  ... Eq. (4)"""
    e = hash_to_int(msg)
    r = scalar_mult(k, G)[0] % n
    assert r != 0
    s = pow(k, -1, n) * (e + r * d) % n
    assert s != 0
    return (r, s)


def verify(Q, msg, sig):
    """verification: x-coord of u1 G + u2 Q equals r  ... Eqs. (5), (6)"""
    r, s = sig
    if not (1 <= r < n and 1 <= s < n):
        return False
    e = hash_to_int(msg)
    w = pow(s, -1, n)
    u1, u2 = e * w % n, r * w % n
    X = ec_add(scalar_mult(u1, G), scalar_mult(u2, Q))
    return X is not O and X[0] % n == r


# --- key generation ---
d = 7                       # private key
Q = scalar_mult(d, G)       # public key Q = dG
assert scalar_mult(n, G) is O   # confirm G has order n

# --- sign and verify ---
msg = b"transfer 1 coin to Bob"
sig = sign(d, msg, k=11)
print("public key Q  =", Q)
print("signature     =", sig)
print("valid verify  :", verify(Q, msg, sig))                        # True
print("tamper detect :", verify(Q, b"transfer 1 coin to Eve", sig))  # False

# --- nonce reuse -> private-key recovery (Eq. (9)) ---
msg2 = b"transfer 2 coin to Bob"
sig2 = sign(d, msg2, k=11)  # SAME k reused (dangerous!)
r, s1 = sig
_, s2 = sig2
e1, e2 = hash_to_int(msg), hash_to_int(msg2)
k_rec = (e1 - e2) * pow(s1 - s2, -1, n) % n
d_rec = (s1 * k_rec - e1) * pow(r, -1, n) % n
print("recovered nonce k =", k_rec, "(true 11)")
print("recovered priv  d =", d_rec, "(true 7)")

Actual output:

public key Q  = (0, 6)
signature     = (13, 14)
valid verify  : True
tamper detect : False
recovered nonce k = 11 (true 11)
recovered priv  d = 7 (true 7)

The valid signature is accepted, a one-character edit is rejected, and reusing nonce \(k = 11\) just twice lets Eq. (9) recover the private key \(d = 7\) completely — the exact mechanism behind the PlayStation 3 break. This code is educational: it omits the huge real-world prime, constant-time arithmetic, DER encoding, and proper nonce generation.

2. Production library: ECDSA / Ed25519 / RSA-PSS with cryptography

In production, use a vetted library. Below are all three schemes with cryptography. This code is shown for reference only and was not executed, because cryptography is not installed in this environment (install it in real use with pip install cryptography).

# Note: requires the cryptography library (pip install cryptography).
#       Not installed in this article's environment, so it is shown but not run.
from cryptography.hazmat.primitives.asymmetric import ec, ed25519, padding, rsa
from cryptography.hazmat.primitives import hashes
from cryptography.exceptions import InvalidSignature

msg = b"contract: pay 100 USD"

# --- (a) ECDSA (P-256): nonce generated safely (RFC 6979 style) inside ---
ec_key = ec.generate_private_key(ec.SECP256R1())
ec_sig = ec_key.sign(msg, ec.ECDSA(hashes.SHA256()))
ec_key.public_key().verify(ec_sig, msg, ec.ECDSA(hashes.SHA256()))

# --- (b) Ed25519: deterministic, minimal API ---
ed_key = ed25519.Ed25519PrivateKey.generate()
ed_sig = ed_key.sign(msg)                       # no hash to choose
ed_key.public_key().verify(ed_sig, msg)         # raises InvalidSignature on failure

# --- (c) RSA-PSS: use PSS + MGF1, not v1.5 ---
rsa_key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
pss = padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                  salt_length=padding.PSS.MAX_LENGTH)
rsa_sig = rsa_key.sign(msg, pss, hashes.SHA256())

try:
    rsa_key.public_key().verify(rsa_sig, msg, pss, hashes.SHA256())
    print("all signatures verified")
except InvalidSignature:
    print("verification failed")

Key points: (a) the library’s ECDSA handles nonce generation safely, giving the caller no chance to mishandle \(k\) ; (b) Ed25519 offers no choice of hash, curve, or nonce — just sign(msg) / verify(sig, msg), a “hard to misuse” minimal API; (c) with RSA, spell out padding.PSS(...) and avoid the legacy padding.PKCS1v15() for new work. The library absorbs the landmines that from-scratch code steps on (nonce disasters, padding oracles), which is the main reason to use it in production.

Summary

• A digital signature is the triple \((\mathsf{Gen}, \mathsf{Sign}, \mathsf{Verify})\) ; hash-and-sign compresses any-length messages to a fixed digest before signing.
• Unlike a MAC, it provides non-repudiation (only the private-key holder can sign; anyone can verify with the public key). The security bar is EUF-CMA.
• ECDSA works via Eqs. (4)–(6), but nonce reuse or bias leaks the private key instantly (PlayStation 3, lattice attacks). RFC 6979 deterministic nonces prevent this structurally.
• Ed25519 (EdDSA) bakes deterministic nonces into the scheme and beats ECDSA on misuse resistance and speed — the default for new protocols.
• For RSA signatures, prefer provably secure RSA-PSS over PKCS#1 v1.5.
• Choose among RSA-PSS / ECDSA / Ed25519 by use case; see the comparison table for TLS, JWT, SSH, and cryptocurrency examples.
• In Python, learn with the from-scratch ECDSA (run and verified) and ship with cryptography’s ec / ed25519 / padding.PSS.

Related Posts

• Cryptography Roadmap: from DLP, factoring, and elliptic curves to PQC - the learning map of the whole field; signatures are a core public-key application.
• Elliptic Curve Cryptography (ECC) in Python - the point arithmetic and ECDLP that ECDSA / Ed25519 ride on.
• RSA in Python: theory, key generation, encryption, decryption - the public-key primitive behind RSA-PSS and PKCS#1 v1.5.
• Diffie-Hellman key exchange: theory and implementation - the key-exchange counterpart used alongside signatures in TLS.
• AES / ChaCha20 symmetric cryptography in Python - contrast between AEAD MACs and signatures.
• Fast modular exponentiation by repeated squaring in Python - the basis of scalar-mult double-and-add and RSA exponentiation.
• Elliptic-curve ElGamal encryption in Python - encryption on elliptic curves, adjacent to ECDSA.
• OAuth 2.0 / OIDC primer - real JWT signature algorithms (RS256 / PS256 / ES256 / EdDSA).
• Zero trust security - fitting signature-based PKI / mTLS into organizational design.
• Security certifications: CISSP vs the Japanese RISS exam - certifications covering signatures and PKI.

Related Tools

• Hash Generator (DevToolBox) - compute the hash-and-sign digest \(H(m)\) .
• Base Converter (CalcBox) - inspect hex encodings of signatures and keys.

References

• Johnson, D., Menezes, A., & Vanstone, S. (2001). “The Elliptic Curve Digital Signature Algorithm (ECDSA)”. International Journal of Information Security, 1(1), 36–63.
• Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B.-Y. (2012). “High-speed high-security signatures”. Journal of Cryptographic Engineering, 2(2), 77–89.
• Josefsson, S., & Liusvaara, I. (2017). “Edwards-Curve Digital Signature Algorithm (EdDSA)”. RFC 8032.
• Pornin, T. (2013). “Deterministic Usage of DSA and ECDSA”. RFC 6979.
• Bellare, M., & Rogaway, P. (1996). “The Exact Security of Digital Signatures — How to Sign with RSA and Rabin”. EUROCRYPT ‘96.
• Moriarty, K. et al. (2016). “PKCS #1: RSA Cryptography Specifications Version 2.2”. RFC 8017.
• NIST (2023). “Digital Signature Standard (DSS)”. FIPS 186-5.