Random numbers

This is a discussion on Random numbers within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by abachler This is generalyl a better random number generator than rand(). It only generates random bytes, so ...

  1. #16
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by abachler View Post
    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.
    Last edited by EVOEx; 11-20-2008 at 12:46 PM.

  2. #17
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by EVOEx View Post
    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
    Last edited by abachler; 11-20-2008 at 02:39 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  3. #18
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by abachler View Post
    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
    Ah, yes, I missed that line. I would've ran the code if I could, but "unfortunately" I run linux. Anyway, what about 289 then? And several others...

  4. #19
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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
    Last edited by abachler; 11-20-2008 at 05:39 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,272
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #21
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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 :
    Attached Images Attached Images  
    Last edited by abachler; 11-21-2008 at 06:53 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,272
    Quote 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).

    Quote 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.

    Quote 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".

    Quote 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().

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #23
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by laserlight View Post
    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.
    The strength is a definition of approximately how many unique states you would have to check to guarantee (100%) findign the exact state used to encrypt the original data. In modern cryptography it is generally defined in bits. So for example, if I was encoding a message using a Vigenere Cipher (a poor example but used for simplicity) using only a single letter as the key it would have 26 unique states (one for each possible letter). This would give it a strenght of ~4.7 bits, log2(26). If you used a 2 letter key then it woudl have ~9.4 bits, since there are now 676, 26 * 26, possible combinations. In modern cryptography the bit strength is used because the actual number of combinations are generally too large to write out. In modulus based cryptography, keys are not subject to the weaknesses of the Vigenere cipher, as any single bit change in the key significantly alters the encoding process.

    The method I posted essentially uses a series (65536) of modulus counters to produce a highly parallel Linear Feedback Shift Register.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. questions....so many questions about random numbers....
    By face_master in forum C++ Programming
    Replies: 2
    Last Post: 07-30-2009, 09:47 AM
  2. Doubts regarding random numbers generation
    By girish1026 in forum C Programming
    Replies: 9
    Last Post: 12-31-2008, 10:47 PM
  3. random numbers limit
    By HAssan in forum C Programming
    Replies: 9
    Last Post: 12-06-2005, 07:51 PM
  4. Generate random numbers in Lucky7 project using C#
    By Grayson_Peddie in forum C# Programming
    Replies: 1
    Last Post: 04-12-2003, 12:03 AM
  5. random numbers
    By lil_plukyduck in forum C++ Programming
    Replies: 5
    Last Post: 01-14-2003, 10:14 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21