trash@oliveb.UUCP (Tom Repa) (09/19/87)
Hello all you you crypto-types.
I've been reading this group for some time and would like
to ask your opinions about about the following cipher, which
I have not seen discussed before ( although this probably only
means I haven't looked hard enough :-)
I've read both "The Codebreakers" and "Cryptography: A Primer",
and I have Aegean Park Press's latest catalog, so if I have missed
something elementary, point me toward the correct book.
I KNOW this is not foolproof, but I was wondering about what
it's weaknesses are.
Assume I have hardware that generates:
Random numbers (phase-jitter of free-runnning osc. or whatever)
[ well ASSUME they are random ]
Pseudorandom number generator (PRN), or more likely a set of
PRN generators which are chained together to
increase the periodicity.
How about the following cipher:
Rk(n) = random numbers from a hardware random # generator
This is the random key number. This would be an offset
into pseudorandom number space.
Rl(n) = another random from a hardware random # generator
This would pick the length of the plaintext to
encipher. Done to help break up patterns.
P(n) = pseudorandom number based on Rk(n)
DeLoop:
Take plaintext of length [Rl(n) - 2] and Rk(n+1) and Rl(n+1)
XOR with
P(Rk(n)) of length Rl(n)
||
Ciphertext
loop DeLoop (till all text is enciphered)
place Rl(1), Rk(1) at predetermined places in the resulting ciphertext
With this you have the plaintext XORed with Psuedo-random numbers,
the seed of which is the random # Rk(n) which is placed at the end
of each preceeding block. The variable length blocks are used to help break
up any patterns inherent in the PRNG. I do realize that most of the
security(?) in this system depends on the periodicity of the PRNG
and that this must be as long as is feasible. To this end Rk(n) could
do two things:
1) act as the seed # of the PRN generator
2) select a PRN generating algorithm
or select how several predifined PRN generators
are chained together.
Clearly if Rl(n)=>1, and there is then no room to add R(n+1) and L(n+1),
we have a one time pad (whoops, well almost. We would have XORed with a
PRN which is a function of a random number which you don't know, which
_should_ be random, depending on the algorithm). This would give us a way
to approach a one time pad's security without the attendent problems of
of key distribution. Security would rest in the period length of the PRN
generators and the placement of the initial numbers R1(1) and R2(1)
within the text. Naturaly they would have to occur at an agreed upon place
(or places) in the ciphertext, or they themselves would be the key(s).
QUESTIONS
Is it a valid to assume that pseudorandom data XORed
with normal text will look (pseudo)random? Or is it dependent on the
language of the plaintext i.e. will the patterns inherent in the
plaintext show through the pseudorandom numbers?
Well, that's my bid for most unbreakable code of the femtosecond.
Flames welcome, as I always find flames illuminating :-)
Tom Repa(trash@oliven)
"Unaware of the scope of simple equations, man has often concluded that
nothing short of God, not mere equations, is required to explain the
complexities of the world." - R.P. Feynman, The Feynman Lectures on Physics
Path: {allegra,glacier,hplabs,ihnp4}!oliveb!oliven!trash
--
"Unaware of the scope of simple equations, man has often concluded that
nothing short of God, not mere equations, is required to explain the
complexities of the world." - R.P. Feynman, The Feynman Lectures on Physics
Path: {allegra,glacier,hplabs,ihnp4}!oliveb!oliven!trashmartin@entropy.ms.washington.edu (Don Martin) (09/20/87)
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