1. Forum
  2. Usenet
  3. SCI.CRYPT.RANDOM-NUMBERS

  • Cheap PRNGs for embedded systems?

    From Philipp Klaus Krause@21:1/5 to All on Tue Sep 22 22:48:06 2015
    The C language has a non-cryptographic PRNG with the srand(), rand()
    interface. The standard also contains a portable example implementation,
    for the smallest allowed value of RAND_MAX:

    static unsigned long int next = 1;

    int rand(void) // RAND_MAX assumed to be 32767
    {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
    }

    void srand(unsigned int seed)
    {
    next = seed;
    }

    unfortunately, the 32-bit multiplication seems a bit too expensive for
    low-end embedded systems.
    I'm looking for a good, cheap alternative PRNG. It should only use cheap operations, such as bitwise opeations, additions or subtractions.
    Any recommendations or pointers to good publications or books on the topic?

    Philipp

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From William Unruh@21:1/5 to Philipp Klaus Krause on Tue Sep 22 22:35:00 2015
    On 2015-09-22, Philipp Klaus Krause <pkk@spth.de> wrote:
    The C language has a non-cryptographic PRNG with the srand(), rand() interface. The standard also contains a portable example implementation,
    for the smallest allowed value of RAND_MAX:

    static unsigned long int next = 1;

    int rand(void) // RAND_MAX assumed to be 32767
    {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
    }

    void srand(unsigned int seed)
    {
    next = seed;
    }

    unfortunately, the 32-bit multiplication seems a bit too expensive for low-end embedded systems.
    I'm looking for a good, cheap alternative PRNG. It should only use cheap operations, such as bitwise opeations, additions or subtractions.
    Any recommendations or pointers to good publications or books on the topic?

    Why not rc4? It is a cryptographic strength random number generator.
    Well, there is some evidence that at the 1 part in about 10^6 the
    distribution is not precisely flat. It uses only byte swaps
    and additions.

    Ie, any cryptographic steam cypher is a PRNG. The setup is a little bit expensive since you must discard the first hundred or so byte output or
    there are some biases in those first 100 bytes. But as PRNG those first
    bytes are stll a HUGE amount better than your rand function which has
    lots of correlations in the output.


    Philipp

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Philipp Klaus Krause@21:1/5 to William Unruh on Thu Sep 24 18:18:47 2015
    On 23.09.2015 00:35, William Unruh wrote:
    Why not rc4? It is a cryptographic strength random number generator.
    Well, there is some evidence that at the 1 part in about 10^6 the distribution is not precisely flat. It uses only byte swaps
    and additions.

    I can't afford the byte-array used in rc4. The devices I want to target typically have 128B to 32KB of RAM total.
    I'd prefer not to have to keep storage for more than 4 bytes in between obtaining two subsequent pseudo-random numbers.

    Philipp

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Eather@21:1/5 to All on Fri Sep 25 08:59:12 2015
    On Wed, 23 Sep 2015 06:48:06 +1000, Philipp Klaus Krause <pkk@spth.de>
    wrote:

    The C language has a non-cryptographic PRNG with the srand(), rand() interface. The standard also contains a portable example implementation,
    for the smallest allowed value of RAND_MAX:

    static unsigned long int next = 1;

    int rand(void) // RAND_MAX assumed to be 32767
    {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
    }

    void srand(unsigned int seed)
    {
    next = seed;
    }

    unfortunately, the 32-bit multiplication seems a bit too expensive for low-end embedded systems.
    I'm looking for a good, cheap alternative PRNG. It should only use cheap operations, such as bitwise opeations, additions or subtractions.
    Any recommendations or pointers to good publications or books on the
    topic?

    Philipp

    You could rewrite the rand function you gave above to use int's and change
    the parameters to

    next = next * 17 + 5

    the trick here being that this is equivalent to:

    next = next < 4 + next + 5

    the '< 4' being a left shift 4 places, which is equivalent to multiply by
    16.

    However LCG random number generators are often not great with micro-controllers. The bits change in a regular order

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Eather@21:1/5 to David Eather on Fri Sep 25 09:01:38 2015
    On Fri, 25 Sep 2015 08:59:12 +1000, David Eather <eather@tpg.com.au> wrote:

    On Wed, 23 Sep 2015 06:48:06 +1000, Philipp Klaus Krause <pkk@spth.de>
    wrote:

    The C language has a non-cryptographic PRNG with the srand(), rand()
    interface. The standard also contains a portable example implementation,
    for the smallest allowed value of RAND_MAX:

    static unsigned long int next = 1;

    int rand(void) // RAND_MAX assumed to be 32767
    {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
    }

    void srand(unsigned int seed)
    {
    next = seed;
    }

    unfortunately, the 32-bit multiplication seems a bit too expensive for
    low-end embedded systems.
    I'm looking for a good, cheap alternative PRNG. It should only use cheap
    operations, such as bitwise opeations, additions or subtractions.
    Any recommendations or pointers to good publications or books on the
    topic?

    Philipp

    You could rewrite the rand function you gave above to use int's and
    change the parameters to

    next = next * 17 + 5

    the trick here being that this is equivalent to:

    next = next < 4 + next + 5

    the '< 4' being a left shift 4 places, which is equivalent to multiply
    by 16.

    However LCG random number generators are often not great with micro-controllers. The bits change in a regular order

    grr.. (next < 4) being a left shift 4 places, which is equivalent to
    multiply
    by 16.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From William Unruh@21:1/5 to Philipp Klaus Krause on Thu Sep 24 17:20:29 2015
    On 2015-09-24, Philipp Klaus Krause <pkk@spth.de> wrote:
    On 23.09.2015 00:35, William Unruh wrote:
    Why not rc4? It is a cryptographic strength random number generator.
    Well, there is some evidence that at the 1 part in about 10^6 the
    distribution is not precisely flat. It uses only byte swaps
    and additions.

    I can't afford the byte-array used in rc4. The devices I want to target typically have 128B to 32KB of RAM total.
    I'd prefer not to have to keep storage for more than 4 bytes in between obtaining two subsequent pseudo-random numbers.

    Well you could always do 2bit rc4, which would need a 4 element memory.
    With more work ( longer program) you could even pack the bytes, but it
    would not buy that much. iYou would make up the random byte 2 bits at a
    time. That would only require swaps, and bit shifts and ands and ors.





    Philipp


    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Philipp Klaus Krause@21:1/5 to David Eather on Fri Sep 25 09:29:28 2015
    On 23.09.2015 02:08, David Eather wrote:

    You could try XORShift

    https://en.wikipedia.org/wiki/Xorshift

    I had a look at Marsaglia's paper "Xorshift RNGs". The 32-bit one could
    be cheap enough; he recommends parameters (13, 17, 5). Are those
    parameters a good choice?
    I'd consider use the lower 16-bit as the PRNG output.
    Is that a reasonable choice? How does it compare in quality to using the
    lower 16-bit of a 32-bit or 24-bit Galois-LFSR?

    Philipp

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Eather@21:1/5 to All on Wed Sep 23 10:08:03 2015
    On Wed, 23 Sep 2015 06:48:06 +1000, Philipp Klaus Krause <pkk@spth.de>
    wrote:

    The C language has a non-cryptographic PRNG with the srand(), rand() interface. The standard also contains a portable example implementation,
    for the smallest allowed value of RAND_MAX:

    static unsigned long int next = 1;

    int rand(void) // RAND_MAX assumed to be 32767
    {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
    }

    void srand(unsigned int seed)
    {
    next = seed;
    }

    unfortunately, the 32-bit multiplication seems a bit too expensive for low-end embedded systems.
    I'm looking for a good, cheap alternative PRNG. It should only use cheap operations, such as bitwise opeations, additions or subtractions.
    Any recommendations or pointers to good publications or books on the
    topic?

    Philipp

    You could try XORShift

    https://en.wikipedia.org/wiki/Xorshift

    but is you have an 8-bit embedded system and can use 256 bytes of RAM then
    also look at RC4

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Philipp Klaus Krause@21:1/5 to Philipp Klaus Krause on Fri Sep 25 09:37:48 2015
    On 25.09.2015 09:29, Philipp Klaus Krause wrote:
    On 23.09.2015 02:08, David Eather wrote:

    You could try XORShift

    https://en.wikipedia.org/wiki/Xorshift

    I had a look at Marsaglia's paper "Xorshift RNGs". The 32-bit one could
    be cheap enough; he recommends parameters (13, 17, 5). Are those
    parameters a good choice?
    I'd consider use the lower 16-bit as the PRNG output.
    Is that a reasonable choice? How does it compare in quality to using the lower 16-bit of a 32-bit or 24-bit Galois-LFSR?

    Sorry for the mistake; I'd use the lower 15 bits for each as output,
    since C rand() returns a nonnegative int, which limits the range to [0,
    32767].

    Philipp

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Eather@21:1/5 to All on Fri Sep 25 18:03:27 2015
    On Fri, 25 Sep 2015 17:29:28 +1000, Philipp Klaus Krause <pkk@spth.de>
    wrote:

    On 23.09.2015 02:08, David Eather wrote:

    You could try XORShift

    https://en.wikipedia.org/wiki/Xorshift

    I had a look at Marsaglia's paper "Xorshift RNGs". The 32-bit one could
    be cheap enough; he recommends parameters (13, 17, 5). Are those
    parameters a good choice?
    I'd consider use the lower 16-bit as the PRNG output.
    Is that a reasonable choice? How does it compare in quality to using the lower 16-bit of a 32-bit or 24-bit Galois-LFSR?

    Philipp


    GM knew what he was doing and it is essentially the same as a GLFSR (since
    many say a GLFSR is essentially the same as a LFSR)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)