paper_and_pencil.tex

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

% $Id: paper_and_pencil.tex 1205 2005-07-04 13:58:13Z koy $
% ..............................................................................
%                V E R S C H L U E S S E L U N G S V E R F A H R E N
%
% Writing rule: Capitel header with all nouns/verbs-words capitalized,
%               All other headers in the normal lower/upper case manner
%               like sentences (without a dot at the end).
%
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\newpage

%------------------------------------------------------------------------------
% First Editor: Christine St鰐zel, April 2004
% Update and corrections: B. Esslinger, June 2005
% corrected by C. Esslinger, June 2005 
%------------------------------------------------------------------------------
\section{Paper and Pencil Encryption Methods}

\hypertarget{Kapitel_PaperandPencil}{}
\label{Kapitel_PaperandPencil}
(Christine St\"otzel, April 2004)

The following chapter provides a broad overview of paper and pencil 
methods\footnotemark
    \footnotetext{Always added with links to further information.}
    \index{Paper- and pencil methods}.
All techniques that people can apply manually to en- and decipher a message are 
embraced by this term. These methods were and still are especially popular with
secret services, as a writing pad and a pencil - in contrast to electronical
aids - are totally unsuspicious.

The first paper- and pencilmethods already arose about 3000 years ago, but new
procedures were developed during the past century, too. All paper and pencil 
methods are a matter of symmetric methods\index{Encryption!symmetric}. 
Even the earliest encryption algorithms use the basic principles such as 
transposition, substitution, block construction and their combinations. 
Hence it is worthwhile to closely consider this ''ancient'' methods especially
under didactic aspects.

xxxxxxxxxxErfolgreiche bzw. verbreiteter eingesetzte Verfahren mussten die gleichen 
Merkmale erf"ullen wie moderne Verfahren:
\begin{itemize}
\item xxxxxxxxxxxxxxVollst"andige Beschreibung, ja fast Standardisierung (incl. 
      Sonderf"alle, Padding, etc.).
\item xxxxxxxxxxGute Balance zwischen Sicherheit und Benutzbarkeit 
      (denn zu kompliziert zu bedienende Verfahren waren fehlertr"achtig
      oder unangemessen langsam).
\end{itemize}


\vskip +20 pt
%------------------------------------------------------------------------------
\subsection{Transposition}

Encrypting a message by means of transposition\index{Transposition} does not change the original characters of this
message, only their layout is modified.

%------------------------------------------------------------------------------
\subsubsection{Introductionary samples of different transposition ciphers}

\begin{itemize}

\item {\bf Railfence}\footnote{In CrypTool\index{CrypTool} 
   you can simulate this method under the menu {\bf Crypt \textbackslash{} 
   Symmetric (classic) \textbackslash{} Permutation}: for a railfence with
   2 lines use as key ''B,A'' and accept the default settings (only one
   permutation, where your input is done line-by-line and the ouput is
   taken column-by-column). 
   Using the key ''A,B'' "' would start the zigzag pattern below in the
   way, that the first letter is written into the first line instead of the
   second line.}
   \cite{Singh2001}%
   : 
   The characters of a message are alternately written in two (or more) lines,
   creating a zigzag pattern. The resulting cipertext is read out 
   line by line.\\
   This is more a children's method.

   Plaintext: an example of transposition\\
\begin{table}[h]
\begin{center}
\begin{tabular}{r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}r@{\:}}
	  & n &   & x &   & m &   & l &   & o &   & t &   & a &   & s &   & o &   & i &   & i &   & n \\
	a &   & e &   & a &   & p &   & e &   & f &   & r &   & n &   & p &   & s &   & t &   & o &   \\
\end{tabular}
\caption{Railfence}
\end{center} 
\end{table}

   Ciphertext\footnote{The letters of the cleartext are -- as used 
   historically -- grouped within blocks of 5 letters. It does not matter
   if the (constant) blocklength is different or no blank is inserted.}%
   : NXMLO TASOI INAEA PEFRN PSTO\\


\item {\bf Scytale}\footnote{%
   The result of this encryption method meets the one of a simple columnar
   transposition.   
   In CrypTool\index{CrypTool} you can simulate this method under the 
   menu {\bf Crypt \textbackslash{} Symmetric (classic) \textbackslash{} 
   Permutation}: For the Scytale within the dialog box only the first 
   permutation is used. If the wood has e.g. 4 angles use as key ''1,2,3,4''.
   This is equivalent to write the text horizontally in blocks of 4 letters 
   in a matrix and to read it out vertically . 
   Because the key is in an in ascending order, the Scytale is denoted as
   an identical permutation; and because writing and read-out is done only
   once it is a simple (no double) permutation.}
   \cite{Singh2001}%
   : 
   This metod was probably used since more than 600 B.C. -- a description
   of how it operated is not known from before Plutarch (50-120 B.C.).\\
   A long strip of paper is wrapped around a wooden cylinder and the 
   message is written along the length of this strip. The ciphertext is 
   produced by unwinding the strip.

\item {\bf Grille} \cite{Goebel2003}: Both parties use identical stencils. 
   Line by line, their holes are filled with plaintext that is read out 
   column by column to produce the ciphertext. If there is plaintext left, 
   the procedure is repeated\footnote{%
   This method cannot be simulated with a pure column transposition.}.

