Outline for October 17, 2003
Reading: Chapters 9.2--9.3
Some programs use passwords for access control, but do not protect
the passwords in a very sophisticated manner (for example, by saving
them in a file) or make determining the correct password very easy
(for example, the Microsoft Word 5.0 encipherment scheme). The
argument for using simple passwords and weak encipherment is that
the data or programs being protected are of little value and the
passwords give a small measure of privacy.
Given that what they are protecting is truly of little value, why
is the use of such simple passwords and easily-broken encipherment
Outline for the Day
- Classical Cryptography (con't)
- Polyalphabetic: Vigenère,
fi(a) = (a + ki) mod n
- Cryptanalysis: first do index of coincidence to see if it's
monoalphabetic or polyalphabetic, then Kasiski method.
- Problem: eliminate periodicity of key
- Long key generation
- 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.)
- Perfect secrecy: when the probability of computing the
plaintext message is the same whether or not you have the ciphertext
- Only cipher with perfect secrecy: one-time pads; C = AZPR;
is that DOIT or DONT?
- Public-Key Cryptography
- Basic idea: 2 keys, one private, one public
- Cryptosystem must satisfy:
- given public key, CI to get private key;
- cipher withstands chosen plaintext attack;
- encryption, decryption computationally feasible [note:
commutativity not required]
- Benefits: can give confidentiality or authentication or both
- Provides both authenticity and confidentiality
- Go through algorithm:
Idea: C = Me mod n,
M = Cd mod n, with
ed mod φ(n) = 1.
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 = 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 = Men =
211 mod 35 = 2048 mod 35 = 18, and
M = Cd mod n =
1811 mod 35 = 2.
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)71 mod 3233 = 3106; etc. =
3106 0100 0931 2691 1984 2927
Here is a PDF version of this document.