From: ghsvax!hal@uunet.UU.NET (Hal Finney)
Date: Tue, 8 Dec 92 14:53:49 PST
To: cypherpunks@toad.com
Subject: PGP key generation
Message-ID: <9212082250.AA22082@nano.noname>
MIME-Version: 1.0
Content-Type: text/plain


Steve Witham asks about PGP's "peasant_modmult" routine, how it can
subtract the modulus on each addition.  It doesn't, but the code is a
little misleading (taken from mpilib.c, PGP 2.1):

    while (bits--)
    {	mp_shift_left(prod);
	msub(prod,pmodulus);	/* turns mult into modmult */
	if (sniff_bit(multiplier,bitmask))
	{   mp_add(prod,multiplicand);
	    msub(prod,pmodulus);	/* turns mult into modmult */
	}
	bump_bitsniffer(multiplier,bitmask);
    }

What is confusing is that "msub" looks like "mp_sub".  Actually, msub
is a macro defined in mpilib.h:

#define msub(r,m) if (mp_compare(r,m) >= 0) mp_sub(r,m)
	/* Prevents r from getting bigger than modulus m */

So, msub actually only subtracts if it's necessary, as would be
expected.


Jim McGrath asks:

> When PGP generates keys doesn't it always pick d and e to have
> the same number of bits, ie 446 for the strongest type?

d and e are the decryption and encryption exponents.  e is chosen to
be small, typically the number 17 or slightly larger.  d is then about
the size of n, your key modulus.

p and q, the two primes which are multiplied to get n, are about the
same size, usually.  PGP does have some code to make sure they aren't
too close to the same size (taken from rsagen.c, PGP 2.1):

        /*	See if p and q are far enough apart.  Is q-p big enough? */
        mp_move(u,q);	/* use u as scratchpad */
        mp_sub(u,p);	/* compute q-p */
        if (mp_tstminus(u))	/* p is bigger */
        {    mp_neg(u);
            too_close_together = (countbits(u) < (countbits(p)-7));
        }
        else		/* q is bigger */
            too_close_together = (countbits(u) < (countbits(q)-7));

        /* Keep trying q's until we get one far enough from p... */
    } while (too_close_together);

What this does is make sure that |p-q| is > 1/128 of the larger of p
or q.  This is designed to make sure that p and q are both very far
from the square root of n.  I.e. if n were 1024 bits, p and q could
both be about 512 bits, but they would be at least about 2^505 from
the square root of n, foiling the square root attacks.

Hal
74076.1041@compuserve.com