\item {\bf Turning grille} \cite{Savard1999}: The German army used turning 
   grilles during WW1\footnote{The turning grille was already invented in 
   1881 by Eduard Flei"sner von Wostrowitz.\\
   A good visualization canbe found under www.turning-grille.com.}%
   . 
   A square grille serves as a stencil, a quarter of its fields being holes.
   The first part of the message is written on a piece of paper through	these
   holes, subsequently the grille is rotated by 90 degrees and the user can
   write down the second part of the message, etc. But this method does only
   work, if the holes are chosen carefully: Every field has to be used, and
   no field may be used twice, either. The ciphertext is read out line by line.

   In the example for a turning grille in the following table you can write
   4 times 16 characters of the cleartext on a piece of paper:
\begin{table}[h]
\begin{center}
\begin{tabular}{|cccc|cccc|}
\hline 	
	O & - & - & - & - & O & - & - \\
	- & - & - & O & O & - & - & O \\
	- & - & - & O & - & - & O & - \\
	- & - & O & - & - & - & - & - \\
\hline 	
	- & - & - & - & O & - & - & - \\
	O & - & O & - & - & - & O & - \\
	- & O & - & - & - & - & - & O \\
	- & - & - & O & O & - & - & - \\
\hline
\end{tabular}  
\end{center} 
\end{table}
\end{itemize}


%------------------------------------------------------------------------------
% {\bf Column and row transposition}
\subsubsection[Column and row transposition]
    {Column and row transposition\footnotemark}
    \footnotetext{%
Most of the following methods can be simulated in CrypTool\index{CrypTool} 
under the menu {\bf Crypt \textbackslash{} Symmetric (classic) 
\textbackslash{} Permutation}.}

\begin{itemize}

\item {\bf Simple columnar transposition} \cite{Savard1999}: First of all, 
   a keyword is chosen, that is written above the columns of a table. This
   table is filled with the text to be encrypted line by line. Then the 
   columns are rearranged by sorting the letters of the keyword alphabetically.
   Afterwards the columns are read out from left to right to build the 
   ciphertext\footnote{%
   Using CrypTool: Choose a key for the 1st permutation, input line by line, 
   permute and output column by column.}.

   Plaintext: an example of transposition\\
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|}
\hline 	
	K & E & Y \\
\hline
	a & n & e \\
	x & a & m \\
	p & l & e \\
	o & f & t \\
	r & a & n \\
	s & p & o \\
	s & i & t \\
	i & o & n \\
\hline
\end{tabular}
\caption{Simple columnar transposition}
\end{center} 
\end{table}

   Transposition key: K=2; E=1; Y=3. \\
   Ciphertext: NALFA PIOAX PORSS IEMET NOTN\\

\item {\bf AMSCO} \cite{ACA2002}: The characters of the plaintext are written
   in alternating groups of one respectively two letters into a grille. 
   Then the columns are swapped and the text can be read out.

\item {\bf Double column transposition} \cite{09}: Double columnar transposition
   was frequently used during WW2 and during the Cold War. Two simple columnar
   transpositions with different keys are executed successively\footnote{%
   Using CrypTool: Choose a key for the 1st permutation, input line by line, 
   permute and output column by column. Then choose a (different) key for the
   2nd permutation, input line by line, permute and output column by column.}.
	
\item {\bf Column transposition, General Luigi Sacco} \cite{Savard1999}: The 
   columns of a table are numbered according to the letters of the keyword. 
   The plaintext is entered line by line, in the first line up to column 
   number one, in the second line up to column number two, etc. 
   Again, the ciphertext is read out in columns.

   Plaintext: an example of transposition\\
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline 	
	C & O & L & U & M & N\\
	1 & 5 & 2 & 6 & 3 & 4\\
\hline
	a &   &   &   &   &  \\
	n & e & x &   &   &  \\
	a & m & p & l & e &  \\
	o & f & t & r & a & n\\
	s & p &   &   &   &  \\
	o & s & i & t &   &  \\
	i & o & n &   &   &  \\
\hline
\end{tabular}
\caption{Columnar transposition (General Luigi Sacco)}
\end{center} 
\end{table}

   Ciphertext: ANAOS OIEMF PSOXP TINLR TEAN\\


\item {\bf Column transposition, french army in WW1} 
   \cite{Savard1999}: 
   After executing a simple columnar transposition, diagonal rows are read out.


\item {\bf Row transposition cipher} \cite{02}: The plaintext is divided 
   into blocks of equal length and a keyword is chosen.
   Now the letters of the keyword are numbered and permutation is done only
   within each block according to this numbering\footnote{%
   Using CrypTool: Choose a key for 1st permutation, input line by line, 
   permute column by column and output line by line.}.

\end{itemize}


%------------------------------------------------------------------------------
\subsubsection{Further transposition algorithms}

\begin{itemize}

\item {\bf Geometric figures} \cite{02}: Write the message into a grille 
   following one pattern and read it out using another.

\item {\bf Union route cipher} \cite{WP}: The union route cipher derives 
   from Civil War. This method does not rearrange letters of a given plaintext,
   but whole words. Particularly sensitive names and terms are substituted by 
   codewords which are recorded in codebooks together with the existing routes.
   A route determines the size of a grille and the pattern that is used to 
   read out the ciphertext. Aditionally, a number of filler words is defined.

\item {\bf Nihilist transposition} \cite{ACA2002}: Insert the plaintext into 
   a square grille and write the same keyword above the columns and next to
   the lines. As this keyword is sorted alphabetically, the contents of the
   grille are rearranged, too. Read out the ciphertext line by line.
	
   Plaintext: an example of transposition\\
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|ccccc||cc|ccccc|}
\hline 	
	  & W & O & R & D & S &   &   & D & O & R & S & W\\
\hline
	W & a & n & e & x & a &   & D & s & p & o & i & s\\
	O & m & p & l & e & o &   & O & e & p & l & o & m\\
	R & f & t & r & a & n &   & R & a & t & r & n & f\\