From: wet!naga (Peter Davidson)
Date: Sat, 19 Jun 93 02:11:53 PDT
To: cypherpunks@toad.com
Subject: weak pseuodrandom number generator
Message-ID: <m0o6ybl-0003IzC@wet.uucp>
MIME-Version: 1.0
Content-Type: text/plain


 
A pseudorandom number generator recently proposed here, namely:
 
int rand1(int seedval) { return (seed * 183041 % 183319 + 1); }
 
needs some cleaning up.  It should be something like:
 
unsigned long rand1(unsigned long n)
{ return ( ( ( n * 183041L) % 183319 ) + 1 ); }
 
where n is initally set to some seed value.  However, this is
particularly weak, and quickly degenerates into a cycle,
usually of length 208, as the following program will confirm:
 
#include <stdio.h>
#include <stdlib.h>
 
unsigned long a[15000];
 
unsigned long rand1( unsigned long n );
 
void main(int argc, char **argv)
{
unsigned int i=0, j;
 
if ( argc < 2 )
    return;
 
a[0] = atol(argv[1]);
while ( ++i < 15000 )
    {
    a[i] = rand1(a[i-1]);
    for ( j=0; j<i; j++ )
        {
        if ( a[i] == a[j] )
            {
            printf(" Cycle of length %d found.\n",i-j);
            return;
            }
        }
    }
}
 
unsigned long rand1( unsigned long n )
{
return ( ( ( n * 183041L ) % 183319L ) + 1 );
}
 
The other generator proposed is equally weak.
 
This does not demonstrate that pseudorandom number generators
cannot be used as a basis for strong encryption.