# RSA with modulus n=p²q

I've been wondering what would happen if the RSA modulus would be $n=p^2q$ instead of $n=pq$. I feel like there is an obvious security flaw (as there is with most modifications). Would this choise of $n$ make RSA less secure? If so, why? If not, then why isn't $n=p^2q$ standard since it allows operations on a bigger $\mathbb{Z}_n$? Btw, I'm talking about textbook RSA here.

-
The "bigger numbers" argument is not valid, because you can set $p'$ and $q'$ to primes of arbitrary size. The exponentiation with $e$ is done in a group with $|n|$ bits, it doesn't matter if $n$ is a product of two primes, or the construction with one prime squared. –  tylo Jul 23 '14 at 13:15
So the security just depends on the size of the primes and not of the modulus? Of course bigger primes imply a bigger modulus in the normal RSA... –  CGFoX Jul 23 '14 at 16:43
That might be oversimplifying it. But either way you can get any modulus size you want, by picking primes in the correct size. As a rule of thumb: factoring $p^2q$ or $p'q'$ is only as hard as finding the smallest prime factor. Therefore, if you have two modulus of the same size, the normal RSA modulus is probably harder to factor than the one with one factor squared, because the lowest prime factor accounts only for $1/3$ of the total size. –  tylo Jul 24 '14 at 12:00

Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations. However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes $p$, $q$ and $r$.

