# Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$

The Congress of ThéOùÇa enacted that civilian use of any public-key encryption system is authorized on the territory of ThéOùÇa, subject to meeting certain security requirements published by the Ministry of Defense. The essence of these is:

..must operate per the internationally recognized RSAES-OAEP algorithm and relevant requirements in PKCS#1 V2.2, with a 2048-bit public modulus $n$ product of two primes $p$ and $q$. In order to ensure separation of key domains with the Pailler cryptosystem used for national defense purposes, the key generator shall be such that $p$ and $q$ also meet the requirement $\gcd(pq, (p-1)(q-1))\ne 1$. Demonstration of conformance to that requirement shall be by submitting the mathematical description of the key generation method to the Ministry of Defense of ThéOùÇa.

Can a public-key encryption system lawfully usable by civilians on the territory of ThéOùÇa be secure? If yes, give a possible submission to the Ministry of Defense (English is spoken in ThéOùÇa). In either case, make a cryptographically convincing argument.

Thanks to Poncho for spotting a big mistake in my transcription of the Official Journal of ThéOùÇa, now fixed.

This is not homework. If you wonder, inspiration was that recent question.

If $n = pq$ with $p, q$ prime and $\gcd(pq, (p - 1)(q - 1)) = r > 1$ then clearly $r = p$ or $r = q$. Now obviously $q - 1$ cannot divide $p$ and so we must have $p$ divides $q - 1$, without loss of generality. Thus: $$q - 1 = kp ~ ~ ~ \text{for some} ~ k > 1$$ Now suppose that $k$ is $B$-powersmooth for small $B$, then we have $M = \alpha k$ for $M$ a suitable product of prime powers up to $B$, some $\alpha$ and so for any $a$ we have: $$a^{Mn} \equiv a^{Mpq} \equiv a^{(\alpha k p)q} \equiv a^{\alpha(q - 1)q} \equiv 1 \pmod{q}$$ And so in general we find that: $$\gcd(a^{Mn} - 1, n) = q$$ Therefore in order for $n$ to be usable in the context of RSA, $k$ should not be smooth. Realistically we will be able to try $B$ up to $2^{80}$ or so (you won't be factoring the 2048-bit modulus through general purpose algorithms anyway) which means $k \approx 2^{81}$ and a special key generation technique needs to be used, probably involving letting $2rp = q - 1$ for large prime $r$ with $k = 2r$.
And since $k$ is large, that means $q/p \approx 2^{81}$ so the modulus is unbalanced. Perhaps this enables polynomial-time factorization of the 2048-bit modulus via existing methods which rely on particularly poor selection of $p$ and $q$, or perhaps the scheme is secure with careful selection of $k$. Further work is needed to determine which conclusion is the right one (but I am less and less confident in this scheme).
• I'm truly glad that you have found and explained me another way to find $p$ given $k$, which is original, very interesting, and perhaps could be useful in some way! – fgrieu Nov 1 '14 at 1:18
• @fgrieu Thanks! Hopefully there is a way to improve on the number theory to provide a faster algorithm to find $k$ than brute force. – Thomas Nov 1 '14 at 1:21
• @fgrieu As I suspected (it was fairly obvious in retrospect) we also need $k$ to be non-smooth: the trick is that $n$ automatically gives us the factor of $p$, which gets us most of the way to $q - 1$ in the context of the Pollard $p - 1$ algorithm. This doesn't really change much, though, it just means that the key generation procedure needs to be adjusted to avoid $k$ being smooth, it is still open whether we can exploit the length difference between $p$ and $q$. – Thomas Nov 2 '14 at 10:31
• @fgrieu No, because we have a multiple of $p$: the modulus $n$ itself. So we get that particular prime factor "for free" by adding $n$ to the product of prime powers. – Thomas Nov 3 '14 at 10:55
• Common wisdom (see this) seems to be that all known factoring algorithms are no more efficient than GNFS at factoring a 2048-bit $pq$ with $p$ and $q$ mostly random primes with a 680-bit difference in size; we would be conservative with 512. AFAIK, among subexponential algorithms, only Lenstra's ECM really takes advantage of the imbalance, but if it is not, and can't be, made faster by the special form implied by $\gcd(pq, (p-1)(q-1))\ne 1$, we seem to be safe from ECM. – fgrieu Nov 5 '14 at 7:03