5
$\begingroup$

While reading on RSA's algorithm, I attempted a simplified implementation and noticed the following:

When choosing the public exponent $e$, if the value chosen is the first coprime after $φ(n)/2$ then the resulting public and private exponents are equal.

Example:
$p = 67\\q = 53\\n = 3551\\φ(n) = 3432$
$e = 1717$ i.e first coprime of 3432 greater than half
$d = 1717$ where $d \times e\ mod\ φ(n) = 1$
resulting in no encryption
$c(41) = 41^{1717}\ mod\ 3551 ≡ 41$

Problem might be in my code?

So I guess my questions are:

  1. Why does this happen?
  2. Is this even a problem?
  3. What am I missing?

Selecting only public exponents that are primes might eliminate the possibility of this occurring, but I have neither tested nor seen that it's a requirement in the RSA algorithm.

$\endgroup$
  • $\begingroup$ Define problem. Do you ask whether the algorithm may fail or whether this may be insecure? $\endgroup$ – SEJPM Jun 4 '16 at 18:21
  • $\begingroup$ @SEJPM the algorithm fails in the sense no encryption happens, which means it is not secure but only for instances where $e = ϕ(n)/2 + 1$. I just wanted to know if this was an intrinsic property of the algorithm or I was goofing somewhere, thanks. Ponco has cleared it up for me. $\endgroup$ – iamogbz Jun 4 '16 at 20:52
6
$\begingroup$

When choosing the public exponent $e$, if the value chosen is the first coprime after $\phi(n)/2$ then the resulting public and private exponents are equal.

Well, yeah, that'll always be true.

  1. Why does this happen?

We have $e=d$ whenever we have both of the following true:

$$e^2 \equiv 1 \pmod{p-1}$$

$$e^2 \equiv 1 \pmod{q-1}$$

Now, if $e = (p-1)(q-1)/2 + 1$ (which is always the first coprime after $\phi(n)/2$), then if we denote $k = (q-1)/2$ (which is an integer),

$e^2 = ((p-1)(q-1)/2 + 1)^2 = ((p-1) k + 1)^2 \equiv 1^2 = 1 \pmod{p-1}$

By symmetry, we also have $e^2 = 1 \pmod{q-1}$ as well, and so $e=d$ works in this case.

Furthermore, whenever we have both the following hold:

$$e \equiv 1 \pmod{p-1}$$ $$e \equiv 1 \pmod{q-1}$$

then we'll have $M^e \equiv M \pmod{N}$ (for all $M$), that is, the RSA operation will always give us the original plaintext. These are also both true in the case of $e = \phi(N)/2 + 1$, and so such an $e$ will also always have plaintext=ciphertext, which is what you observed.

  1. Is this even a problem?

If you intend to use $\phi(n)/2 + 1$ as your public exponent, yeah, that's a problem. Exposing such a value also makes $n$ easy to factor; however the attacker doesn't need to factor to break the system in this case.

However, if you use a more normal public exponent, say, 3 or 65537, it's pretty irrelevant.

Selecting only public exponents that are primes might eliminate the possibility of this occurring, but I have neither tested nor seen that it's a requirement in the RSA algorithm.

Well, what's most common for RSA implementations is to pick $e$ first (and it makes sense to pick it as a small value), and then select primes $p$ and $q$ such that $p-1$ and $q-1$ are relatively prime to $e$. If you do that, then $e=d$ cannot happen, because if $1 < e < \sqrt{p-1}$, then we trivially have $e^2 \not\equiv 1 \pmod{p-1}$.

However, even if you pick $e$ large (for whatever reason), as long as you do it randomly, then the probability that both $e^2 \equiv 1 \pmod{p-1}$ and $e^2 \equiv 1 \pmod{q-1}$ both hold is negligible.

$\endgroup$
  • $\begingroup$ Thanks this has cleared it up. Additionally is it correct to assume all totients of 2 primes results in a number divisible by 2. Is this a proven math fact? $\endgroup$ – iamogbz Jun 4 '16 at 20:55
  • 1
    $\begingroup$ For $p, q$ distinct prime, then $\phi(pq) = (p-1)(q-1)$. Given that at least one of $p, q$ is odd, then $(p-1)(q-1)$ will always be even. If $p=q$, then $\phi(pq) = p(p-1)$, and since one of $p, p-1$ will always be even, their product will always be even; so, yes, it's a (fairly trivally) proven fact. $\endgroup$ – poncho Jun 4 '16 at 21:04
  • $\begingroup$ Of course because all primes > 2 are odd. Thanks again, duh moment. $\endgroup$ – iamogbz Jun 4 '16 at 21:10
  • $\begingroup$ @IamOgbz: actually, for any $N>2$, we have $\phi(N)$ even... $\endgroup$ – poncho Jun 4 '16 at 21:16
  • $\begingroup$ yes, seen your edit. I was referring to the statement "even if primes $p, q$ are not distinct", as all primes > 2 are odd, $p-1$ would always be even. $\endgroup$ – iamogbz Jun 4 '16 at 21:37

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.