2
$\begingroup$

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 = 128343(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).enter image description here

The pseudocode:

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

enter image description here

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. 887 mod 187 = [(884 mod 187) * (882 mod 187) * (881 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 = 7560(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.

enter image description here

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. 1123 mod 187 = [(111 mod 187) * (112 mod 187) * (114 mod 187) * (118 mod 187) * (118 mod 187)] mod 187

$\endgroup$
5
  • 1
    $\begingroup$ Hint: 7=4+2+1 where 4, 2, 1 are powers of two. 343 is 256+64+16+4+2+1 where 256, 64, 16, 4, 2, 1 are powers two. The powers of two present for $d$ can be found by considering if $d$ is odd or even (telling if 1 is present or absent), and considering the powers of two present in $\left\lfloor d/2\right\rfloor$ (that is $d$ divided by 2, rounded down). $\endgroup$
    – fgrieu
    Nov 10, 2022 at 12:09
  • $\begingroup$ @fgrieu I tried this method but wasn't successful. I started from 1 and when up like 1+2+4+8+16+32+64+128+256=511, which is wrong. Also, I did times by 2, not by power of 2, which is also wrong. Might explain the massive failure. Thanks for the hint. $\endgroup$
    – Mote Zart
    Nov 10, 2022 at 15:46
  • $\begingroup$ @MoteZart your observation that this is about two tasks is correct. First one must turn the exponent into its binary representation, then one uses that to calculate the modular exponentiation. The way you apply the algorithm seems correct - the first three columns of the table are fine, and $7^{560} \bmod 561$ is indeed equal to $1$. $\endgroup$
    – Morrolan
    Dec 13, 2022 at 10:52
  • $\begingroup$ @MoteZart regarding 'breaking up' the exponent: Decomposing $23$ into powers of two would yield $23 = 16 + 4 + 2 + 1$. To do this you'd find the largest power of two less than (or equal) to the exponent, subtract it from the exponent, and repeat until you reach $0$. These correspond to the iterations of the loop where the algorithm calculates $f = (f \times a) \bmod n$. But this is 'only' the mathematician's point of view to explain why the algorithm works. The algorithm as written requires the binary representation of the exponent. $\endgroup$
    – Morrolan
    Dec 13, 2022 at 10:59
  • $\begingroup$ @MoteZart I've added a section about this alternative method to decompose the exponent into its binary representation to my answer below, does this clear it up? $\endgroup$
    – Morrolan
    Dec 13, 2022 at 11:10

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks for explaining this. After I get the binary though, how can I use it break down the exponent? There is a table here, but I don't know what it means gacbe.ac.in/images/E%20books/… I agree this isn't the best way to do it, but I should know how to deal with this type of number. $\endgroup$
    – Mote Zart
    Nov 10, 2022 at 15:50
  • $\begingroup$ @MoteZart once you have the binary expansion, you can simply follow the algorithm you posted in your question, or one of the ones shown on Wikipedia. The $b_i$ in the loop corresponds to the i-th bit of the exponent. $\endgroup$
    – Morrolan
    Nov 11, 2022 at 10:31
  • $\begingroup$ (Where $b_k$ is the highest-order bit, and $b_0$ the lowest-order bit of the exponent) $\endgroup$
    – Morrolan
    Nov 11, 2022 at 10:40
  • $\begingroup$ I still don’t have an answer to my original question. I still don’t get it. I’ve done it like in the textbook, using the algorithm, and I have a set of f values but I don’t know what do with these. If I am supposed to use the binary values like U’ve shown above I cannot see how. I’ve tried variations of multiplication and adding. I do not end up with the same value doing this as my original exponent. $\endgroup$
    – Mote Zart
    Dec 10, 2022 at 21:00
  • 1
    $\begingroup$ Thanks for your patience. I updated the question to ask specifically what I mean. $\endgroup$
    – Mote Zart
    Dec 12, 2022 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.