Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!henry
From: henry@utzoo.UUCP (Henry Spencer)
Newsgroups: net.crypt
Subject: Re: Code Breaking
Message-ID: <6629@utzoo.UUCP>
Date: Sat, 26-Apr-86 20:10:21 EST
Article-I.D.: utzoo.6629
Posted: Sat Apr 26 20:10:21 1986
Date-Received: Sat, 26-Apr-86 20:10:21 EST
References: <113@radha.UUCP>
Organization: U of Toronto Zoology
Lines: 65
Keywords: a_brief_tutorial

> Does this apply to the simple scheme of "exclusive or" against a large
> key (I know almost nothing about cryptology ...) 
> ...
> Now, not withstanding how the key is passed, is the above scheme breakable,
> especially with very large keys (say 100 or 200 letters) ?

Exclusive-or with the key is the usual implementation method for substitution
encryption techniques today.  (The alternative is transposition, which
rearranges the order of characters rather than changing them; complex
systems often incorporate both substitution and transposition.)	 The key
(pun intended) question is how the key sequence for exclusive-oring is
generated.  It is usually desirable to transmit a relatively short key by
some secure means, and then mechanically transform that into a quasi-infinite
sequence that can be exclusive-ored with an arbitrarily long message.

If, as in your example, you merely repeat the short key over and over to
generate the key sequence, a knowledgeable high-school kid with a computer
to help can read your messages, if they are reasonably long.  This is a
"simple polyalphabetic" cipher; it is not terribly hard to solve.  Simply
put:  one guesses at the length of the short key, groups together all
characters enciphered with the same letter of the short key, and then sees
whether the resulting groups follow English-like letter-frequency patterns.
(One needs a reasonable number of letters per group, hence the requirement
for a substantial message.)  If the patterns look right, one has guessed
the key length right (or at least, one has a multiple of the right one).
Then one solves each group as a simple one-for-one substitution cipher.

Guessing key length may mean exhaustive search (or statistical methods that
give the same effect), but it is more common than you would think to have
words in the message repeat, lined up with the same part of the key.  The
result will be repetitions in the encrypted message, which will appear at
multiples of the key length.  These can offer strong hints; of course, one
*can* get repetitions by pure chance...

If you use the same key for several messages, then the codebreaker can
lump all the messages together for solution, giving larger groups and
quicker and more positive results.

Running the message through two successive encryptions with different keys
does not help much, because the result is equivalent to a single encryption
with a key whose length is the least common multiple of the key lengths.

If you use a very long or effectively infinite (e.g. the Encyclopedia
Brittanica) key, but it is English text, the patterns found in English
text can still be exploited to break your cipher.  It *is* harder.

The ultimate encryption scheme is the "one-time pad", in which you use
a non-repeating purely random key sequence which is never re-used.  (One
pre-computer way of implementing this is a pad of pre-printed key sheets,
which are torn off and destroyed as they are used; hence the name.)  The
one-time pad is provably unbreakable:  there is not enough information in
the encrypted stuff to recover the message, unless you have the key.  Its
drawback is that there is no "short key", and you need as much key text
as message text (remember, you can't re-use it).  This practical difficulty
has limited its use.

Most modern encryption schemes essentially use very complex transformations
to go from the short key to the key sequence, and often stir in some messy
transposition operations as well.  Beware that complexity doesn't necessarily
equal security, as witness the double-encryption case I mentioned above.
There is no substitute for advice from an expert.  (NB, I am not an expert.)
-- 
Support the International
League For The Derision		Henry Spencer @ U of Toronto Zoology
Of User-Friendliness!		{allegra,ihnp4,decvax,pyramid}!utzoo!henry