**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 it."What does this paragraph say to a system administrator or security officer seeking insight to defend her systems?^{1}

- 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
required]*not*

- Benefits: can give confidentiality or authentication or both

- RSA
- Provides both authenticity and confidentiality
- Go through algorithm:

Idea:*C*=*M*mod^{e}*n*,*M*=*Cd*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). - Example:

*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*=*M*^{e}mod*n*= 2^{11}mod 35 = 2048 mod 35 = 18, and*M*=*C*^{d}mod*n*= 18^{11}mod 35 = 2. - 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)^{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*given*y* - Variant: given
*x*and*y*, computationally infeasible to find a second*x*' such that*y*=*h*(*x*'). - Keyed vs. keyless

- Function

1.
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.