Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent) 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:  


Why does this happen?  
Is this even a problem?  
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.
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.


  
  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.


  
  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 &lt; e &lt; \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.