Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 3 down vote favorite

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$?

share|improve this question
I wouldn't think so as in RSA you always know $e$, and you always know that $gcd(e,\varphi(N))=1$ – mikeazo♦ Dec 1 '11 at 2:16
But here we have more information that N = e. we know that φ(N) = (p-1)(q-1) and N=p*q. So far I have N = p+q-1 mod φ(N) and wonder if we can find a d such that d*N = 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... – Jake Dec 1 '11 at 3:36
1  
@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). – fgrieu Dec 1 '11 at 5:35

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
2  
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$. – fgrieu Dec 1 '11 at 5:09
thanks for both of you! – Jake Dec 1 '11 at 5:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.