Thread: Random numbers

Originally Posted by abachler

This is generalyl a better random number generator than rand(). It only generates random bytes, so just generat 4 random bytes into a DWORD and then apply the aforementioned % 31.

Well, a few things don't seem to fit quite well.
First of all, no offense, but the code is quite horrible. It's mixed C with C++, missing indentation and, you know, I never knew 9 and 15 and 25 were prime numbers. You claim the algorithm is better than mersenne twister, but I doubt that. I'll try to find out what the cycle is. However, what good is a pseudo random number generator when you can't seed? Any value coming from it will be predictable, by simply re-running the sequence. And, as stated, your algorithm is horribly slow.
How secure really is your algorithm? Did you make it up yourself? Because my bet is: nowhere near as secure as mersenne twisters.

Also, if you like secure random numbers, how come you do advies to use "% 31"? Not really secure, is it?

Edit: Ok, analysing it, it won't repeat anytime soon, no . So security wise, should a proper seed be added, this may be OK. Even though I don't know enough to compare its security with mersenne twister.

Originally Posted by EVOEx

I never knew 9 and 15 and 25 were prime numbers.

9 and 15 and 25 dont get selected as prime, seeing as how it starts at 257 you must have misread the code. Its easily seeded by loading the public: array State, if you are going to give a critical analysis, at least bother to analyze the code first.

the % 31 is specifically for the OP's needs

meh, yeah i must have given you an older version of it, although it doesnt effect the security, since it doesnt require primes, only numbers that meet other requirements that all primes just happen to meet. The only non-primes that get selected are pseudo-primes that have roots of the form 2X+1, i.e. 4X^2 + 4X + 1.

AFAIK, the code can be run under linux with a few modifications, for example, you dont have toinclude windows.h and insert

Code:

#define DWORD unsigned int
#define BYTE unsigned char

For my purposes, since I use a much larger number of primes, I load them directly from a database of primes. This version is mainly for applications that dont have access to this database. I can give you the database if you want, but it is quite large at 775MB.

Here is the database, its compressed with RAR so you need to get WinRAR

Um, abachler, you still need to cite (and hopefully link to) those publications that describe and analyse this algorithm whose implementation you posted. At the moment all we have is your word that it is cryptographically secure, and to be honest the "cryptographic strength of greater than 512K bits" claim makes it sound like snake oil to me.

That said, I suspect that a cryptographically secure PRNG is not necessary. If one was necessary, then you should not suggest scaling down the number using modulo as it can affect the distribution.

laserlight, it is an unpublished algorithm of my own design, but I am qualified to design cryptographic algorithms. If you find some unknown security flaw let me know, but it is based on sound research. If you dont think it is, just try running it for a few hundred trillion years and see if it repeats. As pointed out already there are some potential optimizations, but I know of no security flaws, obviously or I would have fixed them.

Now, as it is a pseudo-random number generator, its security does depend on the randomness of the seed if you are using it for cryptographic purposes.

The OP specifically needs an output %31, yes it will affect the distribution and thus the modified output woudl not be truly random, but I suspect for the OP's uses non-repeateability is more important than perfect distribution. Repeatability is the only problem I have with rand(), although to be honest i havent checked rand()'s distribution.

If I were designing a version to specifically generate modulo 31 outputs, the distribution would be perfect, but since I supplied a version that generates modulo 256 outputs, it will not remain perfect after % 31.

The reason I did not give the exact strenght is because it depends upon the specific primes or pseudo-primes used, and since the version I posted and the version I use have different methods of generating the 'Primes' they would have different bit strengths, and thus an approximation is the closest I can come to describing them both. Since each prime used in this version adds a minimum of 8 bits of cryptographic strenght, I just did a quicky estimation of 8 * 65536 to get the 512K. Specifically the formula for the strenght is :

Originally Posted by abachler

laserlight, it is an unpublished algorithm of my own design, but I am qualified to design cryptographic algorithms. If you find some unknown security flaw let me know, but it is based on sound research.
...
As pointed out already there are some potential optimizations, but I know of no security flaws, obviously or I would have fixed them.

Unfortunately, I am not qualified to design cryptographic algorithms. What I do know is that it is generally accepted that - even when the algorithm is designed by an expert - extensive peer review is required before an algorithm can truly be considered strong. Clearly, as I am not qualified to perform such peer review, I would like to see what peer review has been done before we can really recommend it to the OP (if the OP even needs a cryptographically secure PRNG... at the moment we're guessing about almost everything).

Originally Posted by abachler

If you dont think it is, just try running it for a few hundred trillion years and see if it repeats.

As I pointed out, this does not seem a particularly convincing proof that the algorithm is cryptographically secure since it addresses only one aspect, as important as it may be.

Originally Posted by abachler

The OP specifically needs an output %31, yes it will affect the distribution and thus the modified output woudl not be truly random, but I suspect for the OP's uses non-repeateability is more important than perfect distribution.
...
If I were designing a version to specifically generate modulo 31 outputs, the distribution would be perfect, but since I supplied a version that generates modulo 256 outputs, it will not remain perfect after % 31.

However, there is a simple technique to avoid this that applies to non-cryptographic PRNGs as well: simply reduce the range into n "buckets", and discard those generated numbers that cannot fit into any "bucket".

Originally Posted by abachler

Repeatability is the only problem I have with rand(), although to be honest i havent checked rand()'s distribution.

The algorithm for rand() is not specified by the C++ Standard (or the C Standard, for that matter), so you would only be checking a particular implementation of rand().

Originally Posted by abachler

The reason I did not give the exact strenght is because it depends upon the specific primes or pseudo-primes used, and since the version I posted and the version I use have different methods of generating the 'Primes' they would have different bit strengths, and thus an approximation is the closest I can come to describing them both.

Unfortunately, I still do not understand what this "bit strength" means with respect to cryptographic PRNGs. I would appreciate it if you could link me to an online source that explains it in detail.