A shared CISPRNG for casual use

From	Richard Heathfield <rjh@cpax.org.uk>
Newsgroups	sci.crypt
Subject	A shared CISPRNG for casual use
Date	2015-10-20 10:20 +0100
Organization	A noiseless patient Spider
Message-ID	<n050ti$fa1$1@dont-email.me> (permalink)

Show all headers | View raw

I have been studying the problem of how to release almost a megabyte of 
source code to sci.crypt. Clearly, that's not funny. A megabyte doesn't 
sound like much nowadays of Terabyte-sized laptop drives, but when you 
post it on Usenet it's a different matter.

This considerable amount of source was mostly generated rather than 
written, so why not just post the generator source instead?

Right, but it relies on rand(), and of course there are plenty of 
implementations of rand(), and they aren't all guaranteed to give the 
same numbers as each other (for the same seed).

So why not write a PRNG and ship it with the source?

Right, and that's what I plan to do. But I thought it might be more 
generally useful than for just this one application, so I am inviting 
comment on it before I take the other matter (the megabyte of source) 
any further.

CISPRNG - a Cryptographically In-Secure PRNG for sci.crypt use

Design goals:
1) REPRODUCIBLE RESULTS. The PRNG must give the same results on any 
computer that might reasonably be used by sci.crypt people for typical 
sci.crypt-related purposes (e.g. illustrating cipher designs, posting 
challenges, etc).

2) SIMPLE IMPLEMENTATION. The PRNG must be no more than a couple of KB 
of easy-to-follow source code.

3) PATENT-FREE. We don't want any copyright or patent stuff making life 
awkward for people.

4) NOT CRYPTOGRAPHICALLY SECURE. This isn't exactly a requirement as 
such, more the /absence/ of a requirement. This PRNG is not intended for 
use in situations where you need *serious* random numbers, and thus 
should not be judged by a CSPRNG criterion.

Yes, I know there are a million PRNGs out there. But that's the trouble 
- there really /are/ a million. What I'm after is *one* that we can all 
agree to use in situations where we (as a newsgroup) need to share a PRN 
stream that doesn't have to protect us against SMERSH but can be quite 
handy for challenges and so on. One that's simple enough that, for those 
who don't use C, with a modicum of effort they can get the same PRN 
stream by translating the code into Python or Java or Visual Basic or 
Fortran or whatever it is.

Okay, so here's the code, which is in two parts - an interface (which, 
in C, is generally called a header, eg whatever.h), and an 
implementation (the C source file, eg whatever.c).

First, the interface, cisprng.h:

/* CISPRNG - Cryptographically In-Secure
  * Pseudo-Random Number Generator
  *
  * Written by Richard Heathfield,
  * 20 October 2015.
  *
  * You will also need cisprng.c and a
  * C compiler.
  *
  * The author places this code into the
  * public domain, and so it may be freely
  * used for any legal purpose, although
  * I would recommend against using it
  * in circumstances where you really need
  * a cryptographically secure PRNG, because
  * it isn't one.
  */
#ifndef H_CISPRNG_H_
#define H_CISPRNG_H_

#define CISPRNG_RAND_MAX (0x7FFFFFFFUL)

/* set the seed */
void cisprng_set(unsigned long seed);
/* get a PRN */
unsigned long cisprng_random(void);
/* get a PRN in a range */
unsigned long cisprng_range(unsigned long low,
                             unsigned long high);
#endif
/* end of cisprng.h */

Now for the implementation, cisprng.c:

/* CISPRNG - Cryptographically In-Secure
  * Pseudo-Random Number Generator
  *
  * Written by Richard Heathfield,
  * 20 October 2015.
  *
  * You will also need cisprng.h and a
  * C compiler.
  *
  * The author places this code into the
  * public domain, and so it may be freely
  * used for any legal purpose, although
  * I would recommend against using it
  * in circumstances where you really need
  * a cryptographically secure PRNG, because
  * it isn't one.
  */
#include "cisprng.h"

static unsigned long seed_ = 0UL;

/* These constants reflect the algorithm suggested
  * in the ANSI C Standard and in C99 and C11. They
  * are used by glibc, Watcom C, Digital Mars, Code
  * Warrior, and Visual Age.
  * The glibc library yields the low 31 bits of the
  * result, the others giving the lowest 15 bits of
  * the top 16. C99 and C11 suggest an extra bit in
  * the modulo.
  */
#define M    0xFFFFFFFFUL
#define A    0x41C64E6DUL
#define C    0x3039UL

/* Call this to enter the PRN stream at
  * a specific point (optional).
  */
void cisprng_set(unsigned long seed)
{
   seed_ = seed & M;
}

