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