Score:7

How bad is it to leak $k$ in RSA?

in flag

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

Score:2
cn flag

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.

Fractalice avatar
in flag
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.
Gilles 'SO- stop being evil' avatar
@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.
Fractalice avatar
in flag
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.
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.