Outline for April 2, 1997
 Greetings and Felicitations
 Please speak into the microphone
 What is cryptography?
 cipher v. code
 plaintext (cleartext) M, ciphertext C, key k
 encryption E_{k}, decryption D_{k}
 Requirements for a cryptosystem
 enciphering, deciphering is efficient for all keys
 easy to use
 strength is depends on secrecy of keys only,
not on secrecy of E or D

What it can do: Secrecy
 computationally infeasible
to determine D_{k} from C
even if corresponding M known

computationally infeasible to determine M
from C if k unknown

What it can do: Data Authenticity (Integrity)
 computationally infeasible
to determine E_{k} from C
even if corresponding M known
 computationally infeasible to find a
C' such that D_{k}(C')
is valid plaintext
 Attacks
 ciphertext only
 known plaintext
 chosen plaintext
 chosen ciphertext

Measures of strength
 unconditionally secure (theoretically unbreakable)
 conditionally secure (unbreakable in practise);
note environment often affects this
 weak (breakable)
 How to measure strength: Entropy
 Given C, how much uncertainty in M?
 attacker wants 0
 sender wants lg(n), where n is
the length of message

Requirements for function
H(p_{1}, ..., p_{n});
explain these with dice, coins, and (maybe) horses

Review probability notation; assume
p_{1} + ... + p_{n} = 1.

H(p_{1}, ..., p_{n})
is a maximum when
p_{1} = ... = p_{n} = 1/n.
 For any permutation ¼ (Greek letter pi) on
(1, 2, ..., n),
H(p_{1}, ..., p_{n})
=
H(p_{¼(1)}, ..., p_{¼(n)}).
In other words, H must be a symmetric function of the arguments
p_{1}, ..., p_{n}.

H is continuous in its arguments

H(p_{1}, ..., p_{n})
>= 0 and equals 0 only when one of the p_{i} = 1.

H(p_{1}, ..., p_{n}, 0) =
H(p_{1}, ..., p_{n}).


If m and n are positive integers, then

Let p = p_{1} + ... +
p_{m} and q = q_{1} + ... +
q_{n},
where each p_{i}
and q_{j} are nonnegative; then, if
p and q are positive, with p + q = 1, we must have

Only function which does this is

Examples
 rate for message of length n is
r = H(X)/n; for English, 1 to 1.5

absolute rate: assume all chars are equally likely;
assuming L chars, R = lg L; for English, 4.7

redundency D = R  r; for English, 3.2 to 3.7
You can get this document in
Postscript,
ASCII
text,
or
Framemaker
version 5.1.
Notes by Ricardo Anguiano:
[LaTeX]
[Postscript]
[Text]
Send email to
cs253@csif.cs.ucdavis.edu.
Department of Computer Science
University of California at Davis
Davis, CA 956168562
Page last modified on 4/9/97