4
$\begingroup$

In RSA, suppose we know that $e=N$ and we are given the value of $e$. ($N = p\cdot q$ for some large primes $p$ and $q$; $\gcd(e, \varphi(N) = 1)$

Can we calculate $d$ ($d = e^{-1} \mod \varphi(N)$) without factoring $N$?

$\endgroup$
  • $\begingroup$ I wouldn't think so as in RSA you always know $e$, and you always know that $gcd(e,\varphi(N))=1$ $\endgroup$ – mikeazo Dec 1 '11 at 2:16
  • $\begingroup$ But here we have more information that N = e. we know that φ(N) = (p-1)(q-1) and N=pq. So far I have N = p+q-1 mod φ(N) and wonder if we can find a d such that dN = 1 mod (p-1)(q-1) .. Actually the specific question is that given the value of e and e=N along with the message m, compute the RSA signature of m. But RSA signature of m requires that we know d... $\endgroup$ – Jake Dec 1 '11 at 3:36
  • 1
    $\begingroup$ @Jake: We have no proof that computing an RSA signature requires knowledge of $d$, even after adding: mod LCM($p-1$,$q-1$). That is even clearly wrong for very weak padding schemes and selected messages (and for weak padding schemes still in practical use, under the assumption that we can obtain the RSA signature of other messages). $\endgroup$ – fgrieu Dec 1 '11 at 5:35
5
$\begingroup$

No, $e=N$ is no less secure than any other value of $e>1$.

In fact, we can make a stronger statement; if setting $e=N$ allows us to compute the corresponding $d = N^{-1} \mod \phi(N)$, then we can factor $N$ (and hence we can find the $d$ corresponding to any $e$). This is due to the fact that knowledge of any nontrivial pair $(d,e)$ with $d \cdot e = 1 \mod \phi(N)$ allows us to efficiently find the factorization of $N$.

We don't use $e=N$, not because of security reasons, but because of efficiency. Setting $e=N$ makes the public key operation (encryption, signature verification) far more expensive than it would be if we set $e$ to a small value; given that a large $e$ typically would have no advantage to make up for that, we generally don't use large $e$.

Historical note: when Clifford Cox initially devised his varient of RSA (which wasn't declassified until well after RSA was published), he actually had $e = N$.

$\endgroup$
  • 4
    $\begingroup$ What follows "we can make a stronger statement" is not a proof of the preceding assertion, and is a lesser statement IMHO. The reasoning made for $e=N$ (that finding one of the corresponding $d$ allows factorization of $N$, hence breaking RSA for any $e$) works just as well for any $e$, and thus gives no indication that $e=N$ is any more or less secure than any other choice of $e$. It does not rule out in any way that the RSA problem (as opposed to the factorization problem) might be easier for $e=N$ than for a random $e$. $\endgroup$ – fgrieu Dec 1 '11 at 5:09

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.