TL:DR I'm learning RSA. I've made it to the decryption stage but I don't know how to handle huge exponents. These are my values:

p = 17  
q = 31
e = 7
m = 2
n = 527
(n) = 480
de = 7(343) = 2401
d = 343
PU = {7, 527}
PK = {343, 527}
C = 128

So I'm unable to handle the processing of the decryption of Cipher text 128, without a calculator or tool. With a tool, I think the value is 2. How can I process this value? (edit: fixed mod typo below)

M = 128³⁴³(mod 480 527)

More Details

Solving using Special Algorithm

I've found a possible solution but can't understand the explanation.

The Stallings textbook mentions an algorithm that means converting d to binary. It provides pseudocode but next to no explanation, unless you consider this explanation enough (cuz I don't).

The pseudocode:

  a = C, b = d, f = given as 1 to start, c = given as 0 to start

Solving by Breaking Apart Exponent

(edit: I don't really understand this after all. If I did, I would understand how to perform on any number, large or small)

I do understand how to break up small exponents. It seems like this is an easier way to do it without all this processing, since I am doing this by hand. Is there anyway to extend this method to a number like 343? What is the process? It's not always as simple as doubling the power of 2.

i.e. 88⁷ mod 187 = [(88⁴ mod 187) * (88² mod 187) * (88¹ mod 187)] mod 187

Updating original post with more details:

I think I misunderstood what I was even asking. I seemed to be asking two questions unintentionally, since it is like this in my textbook. Each are separate, but since they perform the same action, I have not removed anything (i.e. to make the question simpler). I've just tried to make it more clear.

Part1: getting the overall solution

I think I understand this now, but just to confirm, for the problem

M = 7⁵⁶⁰(mod 561)

Running the binary value of 560 (1000110000) through that algorithm produces the table below, each cell relates to one binary digit (from the Stallings). Is the solution to M 1? If yes, then I think I get this idea now.

Part 2: Breaking up the exponents

This seems to be totally separate from just getting the answer using the algorithm. It seems nice since there is no need to convert to binary which is (for me anyway) quite error prone by hand.

But I don't understand how to do it.

Example: Why is exponent 8 repeated? How do you arrive at this breakdown? I see the exponents add up to 23 but how do you determine which values to use to get there? What if it was some other number like 103, or 243, etc?

i.e. 11²³ mod 187 = [(11¹ mod 187) * (11² mod 187) * (11⁴ mod 187) * (11⁸ mod 187) * (11⁸ mod 187)] mod 187

Exponentiation by squaring

The described algorithm is usually referred to as (modular) exponentiation by squaring. As you did correctly observe, this algorithm requires the binary representation $\sum b_i 2^i$ of your exponent $b$, e.g. $7 = (111)_2$. There are multiple ways to get this representation as a human, such as:

Decimal to binary

Divide by two, note remainders

The most basic way to convert from decimal to binary would be to repeatedly divide the number by $2$. The (inverse) order of the remainders then gives you the binary representation:

$$ \begin{align} 343 & = 2 \cdot 171 & + 1 \\ 171 & = 2 \cdot 85 & + 1 \\ 85 & = 2 \cdot 42 & + 1 \\ 42 & = 2 \cdot 21 & + 0 \\ 21 & = 2 \cdot 10 & + 1 \\ 10 & = 2 \cdot 5 & + 0 \\ 5 & = 2 \cdot 2 & + 1 \\ 2 & = 2 \cdot 1 & + 0 \\ 1 & = 2 \cdot 0 & + 1 \end{align} $$

Thus, $343 = (101010111)_2$.

Subtract powers of two, note down exponents

An arguably faster way, but which is limited to numbers up to where knows the powers of two by heart, is the following:

• Find the largest power of two, $2^k$, which is less than or equal to your exponent $b$
• Note down the $k$
• Subtract $2^k$ from $b$
• Repeat until $b = 0$

Then, the exponents $k$ indicate which bits of the binary representation are $1$.

As an example, again with 343: The largest power of two less than or equal to $343$ is $256 = 2^8$. Thus:

• $343 - 2^8 = 87$
• $87 - 2^6 = 23$
• $23 - 2^4 = 7$
• $7 - 2^2 = 3$
• $3 - 2^1 = 1$
• $1 - 2^0 = 0$

Thus $343 = 2^8 + 2^6 + 2^4 + 2^2 + 2^1 + 2^0$. So it contains the 0-th, 1st, 2nd, 4th, 6th and 8th powers of two, so its binary representation is: $$ (343)_{10} = (101010111)_2 $$

Applying the algorithm

Then, you can follow the algorithm you posted in your original question. $b_i$ in the loop corresponds to the $i$-th bit of the exponent, with $b_k$ being its highest-order, and $b_0$ its lowest-order bit.

Caveats

However, a few things should be noted.

Firstly, this is not exactly how a computer would do it - after all, it has access to the binary representation of numbers by default. You'll thus find other descriptions of the algorithm - such as the one by Knuth - which combine calculating the remainder modulo two to get the low-order bit, with a binary shift to divide by two.

Secondly I don't think there is a lot of value in performing RSA by hand for anything except toy-sized numbers. Any size of numbers you can work with (in a reasonable time) by hand will be way too small to offer any real security. These days, one wants to use a modulus $N$ of at least $2048$ bits, which also means that one's decryption exponent $d$ is going to be approximately that size.

Lastly there exist some other important (for real-world purposes) optimizations based on the CRT, an introduction to which you'll find e.g. on Wikipedia.