For example, Paillier's RSA modulus is $n=pq$, but OU's RSA modulus is $p^2q$. I think when two $n$ are the same, the security of the two cryptographic schemes must be different. So for example, if I take 3072 for Paillier's $n$, how long should I take for OU's $n$?


1 Answer 1


In "I take 3072 for Paillier's $n$", 3072 is surely the bit size of $n$. Thus I'll read the question as:

How wide should be OU's $n=p^2q$ to be as safe as Paillier's $n=pq$ of 3072 bits?

The best known attack against both cryptosystems is the factorization of $n$.

The best known factorization method for $n=pq$ with $p$ and $q$ random primes of roughly the same size is GNFS, of cost $L_n[1/3,4\cdot3^{-2/3}]$, per L notation.

For factorization of $n=p^2q$, GNFS also works with similar cost, thus we must have $n$ at least 3072-bit. However, Lenstra's ECM is also to consider, and (I think) it's cost is about $L_{\min(p,q)}[1/2,2^{1/2}]$. Thus to maximize resistance to that later algorithm we should have $p$ and $q$ of next to the same size. That size must be at least 1024-bit to get a 3072-bit $n$. And if we do the math and ignore the $o(1)$ in $L_k[\alpha,c]=e^{(c+o(1))\ln(k)^\alpha\ln(\ln(k))^{1-\alpha}}$, we get that 1024-bit $p$ and $q$ is (barely) enough for ECM to be more costly than GNFS.

Hence we should have $p$ and $q$ of 1024-bit at least, e.g. in range $[2^{1024-1/3},2^{1024}]$ for 3072-bit $n$. If we want to err on the safe side because we ignored the $o(1)$, we can bump that a little to e.g. 1152-bit, e.g. in range $[2^{1152-1/3},2^{1152}]$ for 3456-bit $n$.

The same computation supports the mysterious Captain Nemo's "RSA Moduli Should Have 3 Prime Factors" quote.

Addition: supporting evidence in Mathematica, yielding 0.5… (resp. 10.3…) for the base-2 logarithm of the ratio of work between ECM @1024-bit (resp. @1152 bits) factors, to the work for GNFS @3072-bit product. Try It Online!.

L[n_, a_, c_] := Exp[c (Log[n]^a) (Log[Log[n]]^(1-a))];
LGNFS[n_] := L[n, 1/3, 4 3^(-2/3)];
LLenstra[p_] := L[p, 1/2, 2^(1/2)];
Log[2., LLenstra[2^{1024,1152}]/LGNFS[2^3072]]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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