0
$\begingroup$

I am following the book "Network security private communication in a public world - 2nd edition. Section 6.3.4.1 Exponentiating big numbers.

base = 123, exponent = 54, mod = 678

What I understand is that, first I need to convert 54 into binary, i.e. 110110. Then I should do (base^exponent)%mod only at those exponent where the exponent bits are set. For example:

123^2 = 123 * 123 = 15129 % 678 = 213

123^4 = (123^2)*(123^2) = (213^2) mod 678 = 621

123^16 = (123^4)(123^4)(123^4)*(123^4) = (621*621*621*621) mod 678 = 219

123^32 = (123^16)*(123^16) mod 678 = 501

If I do this, I am not getting the right answer which is (87). Can someone point out my mistake and help me understand the scenario.

$\endgroup$
3
  • $\begingroup$ Your last result is $123^{32}\bmod 678$ just as you wrote. But you want $123^{54}\bmod 678$. Hint: use that $2+4+16+32=54$ to combine your results appropriately. Next time: you actually want to compute $123^{16}\bmod 678$ just like the others, so that intermediary values in the computation of $123^{8}\bmod 678$ are smaller. Note: what you are doing is often called right-to-left binary modular exponentiation (not left-to-right as I wrongly stated before). $\endgroup$
    – fgrieu
    Feb 1 '20 at 16:32
  • $\begingroup$ The 'bignum' modular exponentiation algorithm works for any numbers, but RSA requires the modulus be squarefree and contain no small factors, or equivalently be the product of two or a few distinct primes each greater than 2, and 678 does not meet those criteria. $\endgroup$ Feb 2 '20 at 5:12
  • $\begingroup$ @dave_thompson_85 You are right for RSA, of course. But on the other hand, it doesn't matter for this question, since no inversion is involved at all. It is just about how to do exponentiation modulo some number. The tag RSA and the mentioning in the title should probably be removed. $\endgroup$
    – tylo
    Feb 2 '20 at 13:51
0
$\begingroup$

The basic algorithm is square and optionally multiply. start with 1 as your accumulator and then for each bit of exponent from MSB to LSB you square your result and if the bit is set multiply by base and appy modulus after each operation. For any leading zeros you are just squaring 1 which doesn't do anything, just like we want. Then after the first set bit you get your base. After a 10 for example you get your base squared and so forth.

Edit: following fgrieu's comment I will add a second Right to Left method. When looking at the exponent in binary we see it is the sum of powers of 2, and the result of the exponentiation is the product of the exponent by these powers. The resulting algorithm is:

  1. Initialize acc=1, power=base //123
  2. For each bit b from right to left do:

    2.1. If bit is set: acc = acc * power % mod

    2.2. power = power * power % mod

result is in acc

$\endgroup$
4
  • $\begingroup$ I wrongly wrote that the OP is doing left-to-right binary exponentiation (raising to the powers 1, 2=1+1, 3=2+1, 6=3+3, 12=6+6, 13=12+1, 26=13+13, 27=26+1, 54=27+27); when the intermediary results show that the OP goes right-to-left (with intermediary results the powers 1, 2=1+1, 4=2+2, 6=4+2, 8=4+4, 16=8+8, 22=16+6, 32=16+16, 54=32+12). Your answer seems to describe the left-to-right way, and that could be my fault. $\endgroup$
    – fgrieu
    Feb 1 '20 at 10:45
  • $\begingroup$ @Meir Maor, Thank you for your reply, I a bit confuse. Can you give me an example of the algorithm please? I am confused because the MSB of (110110) is 32. Then how should I het 54? $\endgroup$
    – Nusrat
    Feb 2 '20 at 1:47
  • $\begingroup$ 1^2=1 top bit is set so multiply by base we get 123. 123^2 = 213 next bit is set multiply 213*123 = 435. 435^2 = 63, next bit isn't set leave as is. That is how we process the top 3 bits in your example 110. continue all the way and get the answer. $\endgroup$
    – Meir Maor
    Feb 2 '20 at 4:53
  • 1
    $\begingroup$ Thank you for helping @Meir Maor. I have accepted your answer $\endgroup$
    – Nusrat
    Feb 2 '20 at 17:28

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.