Newton Hammet newton at hammet.net
Tue Dec 16 00:20:17 CET 2003

```Hello Everyone, and any gnupg developers out there.

I am studying primegen.c and other source modules of gnupg, primarly for
my own edification. And I have a question about primegen.c where a
random number is selected before testing it for primality. The code
comment says that the high order bit is set to "1" to insure that key
is a certain size, and the next to high order bit is set to "0" for
a similiar reason.  But why in the world would the lo-order bit be
set to zero?  Isn't the number supposed to be odd to start with prior
to checking for primality?  Or are mpi numbers represented as one
less or more than the actual number?  Or is there some other explanation
lurking the source code that I have not yet discovered?

Hopefully someone has an answer for me that will solve this particular
puzzle before I eventually solve it myself.

Here is the lines of code in question :::

/* generate a random number */
{   char *p = get_random_bits( nbits, randomlevel, secret );
mpi_set_buffer( prime, p, (nbits+7)/8, 0 );
m_free(p);
}

/* Set high order bit to 1, set low order bit to 0.
If we are generating a secret prime we are most probably
doing that for RSA, to make sure that the modulus does have
the requested keysize we set the 2 high order bits */
mpi_set_highbit( prime, nbits-1 );
if (secret)
mpi_set_bit (prime, nbits-2);
mpi_set_bit( prime, 0 );   /*** code in question ?????? ***/

```