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

Improve this question
$\endgroup$
10
  • $\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, 2016 at 10:57
  • $\begingroup$ I have no idea how to haha. What do you mean by "factorisation of φ(n)"? $\endgroup$
    – ColonCapsDee
    May 8, 2016 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, 2016 at 11:40
  • $\begingroup$ Ah yes, prime factorisation, but how would this help me? IM fairly new to all this. $\endgroup$
    – ColonCapsDee
    May 8, 2016 at 12:05
  • 1
    $\begingroup$ You can always use $e = \varphi(n) - 1$. $\endgroup$
    – Aleph
    May 8, 2016 at 12:53

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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, 2016 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, 2016 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, 2016 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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