2
$\begingroup$

I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically.

Let's say $p=11$, $q=13$ $$N=p \cdot q=11 \cdot 13=143$$ I chose $e$ to be relatively prime to $(p-1)(q-1)$, $e=23$ So the public key is $(23,143)$

Now I want to find out $d$ and for that I've come across $2$ different methods. First is using this formula $$23 \cdot d \equiv1 \mod120$$ where I can't seem to work out what $d$ is. I tried to solve it like a quadratic equation $$23x=1 \mod 120$$ $$x=\frac {1}{23}$$ which doesn't make sense. Then I came across this other method to find the value of $d$.

$$∃k : e \cdot d +k(p-1)(q-1) \equiv1$$ $$23 \cdot (47) + (-9)\cdot120=1$$ So the private key would be $(47,143)$ but there is no mention of how they figured out the value of $d$ and $k$. That's why I need some help to work out the value of $d$ in a way so that I can find it given any problem.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Extended_Euclidean_algorithm $\endgroup$ – xskxzr Mar 22 '18 at 3:15
  • $\begingroup$ @xskxzr Answer the question with this information? $\endgroup$ – Yuval Filmus Mar 22 '18 at 8:36
  • $\begingroup$ @YuvalFilmus I think a link-only answer is not acceptable and describing this algorithm is a bit tedious. You can write an answer if you like. $\endgroup$ – xskxzr Mar 22 '18 at 9:33
1
$\begingroup$

Suppose that you know $e$ and $n$, and want to find out $d$ such that $ed \equiv 1 \pmod{n}$ (this is possible if $(n,e) = 1$). An efficient way to do this is to use the extended Euclidean algorithm, which finds two integers $a,b$ such that $an + be = (n,e) = 1$. You can use $d = b \bmod{n}$, since $de \equiv be \equiv 1-an \equiv 1 \pmod{n}$.

Improve this answer
$\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.