# RSA: select $e$ given $n$ and $\varphi(n)$

I have a question for a course I am doing. In an RSA question, it asks "Is it possible to select $e$ in such a way that it coincides with the corresponding private key $d$? If it is possible, provide a value for such an $e$.

So, this is only part of the question (last part really).

$$n = 22499$$ $$\varphi(n) = 22200$$

How would I go about this? I am completley lost. I have, by luck come across an answer of $149$. $149^2 = 1 \pmod{22200}$. This is because $ed = 1 \pmod{\varphi(n)}$. Is there a method to calculate such a number? [$a^x = 1 \pmod{\varphi(n)}$]

• $e=d\Rightarrow e^2\equiv 1 \pmod{\varphi(n)}$. Can you solve this equation? (given the factorization of $\varphi(n)$?) Commented May 8, 2016 at 10:57
• I have no idea how to haha. What do you mean by "factorisation of φ(n)"? Commented May 8, 2016 at 11:07
• "The factorization of $\phi(n)$"; $\phi(n)$ is an integer; the factorization of an integer is the (multi)set of primes that, when multiplied together, form that integer. For example, the factorization of $22200 = 2 \times 2 \times 2 \times 3 \times 5 \times 5 \times 37$ Commented May 8, 2016 at 11:40
• Ah yes, prime factorisation, but how would this help me? IM fairly new to all this. Commented May 8, 2016 at 12:05
• You can always use $e = \varphi(n) - 1$. Commented May 8, 2016 at 12:53

There are four different solutions, of which three have been identified as the "trivial solutions" in the comments to this question.

1. $e=d=1$ which is obviously fullfilling the condition that $1\cdot 1\equiv 1 \pmod{\varphi(n)}$ should hold.

2. $e=d=\varphi(n)-1$ which is fullfilling the condition that $(\varphi(n)-1)^2\equiv 1 \pmod{\varphi(n)}$ as $(\varphi(n)-1)^2=((\varphi(n))^2-2\varphi(n)+1) \bmod{\varphi(n)}=1$

3. $e=d=\sqrt{\varphi(n)+1}$ (if integer) which is also obviosuly true as $\sqrt{\varphi(n)+1}^2=(\varphi(n)+1)\bmod{\varphi(n)}=1$, this is the solution you stumbled across.

4. Use a full modular square root finding algorithm as documented as algorithm 3.44 in the Handbook of Applied Cryptography on page 102. (PDF version) However this requires you to know the prime factorization of $\varphi(n)$ which may be infeasible to obtain for sufficiently large $n$.

• I've posted this answer as a community wiki, as I do not feel my contribution to answering this question was large enough to warrent any reputation gains, especially since I only could bring the trivial solutions: "look the algorithm up" and "1" in. Commented May 8, 2016 at 13:55
• I would rephrase "four different solutions" as "four different approaches" or something, because it could be (incorrectly) interpreted as meaning that there are four solutions for $e$. Commented May 8, 2016 at 17:01
• @Aleph It's a community wiki answer so feel free to make any edits you see fitting and improving it. Commented May 8, 2016 at 21:57

Factoring $\varphi(n) = 22200$, we get $22200 = 2^3 \cdot 3 \cdot 5^2 \cdot 37$. The condition $d = e$ implies $e^2 \equiv 1 \pmod{\varphi(n)}$. In turn, this yields $e \equiv \{\pm 1,\pm 3\} \pmod{2^3}$, $e \equiv \pm 1 \pmod{3}$, $e \equiv \pm 1 \pmod{5^2}$, and $e \equiv \pm 1 \pmod {37}$. All possible solutions are then obtained through Chinese remaindering. There are $4\cdot 2\cdot 2\cdot 2 = 32$ solutions: 1, 149, 1849, 1999, 3551, 3701, 5401, 5549, 5551, 5699, 7399, 7549, 9101, 9251, 10951, 11099, 11101, 11249, 12949, 13099, 14651, 14801, 16501, 16649, 16651, 16799, 18499, 18649, 20201, 20351, 22051, 22199.