This is a previous exam paper question, as follows:
Alice has a private key (d = 47, n = 1147) and a public key (e = 23, n = 1147). Bob wishes to send the message M = 3 to Alice. Perform the calculation Bob would do to encrypt this message for Alice.
How to encrypt using RSA?
$$ D = M^e \pmod n = 3^{23} \pmod {1147} $$
By performing a direct calculation (or some RSA online calculator) as above:
$$ D = M^e \pmod{n} = 3^{23} \pmod {1147} = 724 $$
How to decrypt using RSA?
$$ M = D^d \pmod{1147} = 724^{47}\pmod {1147} = 3 $$
Unfortunately, when using efficient modular exponentiation or squaring method, I get a different result.
23 in binary is
10111or16 + 4 + 2 + 1
Modular exponentiation for 23:
$ 23^1 \pmod{1147} = 23 $
$ 23^2 \pmod{1147} = 529 $
$ 23^4 \pmod{1147}= 529^2 \pmod{1147} = 1120 $
$ 23^8 \pmod{1147}= 1120^2 \pmod{1147} = 729 $
$ 23^{16} \pmod{1147}= 729^2 \pmod{1147} = 380 $
We then compute:
$$ 3^{23}(mod 1147) = (380 * 1120 * 529 * 23) $$
As follows:
- $ 380 \cdot 1120 \pmod {1147} = 63 $
- $ 63 \cdot 529 \pmod {1147} = 64 $
- $ 64 \cdot 23 \pmod {1147} = 325 $
Then our encrypted message equals:
$$ D = M^e \pmod {n} = 3^{23} \pmod {1147} = 325 $$
Which is incorrect:
$$ 325 \neq 724 $$
When using the inverse process for decryption, it also gives me the wrong result, i.e. not the original message.
Is there any other way to do this that I am not aware of or that I haven't learnt in class (module ended last term) that will always hold the correct result?
If yes, why the formula above yields the incorrect result?
When squaring, why are you taking powers of $23$? You want powers of $3$. $$3^{23} = 3^{16} \cdot 3^{4} \cdot 3^{2} \cdot 3^{1} \text{.} $$
\begin{align*} 3^1 &\cong 3 \pmod{1147} \\ 3^2 &\cong 9 \pmod{1147} \\ 3^4 &\cong 81 \pmod{1147} \\ 3^8 &\cong 826 \pmod{1147} \\ 3^{16} &\cong 958 \pmod{1147} \text{ and } \\ 3^{23} &\cong 958 \cdot 81 \cdot 9 \cdot 3 \cong 724 \pmod{1147} \text{.} \end{align*}