1
$\begingroup$

OpenPGP defines RSA secret key in a way which differs from PKCS #1,having the aforementioned values plus U = P^-1 mod Q. However, OpenSSL seems to work only with (N, E, D) or (N, E, D, P, Q, dP, dQ, qInv) where last three should satisfy the following (as from PKCS #1):

e * dP == 1 (mod (p-1))
e * dQ == 1 (mod (q-1))
q * qInv == 1 (mod p)

Question: from the performance point of view, what would be faster: use just (N, E, D) for the secret-key operations, or calculate the missing dP, dQ and qInv?

$\endgroup$
2
  • $\begingroup$ Just to clarify: are you assuming the availability of $p$ and $q$ ? $\endgroup$
    – Ruggero
    Commented Jul 18, 2022 at 11:53
  • $\begingroup$ Yeah, those are available. $\endgroup$ Commented Jul 18, 2022 at 12:03

1 Answer 1

2
$\begingroup$

from the performance point of view, what would be faster: use just (N, E, D) for the secret-key operations, or calculate the missing dP, dQ and qInv?

Any sort of performance question is always platform specific, however in this case, it seems likely that computing dP, dQ, qInv (and then using the CRT optimization) will allow the private operation to be performed significantly faster (even if you need to perform the private operation only once).

The CRT optimization allows a circa 4x speed-up of the RSA operation itself; instead of doing a 2048 bit modular exponentation (which involves circa 2100 modular multiples over a 2048 bit modulus), you do two 1024 bit modular exponentations (which involve circa 1050 modular multiplies over a 1024 bit modulus) - roughly the same number of modular multiplies, only with a modulus that's only half as large, and if you use the standard $O(n^2)$ modular multiplication routine, that's a 4x speedup. There's the initial 'mod p, mod q' operation at the beginning and a few fixup operations at the end, those are relatively cheap.

Now, let us examine the cost of computation dP, dQ, qInv; dP and dQ are cheap ($dP = d \bmod p-1, dQ = d \bmod q-1$), and so those costs can be ignored.

Computing $qInv = q^{-1} \bmod p$ is a bit more costly, one way of computing it is to use the identity $q^{-1} \bmod p = q^{p-2} \bmod p$ (which is true because $p$ is prime); if we were to use that algorithm, that's another circa 1050 modular multiplies over a 1024 bit modulus.

Hence, the total expense of both methods (ignoring various inexpensive operations that are done only once or twice) is circa 2100 modular multiplies over a 2048 bit modulus (for the algorithm just using $N, D$) vs. circa 3150 modular multiplies over various 1024 bit modulii (for the 'reconstruct the CRT parameters, and use them' algorithm); it seems quite likely that the latter will be faster (even if you use a faster-than-quadratic modular multiply algorithm).


Rereading your question: I see you have $U = p^{-1} \bmod q$; that is effectively qinv (swapping $p$ and $q$, they're symmetric and so which one is which doesn't matter) - all you need to do is compute $dP$ and $dQ$ (just remember to swap which one you tell OpenSSL is $dP$ and which is $dQ$), and you're good to go.

Hence, my answer is even more correct than I originally thought..

$\endgroup$
5
  • $\begingroup$ I think it would be more realistic to factor $n$ first to obtain $p$ and $q$ as it is very unusual to have $p$ and $q$ available but not the other CRT parameters. I've asked @Nickolay-Olshevsky to clarify $\endgroup$
    – Ruggero
    Commented Jul 18, 2022 at 11:55
  • 1
    $\begingroup$ @Ruggero: I just answered the question that was asked. To answer the modified question you asked: if you need to factor $n$ (which is possible with both $d$ and $e$), that changes things - factoring $n$ (with $d, e$) is about as costly as performing a few private operations, hence it makes no sense if you need to do the private operation once; if you're doing it a few hundred times, it would make sense... $\endgroup$
    – poncho
    Commented Jul 18, 2022 at 11:59
  • $\begingroup$ Thanks for the detailed answer! Yeah, P and Q are available as OpenPGP RFC defines things in a different from the PKCS #1 way. First versions of both RFCs were written in 1998 so probably at that time there were no single view on these optimizations. $\endgroup$ Commented Jul 18, 2022 at 12:06
  • $\begingroup$ And thanks for the update. Looks like really PKCS #1 doesn't set rule P < Q as OpenPGP does. $\endgroup$ Commented Jul 18, 2022 at 12:07
  • 1
    $\begingroup$ @NickolayOlshevsky: that is correct; the CRT final step works out whether $P < Q$ or $P > Q$, hence PKCS #1 doesn't make a distinction... $\endgroup$
    – poncho
    Commented Jul 18, 2022 at 12:09

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.