Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am aware that there are concerns if $p$ and $q$ are close i.e. $\Delta=|p-q|$ can't be too small. But I would like to know if there are any known attacks for cases where $p$ and $q$ take on different bit-sizes. (Don't mention extreme cases where the bit-size is close to the modulus.)

Are there vulnerabilities? Can we select $k\pm i$ bits for $p$ and $q$ respectively (where $k$ is the bit size of the modulus and $i$ a small integer)?

share|improve this question
    
The cost of some factoring methods depends on the size of the modulus (GNFS) other methods depend on the size of the smallest prime (ECM). You need to ensure that the size of the factors is large enough so that the cost of ECM exceeds the cost of GNFS. –  CodesInChaos Apr 7 at 8:51
3  
This problem is pretty close to multi-prime RSA. In multi-prime RSA the factors are smaller as well, multi-prime RSA results in a performance gain using CRT, yours degrades performance. –  CodesInChaos Apr 7 at 8:52

2 Answers 2

up vote 9 down vote accepted

No, there is no specific vulnerability associated to choosing $p$ and $q$ with size differing by $i$ bits (or $2\cdot i$ bits as in the statement) for small $i$. However, if $i$ gets too big:

  • That improves the odds that ECM will manage to factor $n$ for some fixed size of $n$, and at some point ECM will become the best algorithm; this is the case if $i$ is about one fourth of the modulus size, perhaps lower.
  • That reduces the speed benefit one can gain from CRT for the private key operation.

Also: unless $i$ is a multiple of $32$ or $64$, that implies one at least of $p$ or $q$ does not have a bit size exactly multiple of $32$ or $64$; in turn, that implies an implementation using the CRT can't assume that $p$ and $q$ have a bit size exactly multiple of $32$ or $64$, which is customary and slightly simplifies implementation.

And more generally, $i\ne0$:

  • Is not standards-conforming: in the venerable ANSI X9.31:1997, and its current successor FIPS 186-4, $p$ and $q$ of an RSA modulus must both have exactly half the bit size of the modulus (among other requirements).
  • Reduces the odds that a key generated on some device can be successfully used as a private key on a different device (it has no impact on usability as a public key, as long as the modulus size remains standard). Addition: an hypothetical CRT implementation of the private exponent exponentiation modulo $n$ that fails to handle one of the exponentiation modulo $p$ or $q$ because of its unusual size, and does not check its final result using the public key, much likely leaks information leading to factorization of the modulus; thus the issue is not only an interoperability issue, it could be a security issue too.

Most importantly, precautions aimed at insuring that $\Delta=|p-q|$ is big enough are technically pointless: the justification given to such precautions is protection against Fermat factoring, which in its most basic form enumerates integers $b$ from $0$ onwards, stopping when $n+b^2$ is a square $a^2$, revealing $q$ as either $(a+b)/2$ or $(a-b)/2$. However, all known improvements of Fermat factoring have fully negligible odds to succeed in factoring $n=p\cdot q$ with $p$ and $q$ of equal size at least $256$ bits, but otherwise mostly random (for the number of $b$ to enumerate by the basic Fermat factoring method is $|p-q|/2$, which is higher than $2^{212}$ with odds better than $1-2^{-40}$, and none of the known improvements lowers that $2^{212}$ steps to something workable). If $p$ and $q$ are known to have the same size and the same leading $50$ bits, GNFS is still a much better choice than Fermat factoring .

As an additional argument, if the adversary had a Fermat factoring variant with sizable odds to factor $n$ knowing that $p$ and $q$ are of equal size, then that method likely can be adapted to $q$ known to be $i$ bits bigger than $p$, much like the basic Fermat factoring can be adapted to the situation $q\approx2^i\cdot p$: enumerate odd $b$ stopping when $2^{i+2}\cdot n+b^2$ is a square $a^2$, revealing $q$ as whichever of $(a+b)/2$ or $(a-b)/2$ is odd.

According to my memories of Robert Silverman's account: the requirement in ANSI X9.31 (kept in FIPS 186-4) that $|p-q|$ must be more than $100$ bits less than half the modulus bit size (for $1024$-bit modulus and higher) was introduced to please the bankers chairing at the standard's committee, who wanted that there is a simple rebuttal to a court argument on the tune of: " I claim that my client did not produce that signature! One simple explanation is that the modulus has been factored. An expert has testified that Fermat factoring, known since the 17th century, potentially could do that, and allow such forged signature. No precaution against it was taken! Whoever carelessly specified that signature system must bear the consequences! "

share|improve this answer
    
making sure the second most significant bit is different between $q$ and $p$ is enough to ensure they are not too close –  ratchet freak Apr 7 at 14:03
1  
Fail-Stop Signatures dispense much more quickly with the argument mentioned in the last paragraph. $\;\;\;\;\;\;$ –  Ricky Demer Apr 7 at 16:13
    
@ratchet freak: Yes, but by the same two arguments I use, that's not useful. That's even counterproductive to some degree: what you propose can HELP an easy variant of Fermat factoring more than not specifying anything. –  fgrieu Apr 7 at 16:25
    
@Ricky Demer: Excellent remark! Standards, and practice by banks, tend to be below the state-of-the-art. E.g. French bank Smart Cards have been issued with 321-bit RSA static signatures way into this century. No to mention ad-hoc RSA padding (ISO/IEC 9796-2 scheme 1), still in use (the fact that the best known attack requires chosen messages helps the status-quo). –  fgrieu Apr 7 at 16:38

Adi Shamir, back in 1995, proposed "RSA for paranoids" in RSA's CryptoBytes newsletter: ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto1n3.pdf. The idea is that you have p of 500 bits, q of 4500 bits, n of 500+4500 = 5000 bits, and constrain m to be 500 bits or less. Then you can encrypt with an exponent of around 20, and decrypt by calculating only m mod p via the CRT, using the fact that m mod p is constrained to be m. I don't know how this interacts with CCA2 security, but it's a cute idea.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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