Outline for April 21, 2005

Reading: §9

Discussion

"To fight and conquer in all your battles is not supreme excellence; supreme excellence consists in breaking the enemy's resistance without fighting. In the practical art of war, the best thing of all is to take the enemy's country whole and intact; to shatter and destroy it is not so good. So, too, it is better to capture an army entire than to destroy it, to capture a regiment, a detachment, or a company entire than to destroy it."¹

What does this paragraph say to a system administrator or security officer seeking insight to defend her systems?

Outline

1. Classical Cryptography
   1. Cryptanalysis of Vigenère: first do index of coincidence to see if it's monoalphabetic or polyalphabetic, then Kasiski method.
   2. Problem: eliminate periodicity of key
2. Long key generation
   1. Running-key cipher: M=THETREASUREISBURIED; K=THESECONDCIPHERISAN; C=MOILVGOFXTMXZFLZAEQ; wedge is that (plaintext,key) letter pairs are not random (T/T, H/H, E/E, T/S, R/E, A/O, S/N, etc.)
   2. Perfect secrecy: when the probability of computing the plaintext message is the same whether or not you have the ciphertext
   3. Only cipher with perfect secrecy: one-time pads; C = AZPR; is that DOIT or DONT?
3. DES
4. Public-Key Cryptography
   1. Basic idea: 2 keys, one private, one public
   2. Cryptosystem must satisfy:
      1. given public key, CI to get private key;
      2. cipher withstands chosen plaintext attack;
      3. encryption, decryption computationally feasible [note: commutativity not required]
   3. Benefits: can give confidentiality or authentication or both
5. 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.
      Proof: M^φ(n) mod n = 1 [by Fermat's theorem as generalized by Euler]; follows immediately from 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; n = 35, φ(n) = (5-1)(7-1) = 24. Pick e = 11. Then ed mod φ(n) = 1, so choose d = 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, n = 3233, φ(n) = (53-1)(61-1) = 3120. Take e = 71; then d = 791. Encipher M = RENAISSANCE: A = 00, B = 01, ..., Z = 25, blank = 26. Then:
      M = RE NA IS SA NC Eblank = 1704 1300 0818 1800 1302 0426
      C = (1704)⁷¹ mod 3233 = 3106; etc. = 3106 0100 0931 2691 1984 2927
6. 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