Score:3

$n=pq$ and $n=p^2q$. How to take the value of two $n$ is the same in security

us flag

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$?

Score:6
ng flag

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]]
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.