/*
  * Obtain a result in the range
  * 0 to CISPRNG_RAND_MAX
  */
unsigned long cisprng_random(void)
{
   seed_ *= A;
   seed_ &= M;
   seed_ += C;
   seed_ &= M;
   return seed_ & CISPRNG_RAND_MAX;
}
/*
  * This is an attempt to give a moderately
  * well-distributed value in the range
  * low to high, without using floating point
  * for a multiplier (because I lack confidence
  * that such results are 100% guaranteed to
  * be reproducible on all machines).
  *
  * The way it works is to find out how many
  * times the required range fits into our
  * range of permitted values, giving an
  * upper limit to the PRN we are prepared
  * to accept. Then we loop until we get
  * such a value, and it's all over bar the
  * modulo.
  */
unsigned long cisprng_range(unsigned long low,
                             unsigned long high)
{
   unsigned long swap = 0;
   unsigned long range = 0;
   unsigned long repeats = 0;
   unsigned long ceiling = 0;
   unsigned long r = 0;
   low &= M;
   high &= M;
   if(low > high)
   {
     swap = low;
     low = high;
     high = swap;
   }
   range = 1 + high - low;
   repeats = CISPRNG_RAND_MAX / range;
   ceiling = repeats * range;
   do
   {
     r = cisprng_random();
   } while(r >= ceiling);
   r %= range;
   return r + low;
}
/* end of cisprng.c */

Any comments?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Back to sci.crypt | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-20 10:20 +0100
  Re: A shared CISPRNG for casual use Rich <rich@example.invalid> - 2015-10-20 10:50 +0000
    Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-20 14:03 +0100
      Re: A shared CISPRNG for casual use Rich <rich@example.invalid> - 2015-10-20 13:19 +0000
        Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-20 14:57 +0100
  Re: A shared CISPRNG for casual use Karl-Uwe Frank <karl.frank@freecx.co.uk> - 2015-10-20 14:02 +0200
    Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-20 14:11 +0100
  Re: A shared CISPRNG for casual use Jeffrey Goldberg <nobody@goldmark.org> - 2015-10-20 11:34 -0500
    Re: A shared CISPRNG for casual use Karl-Uwe Frank <karl.frank@freecx.co.uk> - 2015-10-20 21:16 +0200
      Re: A shared CISPRNG for casual use kg <kristiag+news@math.ntnu.no> - 2015-10-20 19:24 +0000
  Re: A shared CISPRNG for casual use Robert Wessel <robertwessel2@yahoo.com> - 2015-10-20 12:34 -0500
    Re: A shared CISPRNG for casual use gamo <gamo@telecable.es> - 2015-10-22 15:26 +0200
      Re: A shared CISPRNG for casual use Cristiano <cristiapi@NSgmail.com> - 2015-10-22 23:43 +0200
        Re: A shared CISPRNG for casual use Robert Wessel <robertwessel2@yahoo.com> - 2015-10-22 17:41 -0500
          Re: A shared CISPRNG for casual use Cristiano <cristiapi@NSgmail.com> - 2015-10-23 00:57 +0200
          Re: A shared CISPRNG for casual use Cristiano <cristiapi@NSgmail.com> - 2015-10-24 01:08 +0200
  Re: A shared CISPRNG for casual use rsharris.bx.psu.edu@gmail.com - 2015-10-20 13:56 -0700
    Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-20 22:24 +0100
  Re: A shared CISPRNG for casual use rsharris.bx.psu.edu@gmail.com - 2015-10-21 10:14 -0700
  Re: A shared CISPRNG for casual use Rich <rich@example.invalid> - 2015-10-22 03:44 +0000
    Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-22 09:40 +0100
      Re: A shared CISPRNG for casual use Rich <rich@example.invalid> - 2015-10-22 11:00 +0000
    Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-22 09:55 +0100
      Re: A shared CISPRNG for casual use Paulo Marques <pmarques@grupopie.com> - 2015-10-22 11:57 +0100
        Re: A shared CISPRNG for casual use Karl-Uwe Frank <karl.frank@freecx.co.uk> - 2015-10-22 13:05 +0200
        Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-22 12:08 +0100
          Re: A shared CISPRNG for casual use Rich <rich@example.invalid> - 2015-10-22 11:17 +0000
      Re: A shared CISPRNG for casual use Rich <rich@example.invalid> - 2015-10-22 11:11 +0000
        Re: A shared CISPRNG for casual use Richard Heathfield <rjh@cpax.org.uk> - 2015-10-22 12:21 +0100
      Re: A shared CISPRNG for casual use David Thompson <dave.thompson2@verizon.net> - 2015-10-31 06:52 -0400

csiph-web