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.
$\begingroup$
$\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 ♦Commented Dec 3, 2023 at 10:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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$).
