ECS253 4/2/97 Ricardo Anguiano 1. Announcements Web page will be up by Friday. 2. Role of Cryptography (later crypto itself) Broad set of apporaches to conceal 2.1. Steganography * Writting with milk example: conceals the fact that there is a message * Microdot example: documents shrunk to the size of a period and mailed out with an inoccuous letter. * 24 bit images can carry information. 1 bit per pixel will not be visable to the human eye. 2.2. Caeser Cipher - advance each letter by three HELLO WORLD -> KHOOR ZRUOG * Key - the info needed to encipher or decipher a message. * Cipher - maps characters into characters. 2.3. Secret Writing Alternative: Code two sets of phrases. One is a garbled mess, the other the meaning of the garbled mess. Meaning of code depends on the code book used. Example Code Code Groups ------------ ----------- hello AXZB i love XCVJ i hate BSYK broccoli TRUX spinach PLUG 2.4. Supercipherment Combined Approach using Code and Encipherment. Use code book then encipher the code groups. Difficult to break, but has been broken in the past. 2.5 Terms * Plaintext(M): message to be enciphered. Also referred to as cleartext. * Ciphertext(C): output of encipherment function. Not generally understandable. 2.5. Note on International Usage * Encipher - to make unreadable without destroying the message. * Encrypt - similar to crypt, which is a burial ground or cemetary sounds like you are going to bury the message. 2.6. Notation * Encipher(Ek): Algorithm to encipher message * Decipher(Dk): Algorithm to decipher message * Key(k): information used to encipher message using a common algorithm. * Encipher: $E_k(M) = C$ * Decipher: $D_k(C) = M$ Clasical systems: encrypt and decrypt keys are the same. 2.7. Good Cryptosystems and Kirchoff's requirements * Enciphering and deciphering is EFFICIENT for all keys. Should not take forever to get message. * Easy to use. Not as important now because of computerization. Problem with hard to use cryptosystems is that mistakes tend to be made and message is never deciphered correctly, or a crib will be given to those trying to read the message. note: A crib is a hint to the adversary about what is contained in the message. * The strength of the system should not lie in the secrecy of your algorithms. The strength of the system should depend the secrecy of your key. Manuals can be stolen. It is Easy to generate new key, but hard to replace entire cryptosystem. 3. Secrecy or Confidentiality Encipher messages to protect secrecy * Intecepted ciphertext should not lend clues to what the deciphering algorithm is. It should be computationally infeasable (C.I.) * It should be C.I. to find M from C. 4. 4 attacks on cryptosystems * ciphertext only attack given the ciphertext, what is the original message? * known plaintext attack have both the plaintext and ciphertext. What is the key? * chosen plaintext attack give plaintext to adversary, get back enciphered message. * chosen ciphertext give ciphertext to adversary, get back plaintext. Not very practical and noted here for theoretical completeness only. 5. Authentication or Integrity Data is not to be altered. requirements for integrity: * C.I. to find $E_k$. Keeps adversary from changing encrypted messsage. * C.I. to find C' such that $D_{k}(C')$ is valid. 6. Computationally Infeasable (an explanation) Degrees of security * unconditionally secure. Theoretically unbreakable. Only example of this is the one time pad. * conditionally secure. Computationally infeasable in practice. cipher is unbreakable or bt the time you do break it, the message contained within is not irrelevant. * weak Can be broken easily. 7. Quality of strength of ciphers: Information Theory How much uncertainty is there? What is the measure of uncertainty? How many bits of the ciphertext are known? * Goal of attacker: zero uncertainty. * Goal of cryptanalyst: lg(n) uncertainty - the more uncertainty the better. 7.1. Measure of Uncertainty The entropy function measures uncertainty. $P_i$ denotes the probability of the $i^th$ key being the actual key. H(p1, ..., pn) = -\lambda \sum_{i=1 to n} pi lg(pi) where \lambda is a constant and is set equal to 1 for out purposes. H(p1, ..., pn) = -\sum_{i=1 to n} pi lg(pi) 7.2. Example 1. We know something is an ascii character H = -\sum_{i=1 to 256} pi lg(pi) H = -\sum_{i=1 to 256} 1/256 lg(1/256) H = -lg(1/256) = 8 7.3. Alternative Notation Using random variables the notation changes. H(X) = \sum P(X) lg(1/P(X)) 7.4. Example 2. P(M=A) = 3/4 P(M=B) = 1/4 H(M) = P(M=A) lg(1/P(M=A)) + P(M=B) lg(1/P(M=B)) = 3/4 lg(4/3) + 1/4 lg(4) = 3/4 lg(4/3) + 1/2 = uncertainty of measage. 7.5. How does this play into cryptography There are many overloading sounds in English. GHOTI = FISH mst ids cn b xprsd n fwr ltrs 7.6. Rate of a Language The average number of bits of information in each message. Message length n r = H(n)/n r \approx 1.0 - 1.5 Claude Shannon 1947. 7.7. Absolute Rate Assume that characters are equally likely. What is the rate? H(X) = -\sum_{i=1 to n} 1/n lg(1/n) = lg(n) R = lg{26} \approx 4.7