Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA

According to Le Chaud Lapin <jaibuduvin@xxxxxxxxx>:
What are the prevaling recommendations for choosing p, q, such that
the product is indeed, say, 512 bits, for a 512-bit modulus.

You first choose p randomly to be a 256-bit prime (i.e. you select
random odd integers between 2^255, inclusive, and 2^256, exclusive,
until you find one which happens to be prime).

Then, you compute a = ceil(2^511 / p) and b = floor(2^512 / p). Both are
easily obtained through simple euclidian divisions:
-- you divide 2^511 by p, and add one to the quotient;
-- you divide 2^512 by p, and use the quotient.
It is easily seen that since p is odd, these divisions cannot yield
a remainder of zero, hence the rules above are correct. Besides, if
you do it carefully, you can use a single division operation for both.

Then you select q in the [a, b] range: you choose random odd q in that
range, and when you find one which is prime, you keep it.

This guarantees that p has length 256, q has length 256 or 257, and
p*q has length 512.

This process can be further refined in several ways:

-- You can further restrict the range of q so that only 256-bit values
of q are accepted. This is important if you want to feed those primes
into some widely deployed RSA implementations which expect both primes
to have exactly half the length of the modulus, and cannot handle other
situations. Note that some values of p may greatly reduce the
range of possible 256-bit values of q; hence it may pay off to first
restrict the range of p. This yields the following:
** You choose p between sqrt(2)*2^255 and 2^256
** You choose q between ceil(2^511 / p) and 2^256
which guarantees that both primes are 256-bit long, the product is
512-bit long, and each prime is chosen in a comfortably large range.

-- There are less crude selection processes than choosing a random odd
integer and checking whether it is prime. A simple optimization is to
randomly select what the intended prime should be when reduced modulo
small primes (2, 3, 5, 7...) and then build only candidates which match
those values (easily done with CRT). You easily get a speedup of 2 or 3
with this trick.


There are things that can be done to the bit-pattern of p and q during
randomization phase obviously

You do not want to think about it in "bit patterns". The problem is
numeric, and there are ranges.


--Thomas Pornin
.