3
$\begingroup$

If we possess the knowledge that the expression $d^e \equiv c \pmod{n}$ holds for an RSA key pair, what would be the implication or consequence of this? Here, $e$, $n$, and $d$ represent the public exponent, modulus, and private exponent, respectively.

$\endgroup$
1
  • $\begingroup$ Remark: we must set some upper limit to $d$, like $d<n$. That's because if we selected a random $d$ in some largish interval like $[0,n^3)$ among those $d$ such that $e\,d\equiv1\pmod{\lambda(n)}$ (alternatively: $e\,d\equiv1\pmod{\varphi(n)}$ ), then $c$ would be undistinguishable from a uniformly distributed integer on $[0,n)$ and would thus disclose no information. $\endgroup$
    – fgrieu
    Dec 3, 2023 at 10:46

2 Answers 2

4
$\begingroup$

Reformulating: it's asked if disclosing the integer $c=d^e\bmod n$ compromises the security of an otherwise secure RSA public key $(n,e)$ with private exponent $d$. I'll assume $0<d<n$, as customary in most RSA key generation standards, which variably set the upper limit for $d$ to $\lambda(n)$, $\varphi(n)$, or $n$.

The disclosure of $c$ has at least one notable security consequence: with a query to an hypothetical textbook RSA decryption (or signature) oracle, we can obtain $d$ and factor $n$. Whereas there is no known way to factor $n$ or otherwise obtain a permanent textbook RSA oracle from temporary access to one.

The simplest is to submit $c$ to the oracle, which outputs $d$, and now we can decipher. And since $e\,d-1$ is a multiple of $\lambda(n)$, we can factor $n$ (see this answer).

Using the multiplicative property of textbook RSA, we can extend the attack to an oracle that imposes a little formatting to it's input: we pick an arbitrary $u$ and compute $v=u^ec\bmod n$ until that fits the format required by the oracle. Then we submit $v$, get $w$, and compute $d=u^{-1}w\bmod n$.


So far I found no attack that works with common oracles (e.g. computing RSASSA-PKCS1-v1_5 signature of a given message), much less an attack that works without oracle.

$\endgroup$
2
$\begingroup$

As a complement to fgrieu's answer, here is an idea of the sort of issues that can occur.

Let's say that $d$ is taken as the inverse of $e$ mod $\varphi(n)$ (it would work pretty much the same with $\lambda(n)$). We have $ed-1 = k\varphi(n)$ for some $k$ which we can assume is known, since $k<e$ and $e$ is usually small, so exhaustive search is feasible. Then the known leakage value $c$ satisfies:

$$e^e \cdot c \equiv (ed)^e \equiv \big(1+k(n-p-q+1)\big)^e \equiv \big(1+k-k(p+q)\big)^e \pmod n.$$

This means that $p+q$ is a solution of a known degree $e$ equation modulo $n$, of size $\approx n^{1/2}$. If we had $e=2$, this would be sufficient to recover $p+q$ using Coppersmith's theorem and hence factor $n$. Since $e$ is odd and at least $3$, this doesn't give an actual attack, but it does suggest that funny business may occur (for example, if we also had an additional leakage of a third of the bits of $p+q$, we would be able to factor when $e=3$).

$\endgroup$

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.