Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!mit-eddie!uw-beaver!uw-june!uw-entropy!martin
From: martin@entropy.ms.washington.edu (Don Martin)
Newsgroups: sci.crypt
Subject: Re: Naive cipher, with questions
Message-ID: <643@entropy.ms.washington.edu>
Date: Sun, 20-Sep-87 10:32:51 EDT
Article-I.D.: entropy.643
Posted: Sun Sep 20 10:32:51 1987
Date-Received: Sun, 20-Sep-87 21:36:35 EDT
References: <5357@oliveb.UUCP>
Organization: UW MathStat, Seattle
Lines: 50
Keywords: cryptography, cipher, random

First, an answer to a question: Are character codes XORed
with random numbers random.
Answer: Yes but the question needs to be refined. A binary
number, which can be a constant or have any distribution, when
XORed with a same length or longer uniformly distributed 
binary random variable produces a uniformly distributed
binary random variable. The proof is based on the fact that
the bits in the uniform dist. binary variable are independent
and each have a probability of 1/2 of being 1.

The same result holds for addition modulo n where the
random variable is uniform on 0,...,n-1. This is often
a more useful result for designing ciphers.

The Vernam cipher is based on the XOR of a random sequence.

The method that you present could be strong or weak. The 
important issue is the cryptographic properties of the 
psuedo random generator. Also the length of the text used,
which is random. However, in many situation, a short segment of
text is all that is needed. Your system is impractical if you
use, average lenths, that are short because the key size gets 
large and you are better with a one time pad.

Back to the psuedo random generator. A simple linear
congruential generator used directly, needs only short
segments to break it. The recursion relations are
simple, so assume a common sequence or word, ex.  " the ",
and apply the recursion starting  each character of the cipher text.
When it matches, you compute backwards and forwards.

The protection against this attack is to use a psuedo random
generator that requires a long sequence and a large amount
of computing to find the constants used. There is a significant
literature on cryptographically strong random number generators.
Look at the Plenum Press books: Advances in Cryptoology, 
Proceedings of Crypto 8*, for 82 and 83. There are several
papers. See Blum and Micali 1984, SIAM J. Comp. Vol.13:4
pp.850-864. This will give you some recent references and
an idea of the current work.

Side note. It is very hard to get good uniformly distributed
random numbers out of hardware devices. Most people think that
unpredictable is equivalent to uniform random. This is of 
course false. Read the introduction to Rand Corp. 1000000 
random digits for amusement.

Don Martin martin@entropy

characters