2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You are looking for the square roots of 1; finding modular square roots is a well-studied problem. $\endgroup$ – fkraiem May 2 '17 at 12:10
  • $\begingroup$ By the way, I assume you want to find a non-trivial solution, i.e., not 1 or -1... $\endgroup$ – fkraiem May 2 '17 at 12:14
  • $\begingroup$ Yes, I need a non-trivial solution @fkraiem $\endgroup$ – Will May 2 '17 at 12:15
  • $\begingroup$ 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$. $\endgroup$ – fgrieu May 3 '17 at 10:09
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.