0
$\begingroup$

I'm reading about RSA and I have doubts:

1) To choose $e$, this value have to be between $1$ and $\phi=(p-1)(q-1)$, with $\gcd(\phi, e) = 1$, right?

2) In my example, $p = 139$ and $q = 491$. So $n = 68249$ and $\phi = 67620$. Assuming my point 1 is correct, $e$ can be $67619$. But $d$ can be $67619$ too, because $67619^2 \equiv 1 \mod 67620$.

Is this reasoning incorrect?

$\endgroup$
5
$\begingroup$

1) To choose $e$, this value have to be between $1$ and $\phi=(p-1)(q-1)$, with $\gcd(\phi, e) = 1$, right?

No; $e$ can be any value that's relatively prime to both $p-1$ and $q-1$ (or equivalently, relatively prime to $\operatorname{lcm}(p-1, q-1)$). There may be little point in choosing an $e$ larger than $n$; however there's no specific reason it wouldn't work.

2) [Paraphrased] What if I pick an $e$ with $e^2 = 1 \bmod (p-1)(q-1)$; and set $d = e$. Would it work?

Well, yes, it would work, in the sense that the protocol will encrypt and decrypt messages just fine. It wouldn't work in the sense that it wouldn't be secure (even if you used more realistic sizes of $p$ and $q$).

$\endgroup$
  • $\begingroup$ mdc = gdc. I see it here: doc.sagemath.org/html/en/thematic_tutorials/numtheory_rsa.html. "$e$ have to be a positive number that $gdc(e, phi) = 1$". Is not right? $\endgroup$ – eightShirt May 21 '16 at 23:46
  • $\begingroup$ @poncho: Relatively prime to both $p-1$ and $q-1$ (or equivalently, relatively prime to $\operatorname{lcm}(p-1,q-1)$). $\endgroup$ – user94293 May 21 '16 at 23:49
  • $\begingroup$ @user94293: "relatively prime to $lcm(p-1,q-1)$" is yet another equivalent way of stating it. $\endgroup$ – poncho May 22 '16 at 0:23
  • 1
    $\begingroup$ @eightShirt: technically, negative values of $e$ could be made to work (as you can compute the inverse without knowing the factorization); of course, there's absolutely no reason to do this... $\endgroup$ – poncho May 22 '16 at 0:24
  • $\begingroup$ @poncho: Thanks. Just one more question: can I say 'between $1$ and $phi$ I will always have a valid candidate to be $e$' [not just here]? Why that explanation that "$e$ have to be a coprime between $1$ and $phi$" are in so many places? :-( $\endgroup$ – eightShirt May 22 '16 at 0:42
1
$\begingroup$

Yes, math behind this work. But it seems that you are asking, can both public and private exponent be the same value? Answer is no, because you jeopardize the whole system. By choosing equal exponents, you create two identical keys. And if some eavesdropper steals public key, he can decrypt message.

$\endgroup$
0
$\begingroup$

Let $e\ne 1,-1$ be the public exponent such that $e^2=1 \pmod {\phi(N)}$, so we have:

$$(e-1)\cdot (e+1)=0 \pmod {\phi(N)}$$

then we can compute $\phi(N)$ and factor $N$.

$\endgroup$

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.