From msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!ftpbox!mothost!binford!mcdchg!chinet!schneier Sun Oct 17 00:30:56 1993
Newsgroups: sci.crypt
Path: msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!ftpbox!mothost!binford!mcdchg!chinet!schneier
From: schneier@chinet.chinet.com (Bruce Schneier)
Subject: Pencil and paper encryption algorithm
Message-ID: <CEtKr4.7B7@chinet.chinet.com>
Organization: Chinet - Public Access UNIX
Date: Wed, 13 Oct 1993 05:04:13 GMT
Lines: 85

For a while now I have been trying to invent a pencil-and-paper
encryption algorithm.  The idea is to create an algorithm that
can be used without computers, but is still secure against
computer-aided attacks.  Recently I came up with a candidate
algorithm.  I am still testing it, but I figured I'd let it out
into the world for comments and criticisms.

This is what I have come up with:

THE ALGORITHM

         Key Generation:  The key consists of n random key letters,
         and a random permutation of the alphabet.

         Preliminary Processing:  Perform an n-columnar transposition
         of the algorithm.  The algorithm is a block cipher on one of
         these n-column blocks.

         The Block Algorithm:

                 Add the first key letter to the first letter of the
                 block.  (All addition is modulo 26, and the result is
                 another letter.)

                 Use the result of the previous step as an index into
                 the random permutation to return a letter.

                 Add the letter returned in the previous step to every
                 letter of the block except the first.

                 Add the second key letter to the second letter of the
                 block.

                 Use the result of the previous step as an index into
                 the random permutation to return a letter.

                 Add the letter returned in the previous step to every
                 letter of the block except the second.

                 Repeat the previous three steps for each letter of the
                 key.

                 Repeat the whole thing m times (possibly each time with
                 a different block of n random key letters).

         Final Processing:  Arrange the ciphertext in five-character
         groups.

This can all be unrolled to decrypt the text.

Much of the idea for this algorithm comes from the REDOC III
algorithm, which does pretty much the same thing with binary
data.

Both n and m are security parameters.  I have not done nearly
enough testing to determine what values are sufficient for
security.  Right now I am thinking of ten character blocks, and
two passes through the algorithm (each with different random key
letters).

Key generation is also undefined at the moment.  I can think of
several ways to generate random letters.  (I like some of the
methods used in the Soviet pencil-and-paper cipher discussed in
_Kahn_on_Codes_.)  Generating a random permutation using only
pencil and paper is harder, but I have some ideas.

The columnar transposition at the beginning doesn't really add
any security, but is there to prevent any dictionary or block
replay attacks.  I suppose it would be easy to implement this in
a CBC chaining mode, which would do the same thing.

Adding the various letters to random letters before using them as
indexes into the permutation serves to hide any non-randomness in
the plaintext.  Assuming the random letters are truely random,
the result of the addition will be random.

Anyone have any comments on any of this?

Bruce

**************************************************************************
* Bruce Schneier
* Counterpane Systems         For a good prime, call 391581 * 2^216193 - 1
* schneier@chinet.chi.il.us
**************************************************************************