%From sasar@fermat.rutgers.edu Wed Apr 19 14:55:48 2000
%MIME-Version: 1.0
%Date: Wed, 19 Apr 2000 14:56:04 -0400 (EDT)
%From: Sasa Radomirovic <sasar@math.rutgers.edu>
%To: "Stephen J. Greenfield" <greenfie@math.rutgers.edu>
%Subject: Block Cipher Memo
%Content-Type: TEXT/PLAIN; charset=US-ASCII
%
%Hi,
%
%Here's the memo. Somehow I didn't manage to say everything I would have
%liked to say, or at least I have the feeling that I could have done
%better. They seemed confused to me. 

%See you tomorrow.

%Sasa.

\documentclass[10pt]{article}

\newcommand{\RSA}{RSA}
\newcommand{\DES}{\emph{DES}}
\newcommand{\mod}{\ \mathrm{mod}\ }
\setlength{\parindent}{0pt}
\addtolength{\textwidth}{1in}
\addtolength{\hoffset}{-0.5in}

\begin{document}

\title{An introduction to Block Ciphers}
\author{Sa\v{s}a Radomirovi\'{c}}
\date{April 2000}

\maketitle

\section{What is a Block Cipher?}

A block cipher is an example of a \emph{symmetric} crypto system.  The
word ``symmetric'' here means that the same key is used for encryption
and decryption. One of the most famous block ciphers is \DES. But
there are many more.

\section{Why use Block Ciphers?}

Using the same key for encryption and decryption might seem like a
drawback after having learned about \RSA{} and Diffie--Hellman, but in
fact \RSA{} and Diffie--Hellman are only useful together with block
ciphers.  The important point is that block ciphers are much faster
than public key crypto systems.

\section{How are Block Ciphers used ?}

For now, think of a block cipher as a big black box that needs a key
in order to operate. If you feed in some plaintext, then something
encrypted, depending on the key, will come out the other side. And if
you feed in something encrypted, then the plaintext will show up
again.

Recall that Diffie--Hellman allowed Alice and Bob, who might have
never met before, to establish a secret which is only known to them
and nobody else. This secret is used as the key for a block cipher
which encrypts the secret messages Alice and Bob want to exchange.

The combination of \RSA{} and a block cipher works in a similar way.
Recall that in \RSA{} everybody who has Alice's public key can send
secret messages to Alice, but only Alice can decipher the messages and
nobody else.  In the real world, the \RSA{} public key is being used
to encrypt a key for the block cipher and the secret message is being
encrypted with the block cipher.

\section{How does a Block Cipher work now?}

First, what requirements does the block cipher have to fulfill?

\begin{itemize}
\item It must be able to deal with inputs of various length.
\item It must be reversible.
\item It must be fast.
\item It is hopefully hard to break.
\end{itemize}

\subsection*{Letters}

Although a block cipher encrypts a message which consists of 0's and
1's, I will explain everything first in terms of letters. Suppose you
want to encrypt the message \def\m1{``PROFESSOR GREENFIELD''} \m1 with
a block cipher.

The first thing a block cipher does is to divide the message into
blocks of a given length -- hence the name \emph{block} cipher!  If we
take for example blocks of 4 letters in our message, then the first
block would be ``PROF'' the second block would be ``ESSO'' and so on.

Each block is encrypted separately using exactly the same procedure
and key. Essentially, there are only two simple procedures used for
encryption: permutation and substitution. Permutation means changing
the order, for example writing ``ROPF'' instead of ``PROF''.
Substitution means replacing some parts with others, say writing
``GNOF'' instead of ``PROF'' and thereby replacing ``PR'' with ``GN''.
A real block cipher won't actually have a table which tells what to
replace with what. Instead it will use additions, multiplications,
XOR's, and the like to compute the cipher text from the key and the
plain text. Notice that permutations and substitutions are reversible.
Since a small number of permutations and substitutions is not likely
to be very secure, a block cipher usually repeats that process a
certain number of times for each block. Each repetition is called a
``round''.

The following is a simple example of a block cipher:

\begin{enumerate}
\item Divide the text into blocks of 4 letters.
\item Do the following for each block:
\begin{enumerate}
\item Switch the first two letters with the last two letters.
\item Shift the first letter by one, i.e. write 'B' for an 'A', etc.
\item Shift the second letter by two, i.e. write 'C' for an 'A' etc.
\item Shift the third letter by three.
\item Shift the fourth letter by four.
\item Repeat (a) -- (e) 16 times (16 ``rounds'').
\end{enumerate}
\end{enumerate}

To keep things simple we haven't used a key in our block cipher, but
one could for example make the shifting of the letters key--dependent.
Notice that although the steps (a) -- (e) are simple to break.
But after repeating them 16 times it might not be that obvious what is
happening.

\subsection*{Numbers}

Now that we know how block ciphers work in principle, let's have a
look at how they work in the real world. Messages will be strings of
0's and 1's. Today's block ciphers usually have 64 bit blocks.
Permutations are done on selected groups of bits.  Substitutions are
done with mathematical functions like multiplications and additions
mod 2, or XOR's and others. But since these operations are relatively
easy to reverse, as pointed out they will be done many times to
increase security.

\end{document}




