RSA Signatures

To SIGN a message: encrypt the HASH with the PRIVATE key.

Signing:
  h = SHA-256(message)
  signature = h^d mod n         (using private key)

Verifying:
  recovered_h = signature^e mod n   (using public key)
  expected_h = SHA-256(message)
  if recovered_h == expected_h: VALID

Why hash first? RSA's modulus n is bounded; you can't sign arbitrary-length data directly. Hashing reduces any message to a fixed 32-byte value (SHA-256).

The signature proves:

1. Authenticity: only someone with the private key could have produced it.
2. Integrity: changing the message invalidates the hash → invalid signature.

Padding for signing: PKCS#1 v1.5 (sign mode) or PSS. PSS is more secure but PKCS#1 is more compatible.

Hash:        SHA-256(M)
Padded:     0x00 || 0x01 || PS (0xFF repeated) || 0x00 || ASN.1_SHA256_OID || hash
Sign:        signature = padded^d mod n

The ASN.1 prefix identifies the hash algorithm. Without it, signature schemes are vulnerable to attacks where an attacker substitutes a different hash.

In practice: use a library. RSA-PSS-SHA256 is the modern recommendation. PSS includes randomness so two signatures of the same message differ — no replay attacks via signatures.