Series 7 · The cryptography of signatures · 7.2

RSA from the inside.

Modular arithmetic, Euler's theorem and why an RSA signature without padding is not a signature.

October 202610 min read

In April 1977, after a Passover dinner at a student’s home, Ron Rivest could not sleep. For months he, Adi Shamir and Leonard Adleman had been testing candidates for the trapdoor function Diffie and Hellman had imagined; Adleman, the group’s mathematician, had knocked them down one after another. That night Rivest wrote up a proposal based on integer factorization. The next morning Adleman could find no way to break it. The paper they published in Communications of the ACM in February 1978 is still, almost half a century later, the basis of a large share of the world’s digital signatures.

RSA can be explained on a single page. Using it well took decades. This article covers both: the mathematics, with an example you can follow with pencil and paper, and the details that separate an elegant formula from a secure signature.

The trapdoor: multiplying is easy, factoring is not

Multiplying two 1536 bit primes takes microseconds. Recovering those primes from the product, a 3072 bit number, is beyond the reach of any known classical computer. The best algorithm, the general number field sieve, has a subexponential cost that, at that size, amounts to about 2¹²⁸ operations.

Turning that asymmetry into a trapdoor requires a result from 1763. Euler’s theorem states that if m and n share no common factors, then m^φ(n) ≡ 1 (mod n), where φ(n) counts the numbers smaller than n that are coprime to it. If n = p · q with p and q prime, that count is easy to compute, but only for someone who knows p and q:

φ(n) = (p 1)(q 1)

Knowing φ(n) is equivalent to knowing the factorization: given n and φ(n), p and q fall out of a quadratic equation.

Generating keys, signing, verifying

Choose two large primes p and q, at random, of equal size and not too close to each other. Their product n is the modulus.
Choose the public exponent e, coprime to (p 1)(q 1). It is almost always 65537, that is 2¹⁶ + 1: it is prime and has only two ones in binary, so verifying costs 16 squarings and one multiplication.
Compute the private exponent d, the inverse of e modulo φ(n) (or modulo λ(n) = lcm(p 1, q 1), as FIPS 186 5 requires; both work). It is obtained with the extended Euclidean algorithm.
Publish (n, e) and keep d. The primes must be destroyed or protected just like d.

Sign: s = m^d mod n

Verify: s^e mod n = m ?

It works because e · d = 1 + k · φ(n) for some integer k, and then s^e = m^e·d = m · (m^φ(n))^k ≡ m · 1^k = m (mod n). The Chinese remainder theorem shows that it also holds when m shares a factor with n.

The classic example uses p = 61 and q = 53. Then n = 3233, φ(n) = 3120, and with e = 17 we get d = 2753, because 17 · 2753 = 46801 = 15 · 3120 + 1. The signature of the message 65 is 65²⁷⁵³ mod 3233 = 588, and anyone can check that 588¹⁷ mod 3233 = 65. The lab lets you repeat the calculation with other primes and see what happens when something changes.

LabToy RSA, with numbers that fit in your head

Prime p

Prime q

Public exponent e

Message to sign, as a number m smaller than n (in practice, the padded hash)

Choose the parameters and sign.

Why that formula alone is not a signature

What the lab shows, and what the original paper described, is known as “textbook” RSA. It has serious problems if applied as is to messages.

It is multiplicative. If s₁ signs m₁ and s₂ signs m₂, then s₁ · s₂ mod n is a valid signature on m₁ · m₂ mod n. Two legitimate signatures yield a third.
It allows existential forgery. Anyone can pick a random s, compute m = s^e mod n, and hold a valid pair. The message will be meaningless, but the security definition demands that even this be impossible.
It cannot handle long messages. Only a number smaller than n can be signed.

The answer to all three is the same: you do not sign the message but its hash, and the hash is encoded in a rigid format, the padding, before being raised to d. The hash removes the algebraic relations between messages; the padding fills the full width of the modulus and gives it a structure that a random number lacks.

PKCS #1 version 1.5

The most widespread format, defined by RSA Laboratories in the early 1990s and maintained today in RFC 8017, is deterministic. The block raised to d is:

EM = 00 ‖ 01 ‖ FF FF … FF ‖ 00 ‖ DigestInfo(algorithm, H(m))

