0

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?

Jaja 1
  • 1

2 Answers2

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.

AlgorithmsX
  • 4,560
  • thnx, but my example has larger numbers. Is mine possible to solve by hand? – Jaja 1 Oct 25 '16 at 23:21
  • You should do somewhere around $16$ squarings of these numbers, find the remainder about $16$ times, and then do at most $16$ multiplications. I'm getting the $16$ from $\log_2 90043$. Plus, you might get lucky and get some small numbers. You might also be able to use some Montgomery Reductions, which I completely forgot about when writing my answer. – AlgorithmsX Oct 25 '16 at 23:45
0

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

Henno Brandsma
  • 242,131