\documentstyle{article}
\begin{document}
\title{ECS253 4/2/97}
\author{Ricardo Anguiano}

\section{Announcements}
Web page will be up by Friday.

\section{Role of Cryptography (later crypto itself)}
Broad set of apporaches to conceal

\subsection{Steganography} 
\begin{itemize}
\item Writting with milk example: conceals the fact that there is a message 
\item Microdot example: documents shrunk to the size of a period and mailed out with an inoccuous letter. 
\item 24 bit images can carry information.  1 bit per pixel will not be visable to the human eye.
\end{itemize}

\subsection{Caeser Cipher - advance each letter by three}
	$HELLO WORLD \to KHOOR ZRUOG$

\begin{itemize}
\item Key - the info needed to encipher or decipher a message.
\item Cipher - maps characters into characters.
\end{itemize}

\subsection{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.

\begin{verbatim}
Example Code		Code Groups
------------		-----------
hello			AXZB
i love			XCVJ
i hate			BSYK
broccoli		TRUX
spinach			PLUG
\end{verbatim}

\subsection{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.

\subsection{Terms}
\begin{itemize}
\item Plaintext(M): message to be enciphered.  Also referred to as cleartext.
\item Ciphertext(C): output of encipherment function.  Not generally understandable.
\end{itemize}

\subsection{Note on International Usage}
\begin{itemize}
\item Encipher - to make unreadable without destroying the message.
\item Encrypt - similar to crypt, which is a burial ground or cemetary sounds like you are going to bury the message.
\end{itemize}

\subsection{Notation}
\begin{itemize}
\item Encipher(Ek): Algorithm to encipher message
\item Decipher(Dk): Algorithm to decipher message
\item Key(k): information used to encipher message using a common algorithm.
\item Encipher:  $E_k(M) = C$
\item Decipher:  $D_k(C) = M$
\end{itemize}
Clasical systems: encrypt and decrypt keys are the same.

\section{Good Cryptosystems and Kirchoff's requirements}
\begin{enumerate}
\item Enciphering and deciphering is EFFICIENT for all keys.  Should not take forever to get message.
\item 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.

\item 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.
\end{enumerate}

\section{Secrecy or Confidentiality}
Encipher messages to protect secrecy
\begin{enumerate}
\item Intecepted ciphertext should not lend clues to what the deciphering algorithm is.  It should be computationally infeasable (C.I.)
\item It should be C.I. to find M from C.
\end{enumerate}

\section{4 attacks on cryptosystems}
\begin{enumerate}
\item ciphertext only attack
given the ciphertext, what is the original message?
\item known plaintext attack
have both the plaintext and ciphertext.  What is the key?
\item chosen plaintext attack
give plaintext to adversary, get back enciphered message.
\item chosen ciphertext
give ciphertext to adversary, get back plaintext.  Not
very practical and noted here for theoretical completeness only.
\end{enumerate}

\section{Authentication or Integrity}
Data is not to be altered. requirements for integrity:
\begin{enumerate}
\item C.I. to find $E_k$. Keeps adversary from changing encrypted messsage.
\item C.I. to find C' such that $D_{k}(C')$ is valid.
\end{enumerate}
\section{Computationally Infeasable (an explanation)}
Degrees of security
\begin{enumerate}
\item unconditionally secure.  
Theoretically unbreakable.  Only example of this is the one time pad.
\item conditionally secure.  
Computationally infeasable in practice.
cipher is unbreakable or bt the time you do break it, the
message contained within is not irrelevant.
\item weak
Can be broken easily.
\end{enumerate}
\section{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?

\begin{itemize}
\item Goal of attacker: zero uncertainty.
\item Goal of cryptanalyst: lg(n) uncertainty - the more uncertainty the better. 
\end{itemize}
\subsection{Measure of Uncertainty}
The entropy function measures uncertainty. $P_i$ denotes the probability 
of the $i^th$ key being the actual key. \\

\begin{math}
H(P_1 \cdots P_n) = -\lambda \sum_{i=1}^{n} P_i \lg{P_i}
\end{math} \\

Lambda is a constant and is set equal to 1 for out purposes. \\

\begin{math}
H(P_1 \cdots P_n) = -\sum_{i=1}^{n} P_i \lg{P_i}
\end{math}

\subsection {Example 1.}
We know something is an ascii character \\
\begin{math}
H = -\sum_{i=1}^{256} P_i \ln P_i \\
H = -\sum_{i=1}^{256} 1/256 \ln 1/256 \\
H = -\lg 1/256 = 8
\end{math}

\subsection{Alternative Notation}
Using random variables the notation changes. \\
\begin{math}
H(X) = \sum P(X) \lg 1/P(X)
\end{math}

\subsection{Example 2.}

\begin{math}
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. 
\end{math}

\subsection{How does this play into cryptography}
There are many overloading sounds in English.\\
GHOTI = FISH\\
mst ids cn b xprsd n fwr ltrs

\subsection{Rate of a Language}
The average number of bits of information in each message.\\
Message length n\\
\begin{math}
r = H(n)/n \\
r \approx 1.0 - 1.5 \\
\end{math}
Claude Shannon 1947.

\subsection{Absolute Rate}
Assume that characters are equally likely.  What is the rate? \\
\begin{math}
H(X) = -\sum_{i=1}^{n} 1/n \lg{1/n} = \lg{n}\\
R = \lg{26} \approx 4.7
\end{math}

\end{document}