4

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.

Community
  • 1
fgrieu
  • 131,696
  • 12
  • 284
  • 553

1 Answers1

4

Okay, I came up with this, it's not a complete answer and the attack presented is pretty weak without a follow-up algorithm for breaking a somewhat unbalanced modulus but let me know if you spot any flaws or have any ideas to improve it...

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).

Thomas
  • 7,388
  • 1
  • 30
  • 43
  • Kudos for the number-theoretic method to find $p$ given $k$; I only considered solving for $p$ the second-degree equation: $k⋅p^2+p=n$, perhaps just as $p=\lfloor\sqrt{n/k}\rfloor$ followed by a check that this divides $n$. $\;$ I agree with everything except perhaps the sentence ending in _security is at least questionable_; I really don't know for sure! – fgrieu Nov 01 '14 at 01:00
  • @fgrieu Hmm, the square root approach seems more direct, looks like I missed the obvious! But in any case, yes, it means that subject to the restrictions the modulus has to be pretty unbalanced to offer any security, but I don't have anything better than that so far :/ – Thomas Nov 01 '14 at 01:08
  • 1
    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 01 '14 at 01:18
  • 1
    @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 01 '14 at 01:21
  • 1
    @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 02 '14 at 10:31
  • Thinking about it again, $q-1$ is bound to have a high prime factor (that's $p$); is not that sufficient to guard against Pollard's $p−1$ algorithm on the $q$ side, even if $k$ is smooth? – fgrieu Nov 03 '14 at 10:54
  • 1
    @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 03 '14 at 10:55
  • Ah yes I now see the idea. So we need an even $k$ with a large prime factor. And we are left wondering if that's good enough. – fgrieu Nov 03 '14 at 11:01
  • 1
    Common wisdom (see [this](http://crypto.stackexchange.com/q/15823/555)) 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](http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization) 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 05 '14 at 07:03