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