6
$\begingroup$

How do you encrypt $51$ with public key $(n,e) = (91,23)$

I understand that $c = 51^{23} \bmod 91$. How can I calculate the result on a calculator?

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Standard calculators cannot do that because $15^{23}$ is too big for a calculator to store. Computers use special algorithms to combine the exponentiation and the modulus in one calcuation step thus avoiding having to calculate $m^e$. If you get hands on a scientific calcuator that allows custom programs to be written on it, you can implement such an algorithm. $\endgroup$ – marstato Dec 28 '15 at 20:04
  • $\begingroup$ @marstato is there a way where i can simplify the problem to be able to compute it on a calculator. Thanks $\endgroup$ – James Dec 28 '15 at 20:29
  • $\begingroup$ As said: there are algorithms. Google for mod pow operation. But you dont want to type these out on your small calculator. Use sth. like this: javascripter.net/math/calculators/100digitbigintcalculator.htm $\endgroup$ – marstato Dec 28 '15 at 20:41
  • 1
    $\begingroup$ @otus It's still about cryptography though, and I think the question will pop up again if we close it anyways. There are currently three upvotes and three downvotes. I suggest we keep it as it is obviously disputed, and I think we should leave disputed questions be disputed but open. $\endgroup$ – Maarten Bodewes♦ Dec 29 '15 at 12:09
  • $\begingroup$ I've edited the question to change $(n,e)=(23,91)$ to $(n,e)=(91,23)$ as $n<e$ made no sense and $n\in\mathbb P$ also made no sense. I think this was intended by the OP as he used $c=51^{23}\bmod 91$ using $n=91$ and $e=23$. $\endgroup$ – SEJPM♦ Dec 29 '15 at 12:36
7
$\begingroup$

If your calculator is able to compute $n^2$, you can compute $m^e \bmod n$ using the binary exponential method.

In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$.

Now, with the algorithm below, you can compute $c$:

$z:=1$
$\text{for } i:= \ell \text{ down to } 0 \text{ do:}$
$\quad z:=z^2 \bmod n$
$\quad \text{if } e_i = 1 \text{ then } z:=(z \cdot m) \bmod n$
$\text{end for}$
$\text{return } z$

| improve this answer | |
$\endgroup$
  • $\begingroup$ As described, except for $e=0$, and since $\ell$ is the number of bits in $e$, it holds that $e_\ell=0$, and $e_{\ell-1}=1$. The algorithm always performs one more loop than there are bits in $e$, and at the end of the second loop $z=m$ always holds. It follows the algorithm is best changed to$$\begin{align}&z:=m\\&\text{for } i:= \ell-2 \text{ down to } 0 \text{ do:}\\&\quad z:=z^2 \bmod n\\&\quad\text{if }e_i=1\text{ then }z:=(z\cdot m)\bmod n\\&\text{end for}\\&\text{return }z\end{align}$$ $\endgroup$ – fgrieu♦ Jun 28 '17 at 18:22

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.