Cryptography
plaintext
encrypt
ciphertext
4/14/2006
Cryptography
Outline
Traditional cryptography Statistical attacks Secret-key encryption Public-key encryption
4/14/2006
Cryptography
Encryption
Scenario:
Alice wants to send a message (plaintext p) to Bob. The communication channel is insecure and can be eavesdropped If Alice and Bob have previously agreed on an encryption scheme (cipher), the message can be sent encrypted (ciphertext c)
Issues:
What is a good encryption scheme? What is the complexity of encrypting/decrypting? What is the size of the ciphertext, relative to the plaintext? If Alice and Bob have never interacted before, how can they agree on an encryption scheme?
plaintext
4/14/2006
encrypt
ciphertext
Cryptography
decrypt
plaintext
3
Traditional Cryptography
Ciphers were already studied in ancient times Caesars cipher:
replace a with d replace b with e ... replace z with c
Caesars cipher is an example of a monoalphabetic substitution cipher, which permutes the characters Armed with simple statistical knowledge, one can easily break a monoalphabetic substitution cipher
most frequent letters in English: e, t, o, a, n, i, ... most frequent digrams: th, in, er, re, an, ... most frequent trigrams: the, ing, and, ion, ...
The first description of the frequency analysis attack appears in a book written in the 9th century by the Arab philosopher al-Kindi
4/14/2006 Cryptography 4
Statistical Attacks
Armed with statistical knowledge about the plaintext language, one can easily break a monoalphabetic substitution cipher
Most frequent characters in English: e, t, o, a, n, i, ... Most frequent digrams: th, in, er, re, an, ... Most frequent trigrams: the, ing, and, ion, ...
The first description of the frequency analysis attack appears in a book written in the 9th century by the Arab philosopher al-Kindi Example (S. Singh, The Code Book, 1999):
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU? OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK
4/14/2006 Cryptography 5
Frequency Analysis (1)
We identify the most common characters, digrams and trigrams in the ciphertext Example PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU? OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK First guess:
LBO is THE
4/14/2006
Cryptography
Frequency Analysis (2)
Assuming LBO represents THE, we replace L with T, B with H, and O with E and get PCQ VMJYPD THYK TYSE KHXHJXWXV HXV ZCJPE EYPD KHXHJYUXJ THJEE KCPK. CP THE THCMKXPV XPV IYJKT PYDHT, QHEP KHO HXV EPVEV THE LXRE CI SX'XJMI, KHE JCKE XPV EYKKEV THE DJCMPV ZEICJE HYS, KXUYPD: DJEXT EYPD, ICJ X THCMKXPV XPV CPE PYDHTK Y HXNE ZEEP JEACMPTYPD TC UCM THE IXZREK CI FXKT XDEK XPV THE REDEPVK CI XPAYEPT EYPDK. SXU Y SXEE KC ZCRV XK TC AJXNE X IXNCMJ CI UCMJ SXGEKTU? EFYRCDME, TXREK IJCS THE THCMKXPV XPV CPE PYDBTK
4/14/2006
Cryptography
Decryption
Code: X Z A V O I D B Y G E R S P C F H J K L M N Q T U W A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Ciphertext: PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU? OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK Plaintext: Now during this time Shahrazad had borne King Shahriyar three sons. On the thousand and first night, when she had ended the tale of Ma'aruf, she rose and kissed the ground before him, saying: Great King, for a thousand and one nights I have been recounting to you the fables of past ages and the legends of ancient kings. May I make so bold as to crave a favour of your majesty? Epilogue, Tales from the Thousand and One Nights
4/14/2006 Cryptography 8
Enigma Machine
The Enigma was a commercial crypto device adopted by various military and governmental services, including Nazi Germany during World War II Computer science pioneer Alan Turing helped decrypting the Enigma Reuse of keys helped It is conjectured that two years of war were prevented by decrypting the Enigma
4/14/2006 Cryptography 9
Secret-Key Encryption
A secret-key cipher uses a unique key K to encrypt and decrypt Caesars generalized cipher uses the modular addition of each character (viewed as an integer) with the key: C[i] = P[i] + K mod m P[i] = C[i] K mod m More secure secret-key encryption schemes have been devised in this century Examples:
AES DES 3DES IDEA BLOWFISH
With private-key encryption, a distinct secret key must be established for every pair of parties
4/14/2006 Cryptography 10
Data Encryption Standard (DES)
Developed in 1977 NIST / NSA 64 bit blocks 64 bit key
Every 8th bit parity bit Effective key length: 56 bits
Multiple rounds per block Electronic code book (ECB) mode
Encrypt blocks independently Position of block in sequence does not matter
Cipher block chaining (CBC) mode
Block i of ciphertext XORed with block i +1 of plaintext Dependency between blocks
4/14/2006 Cryptography 11
3DES and AES
DES key space size too small (256) 3DES: triple DES key size
Brute force cracking in less than a day DES(DES(DES(plaintext , key1), key2), key3) Substitution-permutation network Current government standard Key size
Secret: 128+ bits Top Secret: 192+ bits
Advanced Encryption Standard (AES)
Timing (side channel) attacks
4/14/2006 Cryptography 12
Symmetric Encryption in Java
Create Key
KeyGenerator keygen = KeyGenerator.getInstance("DES"); SecretKey desKey = keygen.generateKey();
Encrypt
Cipher desCipher = Cipher.getInstance("DES/ECB/PKCS5Padding"); desCipher.init(Cipher.ENCRYPT_MODE, desKey); byte[] plaintext = someplaintext".getBytes(); byte[] ciphertext = desCipher.doFinal(plaintext);
Decrypt
desCipher.init(Cipher.DECRYPT_MODE, desKey); byte[] decrypted = desCipher.doFinal(ciphertext);
4/14/2006 Cryptography 13
Public-Key Encryption
Bob uses a pair of keys (KE,KD) and
makes key KE public keeps key KD private
Anyone can use the public key KE to encrypt a plaintext into a ciphertext sent to Bob Only Bob can decrypt the ciphertext using the private key KD The most popular encryption scheme is RSA, named after its inventors Rivest, Shamir, and Adleman (1978) The RSA patent expired in 2000 public key plaintext
4/14/2006
private key ciphertext
Cryptography
encrypt
decrypt
plaintext
14
