2
$\begingroup$

I am currently working on a Multipower RSA given by Takagi. I am following the book 'Cryptanalysis of RSA and Its Variants' by Jason Hinek. It gives the definition of balanced primes for standard RSA as given below:

In addition, we only consider instances of RSA with balanced primes. By balanced primes, we mean that the two RSA primes are roughly the same size. In particular, for an RSA modulus N= pq we assume that $$ 4 <\frac{1}{2}N^\frac{1}{2} < p < N^\frac{1}{2} < q < 2N^\frac{1}{2}$$

I am bit confused how to choose primes if we have already computed the Modulus without any sufficient knowledge about the size of the primes. Does author mean that we should firstly compute the Modulus of huge size and later find the primes in the bounds given?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

In the question's equation we replace $N$ by $p\;\!q$ and square each term, obtaining the equivalent $$16 <\frac14p\;\!q < p^2 < p\;\!q < q^2 < 4p\;\!q$$ The conditions $p^2 < p\;\!q$ and $p\;\!q < q^2$ are equivalent to $p<q$. The $\frac14p\;\!q < p^2$ and $q^2 < 4p\;\!q$ are equivalent to $q<4p$. With $p<q$ the left condition $16 <\displaystyle\frac14p\;\!q$ is met if (but not only if) $p>8$.

Thus assuming $p>8$, the question's equation is equivalent to $p<q<4p$ (which I find preferable).

how to choose primes

Nowadays a usual way is to decide the size $k$ of $N$ in bits (e.g. 4096 or 3072, or at least 2048 for signature keys with a set expiration date, at least 1024 at the end of the previous century, typically a multiple of 64 and almost always even); then choose two primes in the interval $[2^{(k-1)/2},2^{k/2}]$ or some subset like $[3\cdot2^{k/2-2},2^{k/2}]$; name $p$ the smallest prime and $q$ the other; perhaps check $p\ne q$ if we don't trust our prime generator. This insures $p\;\!q$ is in range $[2^{k-1},2^k)$ and thus that $N$ is exactly $k$-bit. We also have $p<q<\sqrt2\,p$, thus the question's condition is met with a wide margin. Some standards (e.g. FIPS 186-5) define additional requirements (e.g. some characteristics of the primes, and bounds for $q-p$).

Does author mean that we should firstly compute the Modulus of huge size and later find the primes in the bounds given?

No. The condition is stated to bound the kind of RSA keys considered in the rest of the work (attacks in particular). The condition is NOT intended to be a reference for the choice of primes in RSA. It's purposely looser than many (but not all) practices.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for detailed information i understood it now. $\endgroup$ Commented Jun 3 at 21:32
3
$\begingroup$

Does author mean that we should firstly compute the Modulus of huge size and later find the primes in the bounds given?

Obviously not - if you could find the primes that correspond to a specific modulus, then anyone else could as well, and so RSA wouldn't be secure.

Instead, we pick the approximate size of $N$, typically "the number of bits", and then search for $p, q$ that, when multiplied together, give an $N$ of that size.

Most commonly, we pick an $n$, which is the number of bits of the eventually $N$; common values for $n$ might be 2048 or 3072.

Then, we pick $p, q$ to be in an appropriate range, say, $2^{n/2} < p, q < \sqrt{1/2} \cdot 2^{n/2}$ (where sometimes $0.75$ replaces $\sqrt{1/2}$). If you go through the math, you'll see that these satisfy the inequalities.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for detailed explaination I understood it now. $\endgroup$ Commented Jun 3 at 21:30
2
$\begingroup$

One way of doing this is to apply the equivalent condition $q<4p$ (with $p<q$). we then immediately have $q^2<4pq=4N$ and $N=pq<4p^2$ which rearrange to $q<2\sqrt N$ and $\frac12\sqrt N<p$.

Thus if we generate first the prime $p$, we then only test candidates $q$ from the range $(p,4p)$ and we will obtain a suitable modulus.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.