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

54 Views Asked by At

The modulus, $n=8633$, is given (it's simple to find $p$ and $q$ such that $n=pq$, i.e. $p=89$ and $q=97$) and the task is to find an encoding exponent, $e$, such that the correpsonding decoding exponent, $d$, is equal to $e$.

As $n=89 \times 97$, $\varphi(n)=88 \times 96 = 8448$. Also, if we require $e=d$, we need $$\text{gcf}(e,8448)=1$$ and $$ed \equiv 1 \pmod{8448} \implies e^2 \equiv 1 \pmod{8448}.$$ How would I go about solving a problem like this?

1

There are 1 best solutions below

1
On

So $e^2\equiv 1(\textrm{mod}\quad 89)$ and $e^2\equiv 1(\textrm{mod}\quad 97)$. This tell us that $e\equiv\pm 1(\textrm{mod}\quad 89)$ and similarly $e\equiv\pm 1(\textrm{mod}\quad 97)$. Take a nontrivial pair, (for example, $e\equiv-1(\textrm{mod}\quad 89)$ and $e\equiv 1(\textrm{mod}\quad 97)$) and use Chinese remainder theorem to work out the congruence modulo $89\times 97$.