NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/crypt/2770

Text File | 1992-07-29 | 3.2 KB | 75 lines

Newsgroups: sci.crypt
Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!informatik.tu-muenchen.de!zeisset
From: [e-mail] (Stephan Zeisset)
Subject: Re: Cypher algorithm question.
Keywords: question, algorithm, encrypt, crypt, decrypt
References:  <tom.712397505@cluster>
Originator: [e-mail]
Sender: [e-mail] (USENET Newssystem)
Organization: TU M"unchen (FRG)
Date: Wed, 29 Jul 1992 10:06:09 GMT
Message-ID: <[e-mail]>
Lines: 61


In article <tom.712397505@cluster>, [e-mail] (Thomas Essebier) writes:
|> By far not being an expert on cryptology, I would appreciate some
|> comments on the crypto scheme below.
|>
|> Where does it stand in terms of security when compared to transposition
|> cyphers, DES etc.
|>
|> My initial thoughts were that other then using a brute force approach,
|> e.g. trying all 2^31 seeds (or so), there is no easy way to deal
|> with it - but I am probably wrong :-)
|>
|> I presume that due to its simplicity this sort of crypto approach must
|> be quite well known, its just that in my rather limited explorations of
|> the field I have not come accros any.
|>
|> Algorithm:
|> - Create a sequence of random numbers that starts at 'seed' and is known
|>   to be deterministic and to have a large period. e.g. linear congruential:
|>   X[i+1] = (a*X[i] + c) mod m, choose coefficients as follows
|>   a = 16807, m = 2,147,483,647 (2^31 - 1), c = 0
|>   #define RANDOM ((unsigned char) (seed = (16807 * seed) % 2147483647))
|>   supposedly has a period of 2^31.
|>
|> - use the 'key' to choose the first seed, e.g. add up all the bytes or
|>   some such, so that a key >= 4 byte could cover 0-2^31, roughly at least.
|>
|> - take the the data stream and for each byte 'xor' the LSB of the 'seed'.
|>   A stronger method might be to use 4 byte chunks (assuming seed is 4 bytes)?
|>   The advantage of using xor is that there is that the algorithm is self
|>   reversing. Perhaps it entails some pitfall(s) however?
|>
|> If anybody could point me to some literature that explains why the above
|> is (un?)reasonably (in?)secure I would be most grateful. Please note that
|> I make no claim to have carefully studied and researched this topic.
|> I was hoping to avoid all that :-)

The problem with your algorithm is with the know plaintext text.
That means, your opponent knows some of the original plaintext or
makes a good guess of it.
For example, if the plaintext is a letter to someone, you
would expect something like 'Dear Mr ...' or anything alike
in the first few lines of the plaintext.
If I know only 4 Bytes of the plaintext and its position
(must be divideable by 4) I can easily tell the state of
your random generator at this time (= plaintext word
xor ciphertext word) and decode the following ciphertext.

You could improve your algorithm by:
- Increasing the # of states of your generator,
  e.g. by using an intermediate array:
    r = RANDOM;
    num = A[index];
    A[index] = r;
    index = r;
    return(num);
- Backcoupling the plaintext into the state of your random
  generator.

Stephan.