RSA is a public-key cryptosystem built on integer factorization. Multiplying two large primes is easy; recovering those primes from their product is computationally expensive, creating the trapdoor. section 8.3.2
Alice publishes the key pair components (n, e) while retaining d. Bob encrypts plaintext m as c = m^e mod n; Alice decrypts it as m = c^d mod n. section 8.3.2
Equation 8.9
\[\begin{aligned} \begin{aligned} \text{PubKey}_{\text{Alice}} &= (n, e) \\ \text{PrivKey}_{\text{Alice}} &= (d) \end{aligned} \label{equation:alice-rsa-keypair} \end{aligned}\]Inspect the public and private key notation used to describe an RSA key pair. section 8.3.2
Equation 8.10
\[\begin{aligned} \begin{aligned} c &= \text{Encrypt}(m, \text{PubKey}_{\text{Alice}}) \\ c &= m^e \bmod n \end{aligned} \label{equation:bob-rsa-encrypt} \end{aligned}\]Follow the modular exponentiation operation that turns plaintext into RSA ciphertext. section 8.3.2
Equation 8.11
\[\begin{aligned} \begin{aligned} m &= \text{Decrypt}(c, \text{PrivKey}_{\text{Alice}}) \\ m &= c^d \bmod n \end{aligned} \label{equation:alice-rsa-decrypt} \end{aligned}\]Follow the corresponding modular exponentiation operation that recovers plaintext with the private key. section 8.3.2
Figure 8.14 A sequence diagram depicting Bob sending a message to Alice using RSA encryption
Trace the message flow between sender and recipient in an RSA encryption exchange. section 8.3.2
Treat RSA as an implementation-sensitive construction:
- Use large integers to make factoring the modulus computationally expensive, accepting slower key generation and encryption or decryption. section 8.3.2
- Generate primes with strong randomness and test candidates for primality; poor randomness or hardware faults can produce shared-prime RSA keys. section 8.5
- Avoid textbook RSA’s deterministic behavior by using probabilistic padding schemes, and avoid small private exponents during key generation. section 8.5
- Detect vulnerable public moduli efficiently with the batch GCD algorithm. section 8.5
From factoring to RSA
Factoring a small number such as 764,512 can be attempted by trial division. Replacing its factors with large primes makes the same underlying operation impractical for computers, while preserving the paper-and-pencil intuition. section 8.3.2
