Efficient pseudo-random number generation

[Ioannis Vranos]

I want to create some random numbers for encryption purposes, and i wonder
if the following scheme makes it more hard to guess the underneath number
generation pattern, than the plain use of rand():



#include <stdlib.h>
#include <time.h>


int GetRandomNumber(void)
{
int depth=rand();

for(int i=0; i<depth; ++i)
rand();

return rand();
}

int main(void)
{
srand(time(0));

int y=GetRandomNumber();
}


Does the above make any difference over plain use of rand()?






Regards,

Ioannis Vranos

 

[Régis Troadec]

"Ioannis Vranos" <[email protected]> a écrit dans le message de

Hi,

I want to create some random numbers for encryption purposes, and i wonder
if the following scheme makes it more hard to guess the underneath number
generation pattern, than the plain use of rand():



#include <stdlib.h>
#include <time.h>


int GetRandomNumber(void)
{
int depth=rand();

for(int i=0; i<depth; ++i)
rand();

return rand();
}

I'm not sure this one should be better than using plain rand(). Try a Khi
Square test to verify. Assuming the generator of rand() uses for example
additive congruence (linear conguence generators as well), you'll find the
same pattern of numbers modulo the number of cycles. By calling rand() in a
loop, you just increment the position in the cycle depth times. I find this
generator too weak for encryption purposes.

Reading the chapter 7 from numerical recipes (and given references like
Knuth's books) will help :
http://www.library.cornell.edu/nr/cbookcpdf.html

HTH
Regis

 

[Ben Pfaff]

I want to create some random numbers for encryption purposes, and i wonder
if the following scheme makes it more hard to guess the underneath number
generation pattern, than the plain use of rand():

Do not use rand() to generate random numbers for encryption. You
will not get cryptographically secure results. Instead, you will
need to use a random number generator designed for cryptographic
purposes. Many modern operating systems include one of these in
the OS itself. If you still have questions, sci.crypt is a
better place to ask them.

 

[Christian Bau]

I want to create some random numbers for encryption purposes, and i wonder
if the following scheme makes it more hard to guess the underneath number
generation pattern, than the plain use of rand():



#include <stdlib.h>
#include <time.h>


int GetRandomNumber(void)
{
int depth=rand();

for(int i=0; i<depth; ++i)
rand();

return rand();
}

int main(void)
{
srand(time(0));

int y=GetRandomNumber();
}


Does the above make any difference over plain use of rand()?

As Donald Knuth says: A random number generator, generated at random, is
usually not very random.

 

[Carsten Hansen]

I want to create some random numbers for encryption purposes, and i wonder
if the following scheme makes it more hard to guess the underneath number
generation pattern, than the plain use of rand():



#include <stdlib.h>
#include <time.h>


int GetRandomNumber(void)
{
int depth=rand();

for(int i=0; i<depth; ++i)
rand();

return rand();
}

int main(void)
{
srand(time(0));

int y=GetRandomNumber();
}


Does the above make any difference over plain use of rand()?






Regards,

Ioannis Vranos

The typical implementation of rand() is a linear congruential method.
Here X_{n+1} = a * X_{n} + c mod m.
Typically, m is the power of a prime.
For such an implementation your idea provides hardly any protection against
a brute-force attack.
That is because raising a number x to a power n modulo a number m only takes
log(m) steps, and the
same goes for finding the reciprocal of a number. The former depends on
Fermat's little theorem.
The latter on the Euclidean algorithm.
Basically it is cheap to skip forward in the sequence of random numbers.
To simplify the notation, let
k = X_{1}
Then
X_{k+1} = a^k * k + a^(k-1)*c + a^(k-2)*c + ... + a*c + c
= a^k * k + (a^k - 1)/(a - 1) * c

Carsten Hansen

That raising a number x to a power n modulo a number m is computational easy
is actually used in
cryptography. Google "discrete logarithm problem".

 

[Zoran Cutura]

I want to create some random numbers for encryption purposes, and i wonder
if the following scheme makes it more hard to guess the underneath number
generation pattern, than the plain use of rand():



#include <stdlib.h>
#include <time.h>


int GetRandomNumber(void)
{
int depth=rand();

for(int i=0; i<depth; ++i)
rand();

return rand();
}

int main(void)
{
srand(time(0));

int y=GetRandomNumber();
}


Does the above make any difference over plain use of rand()?

I changed the code to demonstrate that it makes no difference:

jules:[usenet] >cat random.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>


int GetRandomNumber(void)
{
int depth=rand()%1000; /* it takes to long if you don't narrow the depth */
int i=0;

for( i=0; i<depth; ++i)
rand();

return rand();
}

int main(void)
{
srand(0);

printf("%d\n", rand());
printf("%d\n", GetRandomNumber());
return 0;
}

jules:[usenet] >gcc -o random random.c
jules:[usenet] >./random
1804289383
1442767057
jules:[usenet] >./random
1804289383
1442767057
jules:[usenet] >

 

[Darrell Grainger]

I want to create some random numbers for encryption purposes, and i wonder
if the following scheme makes it more hard to guess the underneath number
generation pattern, than the plain use of rand():

Does it have to be portable? The best random number generation will
involve some hardware. Many processors now have hardware capabilities you
can take advantage of. For example, from Intel
(http://www.intel.com/design/chipsets/manuals/298029.pdf)

The RNG is dedicated hardware that harnesses system thermal
noise to generate random and indeterministic values.

If it has to be portable then avoid using rand() and search for PRNGs
designed specifically for your purpose.

 

[Kevin D. Quitt]

Check out:

ftp://ftp.quitt.net/C/Techniques/random01.pdf

 

[Ioannis Vranos]

Check out:

ftp://ftp.quitt.net/C/Techniques/random01.pdf

That PDF is very interesting.






Regards,

Ioannis Vranos

 

[Kevin D. Quitt]

That PDF is very interesting.

Yeah, I wish I'd written it. I talked earlier about setting up a
repository for comp.lang.c to house Good Stuff (TM), but was distracted by
a number of things. I'm ready to add Those Things That Everybody Should
Have; if only I knew what they all were.

 

[Ioannis Vranos]

Yeah, I wish I'd written it. I talked earlier about setting up a
repository for comp.lang.c to house Good Stuff (TM), but was distracted by
a number of things. I'm ready to add Those Things That Everybody Should
Have; if only I knew what they all were.

Well always you can create your own web pages for that.






Ioannis Vranos