Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent)

Question

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.

Answer 1

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.

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