7
$\begingroup$

In RSA using a small public exponent $e$ such as $65537$, how bad is it if the value $k$ leaks? $k$ as in the following equations:

$ed - 1 = k \phi(n)$

or

$ed - 1 = k \cdot \operatorname{lcm}(p-1,q-1)$

Intuitively, this would only reduce the complexity of the breaking the system by $65535$ times, nowhere near enough to matter, though I assume that GNFS would not be improved by knowing $k$.

EDIT: This came up in thinking about what happens if the high bits of $d$ leak as opposed to the low bits. The low bits of $d$ leaking leads to key factorization. The high bits, however, just reveal $k$, because $n$ can be used as an approximation of $\phi(n)$ to compute the high half of $d$ given $k$.

$\endgroup$

1 Answer 1

2
$\begingroup$

It's not bad at all.

Practical argument: many implementations calculate $d$ as $e^{-1} \mod \mathrm{lcm}(p-1,q-1)$ (OpenSSL, wolfCrypt, Mbed TLS) or $e^{-1} \mod \mathrm{(p-1)(q-1)}$ (Cryptlib, Nettle). So in practice an adversary can make a good guess anyway.

Meta argument: an RSA private exponent matching the public key $(n,e)$ is any $d$ such that $\forall x, (x^e)^d = x \mod{n}$. Any choice will do — otherwise RSA decryption wouldn't work, since the encryption only depends on $n$ and $e$. So revealing which particular choice of $d$ the private key holder uses does not leak any information about the private key. It only leaks information about how the implementation of the private key operation works.

Mathematical argument: you've picked a private exponent $d = k \, a$ where $a = \mathrm{lcm}(p-1,q-1)$. Suppose the adversary finds the value of $k$, and uses this knowledge to find a candidate private exponent $d'$. The adversary tests their guess by calculating $(x^e)^{d'} \mod{n}$. It doesn't matter whether they found the same private exponent that you're using: that doesn't impact the validation of the guess $d'$, and it doesn't impact the usefulness of knowing $d'$.

The only reason leaking $k$ might matter at all is if there's a side channel in the implementation of the private key operation, and knowing which private exponent is used helps in the exploitation of this side channel. With respect to the mathematical analysis, the affected step is “uses this knowledge to find a candidate private exponent”: if this step uses internal details of your implementation, it could be easier if $k$ is known. This only concerns implementations that use the private exponent: most implementations use the CRT optimization, with exponentiations to the power of $d_P$ and $d_Q$, and the size of those two values is not correlated with the size of $d$ (to make any such correlation, you'd need to know $p$ and $q$, which would be a separate break of its own). A side channel is likely to reveal the approximate size of $d$ anyway. A side channel that leaks some information about $d$ without revealing its size seems far-fetched to me, but I don't have a solid argument that it couldn't happen.

$\endgroup$
3
  • 2
    $\begingroup$ I have a feeling the answer focuses more on the difference between using $\varphi(n)$ or $\lambda(n)$, but the question is more about the value of $k$ itself. $\endgroup$
    – Fractalice
    Oct 31, 2021 at 6:55
  • $\begingroup$ @Fractalice I don't understand your comment. My point is that it doesn't matter whether you're using $k=1$, $k=\phi(n)/\lambda(n)$ or some other value of $k$, since it's just a choice of representation of the private key. $\endgroup$ Nov 7, 2021 at 19:42
  • $\begingroup$ No, $k$ in the question is the ratio $(ed-1)/\phi(n)$, not the secret group order (could be also $\lambda(n)$ or any other multiple). It does leak some information about $d$, such as high half of it. But e.g. for small $e$ it's indeed not a big deal since it could be guessed. $\endgroup$
    – Fractalice
    Nov 7, 2021 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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