Outline for October 20, 2003
Reading: Chapters 9.3--9.4
"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
What does this paragraph say to a system administrator or security
officer seeking insight to defend her systems?
Outline for the Day
- 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 de mod φ(n) = 1,
so choose d = 11. To encipher 2,
C = Me mod n =
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
- Cryptographic Checksums
- Function y = h(x): easy to compute y
given x; computationally infeasible to compute x
- Variant: given x and y, computationally infeasible
to find a second x' such that y = h(x').
- Keyed vs. keyless
Sun Tzu, The Art of War, James Clavell, ed., Dell Publishing,
New York, NY ©1983, p. 15
Here is a PDF version of this document.