Lecture 8 Notes; April 16, 1997; Notetaker: Elizabeth Jurrus
DES - Data Encryption Standard (unbroken)
- main function: secrecy. Not used for classified data
- takes in 64 bits, outputs 64 bits, key is 56 bits (ignore parity bit)
- encipher and decipher blocks of data
- deciphering is the reverse processes of the enciphering processes
IDEA cipher - fixes weaknesses in DES
Lucifer Cipher - key changed from 128 to 64 bits. Good cipher
Product cipher - uses transposition and substitution at the bit level. Is also a round
cipher (iterates 16 times, 16 different keys).
DES - 3 parts
1) Initial Permutation (IP) (see page 17 of the Data Encryption Standard Handout)
- Used to generate 16 sets of keys („round keys¾) used to encipher
2) Complex key-dependent computation (see page 8 of the Data Encryption Standard
Handout )
- defined in terms of function f (the cipher function) and KS (the key
schedule)
- strength lies in how hard it is to invert f.
(see page 11 of the Data Encryption Standard Handout)
3) Inverse Initial Permutation (IP-1)
Things people noticed:
1) Complementation Problem (Diffie & Hellman):
DESk(M) = C DESe(M¼) = C¼
2) Certain keys contain their own inverses
DES0(M) = C DES0(C) = M
3) Double Encipherment does not help.
if (DESk2 (DESk1(M) ) = C then
DESk3(M) = C
How good is key length?
4) Differential Cryptanalysis
focus on plaintext and ciphertext pairs
C1 xor C2 = b
M1 xor M2 = b¼
DES modes:
1) ECD - straight DES. On it¼s way to being broken.
2) CBC - Cipher Block Chain
3) Triple DES - uses only 3 keys
4) EDE mode - uses 2 keys to add more complexity
(DESk1 (DES-1k2 (DESk1 (M)))
Public Key Cryptography (Diffie and Hellman):
- Created key exchange protocol
- How do you distribute keys?
- use 2 keys: 1) public - available to all ( E )
2) private - you are the only one who knows it (D)
RSA - an exponentiation cipher
C, M elem [0, n - 1]
Me mod n = C
Cd mod n = M
in order for this to work:
1) (Me mod n)d mod n = M or
2) Med mod n = M
must hold
ed mod g(n) = 1
Med mod n = M1+kg(n) mod n
( ed mod g(n) = 1 <=> ed = 1 + k g(n) )
= M (Mg(n))k mod n
= M (Mg(n) mod n) k mod n
= M ( 1 ) mod n
pick two large primes, p & q
p * q = n
pick e so that this holds:
ed mod g(n) = 1
where
g(n) = (p - 1)(q - 1)
d is a private key and the pair of e & n are public
take message, M
Me mod n = C
ed mod n = M (to decipher)
example:
p = 5, q = 7, => n = 35, g(n) = 24
e = 11
11d mod 24 = 1, so d = 1
M = hello ( message must not exceed 25 )
so, h e l l o
maps to 07 04 11 11 14
use 2811 mod 37 = 7 to decipher
Note: g(n) -> since e and n are unknown, it is easy to break the cipher. However, n cannot be
factored and you can¼t break the cipher.