How to decrypt using CRT, and then verify by encrypting without CRT?

Here is the actual question that I need to answer:

An RSA encryption scheme has the set-up parameters $$p = 31$$ and $$q = 37$$. The public exponent is $$e = 17$$.

1. Decrypt the ciphertext $$y = 2$$ using the CRT.

2. Verify your result by encrypting the plaintext without using the CRT.

I have figured out the answer for the first part: $$x = 721 \bmod 1147$$, but I am unsure how to encrypt it. I know that using RSA would mean: $$y = e_{kpub}(x) \equiv x^e \mod n$$, where $$x,y \in \mathbb{Z}_n$$, so it should be as easy as $$721^{17} \bmod 1147$$, but this is a huge number that I cannot work with. I am pretty sure that I should use the square and multiply algorithm, but I don't understand how, and my textbook is not clarifying.

I know that $$x^{17}$$ means #MUL + #SQ= 5, but what do I do with this information? The textbook does not describe this well.

I could really use some help!

• Is your question how to use the square and multiply algorithm to compute $721^{17}\bmod 1147$?
– Mark
Mar 8 '20 at 0:42
• Basically, I think that is what I need to do, but I am not sure.
– CEL
Mar 8 '20 at 1:06
• Handbook of Applied Cryptography now is a free book that contains examples. See page 71 in chapter 2 Mar 8 '20 at 18:26

The square and multiply algorithm allows you to compute $$g^k$$ in an arbitrary group using $$O(\log k)$$ multiplications, instead of the $$O(k)$$ you would expect. This is done by letting: $$k = \sum_{i = 0}^{\lceil \log_2 k\rceil} 2^i k_i,\quad k_i\in\{0,1\}$$ To be the base-2 decomposition of $$k$$. Then, we have that: $$g^k = g^{\sum_{i = 0}^{\lceil\log_2 k\rceil}2^ik_i} = \prod_{\substack{0\leq i \leq \lceil\log_2 k\rceil\\k_i = 1}} g^{2^i}$$ I'll demonstrate the computation for your particular case, where we want to compute $$721^{17}\bmod 1147$$. Note that for modular arithmetic, we additionally have Euler's Theorem to work with, which states that: $$x^{\varphi(N)}\equiv 1\bmod N$$ Where $$\varphi(N)$$ is Euler's totient function. Using basic properties of $$\varphi$$, one can compute that $$\varphi(31\times 37) = 30\times 36 = 1080$$. So throughout our computations, we have the identity $$x^{1080}\equiv 1\bmod 1147$$ (which unfortunately ends up not being useful).
One can compute by hand that $$721^2 = 519841$$, which we can then reduce mod $$1147$$ to get $$721^2\bmod 1147 = 250$$. We can repeat this to find that $$250^2 = 62500$$, which we reduce mod $$1147$$ to get 562. We square this again to get 315844, which we reduce mod 1147 to get 419. Finally, we square this again to get 175561, which we reduce mod 1147 to get 70.
Collecting together these computations, we get: \begin{align} 721^{2^0} &= 721 \mod 1147\\ 721^{2^1} &= 250 \mod 1147\\ 721^{2^2} &= 562 \mod 1147\\ 721^{2^3} &= 419 \mod 1147\\ 721^{2^4} &= 70 \mod 1147. \end{align} Note that $$17$$ decomposes base 2 as $$1 + 16 = 2^0 + 2^4$$. We can then find the result via: $$721^{2^0}\times 721^{2^4} = 721\times 70\mod 1147 = 50470 \mod 1147 = 2\mod 1147$$
You may look at this and think it still involved a ton of multiplications of three digit numbers. This is true --- this is the group operation in $$(\mathbb{Z}/1147\mathbb{Z})^*$$, so one expects to have to do it a number of times. You can count to see that we only used 5 multiplications, instead of the 16 one would naively expect. It's still not great to do by hand though, but the only way I know of making the computations better by hand is by using the Chinese remainder theorem, which you specifically don't want to be used.