Outline for October 13, 2025

Reading: text, §10.3.2, 10.4–10.5
Assignments: Homework 2, due October 22; Project selection, due November 7

1. Greetings and Felicitations!
   1. Zoom office hour on Wednesday moved to 4:00pm–4:50pm; same meeting id, password

2. RSA
   1. Provides both authenticity and confidentiality
   2. Based on difficulty of computing totient, φ(n), when n is difficult to factor
   3. Go through algorithm:
      Idea: Choose n = pq; then φ(n) = (p−1)(q−1)
      Choose d and compute e such that ed mod φ(n) = 1
      Now C = M_e mod n, M = C^d mod n
      Public key is (e, n); private key is d.
   4. Example: p = 5, q = 7; then n = 35, φ(n) = (5−1)(7−1) = 24. Pick d = 11. Then ed mod φ(n) = 1, so e = 11
      To encipher 2, C = M_e mod n = 2¹¹ mod 35 = 2048 mod 35 = 18
      To decipher 18, M = C^d mod nn = 18¹¹ mod 35 = 2.
   5. Example: p = 53, q = 61; then n = 3233, φ(n) = (53−1)(61−1) = 3120. Pick d = 791. Then e = 71
      To encipher M = RENAISSANCE, use the mapping A = 00, B = 01, …, Z = 25, ␢ = 26.
      Then: M = RE NA IS SA NC E␢ = 1704 1300 0818 1800 1302 0426
      So: C = 1704⁷¹ mod 3233 = 3106 …, giving C = 3106 0100 0931 2691 1984 2927
      And: M = 3106⁷⁹¹ mod 3233 = 1704 …, giving M = 1704 1300 0818 1800 1302 0426

3. Cryptographic Checksums
   1. Function y = h(x): easy to compute y given x; computationally infeasible to compute x given y
   2. Variant: given x and y, computationally infeasible to find a second x′ such that y = h(x′)
   3. Keyed vs. keyless

4. Digital Signatures
   1. Judge can confirm, to the limits of technology, that claimed signer did sign message
   2. RSA digital signatures: sign, then encipher, then sign

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 235A, Computer and Information Security Version of October 13 2025 at 10:35AM

You can also obtain a PDF version of this.