# What happens if we know that for an RSA key pair, the equation $d^e \equiv c \pmod{n}$ holds?

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.

• 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.
– fgrieu
Dec 3, 2023 at 10:46

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

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