# 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:

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.

• Define problem. Do you ask whether the algorithm may fail or whether this may be insecure? – SEJPM Jun 4 '16 at 18:21
• @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. – iamogbz Jun 4 '16 at 20:52

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.

• 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? – iamogbz Jun 4 '16 at 20:55
• 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. – poncho Jun 4 '16 at 21:04
• Of course because all primes > 2 are odd. Thanks again, duh moment. – iamogbz Jun 4 '16 at 21:10
• @IamOgbz: actually, for any $N>2$, we have $\phi(N)$ even... – poncho Jun 4 '16 at 21:16
• 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. – iamogbz Jun 4 '16 at 21:37