Computational cryptography › Public-key encryption and key exchange › Classical number theory › Factoring
SIGNATUREPrimitiveROMCRH

RSA signatures

In plain words

Digital signatures with RSA: proof that a document came from the owner of a key and wasn't changed.

The idea: To sign, you hash the document, pad the hash, and apply the RSA operation only the private key can do. Anyone can apply the public operation to the signature and check that they get the padded hash back. Hashing first keeps signatures short, but it means a signature really vouches for the hash: if someone found two documents with the same hash, a signature on one would also work for the other.

Why it matters: Most website certificates and many software updates are signed this way.

The details

On the map: PSS, PKCS#1 v1.5: certificates, code signing

An RSA signature is an e-th root of a padded hash of the message, computed with the private key. PSS is the provably secure padding (in the random oracle model)[1]. PKCS#1 v1.5 is the older format that still dominates certificates[2].

Because the message is hashed first, a hash collision becomes a forgery (the CRH tag): MD5 collisions were used to create a rogue certificate authority in 2008[3]. Most web certificate chains and much code signing still use RSA.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

ROM
Its security proof treats a hash function as a perfectly random function (the random oracle model). Real hashes aren't random functions, so this is a heuristic. For signatures and encryption no practical attack has exploited it. For multi-round proof systems, see the Fiat-Shamir box.
CRH
Hash-then-sign: the message is hashed before signing, so a collision in the hash function lets an attacker move a signature onto a different message.

References

  1. Mihir Bellare and Phillip Rogaway. The Exact Security of Digital Signatures-How to Sign with RSA and Rabin. Advances in Cryptology — EUROCRYPT ’96, 1996. doi:10.1007/3-540-68339-9_34
  2. B. Kaliski, J. Jonsson and A. Rusch. PKCS #1: RSA Cryptography Specifications Version 2.2. RFC 8017, 2016. rfc-editor.org/rfc/rfc8017
  3. Marc Stevens, Alexander Sotirov, Jacob Appelbaum et al. Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate. Advances in Cryptology - CRYPTO 2009. doi:10.1007/978-3-642-03356-8_4