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$

3 Answers 3

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$
6
  • $\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
    Commented May 21, 2016 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
    Commented May 21, 2016 at 23:49
  • $\begingroup$ @user94293: "relatively prime to $lcm(p-1,q-1)$" is yet another equivalent way of stating it. $\endgroup$
    – poncho
    Commented May 22, 2016 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
    Commented May 22, 2016 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
    Commented May 22, 2016 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 and acknowledge you have read our privacy policy.

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