The signer raises the message to the secret exponent, $s = m^d \bmod N$; anyone verifies by raising the signature to the public exponent and checking $s^e \bmod N = m$. It is the same modular exponentiation run with opposite keys.

* Signing and verifying are the same exponentiation with opposite keys — they cancel because e·d ≡ 1 mod φ(N). *

The signer holds the RSA secret key $(p, q, d)$ and publishes $(N, e)$ with $N = p\cdot q$. Signing is just the private RSA operation:

$$s = m^d \bmod N$$

and verification is the public operation applied back:

$$s^e \equiv (m^d)^e \equiv m^{ed} \equiv m \bmod N.$$

The two undo each other because the key is built so that $e\cdot d \equiv 1 \pmod{\varphi(N)}$ — exactly the same relation that makes RSA decryption undo RSA encryption. So verifying a signature literally recomputes the message out of $s$; if the recomputed value equals the message the verifier holds, the signature is genuine.

Two practical points the raw formula hides:

• You sign a hash, not the raw document. In practice $m$ is $h(\text{message})$ — a fixed-size digest — so any length of contract fits inside $\mathbb{Z}_N$ and one exponentiation binds the whole document.
• Signing is the "reverse" of encrypting only for RSA. Encryption is $c = m^e$ (public exponent), signing is $s = m^d$ (secret exponent) — the operations look symmetric here, which is convenient but is precisely what the existential-forgery attack exploits (see the next card). Most other signature schemes (DSA, Schnorr) deliberately make signing and verifying different operations to avoid that.

Go deeper:

• RSA (cryptosystem) — signing and verification — the same modulus-and-exponent machinery, formalised, with the padding caveats.

Schoolbook RSA is deterministic — the same plaintext always encrypts to the same ciphertext — so an attacker can pre-encrypt every likely message under the public key, store the results as a look-up table, and read off plaintexts by matching intercepted ciphertexts.

* Because encryption is repeatable, the attacker precomputes every likely (m, c) pair and inverts intercepts by lookup — no factoring needed. *

RSA on its own is not a probabilistic algorithm: with the public key $(N, e)$ fixed, $c = m^e \bmod N$ is a fixed function of $m$. That determinism is fatal whenever the message space is small or guessable — a yes/no vote, a price from a short list, a PIN, a database field with few values. The attacker knows $(N, e)$, so she simply:

1. Enumerates every candidate plaintext $m$.
2. Computes $c = m^e \bmod N$ for each and stores the pairs $(m, c)$ — the "codebook".
3. Later inverts any captured ciphertext by looking it up in the table.

No factoring of $N$, no knowledge of $d$ — the confidentiality is broken purely because encryption is repeatable. The cure is to destroy the determinism: pad the message with fresh randomness before encrypting (OAEP — Optimal Asymmetric Encryption Padding), so the same plaintext maps to a different ciphertext every time and no finite table can ever cover it. The same padding also kills RSA's multiplicative malleability. (This is an attack on RSA encryption; RSA signing has its own separate weakness — existential forgery, next.)

Go deeper:

• Deterministic encryption — why it leaks — the "build a dictionary of plaintext/ciphertext pairs" attack, stated generally.
• Optimal Asymmetric Encryption Padding (OAEP) — the randomised padding that turns deterministic RSA probabilistic.