# RSA: Given $n$ and $\varphi(n)$, find $e$ such that $e=d$

Say we have chosen $n=pq$, with $p=89,q=97 \implies n=8633$ and $\varphi(n)=88\times96=8448$. Also, if we want the encoding ($e$) and decoding ($d$) exponents to be equal, we need $$(e,8448)=1 \: \: \text{(relatively prime),}$$ $$ed \equiv 1 \pmod{8448} \implies e^2 \equiv 1 \pmod{8448}.$$

How do I go about solving something like this? My first inclination is that $(e,8448)=1$ means that $e$ must be prime, but I'm really not sure.

• You are looking for the square roots of 1; finding modular square roots is a well-studied problem. – fkraiem May 2 '17 at 12:10
• By the way, I assume you want to find a non-trivial solution, i.e., not 1 or -1... – fkraiem May 2 '17 at 12:14
• Yes, I need a non-trivial solution @fkraiem – George Wilson May 2 '17 at 12:15
• The question is ambiguous; is it wanted $e$ such that $d=e$ is a valid decryption exponent, or is it wanted $e$ such that $e^2\equiv1\pmod{\varphi(N)}$ ? In the former case, we only need $e^2\equiv1\pmod{\lambda(N)}$ where $\lambda$ is the Carmichael function, and $e=65$ works. In the later case, the lowest $e>1$ that works is $e=769$. – fgrieu May 3 '17 at 10:09

If you know the factorization of $\phi(n)$, this can be done like this:
The factorization gives you various prime powers as factors of $\phi(n)$, let's call those $p_i^{e_i}$. Then:
• For each $p_i^{e_i}$ with $p_i>2$, the roots of the polynomial $x^2 - 1 = 0 \mod p_i^{e_i}$ are $1$ and $p_i^{e_i}-1$ and there are no other roots. This can be proven by using Hensel lifting for the two roots of the polynomial $x^2-1 \mod p_i$.
• For powers of $2$, Hensel lifting the polynomial $x^2-1$ also gives you solutions, but it's more complicated if you want to find all of them, because $f'(r)=2r$ will be $0$ for some root $r$. If you want to find just one, then just use $x=1 \mod 2^x$, where $x$ is the power of $2$ in the factorization of $\phi(n)$. Edit: As an example, every odd number is a square root of $1$ modulo $8$, and modulo $16$ the square roots of $1$ are $\{1,7,9,15\}$.
• For each prime power you have a set of two roots $r_1$ and $r_2$ (in a formal prove, you should have indices for the prime powers as well). Choose for each prime power either $x=r_1 \mod p_i^{e_i}$ or $x=r_2 \mod p_i^{e_i}$. If you don't want the trivial solutions $1$ and $-1$, make sure to avoid the 'all $1$' and 'all $p_i^{e_i}-1$' roots.
• Use Chinese remainder theorem to assemble the solution $x \mod \phi(n)$
Edit: In the question you only wanted square roots of $1$, which is either $1$ or $-1$ mod any prime $p$. More generally, if you want to find square roots of arbitrary elements, there are also algorithms for that, e.g. Tonelli-Shanks, which work for any prime $p$. Hensel lifting then gives you the roots in the prime powers (but you need to adapt the polynomial), and then assemble the solution via CRT.
Edit: Of course the choice $e=d$ makes the RSA cryptosystem with public key $(N,e)$ completely unsafe - the value of $e$ is public and you have to assume by Kerckhoff's principle that the attacker knows your system, in this case that you use such a defining equation.