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

On May 29, 3:14 am, Christian Siebert <iB...@xxxxxx> wrote:
What are the prevaling recommendations for choosing p, q, such that
the product is indeed, say, 512 bits, for a 512-bit modulus.

What do you all think about the following lo-fi approach?
Does this reveal any additional information to an adversary?
(note: x_min <= x <= x_max)

let 'b' be the base (e.g. 2 for binary numbers or 10 for decimal ones)
let 'd' be the number of digits to base 'b' (e.g. d=512 in your
example)

N_min = b^{d - 1} , N_max = b^d - 1
p_min = ceil(sqrt(N_min)) , p_max = floor(sqrt(N_max))
p = generate_RSA_prime(p_min, p_max)
q_min = ceil(N_min/p) , q_max = floor(N_max/p)
q = generate_RSA_prime(q_min, q_max)
return p*q

That works.

Though I wonder how tedious it would be to deal with floating-points
in ceil/floor/sqrt and gurantee that code is correct. A nit-pick, but
one would have to be very careful if one were to ensure that a
possible states of n were reachable. :)

-Le Chaud Lapin-
.

Relevant Pages

  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... the product is indeed, say, 512 bits, for a 512-bit modulus. ... What do you all think about the following lo-fi approach? ... will necessarily be a non-trivial (relatively speaking) function. ... In my multiply-and-check scheme, I simply make all bits of p and q ...
    (sci.crypt)
  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... Le Chaud Lapin wrote: ... What are the prevaling recommendations for choosing p, q, such that ... the product is indeed, say, 512 bits, for a 512-bit modulus. ... If the result is longer than the length of N/2 the product is too big ...
    (sci.crypt)