3
$\begingroup$

Given the following RSA generated public key: $P(3, 55)$. Which integer value should be chosen for $d$ to decrypt messages encrypted with $P$?
Check your answer with $M = 8$ and $C = 17$.

$P(3,55)$ is $p(e,n)$

So through trial and error i have got $d = 7$ but how do you calculate this the proper way?

To check this we can use the encryption formulas:
$p(M) = M^e \bmod n $
so $ p(8) = 8^3 \bmod 55 = 17 = c\\ s(c)= c^d \bmod n \\ s(17)=17^d \bmod 55 = M = 8$

so basically we have $17^d \bmod 55=8$

Now how do we find out $d$ from that equation other than trial and error, which was how I found $d=7$

$\endgroup$
2
$\begingroup$

Because we (as decrypters) know that $55=5\times 11$, we also know that Carmichael's function $\lambda(55) =\text{lcm}(\phi(5), \phi(11)) = \text{lcm}(4,10) = 20$

So we need to find the multiplicative inverse of $3 \bmod 20$, that number $b$ such that $3b \equiv 1 \bmod 20$, which is obvious enough by inspection for these small numbers $(3\times 7 = 21)$ but otherwise can be found by the extended Euclidean algorithm, which I explain here.

$$\begin{array}{c|c|c|c} \large{n}\atop{ = ms+at} & \color{gray}{s} & t & q \\ \hline 20 & \color{gray}{1} & 0 & \\ 3 & \color{gray}{0} & 1 & 6 \\ 2 & \color{gray}{1} & -6 & 1 \\ 1 & \color{gray}{-1} & \color{red}{7} & 2 \\ \end{array}$$ and $3^{-1} \equiv \color{red}7 \bmod 20$. $\quad 3\times 7 = 21 \equiv 1 \bmod 20 \quad \checkmark$

And when we have that, that gives us $(8^3)^7=8^{21} = 8^{k\lambda(55)+1} \equiv 8^1 \bmod 55$, so decrypting the message.

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