As for the security, well, reducing the size of the primes does make factoring methods such as ECM easier. However, with the current state of the art, it would appear that ECM against a product of three 682-bit primes (whether two of the primes were duplicated or not) would be harder than doing NFS (which doesn't care how big the primes were); however it's still enough to make people uneasy.

If you are really interested in performance, you probably should look at Elliptic Curve systems anyways...

-
Like Elgamal? Is that faster than RSA? –  CGFoX Jul 22 '14 at 18:36
Like ECIES; decryption is a lot faster than RSA; for encryption, you can do precomputation so you can do most of the work before you see the message. –  poncho Jul 22 '14 at 18:39
The Okamoto–Uchiyama cryptosystem uses a modulus $p^2 q$ to good effect. It is a precursor to Paillier's cryptosystem, which has proven fantastically useful. –  K.G. Jul 22 '14 at 20:07
The potential saving is actually greater than for multiprime RSA with 3 primes, because there are only 2 expensive modexp to perform, rather than 3. On the other hand, the modified CRT is quite a bit unusual.$\;$ Note: To get the paper, a click on "download chapter" on the page you link works for me; and then I can save the PDF (I believe, legally); that's a fortunate consequence of the IACR copyright policy. –  fgrieu Jul 23 '14 at 12:58

A possible RSA variant uses:

• some odd exponent $e>2$ (that can be $e=3$ or $e=2^{16}+1$ as customary in standard RSA);
• $p$ and $q$ distinct large random primes, with $\gcd(e,p)=\gcd(e,p-1)=\gcd(e,q-1)=1$;
• $N=p^2\cdot q$;
• some $d$ computed such that $d\cdot e\equiv 1\pmod{\operatorname{lcm}(p,p-1,q-1)}$;
• public-key function $x\to x^e\bmod N$;
• private-key function $y\to y^d\bmod N$.

It mostly works as naked/textbook RSA; in particular, if we restrict plaintext $x$ and ciphertext $y$ to positive integers less than $N$ that are not a multiple of $p$, the public-key and private-key functions are inverse functions. That restriction is NOT needed for RSA, however we can ignore it in practice: as is the case for RSA, we want to use these public-key and private-key functions on random elements $x$ and $y$, and for $p$ of practical interest (like at least 512 bit), odds of accidentally hitting a multiple of $p$ are just negligible.

Something similar was proposed, in a more general setup, by Tsuyoshi Takagi: Fast RSA-type cryptosystem modulo $p^k\cdot q$, in proceedings of Crypto 1998, where it is used a different method of evaluation of the same private-key function (with a different but ultimately equivalent $d$) using the CRT technique, allowing a considerable speed advantage. For a modern and concise exposition, see section 3.1 of Dan Boneh and Hovav Shacham's Fast Variants of RSA (extract in Cryptobytes V5N1, 2002).

The main advantage compared to standard RSA is a potential speedup of the private key function for a given size of $N$ when using the CRT, as explained in the above two papers. If we keep the size of $p$ and $q$ constant, we get a 50% larger $\log_2(N)$ for nearly the same computational cost of the private-key function (but an increase by up to 125% of the computational cost of the public-key-key function). The larger $N$ makes it more difficult to factor, thus more secure: considerably so with GNFS and other algorithm which (heuristic) cost grows as a function of $N$; but not much with ECM and other algorithm which (heuristic) cost grows as a function of the factor found. There are variants of ECM that use the special form $N=p^2\cdot q$, but the time saving is relatively manor, and I'm unsure if it can even offset the increase of the width of $N$ by 50%.

If we keep the size of $N$ the same as in standard RSA, assuming the size of $p$ and $q$ about equal and textbook multiplication, for the private key function we get a computational cost/time saving up to 70% (nothing changes for the public key function). The security w.r.t. GNFS is about kept, but it is no longer so sure that we can ignore ECM and friends. The issue is comparable to that for multiprime RSA. In a nutshell, common wisdom is that for $p$ and $q$ of 512 bits or more, security can be considered unchanged, but I add two caveats:

• ECM and related algorithms are much easier than GNFS to distribute on commodity machines, so the reasoning might be invalidated for an adversary having access to many such machines, but no supercomputer with huge memory.
• It becomes more useful (or less useless) to guard against Pollard's p − 1 and Williams' p + 1 by generating $p$ and $q$ such that $p-1$, $p+1$, $q-1$, $q+1$ have large prime factors, especially if the adversary would be content with factoring any of many $N$ (rather than a particular $N$), and $p$ and $q$ are relatively small (perhaps, less than 800 bit).

Also noteworthy: there is a signature scheme, ESIGN, using RSA modulus of the form $N=p^2\cdot q$, with much faster signature than RSA, and security reducible to that of the approximate $e$-th root problem, AERP. See Tatsuaki Okamoto and Jacques Stern: Almost uniform density of power residues and the provable security of ESIGN (in proceedings of AsiaCrypt 2003). Some versions of ESIGN are broken, but AFAIK some proposed variants are not; see also this Evaluation Report.

-
Nice answer! Have not heard of ESIGN before! –  DrLecter Jul 22 '14 at 20:08
More generally, one could also use moduli of the form $\; p^{\hspace{.03 in}j} \hspace{-0.02 in}\cdot q^{\hspace{.02 in}k} \;$ for coprime $j$ and $k$. $\hspace{1.21 in}$ Also, one could make the operations actual permutations by computing gcd(N,x) $\hspace{1.39 in}$ and sending x to gcd*((x/gcd)^e mod N/gcd). $\;$ –  Ricky Demer Jul 23 '14 at 5:58
@Ricky Demer: I fail to see why the restriction to coprime $j$ and $k$. $\;$ That $\gcd$ trick is nice! –  fgrieu Jul 23 '14 at 12:13
if j and k have a common factor i, then n has an integer ith root. This will be easier to factor to recover p and q. –  bmm6o Jul 23 '14 at 15:07
@bmm6o: Ah right, I had missed that. –  fgrieu Jul 23 '14 at 15:15

It would probably work: RSA with composite numbers

But it would be better to just choose 2 larger primes instead of reusing the same prime twice.

-
I don't really get why. –  CGFoX Jul 22 '14 at 17:36
The smaller the primes, the faster an attacker might succeed in factorization. If you use RSA 2048 bit, your primes are about 1024 bit long. In your case they would be smaller, e.g. below 700 bit. –  Thor Jul 22 '14 at 17:44
@Thor, I don't think CGFoX is planning on making the primes smaller to achieve the same bit size. Especially since the question specifies that using $p^2q$ would allow operations on a bigger $\mathbb{Z}_n$. That said, if the only benefit is a larger group, I would just pick larger primes to get the larger group personally (as you suggest). –  mikeazo Jul 22 '14 at 17:58
Yep. Of course bigger primes are the obvious way to create a bigger $n$. I'm rather wondering if there are any attacks that work on this modification, but not on the normal textbook RSA. –  CGFoX Jul 22 '14 at 17:58
@CGFoX: however, wouldn't that slow down the operation? What would the advantage be over doing standard RSA, and picking larger primes? –  poncho Jul 22 '14 at 18:01