RSA-PSS — Probabilistic Signature Scheme

PKCS#1 v1.5 signatures are deterministic — same message, same signature. RSA-PSS adds a random salt, which gives a tight security proof (Bellare-Rogaway 1996, Coron 2002) in the random-oracle model.

TLS 1.3 (RFC 8446 §4.2.3) requires PSS for RSA signatures; PKCS#1 v1.5 is permitted only for legacy certificate verification.

EMSA-PSS-encode (RFC 8017 §9.1.1)

Given hash H (output hLen), message M, salt salt (length sLen), modulus bits emBits = modBits - 1:

mHash  = H(M)                                            // hLen bytes
M'     = 00 00 00 00 00 00 00 00 || mHash || salt        // 8 zeros prefix
H'     = H(M')                                           // hLen bytes
PS     = 00...00                                         // emLen - sLen - hLen - 2 bytes
DB     = PS || 0x01 || salt                              // emLen - hLen - 1 bytes
dbMask = MGF1(H', emLen - hLen - 1)
maskedDB = DB XOR dbMask
// Zero the leftmost (8*emLen - emBits) bits of maskedDB[0].
EM     = maskedDB || H' || 0xbc                          // emLen bytes

Signature: s = pow(int(EM), d, n).

Verification mirror

Verifier recovers EM from the signature, undoes the masking, recomputes H', and compares. The salt is embedded inside the EM — so the verifier doesn't need it provided separately.

Why the eight-byte zero prefix?

Bellare-Rogaway's proof needs the hash input to a unique structure. Eight zero bytes plus the message hash plus salt is domain-separated from any other use of H an attacker might exploit.

Salt length

sLen is a knob. RFC 8017 examples use sLen = hLen (32 bytes for SHA-256). TLS 1.3 mandates sLen = hLen. Some standards (X.509) allow sLen = 0 for "deterministic" PSS — still safe under the proof, just slightly looser.

Common foot-guns

• Modulus bit count: emBits = modBits - 1. For a 2048-bit key, emBits = 2047 so the leftmost bit of the first byte must be cleared after masking.
• The trailing 0xbc byte is mandatory — it's the "BC" terminator that distinguishes PSS from other padding schemes.
• Hash mismatch: signer and verifier must agree on H and MGF1's hash (usually the same). Mixing is allowed by the spec but cause of many interop bugs.

In this exercise

Implement EMSA-PSS-ENCODE and EMSA-PSS-VERIFY for an explicit salt. The RSA modular-exponentiation step is separate; here we exercise just the encoding/verification.