5
$\begingroup$

From Fundamental theorem of arithmetic, every integer greater than 1 either is prime itself or is the product of prime numbers, and that this product is unique, up to the order of the factors.

$$n=p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_r^{e_r}$$

Inorder to factorize, the worst case is if the composite number is a product of two large primes. (general statement)

In RSA key generation, it is stated as follows

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'to make factoring harder.

In Paillier key generation, it is stated as follows

Choose two large prime numbers p and q randomly and independently of each other such that $\gcd(pq,(p-1)(q-1))=1$. This property is assured if both primes are of equal length.

My doubt is, what is the actual worst case for integer factorization problem?

1) $n=pq $ and $length(p) = length(q)$ $\ge$ k, for some $k \ge 1024,2048 \cdots $

2) $n=pq$ and $|length(p)-length(q)| \le k$, for some $k \ge 1,2,3\cdots$

Provide reference stating the worst case for integer factorization with particular values of $k$

$\endgroup$
  • 1
    $\begingroup$ As long as p and q are of reasonable size, e.g. > 1000 bit and the difference (k) between the length of p and q is not too big, e.g. k < 30 bit and the values of p and q differ by some amount, e.g. |p-q| > 2^500, then factoring will be hard. (The last condition has to be taken into account when you choose p and q of equal size). $\endgroup$ – user27950 Feb 27 '17 at 5:28
  • 1
    $\begingroup$ My magical secret factoring algorithm is O(n) for all inputs,except for "evil" primes whos decimal expansion starts with 666. Since we don't have good lower bounds on how hard factoring is your question is only meaningful when limiting to current state of the art factorization algorithms. $\endgroup$ – Meir Maor Feb 27 '17 at 5:55
  • 2
    $\begingroup$ @Cryptosasis: it is debatable if the condition $|p-q|>2^{500}$ (or any similar condition on $|p-q|$) is necessary: if it was, why would not it be necessary that $|13p/11-q|$ is large? If it is not, a trivial variant of Fermat factors $pq$. And if we posit that it is necessary that $|p-q|$ is large, it is debatable what the right bound is. FIPS 186-4 appendix B 3.1, 2(d) (borrowing from ANSI X9.31:1998) asks $|p-q|>2^{\text{length}(p)-100}$, with $\text{length}(p)=\text{length}(q)$. $\endgroup$ – fgrieu Feb 27 '17 at 9:57
  • 1
    $\begingroup$ The bound on the difference of the primes is not a natural constant. Different specifications will provide different values. For instance, the German health card standard says: $0.1 < |log_2(p) - log_2(q)| < 30$. $\endgroup$ – user27950 Mar 1 '17 at 5:55
  • 1
    $\begingroup$ @fgrieu: only in German language: gematik.de/cms/media/dokumente/ors1_release_1_5/… (See cos spec v3.8.0 ) $\endgroup$ – user27950 Mar 29 '17 at 18:24
4
$\begingroup$

My doubt is, what is the actual worst case for integer factorization problem?

...

Provide reference stating the worst case for integer factorization with particular values of k

Such a statement can not be done for any class of algorithms at all, only a specific algorithm can have a worst case runtime.

In general, worst case estimations are barely used in cryptography at all, because the average case matters much more. Here's an example for that: Assume you had a new, hypothetical factorization algorithm, which has linear runtime for composite numbers on almost all inputs, but for values of the factorial function it has exponential runtime. Now the worst-case runtime is exponential, but the average is barely more than linear. And even worse: In the cases of $x!$ as input,the input is divisibly by $2$ when $x>1$, so just run the algorithm on $x!/2$ instead, with its linear runtime. This would make factorization entirely useless for cryptography - but the algorithm has exponential worst case runtime. Worst case assumptions are only useful if you can somehow reduce the average case to the worst case (possibly under randomized reductions, etc.) - for example in lattice-based cryptography these methods apply.

When looking at known factorization algorithms, there are some which scale with the size of the smallest prime factor, some scale with the total length of the numbers and some on "closeness of prime factors". In order to counter them all, suggestions like the ones you found are often made. However, those suggestions are made in reference to known algorithms not proven in any way whatsoever.

In order to get actual current state-of-the-art recommendations, keylength.com lists the recommendations of various sources with the publication date. The latest one references the BSI publication of Feb 2017 here: Publication in German, edit: found the English Verison

It has the following suggestion in the subsection RSA:

$\epsilon_1 < |\log_2(p) - \log_2(q)| < \epsilon_2$

And the suggested values for the boundaries are: $\epsilon_1 \approx 0.1, \epsilon_2 \approx 30$. The value $0.1$ for the metric would imply that $p/q$ differs from $1$ by at least a factor of $\approx 1.07177346$, which implies roughly if given the smaller prime $p$, that $q > (1+\frac{1}{14})p$, which in return means for length $b$ primes, the difference should be at least $b-4$ bits (which would mean the difference is $1/16$, but it should be $1/14$ or more).

$\endgroup$
3
$\begingroup$

If you allow the primes to be of radically different size, elliptic curve factoring could be faster than the number field sieve. But it seems like both your options preclude that happening.

Therefore, for either of your cases, the best known factoring algorithm is the number field sieve, which doesn't much care about the size of the factors. Which means that both cases are equally hard, as long as the size of the product is about the same.

As for references, any reasonably recent key length study should contain (a reference to) a reasonably complete survey on factoring algorithms, from which the above can be deduced.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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