#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    56

    [pqRNG] - an unbiased Random Number Generator with entire Cycle Length


    Today I would like to introduce a new Pseudo Random Number Generator which I have invented over the last weeks. Any constructive critic or comment is welcome.

    Mathematical Formula of pqRNG

    Q[n] = ((Q[n-1] xor R) * P) mod M

    An unbiased complete Cycle Length of all Integers between 0 and 2**n will be achieved if the following Conditions are complied

    R mod 8 = 5
    P mod 8 = 3

    M = 2**n >= 8

    One Advantage of this Pseudo Random Number Generator is that we can feed it with 3 different random Values or Values of Choice for Q, P and R as IV (Initialization Vectors). Of course R and P have to be adjusted accordingly in order to gain the unbiased entire Cycle Length of M. Due to the mathematical relation between R and P the maximum Quantity of different Number Sequences pqRNG can generate will than count 2**(2*n-6) [1].

    Below a short Example of one unbiased entire Cycle Length of M

    Start IV (pqRNG)
    Q = 0, P = 3, R = 13, M = 16

    7, 14, 9, 12, 3, 10, 5, 8, 15, 6, 1, 4, 11, 2, 13, 0

    The 32bit binary Output of pqRNG with M = 2147483647 over the Integer Interval [0, 255] passes quite remarkable all empirical and statistical Tests for Randomness as there are FIPS-140-1, Diehard Test Battery, Frequency-, Poker-, Runs-, Long-Runs and Serial-Test, also Monte Carlo Value of Pi, Arithmetic Mean, Serial Correlation Coefficient and it generate a good Uniform Distribution of Zeros (0) and Ones(1).

    Annotation: This PRNG should not be considered cryptographically secure. If a cryptographically secure Keystream for Encryption is needed it should be considered to use two pqRNG and XOR the binary Output of each into a new Stream of Byte. In that Case of course the best Results are obtained if you seed both pqRNG with a Total of 6 different IV.[2]

    Further Information can be found at http://www.freecx.co.uk/pqRNG/

    Cheers,
    Karl-Uwe

    ---
    Copyright (c) 2011, Karl-Uwe Frank
    All rights reserved.



    Reference:
    1. Correction of the maximum Quantity of different Number Sequences according to Maaartin G
    2. Withdrawn because of a certain weakness against divide-and-conquer attack as mentioned by Greg Rose
    Last edited by Karl-Uwe Frank; November 6th, 2011 at 04:41 PM. Reason: Correction
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    56
    I have uploaded source code which allows anyone to verify that my formula is working correctly in generating always all integer modulo 2^n (or perhaps modulo 2^n-1) in a full cycle - in these examples all signed and unsigned 16-bit integer. Furthermore three examples of test results, two with modulo 32767 and one with modulo 65536.

    http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_65535_full_period.txt
    http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_full_cycle_2**16_test.pb

    http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_32767_full_period.txt
    http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_32767*2+1_full_period.txt
    http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_full_cycle_2**15-1_test.pb

    The source code is simply a text file with extension *.pb and can be compiled with PureBasic on MacOSX, Linux and Windows using the PureBasic-Demo which can be downloaded for free at this URL
    http://www.purebasic.com/

    Cheers,
    Karl-Uwe
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    56
    (2011-12-12)

    This is the extended Algorithm of pqRNG named pqRNGr2

    Q[n] = ((Q[n-1] xor R1) + (P * s) + (R2 + (P xor (s-1))) mod M
    s = s + 2 + (s * 2^3)


    An unbiased complete Cycle Length of all Integers between 0 and 2n will be achieved if the following Conditions are complied

    P mod 4 = 3
    R1 mod 8 = 5 or R1 mod 8 = 7
    R2 mod 8 = 5 or R2 mod 8 = 7
    s mod 2 = 1
    M = 2^n >= 16

    An ANSI-C Source Code is avialable which allows Anyone to verify that my Formula is working correctly in generating always all Integer Modulo 2^n in a full Cycle, in this Example Source Code all unsigned 16-bit Integer (http://freecx.co.uk/pqRNG/#pqRNGr2)
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2011
    Posts
    11
    Rep Power
    0
    Have you proved that it will generate the suggested values for all values of n? Can this be initialised with negative numbers? and if it can't perhaps you should consider that.

    What I mean is, for any cryptographic tool (I noticed you said this isn't cryptographically secure but we'll treat it as a candidate) your greatest enemy is the brute force approach. Your key stream is based on three numbers, and I know in theoretical mathematics that is infinity^3, in practise it's not often the case.

    But, having said that, this is one hell of a freaking good idea, and you should pursue it, perfect it and optimise it (and write it in other, faster languages than Basic. I recommend C++ or C#, both of which I'll happily help you with if you need it).

    Good luck with this man, it's a nice idea!
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    56
    Thanks very much for your comment and encouragement.

    There is a ANSI-C source code of this formula available at http://www.freecx.co.uk/pqRNG/test_sources/pqRNGr2_full_cycle_test.c because for some weeks I am using ANSI-C instead of Basic now.

    Regarding this formula I need to mention that I think that it will never be useful for cryptographic purposes, mainly because the result is alternating. Of course in a proper combination, like within xqRNG32 or sqRNG32 it has the ability of generating quite good random values for any none cryptographic application.

    Currently I'm working on a different, more complex approach in creating a cryptographic secure PRNG.

    Code:
    /* 
    Algorithm tt32, 
    Copyright (c) 2011 Adverteam Limited (UK), Karl-Uwe Frank. 
    All rights reserved.  
    
    Free to use with or without modification and without a fee is granted
    only for private, research, academic or other non-commercial purposes.
    */
    
    static uint32_t x, q, s;    
    
    x = rand() % 0xffffffff;
    q = rand() % 0xffffffff;
    s = rand() % 0xffffffff;
    
    
    //-----------------------------------------
    //
    // tt32 (#5)
    //
    unsigned int tt32()
    {
      uint32_t t1,t2,t3,tz;
      uint16_t tt;
        
      // take parts from last x and q
      tt = (x >> 17);
      tz = (q >> 16 | q << 11);
        
      // generate new s and q
      s  = (s + tt + (s >> 14));
      q  = ((q << 5) + tt ^ s) ^ (tz ^ (s-1));
        
      // generate new x
      t1 = ((x << 11) ^ (s  >> 13));
      t2 = ((tz << 9) ^ (t1 >> 19));
      t3 = ((x  + tt) + (x  >> 23)) << 16;
      x  = ((t3 + (t1 ^ (t2 >> 15)) + (t2 ^ (t1 >> 17)) + (s >> 5)));
    
      return x;
    }
    So far this algorithm passed several thousand SmallCrush without showing the tiniest weakness, a considerable amount of Crush ... BigCrush is tested currently.

    I am posting the algorithm of tt32 right now in the context that a more reliable PRNG as part of a cryptographically secure PRNG is definitely needed, but will open up a different thread on that subject soon.

    Cheers,
    Karl-Uwe

    ---
    Algorithm tt32, Copyright (c) 2011 Adverteam Limited (UK), Karl-Uwe Frank. All rights reserved.

IMN logo majestic logo threadwatch logo seochat tools logo