State of PRNG code in GMP

[Torbjörn Granlund]

Thanks Pedro for a quick and thorough answer!  Much appreciated!

Pedro Gimeno <gmpdevel at formauri.es> writes:

  > Question 1: Why is _mp_lc wrapped in a union?

  Historical reasons. It was that way when I implemented MT.

I see.

  > Question 2: "_lc" = Linear Congruential? This is supposed to be a
  > generic structure, right?

  Historical reasons again :)

Surely the field _lc could be be renamed to something less confusing
without dire compatibility consequences.  :-)

  Yes, LC is Linear Congruential. It was the only available generator
  when I started working on the MT one. The struct had the exact same
  shape before I took it, and I fitted the new generator into that
  struct trying to use the available fields in a backwards compatible
  way. Kevin went quite paranoid about ABI compatibility, to the point
  of not wanting to add another pointer member to the union for fear of
  changing the size of the structure. I think his words were along the
  lines of "I don't know if it would be compatible, it should be, but
  better safe than sorry". So my patch included these changes:

I see, I don't know if it is a valid compatibility concern; perhaps the
C standard does not pin down that pointers to two different struct types
need to be the same size, but I wouldn't have worried about that.

  The pre-existing random structure was very limited, and building a
  compatible generic generator layer on top of it while keeping
  backwards compatibility needed some compromises, like having to
  allocate a function pointers struct instead of using the random state
  struct itself to store them; abusing the pointer field in the seed's
  mpz_t for the state, and using the macros RNG_FNPTR() and RNG_STATE()
  to access those in a more programmer-friendly way.

I understand.

  The plan was to get rid of the struct issues in the next ABI breakage,
  but I guess no one took note of that with respect to the generators,
  or at least no one did anything about it (we've broken the ABI since
  GMP 4.0.1, right?)

What breakage happened for 4.0.1?

  LC (2exp) is the default and the only choice for gmp_randinit, which
  is considered obsolete. When I implemented the MT patch, there was
  also a disabled and probably non-functional Blum-Blum-Shub generator.

  I'm not too sure why I removed gmp_randinit_lc, but something about it
  being broken rings a bell, so it's possible that Kevin told me to do
  that.

It's strange, but I cannot recall the reasons either.

  >    gmp_randinit (my_randstate, GMP_RAND_ALG_DEFAULT)
  >
  > to also choose Mersenne Twister.  But GMP_RAND_ALG_DEFAULT =
  > GMP_RAND_ALG_LC as per the enum definition.

  No, gmp_randinit is declared obsolete. You're supposed to use the
  algorithm-specific gmp_randinit_xxxx for any supported algorithm xxxx.

  I don't know for sure why gmp_randinit was not adapted to the new
  generators. Probably Kevin told me to do that but I don't remember the
  rationale.

Perhaps it was to avoid more code than necessary to be pulled into a
user binary?  With a generic init function, there will be a broad link
deendency on all (init_[ALGORITHM] functions which may in turn pull in
the actual generators.

  > Question 3: What algorithm does the call
  >    gmp_randinit (my_randstate, GMP_RAND_ALG_DEFAULT)
  > choose?  Is it Mersenne Twister?

  No, it should be LC if it hasn't changed since the time I wrote the patch.

I don't think it makes any sense to have gmp_randinit_default and
gmp_randinit (..., GMP_RAND_ALG_DEFAULT) give different algorithms.

  > Perhaps we should start anew with a new set of random state functions
  > and a new type (where all fields are actually used!).  The name
  > gmp_prngstate_t might be useful.

  That would not be off the mark. Trying to build on the existing
  facilities is what led to the current mess.

I'd like to have a coherent interface which also provide reentrant
random functions to the mpn layer.  And in no case should mpn pull in
mpz.

I'd like to keep Mersenne Twister, and add block cipher based PRNGs (AES
and perhaps Salsa20r12).  We might also keep LC for historical or
compatibility reasons.

Unfortunately, Mersenne Twister uses mpz, and I am not saying that that
was a bad choice when you implemented it.  But in order to provide
reentrant mpn PRNG functions, we either rewrite the relevant parts of MT
to use mpn, or exclude it from a new mpn PRNG interface.

Here is some code I have tinkered with.

/* PRNG algorithm specific data for any constants, buffered random bits, or
   other state.  The _mp_data field should typically point to a algorithm
   specific struct.  The _mp_datasize field is used by generic code for
   de-allocating and copying a gmp_prng_t in an algorithm agnostic manner.  */
struct appdata {
  void* _mp_data;
  size_t _mp_datasize;
};

struct prng {
  void (*_prng_seed_fn) (struct appdata*, const mp_limb_t*, size_t);
  void (*_prng_run_fn) (mp_limb_t*, size_t, struct appdata*);
  struct appdata _mp_app;
};
typedef struct prng gmp_prng_t[1];

struct prng_aes {
  uint32_t key[44];
  uint32_t buf[4*8];
  uint8_t n_in_buf;
};

typedef enum {
  GMP_PRNG_ALG_LC,  GMP_PRNG_ALG_MT,  GMP_PRNG_ALG_AES,
  GMP_PRNG_ALG_LIM,  GMP_PRNG_ALG_DEFAULT = GMP_PRNG_ALG_AES
} gmp_prng_alg;

void gmp_prng_lc_seed (struct appdata*, const mp_limb_t*, size_t);
void gmp_prng_lc (mp_limb_t*, size_t, struct appdata*);
void gmp_prng_mt_seed (struct appdata*, const mp_limb_t*, size_t);
void gmp_prng_mt (mp_limb_t*, size_t, struct appdata*);
void gmp_prng_aes_seed (struct appdata*, const mp_limb_t*, size_t);
void gmp_prng_aes (mp_limb_t*, size_t, struct appdata*);

/* Generic PRNG init function.  Is this really a good idea?  A problem is that
   this will pull in all PRNG code into a binary which uses just one
   algorithms.  It even pulls in mpz functions in a mpn-only program if any
   PRNG uses mpz. */
void
gmp_prng_init (gmp_prng_t rs, gmp_prng_alg alg, ...)
{
  if (alg == GMP_PRNG_ALG_LC)
    {
      rs->_prng_run_fn = gmp_prng_lc;
      rs->_prng_seed_fn = gmp_prng_lc_seed;
      /* ... */
    }
  else if (alg == GMP_PRNG_ALG_MT)
    {
      /* ... */
    }
  else if (alg == GMP_PRNG_ALG_AES)
    {
      struct prng_aes* pa;

      rs->_prng_run_fn = gmp_prng_aes;
      rs->_prng_seed_fn = gmp_prng_aes_seed;

      pa = malloc (sizeof (struct prng_aes));
      rs->_mp_app._mp_data = pa;
      rs->_mp_app._mp_datasize = sizeof (struct prng_aes);
      pa->n_in_buf = 0xff;	/* "not initialied yet" */
    }
  else
    {
      /* use whatever we define as default */
      /* ... */
    }
}

void
mpn_prng_uniform (mp_ptr rp, mp_size_t rn, gmp_prng_t rs)
{
  (rs->_prng_run_fn) (rp, rn, &(rs->_mp_app));
}



-- 
Torbjörn
Please encrypt, key id 0xC8601622