4
$\begingroup$

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)}$]

$\endgroup$
  • $\begingroup$ $e=d\Rightarrow e^2\equiv 1 \pmod{\varphi(n)}$. Can you solve this equation? (given the factorization of $\varphi(n)$?) $\endgroup$ – SEJPM May 8 '16 at 10:57
  • $\begingroup$ I have no idea how to haha. What do you mean by "factorisation of φ(n)"? $\endgroup$ – ColonCapsDee May 8 '16 at 11:07
  • $\begingroup$ "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$ $\endgroup$ – poncho May 8 '16 at 11:40
  • $\begingroup$ Ah yes, prime factorisation, but how would this help me? IM fairly new to all this. $\endgroup$ – ColonCapsDee May 8 '16 at 12:05
  • 1
    $\begingroup$ You can always use $e = \varphi(n) - 1$. $\endgroup$ – Aleph May 8 '16 at 12:53
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM May 8 '16 at 13:55
  • $\begingroup$ 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$. $\endgroup$ – Aleph May 8 '16 at 17:01
  • $\begingroup$ @Aleph It's a community wiki answer so feel free to make any edits you see fitting and improving it. $\endgroup$ – SEJPM May 8 '16 at 21:57
1
$\begingroup$

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.

$\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.