Skip to content

RSA Signature Scheme

links: AC2 TOC - Digital Signatures - Index


See RSA to understand the basics.

Let \(pk=(n,e)\) and \(sk=(n,d)\) be ordinary RSA keys and \(M=S=\mathbb{Z}_n^*\)

RSA Signature.png

Again as in the encrypt-decrypt cycle in RSA, the signature and verify cycle relies on the inverse feature of the two keys leveraged. Signing is done by applying a modular exponentiation to the message using the senders private key \((d,n)\). The verification is done by applying the modular exponentiation to the signature received using the senders public key \((e,n)\). The result of the modular exponentiation must be equal to the received signature (which indicates a valid signature).

Security

Textbook RSA should never be implemented like that as it's not EUF-CMA secure:

  • Textbook RSA is deterministic (same message always gives the same result)
  • Textbook RSA is multiplicative (The attacker can choose \(m_1\) and \(m_2\), get signatures on them, and then construct a valid signature on the message \(m_1m_2\), even though they never got a signature on that message)

Sign the hash not the message!

Hash-and-Sign

Sign \(h = hash(m)\) instead of \(m \in \{0, 1\}^∗\), use a collision-resistant hash function.

RSA-SHA

\(hash: \{0, 1\}^∗ \rightarrow \{0, 1\}^{256}\) for SHA-256

  • Standardised in PKCS#1 v1.5 (includes padding)
  • No proof for EUF-CMA security

RSA-FDH (RSA-PSS)

Standardised in PKCS#1 v2.1 as RSA-PSS (probabilistic signature scheme)

EUF-CMA secure under RSA assumption (provided that \(hash(·)\) has the properties of a random oracle)

See more details here: FDH


links: AC2 TOC - Digital Signatures - Index