1CS 161– 11 September 2006© 2006 Doug Tygar 1CS 161 – Introduction to Cryptography; Symmetric Cryptography11 September 2006CS 161 – 11 September 2006© 2006 Doug Tygar 2Cryptography• History: Gallic Wars to WW2 (Enigma, Purple)• Ciphers vs. codes• Cryptology– Cryptography: making ciphers– Cryptanalysis: breaking ciphers– Traffic analysis: watching patterns of communications• Need: communications can be tapped• Building block for cryptographic protocols• In the US: National Security Agency2CS 161 – 11 September 2006© 2006 Doug Tygar 3Notation• Ciphertext = Encryption (Plaintext, encryption-Key)– sometimes we use “cleartext” instead of “plaintext”•Key ∈ Keyspace• Keysize = log2( |Keyspace| )• c=E(m,k) (or c=Ek(m) or c={m}k)• Also Plaintext = Decryption(Ciphertext, decryption-Key)• encyption-Key = decryption-Key (symmetric)• encyption-Key ≠ decryption-Key (asymmetric)•m=D(c,k)=E-1(c,k) (or c=Dk(m))CS 161 – 11 September 2006© 2006 Doug Tygar 4Attacks on cryptography• Direct attack– example: exhaustive search• Known plaintext• Chosen plaintext• Usual assumptions: chosen plaintext attack; attacker knows E, D but not key3CS 161 – 11 September 2006© 2006 Doug Tygar 5Perfect cryptosystem• One-time pad• Share a common key (key size ≥ message size)• XOR key with message• No information at all is leaked–Why?• What problem does this system have?CS 161 – 11 September 2006© 2006 Doug Tygar 6DES• Origins: mid-70s• History: (Lucifer, NIST, NSA)• 56 bit key, 64 bit block cipher• Differential cryptanalysis• Exhaustive search• AES (Rijndael)• 128-256 bit key, 128 bit block cipher4CS 161 – 11 September 2006© 2006 Doug Tygar 7Symmetric crypto• Advantages–Fast– Reasonably well-understood– Standardized– Can be implemented in hardware easily– Exhaustive search attack hard (with large key size)• Disadvantages– Key distribution– Single target– Still needs to be implemented in
View Full Document