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 <cstdlib>
#include <ctime>
int GetRandomNumber()
{
using namespace std;

int depth=rand();

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

return rand();
}

int main()
{
using namespace std;

srand(time(0));

int y=GetRandomNumber();
}
Does the above make any difference over plain use of rand()?


Regards,

Ioannis Vranos

[Pete Becker]

Ioannis Vranos wrote:

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

Probably: it is almost certainly worse. Creating good random number
generators requires pretty careful analysis; it's easy to fiddle with
existing generators and end up with something that's really bad. Knuth
talks about an experiment he did where he combined eight (I think)
different random number generators, using a random number to pick which
generator to use to generate the next value. Turned out to be worse than
any of the individual generators that went into the mix.

If you've tested the implementation of rand that you're using and
determined that it isn't good enough for what you're doing then you need
to look at other generators. In particular, you ought to look at the
Mersenne Twister: it's big (the most common form of the generator stores
624 32-bit values), but it's fast and it has a long period.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Claudio Puviani]

"Ioannis Vranos" <iv*@guesswh.at.emails.ru> wrote

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 <cstdlib>
#include <ctime>
int GetRandomNumber()
{
using namespace std;

int depth=rand();

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

return rand();
}

int main()
{
using namespace std;

srand(time(0));

int y=GetRandomNumber();
}
Does the above make any difference over plain use of rand()?

As Pete Becker indicated, you're probably making things worse. rand() is
typically implemented as an MLCG (taking the form R[n] = m*R[n-1]+c). Under the
very best circumstances, this can have a maximum period of 2^(number of bits in
the word). This is easy to demonstrate by the fact that for every value, there
is only one subsequent value that maps back into the range.

What you're doing by skipping gaps in the sequence is (1) probably shortening
the period, and as a consequence (2) skewing the distribution so that some
values appear more often and others don't appear at all.

Now, on the topic of fitness for the purpose, rand() is not even remotely
appropriate for cryptographic purposes. Nor are most commonly available
pseudo-random number generators. I really recommend that you read "Applied
Cryptography" by Bruce Schneier a an introduction to the field.

Claudio Puviani

[Cy Edmunds]

"Ioannis Vranos" <iv*@guesswh.at.emails.ru> wrote in message
news:c6***********@ulysses.noc.ntua.gr...

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 <cstdlib>
#include <ctime>
int GetRandomNumber()
{
using namespace std;

int depth=rand();

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

return rand();
}

int main()
{
using namespace std;

srand(time(0));

int y=GetRandomNumber();
}
Does the above make any difference over plain use of rand()?


Regards,

Ioannis Vranos

rand() is OK for making a Yahtzee program, but for something as important as
encryption I would not recommend it. The standard only requires it to
deliver 16 bits and the requirements of its statistical performance are
inadequately defined. Good portable generators of 31 bits or more are
readily available -- e.g. www.boost.org

--
Cy
http://home.rochester.rr.com/cyhome/

[Keith H Duggar]

> If you've tested the implementation of rand that you're using and

determined that it isn't good enough for what you're doing then you need
to look at other generators. In particular, you ought to look at the
Mersenne Twister: it's big (the most common form of the generator stores
624 32-bit values), but it's fast and it has a long period.

The OP said his application is cryptography. I don't know if that
means a toy project or a "real" software project. I hope the OP is
working on a toy project. Otherwise, they need to learn MUCH more
about random number generators and particularly those that are crypto
secure and this topic seems off topic here.

OP, neither rand nor Mersenne are suitable for cryptography. You need
to be using something such as Blum Blum Shub for example.

L. Blum, M. Blum, and M. Shub.
A Simple Unpredictable Pseudo-Random Number Generator.
SIAM Journal on Computing, volume 15, pages 364-383, May 1986

But more importantly, if this isn't a toy, please take the time to
learn the field as well as you can. I'm sure anyone that uses your
software will appreciate having a decent crypto system.

If it is a toy, well have fun with whichever generator you choose :)

[bartek]

"Ioannis Vranos" <iv*@guesswh.at.emails.ru> wrote in
news:c6***********@ulysses.noc.ntua.gr:

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():

You might want to take a look at the Crypto++ library:
http://www.eskimo.com/~weidai/cryptlib.html

It's free, open source, and pretty extensive.

b

[Ioannis Vranos]

"Keith H Duggar" <du****@mit.edu> wrote in message
news:b4*************************@posting.google.co m...

The OP said his application is cryptography. I don't know if that
means a toy project or a "real" software project. I hope the OP is
working on a toy project. Otherwise, they need to learn MUCH more
about random number generators and particularly those that are crypto
secure and this topic seems off topic here.

Look in fact i was making a random password generator utility and i wanted
cryptographic level randomness. My first priority is portability by using
the standard library. Since i saw that rand() rand()ised isn't any good, i
used a RNG of .NET cryptographic API (a RNGCryptoServiceProvider object).
It's supposed to be thoroughly checked.


Ioannis Vranos

[Jerry Coffin]

"Cy Edmunds" <ce******@spamless.rochester.rr.com> wrote in message news:<eZ******************@twister.nyroc.rr.com>.. .

[ ... ]

rand() is OK for making a Yahtzee program, but for something as important as
encryption I would not recommend it. The standard only requires it to
deliver 16 bits and the requirements of its statistical performance are
inadequately defined. Good portable generators of 31 bits or more are
readily available -- e.g. www.boost.org

Though you don't state it directly, you more or less imply that a
31-bit generator IS suitable for encryption.

This is NOT generally the case. First of all, rand() is typically
implemented as a linear-congruential PRNG, which not suitable for
cryptographic purposes, regardless of size.

Second, if you do start with a suitable algorithm, a cryptographic
generator will generally need to store substantially more than 31 bits
of state -- somewhere in the vicinity of twice that would be a
reasonable starting point, and depending on exactly what you're doing,
the requirements might easily go up from there.

--
Later,
Jerry.

The universe is a figment of its own imagination.