Newsgroups: sci.crypt
Path: cactus.org!cs.utexas.edu!usc!elroy.jpl.nasa.gov!decwrl!netcomsv!netcom.
+     com!straits
From: straits@netcom.com (Stewart C. Strait)

Subject: Re: Strong Block Ciphers from Weak Ones: NxM DES
Message-ID: 
Organization: NETCOM On-line Communication Services (408 241-9760 guest)
X-Newsreader: TIN [version 1.2 PL1]
References: <1994Feb2.071956.29014@cactus.org>
Date: Wed, 2 Feb 1994 23:19:11 GMT
Lines: 50

Terry Ritter (ritter@cactus.org) presented a long-overdue idea.

It is analogous in some sense to Playfair, which can
be though of as 2x2 simple substitution.

Start with plaintext--convert to a string of mod-25 (usually) numbers
by deleting non-alpha characters, forcing case to upper, replacing
J by I, and replacing letters by numbers in order (A=0, B=1, ..., I=8,
K=9, L=10, ... Z=24).

Now do simple substitution, swap high-order digits base 5, and
substitute again using the inverse of the original substitution.

Replace numbers by letters and you have the ciphertext.  

[Real Playfair introduces special rules for the cases where the
interchanged digits or the noninterchanged digits are the same.
Leaving out the special rules makes an easy puzzle, in which the
degenerate cases show bits of plaintext, sometimes with letter
pairs reversed, so the solver has many hints.  I think that using
the inverse of a previous block encryption might require special
rules even with DES, but Terry Ritter does not fall into this
pitfall.]

Another idea that comes to mind is using a block cipher in 
what might be called "overlapping block mode".  This would be encrypting
the first block, overwriting the plaintext (or better a copy of it),
moving on by part of a block, and then encrypting and overwriting again.
A disadvantage is that decryption must work backwards through the text.
A crude example:

  Block cipher:  multiply by 3 mod 100
  Overlap:  one decimal digit
  Plaintext:  3141592
  Step 1:     9341592
  Step 2:     9021592
  Step 3:     9063592
  Step 4:     9060592
  Step 5:     9060772
  Step 6:     9060716=ciphertext

Of course, this example is not a strong cipher.  Repeating the whole
process twice would turn the whole plaintext into one block, but
I don't think its avalanch properties are as good as the NxM idea.

There must be many other block cipher modes that lengthen the effective
block size.  Perhaps there are more of special interest.
-- 
Stewart C. Strait
straits@netcom.com