Further Reading: Cryptography — From Caesar Cipher to RSA

Annotated pointers for going deeper, grouped by what you want next: the number-theory underpinnings, the cryptography proper, the security mindset, and the history. Start with the textbook sections, then branch out as your interest (rigor, security practice, or the human story) pulls you. All sources below are Tier-1 (canonical, verifiable) or Tier-2 (a real result/idea attributed carefully).

Core textbook treatments (the math behind RSA)

Rosen, Discrete Mathematics and Its Applications (8th ed.), §4.6 ("Cryptography") and §4.1–4.4 (Tier 1.) The market-standard discrete-math treatment: classical ciphers, the RSA cryptosystem, and the modular-arithmetic and Euclidean-algorithm machinery (§4.1–4.4) that §25.4 leans on. If you want more drill problems on shift/affine ciphers and RSA than this chapter provides, this is the first stop.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), number-theory chapters (Tier 1; freely available.) The most CS-flavored derivation of the Euler/Fermat results and RSA in print, in the same "number theory is a tool for computation" spirit as this chapter. The RSA correctness argument is developed with exactly the care §25.5 uses. Highly recommended as a free companion.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 4 ("Number Theory") (Tier 1.) Dense but rewarding background on congruences, the totient $\phi$, and the structure that makes Euler's theorem tick. Read it if you want the number theory of §25.4–25.5 with more depth and more identities.

Cryptography proper (the security half)

Katz & Lindell, Introduction to Modern Cryptography (3rd ed.) (Tier 1.) The standard modern graduate/upper-undergraduate text and the natural next book after this chapter. It is where the §25.6 ideas become precise: it defines semantic security (why determinism is a flaw), develops RSA with padding (OAEP), treats the factoring and RSA assumptions rigorously, and covers digital signatures properly. The English-letter frequency figures and the "textbook RSA is insecure" analysis in §25.1 and §25.6 are presented here in full.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the number-theoretic algorithms chapter (Tier 1.) The algorithmic companion: the extended Euclidean algorithm, modular exponentiation, the RSA public-key cryptosystem, and primality testing, all as analyzed algorithms with running times. This is where the "how fast is each step" question behind §25.6's key-size discussion is answered carefully. (Rivest and Adleman, two of CLRS's authors, are the "R" and "A" of RSA.)

The security mindset (why correct ≠ secure)

Diffie & Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory (1976) (Tier 1.) The paper that opens this chapter's epigraph and invented public-key cryptography — the key-distribution problem of §25.2 and the trapdoor idea of §25.3 are stated here for the first time in the open literature. Short, historic, and surprisingly readable; read it once for the thrill of seeing the idea born.

Rivest, Shamir & Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM (1978) (Tier 1.) The original RSA paper. Everything in §25.4–25.6 — key generation, the $m^{ed}\equiv m$ correctness argument, the security-rests-on-factoring claim, and even the digital-signature application — is in this one paper. Reading the source after building RSA yourself is unusually satisfying.

Kerckhoffs's principle (Tier 2.) The maxim that a cryptosystem must stay secure even when the attacker knows everything but the key (§25.1) is due to Auguste Kerckhoffs's 1883 essay La cryptographie militaire; it is most often encountered via Shannon's restatement, "the enemy knows the system." Any of the textbooks above states and uses it; the historical attribution is reliable even if you read it secondhand.

History and human story

Singh, The Code Book (1999) (Tier 2.) A widely praised popular history of cryptography from Caesar's cipher through al-Kindi's frequency analysis (§25.1) to RSA and the secret British prehistory of public-key crypto (Ellis, Cocks, Williamson, named in §25.3). Not a textbook, but the best narrative companion to this chapter — read it for why each idea mattered when it appeared.

A note on what comes after RSA

Post-quantum cryptography (overview). (Tier 2.) §25.6 notes that a large quantum computer running Shor's algorithm would factor efficiently and break RSA. The field building replacements is real and active; the U.S. NIST post-quantum standardization effort (concluding in the mid-2020s) is the standard entry point. Katz & Lindell (above) is the right place to first read why RSA's hardness assumption is quantum-fragile before diving into the lattice-based alternatives.

Suggested order

  1. Re-read §§25.4–25.6 here, then do Rosen §4.6 exercises for drill on RSA and the classical ciphers.
  2. Read the MIT 6.042 number-theory chapters to re-derive Euler/Fermat and the RSA correctness proof in a second voice.
  3. Read the original Diffie–Hellman (1976) and RSA (1978) papers — short, and far more accessible once you have built RSA yourself.
  4. Move to Katz & Lindell for the security half: semantic security, padding/OAEP, the factoring assumption, and signatures — i.e., everything §25.6 only gestured at.
  5. Read CLRS's number-theoretic-algorithms chapter alongside Katz–Lindell for the running-time view behind key-size choices.
  6. Save Singh's The Code Book for any evening you want the story rather than the math.