DigestInfo is an ASN.1 structure that identifies the hash function and contains the hash. The FF bytes pad to the exact size of the modulus.

No practical attack is known against a properly implemented PKCS #1 version 1.5 signature. But “properly implemented” turned out to be demanding. In 2006 Daniel Bleichenbacher showed that many verifiers, instead of rebuilding the complete block and comparing it, parsed it from left to right and did not check that there were no leftover bytes after the hash. With e = 3, this made it possible to construct by hand a number whose cube began with the correct prefix and ended in garbage, and thereby forge signatures without the key. Variants of the same bug resurfaced in different libraries for years. The lesson is general: a verifier must recompute what it expects and compare the whole thing, never parse what it receives.

PSS: the signature with a proof

In 1996 Mihir Bellare and Phillip Rogaway proposed the probabilistic signature scheme, PSS. It adds a random salt and mixes everything with a mask generation function, so that signing the same message twice yields two different signatures:

M′ = 00…00 (8 bytes) ‖ H(m) ‖ salt

h = H(M′)

DB = padding ‖ 01 ‖ salt maskedDB = DB ⊕ MGF1(h)

EM = maskedDB ‖ h ‖ BC → s = EM^d mod n

Its advantage is not merely practical. PSS has a security proof: in the random oracle model, forging a signature is as hard as inverting RSA, with a tight reduction, losing no significant security along the way. PKCS #1 version 1.5 has no comparable proof. That is why the standards recommend PSS for new systems, even though version 1.5 remains ubiquitous for compatibility.

The Chinese remainder shortcut, and its trap

Signing is expensive: d is as long as n. Every serious implementation uses the Chinese remainder theorem. It computes the signature separately modulo p and modulo q, with reduced exponents d mod (p 1) and d mod (q 1), and combines the two results. Since each half works with numbers of half the size, signing becomes about four times faster.

In 1997 Dan Boneh, Richard DeMillo and Richard Lipton pointed out the price, and Arjen Lenstra showed that a single faulty signature is enough. If just one of the two halves is computed incorrectly, through a hardware error, a voltage glitch or a laser pulse deliberately fired at a card, the resulting signature s′ is correct modulo one prime and wrong modulo the other. Then:

gcd(s′^e m, n) = p

A single faulty signature hands over the factorization of the modulus, and with it the entire private key.

The countermeasure is simple and mandatory: verify the signature before releasing it. Secure signature creation devices do this, and their security evaluations include fault injection attacks for exactly this reason.

In RSA the mathematics is the easy part. The hard part is everything around it: the padding, the verification, the prime generation and the hardware doing the computing.

How long a key should be

RSA security is measured in equivalent bits: how many operations the best known attack would cost, expressed as a power of two. NIST publishes the equivalence in its key management recommendation.

RSA modulus	Equivalent security	Status
1024 bits	about 80 bits	Not accepted for new signatures.
2048 bits	112 bits	Minimum accepted today.
3072 bits	128 bits	Recommended for long horizons.
7680 bits	192 bits	Rarely used: slow, large signatures.
15360 bits	256 bits	Impractical; here elliptic curves win clearly.

Public factoring records show the real pace of progress. In 2019 an academic team factored RSA 240, a 795 bit number, using about 900 core years of computation. Doubling the size of the modulus multiplies the cost by astronomical factors, which is why 2048 bits remains out of classical reach by a wide margin. The threat that would genuinely change the picture is a different one: Shor’s algorithm, which on a fault tolerant quantum computer factors in polynomial time. The last article in this series is devoted to it.

What the formula does not show

Primes generated with a good random generator: if two devices share a prime, a simple greatest common divisor breaks both.
Primes of equal size but not close together: if |p q| is small, Fermat’s method factors instantly.
PSS padding or, for compatibility, PKCS #1 version 1.5 with strict verification.
Signature verified before it leaves the device, as a defense against faults.
Constant time implementation, so as not to leak bits of d through computation time.

Key takeaways

RSA signs with s = m^d mod n and verifies with s^e mod n; it works thanks to Euler’s theorem and it is secure because computing d requires factoring n. But the formula alone is not a signature: it needs hashing and padding, ideally PSS. RSA’s historical failures were almost never mathematical; they came from verification, key generation or hardware.

Sources

← All notes