Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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)?
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:
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$:
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! "
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.
