How can I decrypt the ciphertext?

Question

In RSA, how do I calculate $c^d \bmod n$ to decrypt a ciphertext $c$?

Suppose that: $$ n= 120781\\ e=3\\ d=90043\\ c=38191 $$

How can I work this out by hand or with a basic calculator so that I can see the steps?

Answer 1

Exponentiation by Squaring is one of the most efficient methods. I will give a simple example: $$3^{22}\equiv 3^{16}*3^4*3^2 \mod 51$$ $$3^2\equiv 9 \mod 51$$ $$3^4\equiv (3^2)^2 \equiv 9^2\equiv 81\equiv 30\mod 51$$ $$3^{16}\equiv((3^4)^2)^2\equiv(30^2)^2\equiv900^2\equiv33^2\equiv1089\equiv18\mod51$$ $$(18)*(30)*(9)\equiv18*(270)\equiv18*15\equiv270\equiv15\mod51$$

Another trick you can use is Montgomery Reduction. What you do is convert the numbers into a different form in which it is easier to multiply and divide and then convert the result back.

Answer 2

Using the repeated squaring as mentioned in the other post: $38191^{90043} \equiv 38191 \cdot(38191^2)^{45021}$. (all modulo $n$ of course) We can compute the square of $38191$ (modulo $n$) as 1125. So we need $1125^{45021}$ which equals $1125 \cdot (1125^2)^{22510}$. Then $1125^2 = 57815$ modulo $n$ again. So we are reduced to finding $(57815)^{22510} = (57815^2)^{11255}$ modulo $n$ and $(57815^2) \equiv 80831$. So to proceed, we need $80831^{11255}$ where $80831^2\equiv 2366$, so this equals, in turn, $80831 \cdot 2366^{5627}$ modulo $n$. Continue this way and backsubstute your results. This way we compute the power just using squares modulo $n$ and some extra multiplications modulo $n$. Using python (which has built-in modular powers) I checked that the end result should be $45559$.