Digital Signatures

RSA Signatures

The RSA signature scheme was introduced by Rivest, Shamir, and Adleman. It parallels the structure of RSA encryption but is used to achieve data origin authentication, integrity, and non-repudiation.

• Key Generation: Same as RSA encryption (pick n, e, and d).
  Public key: (n, e), Private key: (n, d).
• Signing: For a message m, compute signature s = m^d mod n.
• Verification: To verify (m, s), check that s^e mod n = m.

Defining Signature Schemes

A digital signature scheme includes:

1. A randomized key generation algorithm G → (k_pubkey, k_privkey).
2. A signing algorithm that produces a signature S(k_privkey, m) for a message m.
3. A verification algorithm V(k_pubkey, m, σ) that outputs true or false.

Correctness demands that any signature generated with a valid private key must verify under the corresponding public key. The security requirement is that forging signatures without the private key should be infeasible.

Basic Security Requirements

• It should be hard to recover the private key from the public key.
• It should be infeasible to produce valid signatures without the private key.

Attack Models

Adversaries may attempt:

• Total break: recover the private key.
• Selective forgery: forge a signature on specific messages chosen by the adversary.
• Existential forgery: forge a valid signature on at least one message (not necessarily chosen in advance).

Possible adversarial capabilities include known-message attacks or chosen-message attacks (i.e., obtaining signatures on messages of their choice).

EUF-CMA Security

A standard notion is existential unforgeability under chosen-message attack (EUF-CMA): given oracle access to a signer for messages of the adversary’s choice, it should still be infeasible to create a valid signature on any new message not queried.

RSA Signatures (Continued)

A naive RSA signature (i.e., signing m directly by m^d mod n) can be insecure if used without additional care:

• Existential Forgery: Because the RSA function x → x^e mod n is multiplicatively malleable, an attacker might craft valid signatures on unintended messages.

Full Domain Hash RSA (RSA-FDH)

To counter these issues, one typically applies a hash function H:

1. Key Generation: same as RSA (public key (n, e), private key (n, d)).
2. Sign: σ = H(m)^d mod n.
3. Verify: check σ^e mod n == H(m).

In practice, H should be collision-resistant, preimage-resistant, and 2nd preimage-resistant for security.

Diffie–Hellman-based Signatures

Beyond RSA, signature schemes can also be built from Diffie–Hellman-type assumptions, leading to variants like DSA or ECDSA in elliptic curve settings.

For elliptic curves (ECDSA), we typically have:

• System parameters: large prime p, curve E over Z_p, base point P of prime order q.
• Key Generation: choose a random α, compute public key αP.
• Sign: pick random k, compute r from kP, then s = (H(m) + αr)*k⁻¹ mod q.
• Verify: recompute a point from the signature and check that its x-coordinate matches r.

These rely on the hardness of the Elliptic Curve Discrete Logarithm Problem.

Schnorr Signatures

A compact alternative in the Diffie–Hellman family is the Schnorr signature. It uses randomization plus a hash challenge:

1. Pick random k and compute W = kP.
2. Hash c = H(m || W || k_pubkey || ...).
3. Compute z = k + c·α mod q, where α is the private key.
4. Signature (W, c, z) verifies by checking W + c·(αP) = zP.

Schnorr’s design influences many modern signature schemes, including post-quantum variants based on lattice assumptions.

Post-quantum Digital Signatures

Quantum computers threaten classical number-theoretic problems like factoring or discrete logs. Hence, signature schemes that remain secure against quantum adversaries are being standardized. Examples include:

• Dilithium (ML-DSA): Based on module learning with errors.
• Falcon: Uses the NTRU lattice problem.
• SPHINCS+: A stateless hash-based signature scheme.
• HSS/LMS and XMSS: Stateful hash-based schemes (limited number of signatures).

These approaches protect against quantum algorithms that break RSA, ECDSA, and other classical techniques.

Standardization efforts by NIST (as of 2022–2025) focus on selecting robust post-quantum signature algorithms for widespread adoption.