State of PRNG code in GMP

Tue Jun 2 10:11:10 UTC 2020

Hi,

While you're at it touching the PRNG code, could you give consideration
to this feature request ? (adding gmp_randstate_ptr , and more generally
documenting {srcptr,ptr} types). I don't mind if you don't feel like
checking this in, but feedback would be appreciated.

https://gmplib.org/list-archives/gmp-devel/2017-August/004664.html
https://gmplib.org/list-archives/gmp-devel/2018-May/004964.html
https://gmplib.org/list-archives/gmp-devel/2018-June/005004.html
https://gmplib.org/list-archives/gmp-devel/2019-January/005182.html

Best,

E.

On Tue, Jun 02, 2020 at 11:22:19AM +0200, Torbjörn Granlund wrote:
> 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
> _______________________________________________
> gmp-devel mailing list
> gmp-devel at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-devel