1
$\begingroup$

Is there a specified size range for $p$ and $q$ when calculating $N$? For example, what size would $p$ and $q$ be when $N$ is 1024 bits?

$\endgroup$
  • 2
    $\begingroup$ In general you'll have $|q| \approx |p| \approx \frac{|N|}{2}$ so in the case of $N = 1024$ you'd have $|p| \approx |q| \approx 512$. $\endgroup$ – puzzlepalace Jun 14 '17 at 18:30
4
$\begingroup$

There is no specific length for $p$ and $q$; however, one must mind the following:

  • Since $N = pq$, the size of $N$ will be more or less the sum of the sizes of $p$ and $q$ (± 1 bit).

  • Security of the key relies on the difficulty of integer factorization. The best known algorithms for that have a cost that depends on the size of $N$, but some other algorithms (in particular ECM) have a running cost that depends on the size of the smallest factor. If one of the factors $p$ and $q$ is too small, then it may make ECM practical, leading to a security weakening.

  • Private key operations with RSA can be expensive (especially on small, embedded hardware). A common optimisation is to do private key operations not modulo $N$, but modulo $p$ and $q$ (the Chinese remainder theorem tells us that it works). Since $p$ and $q$ are smaller than $N$, this is a net gain. The speed-up factor is highest when $p$ and $q$ are both about half the size of $N$.

  • Some widespread implementations of RSA require the two factors to be exactly half the size of the modulus. This is the case, for instance, for Microsoft's CryptoAPI: when importing a private key, the import format uses fixed-size slots for the factors, that are exactly half the size of the modulus.

Therefore, while the RSA standard does not mandate any specific sizes for the individual factors, the general practice is to make both factors $p$ and $q$ to be exactly half the size of the modulus $N$. So, for a 1024-bit modulus, the factors will be 512-bit integers.

(To be even more precise, it is customary to generate each factor with its two top bits set to 1. If you just take two 512-bit integers, their product may be a 1023-bit integer; by setting the two top bits of each factor to 1, this ensures that the product will be a 1024-bit integer.)

$\endgroup$
  • $\begingroup$ There is a Wikipedia note that says: For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but 'differ in length by a few digits'[2]. I don't understand why, just pointing that out. $\endgroup$ – daniel Jun 14 '17 at 20:25
  • $\begingroup$ This is to prevent recovery of $p$ and $q$ from $N$ using Fermat's factorization method. $\endgroup$ – puzzlepalace Jun 14 '17 at 22:41
  • $\begingroup$ About setting the top two bits to 1, do you have any links to this? I thought in computer science (not mathematics) you could have a 512 bit number where the first 100 bits were 0. It feels like you are halving your range if you say something like min = 2^511 max = 2^512, instead of min = 2^0. I did find this but its pretty informal stackoverflow.com/a/12195783/866502 $\endgroup$ – daniel Jun 15 '17 at 14:54
  • 1
    $\begingroup$ @daniel The top bit is always 1, otherwise your 512-bit integer is not a 512-bit integer, but a 511-or-less-bit integer. The next one is explicitly set to 1 by some key generators, e.g. the one in OpenSSL, precisely to ensure that the product of two such 512-bit integers yields a 1024-bit integer, not a 1023-bit integer. $\endgroup$ – Thomas Pornin Jun 15 '17 at 15:09
  • 1
    $\begingroup$ @daniel To be more precise, I make a distinction between "a 512-bit integer" (value is between 2^511 and 2^512-1), and "a 512-bit sequence" which is a sequence of 512 bits, that could start with zeros and could also be interpreted as an integer (whose size would then be at most 512 bits, but possibly less). $\endgroup$ – Thomas Pornin Jun 15 '17 at 15:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.