L15 Digital Signatures

Real-world and digital signatures. RSA signatures, attacks, and padding schemes.

What does a digital signature provide that a MAC does not?

Non-repudiation.

With a MAC, either party could have generated it (since both share the key).

With a digital signature using asymmetric cryptography, only the signer’s private key could have produced the signature - so the signer cannot deny having signed

What are the three properties a digital signature scheme provides?

• Authenticity - confirms who sent it

• Integrity - message hasn’t been changed

• Non-repudiation - sender cannot deny signing

How does RSA signing work (in general)?

The signer uses their private key to produce a signature from the message

The verifier uses the signer’s public key to verify it

Only the private key holder can sign, but anyone with the public key can verify

Why is it efficient to keep e (the public exponent) small in RSA signatures?

Verification uses the public exponent e and is performed far more than signing.

A small e makes verification fast, which is important for performance at scale

What is a signature forgery?

The ability to create a valid (message, signature) pair for a message that was never signed by the legitimate signer.

Replaying a previous observed (m, s) pair does not count

What is an existential forgery in RSA?

An attacker with the public key can pick a random s and compute m’, producing a valid (m’, s) pair - without knowing the private key.

The message m’ is meaningless, but it’s technically a valid forgery. This shows why you must hash and pad messages before signing.

How does padding *like adding structured bits) help prevent signature forgeries?

If valid signatures must conform to a specific format, a random formed message is extremely unlikely to match it.

The probability of a successful forgery is approximately 2^-y, where y is the number of enforced padding bits

What is the difference between PKCS v1.5 and PSS padding for RSA signatures?

PKCS v1.5 is a deterministic scheme - signing the same message always gives the same signature

PSS (Probabilistic Signature Scheme) adds a random salt, so repeated signings of the same message gives different signatures - providing stronger security guarantees.