From: lwloen@rchland.vnet.ibm.com (Larry Loen)
Subject:     transposition ciphers
Date: Wed, 29 Jul 1992 19:34:39 GMT
Reply-To: lwloen@vnet.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: IBM Rochester
Keywords: transposition substitution DES RSA

In <92207.142318U27239@uicvm.uic.edu> Gerald S. Strom writes --
>     When Julius Caesar wanted to keep his messages from being read
>by his enemies (and probably a few friends as well), he devised a simple
>substitution cipher whereby one letter was replaced by another.  This
>Caesar Cipher is not secure by the standards of today but interestingly,
>the method used, substituting one letter or character for another in a
>regular way, is still the fundamental basis for encipherment in modern
>ciphers systems.  The DES system developed by the United States
>government, the various public key ciphers systems, as well as the
>German Enigma cipher cracked by Allen Turing during World War II
>using one of the first computers are all substitution ciphers whereby
>letters in the plain (or un-enciphered) text are replaced by different
>letters or characters to create the cipher (or enciphered) text.
>     The cipher described here differs fundamentally from the
>substitution ciphers systems in that it does not rely on replacing one
>letter with another.  Instead, it is a transposition cipher that relies on
>scrambling the letters of the plain text in a random fashion so that the

  (rest of article omitted, including description of a transposition based
   on a "random number generator" based on a 256 byte transposition block)

I would regard paragraph 1 as true, but misleading, especially to the general 
public.  To the unititiated (to whom this article seems targeted), 
readers might imply that there is no qualitative difference 
between Caesar and RSA or DES.  Is this what Mr. Strom meant?

Moreover, there is not as great a distinction between a transposition cipher
and a substitution cipher as seems to be implied, here.

One could, in fact, in the spirit of the article, call its "transposition" a
form of substitution where the current 256 bytes are substituted by a "different"
256 bytes according to a subsitution that varied and was conveniently
implemented as a transpostion to reduce the size of the needed tables.  
I'd have to think a bit on whether the "256 byte" system in Mr Stom's article 
maps to a Vigenere model or a more rotor-like model, but it 
seems clear that one could construct the argument.  Other than the size of the
"alphabet", it seems we have moved to familiar ground; so it may also be true that
one could adapt a rotor-system attack so that the obviously huge
lookup tables could be dispensed with, but the rotor-style attack could proceed in
modified form.

In any case, the system described seems very vulnerable to mulitple anagramming
techniques (at least for any two files, including edited versions of the same
file) that used the same random number seed.  

I also would like Mr. Strom to describe more the motivation for presenting
this system and particularly in supplying complete source code.

1)  It does not appear to be a particularly secure system.  (Assuming my
  informal multiple-anagramming analysis holds in detail).

2)  It does not appear to reliably replicate in multiple installations,
  because it relies on a compiler built-in function, which may be implemented
  differently on different compilers.

If the point is to suggest that "transposition" is as reliable a basis as
"substitution" for a cipher system, this seems to be a slippery point.  Since
any transposition can be built, in theory, as a substitution system (some more
readily than others :-) ) and at least some substitutions can be modelled as
cyclic permutations (which has the look and feel of transposition, to me),
I'm not sure what is being demonstrated, here.

Finally, systems such as DES, at least, contain elements of both substitution
and transposition (and include a qualitatively important concept called
"fractionization" to boot).  To call DES, at least, just a substitution is to
ignore some very significant qualitative aspects of the cipher and to overlook
its transpositional elements.

What, exactly is this article accomplishing?



-- 
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer