Textbook RSA applies modular exponentiation directly to an unpadded message representative. For encryption, it computes c = m^e mod n; for decryption, m = c^d mod n. For signatures, the private exponent produces s = m^d mod n, and the public exponent verifies it by recovering m. section 8.4.2 section 9.4
Treat direct textbook RSA as an explanatory primitive, not a safe deployment format:
- Deterministic encryption maps equal plaintexts to equal ciphertexts, revealing message equality; fixed points can also remain unchanged. section 8.4.2
- Unpadded signatures permit existential forgery: choose a signature s first, then publish m = s^e mod n. section 9.4
- Short private exponents enable Wiener’s attack when d < 1/3 n^(1/4); continued-fraction convergents of e/n can recover d. section 8.4.2
- Use probabilistic padding and strict message formatting in real implementations; avoid weak private exponents during key generation. section 8.4.2 section 9.7
Recovering a weak private exponent
A vulnerable Go implementation deliberately generates d below n^(1/4)/3, computes e as the inverse of d modulo φ(n), and encrypts m = 1337 as c = 60818 modulo n = 111361. An attacker expands e/n into continued fractions, tests each convergent denominator as a candidate d, and confirms the correct one when decryption reproduces the plaintext. section 8.4.2
Equation 9.2
\[\begin{aligned} \begin{aligned} s &= \text{Sign}(m, \text{PrivKey}_{\text{Alice}}) \\ s &= m^d \bmod n \end{aligned} \label{equation:alice-rsa-sign} \end{aligned}\]Follow the signing equation alongside verification to see how the private exponent creates a signature and the public exponent cancels it. section 9.4
