-1
$\begingroup$

The question “Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid” assumes the factors are known. This got me wondering if it is possible to calculate the value of $d$ when being given only the values of $c$, $n$ and $e$… and factors remain secret.

  • If it’s possible, is there an easy way to do so?
  • If it’s hard/complex, what exactly makes it hard/complex?
  • And in case it’s generally impossible to calculate $d$ using only those values, why?

This may be an amateurish question, but I couldn’t find the answer at Crypto.SE – so, I’m asking.

$\endgroup$
  • 1
    $\begingroup$ If you find a way, please tell us, this would just about break the entire internet security... (also, do you know anything else about these values or their relation?) $\endgroup$ – SEJPM Jul 16 '16 at 14:49
  • 4
    $\begingroup$ Of course it's possible. Merely factorize $n$ and then compute the multiplicative inverse of $e \pmod {\phi (n)}$ using the extended Euclidean algorithm. Note however that 'possible' does not equal 'easy'. $\endgroup$ – J.D. Jul 16 '16 at 14:59
0
$\begingroup$

I am afraid I was a little flippant in my comment to the first version of your question. Your edits have made for a more substantive question, so I feel I owe you a more substantive answer.

It must be at least as hard as factoring to compute $d$ because (as I will show below) if you can compute $d$ for arbitrary $e$ then you can easily factor. So computing $d$ is hard if and only if factoring is hard.

To see why, let's say you have an oracle that upon input of $(e,n)$ gives an output of $d$. From this oracle we can construct an algorithm that efficiently factorizes $n$. Recall that $d \cdot e \equiv 1 \pmod {\varphi(n)}$, or in other words $d$ and $e$ are multiplicative inverses of each other mod $\varphi(n)$. Observe the following:

Let $^x//_y$ denote the remainder when you divide $x$ by $y$, or in other words $^x//_y = x - \lfloor \frac{x}{y}\rfloor \cdot y$. Similarly, let the multiplicative inverse of $x$ mod $y$ be denoted by $^{x^{-1}}//\;_y$.

For any $a,b \in \mathbb{N}$ such that $1>a>b$ and $gcd(a,b) = 1$, $$(^{a^{-1}}//\;_b) = \dfrac{(^{-b^{-1}}//\:_a)\cdot b - a + 1}{a}+1 \tag{1}$$ Proof of (1):
$a$ is coprime to $b$, so it has a multiplicative inverse. The multiplicative inverse of $a$ mod $b$ is i) a natural number less than $b$ which ii) when multiplied by $a$ is congruent to 1 mod $b$. If we multiply the right side of (1) by $a$ we get the following: $$\left(\dfrac{(^{-b^{-1}}//\:_a)\cdot b - a + 1}{a}+1\right) \cdot a \:= (^{-b^{-1}}//\:_a)\cdot b - a + 1 + a \:\:\equiv 1 \pmod b$$ So we can complete the proof by showing that the right side of (1) is a natural number less than $b$. First let's show that it is less than $b$ through proof by contradiction. Assuming the opposite: $$\begin{align*}\dfrac{(^{-b^{-1}}//\:_a)\cdot b - a + 1}{a}+1 &> b \\ (^{-b^{-1}}//\:_a)\cdot b - a + 1 &> a \cdot b - a \\ (^{-b^{-1}}//\:_a)\cdot b +1 &> a \cdot b \\ 1 &> b \cdot (a - (^{-b^{-1}}//\:_a))\end{align*}$$ Recall that $b > 1$ and that $(^{-b^{-1}}//\:_a)$ is by definition smaller than $a$. So $a - (^{-b^{-1}}//\:_a) \geq 1$, and we have our contradiction.

Second we can show that the right hand side of (1) is a natural number by showing that $(^{-b^{-1}}//\:_a)\cdot b - a + 1$ is divisible by $a$. Note that $-b^{-1} \cdot b \equiv -1 \pmod a$, so $(^{-b^{-1}}//\:_a)\cdot b$ is one less than a multiple of $a$. Adding one and subtracting $a$ from one less than a multiple of $a$ will result in something that is divisible by $a$. $$\tag*{QED}$$ As a consequence, if our oracle gives us $d$ given $e$, then we can use (1) to express $\varphi(n)$ in terms of $d$ and $e$: $$\begin{align*}d = \;^{e^{-1}}//\:_{\varphi(n)} \; &= \dfrac{(^{-\varphi(n)^{-1}}//\:_e)\cdot \varphi(n) - e + 1}{e}+1 \\ (d -1) \cdot e -1 + e &= (^{-\varphi(n)^{-1}}//\:_e)\cdot \varphi(n) \\ \tag{2}\end{align*}$$ Now, select a different number, $e'$, and submit that to the oracle to get $d'$, the multiplicative inverse of $e'$. Substituting $e'$ and $d'$ into (2) and we get $(^{-\varphi(n)^{-1}}//\:_{e'})\cdot \varphi(n)$. If $gcd\left((^{-\varphi(n)^{-1}}//\:_{e}), (^{-\varphi(n)^{-1}}//\:_{e'})\right) = 1$, then we can then use the Euclidean Algorithm to pull out the common factor $\varphi(n)$. We may need to repeat this process with a few different numbers submitted to the oracle to be sure we have settled on $\varphi(n)$ and not a multiple of $\varphi(n)$. Once you know $\varphi(n)$., you can easily find the prime factors of $n$.

$\endgroup$
  • 2
    $\begingroup$ Please note though: while finding the private exponent is equivalent to factoring the modulus, breaking the RSA problem (eg finding the e-th root modulo a composite) is not proven to be equivalent to factoring but may be easier. $\endgroup$ – SEJPM Jul 17 '16 at 9:46

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.