Lecture 15 Outline

Reading: text, §10, 11
Due: Homework 4, on May 23

1. Greetings and felicitations!
   1. Discussion question
2. RSA
   1. Provides both authenticity and confidentiality
   2. Go through algorithm:
      Idea: C = M^e mod n, M = C^d mod n, with ed mod φ(n) = 1
      Public key is (e, n); private key is d. Choose n = pq; then φ(n) = (p−1)(q−1).
   3. 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, and M = C^d mod n = 18¹¹ mod 35 = 2.
   4. 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; … = 3106 0100 0931 2691 1984 2927
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: encipher, then signs (risks)
5. Key Exchange
   1. Needham-Schroeder and Kerberos
   2. Public key; man-in-the-middle attacks
6. Key Generation
   1. Cryptographically random numbers
   2. Cryptographically pseudorandom numbers
   3. Strong mixing function

Discussion question. How does weapon development, as described in the following paragraph, compare to developing computer security mechanisms?

Weapons developers, when given a choice, always go for the complex, elaborate solution at the expense of the simple one. Complexity leads to higher costs: purchase costs, operations costs, and maintenance costs. Higher costs result in fewer weapons, which, in turn, lead to contrived tests and analyses to prove that the relatively few complex systems can overcome the larger numbers of the simpler, less expensive weapons of the enemy. The fewer the weapons, the tighter is the control of these precious assets by a centralized command structure. The elaborate paraphernalia that comes with the centralized command structure only adds to the complexity of the overall system.

From J. Burton, The Pentagon Wars, Naval Institute Press, Annapolis, MD (1993), p. 41.

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

ECS 153, Computer Security Version of May 16, 2016 at 8:12PM You can also obtain a PDF version of this.