0
$\begingroup$

The theory for right to left modulus exponential technique is very straight forward if the explanation is using a small modulus n number. For example,

$$3^{77} \bmod 11$$

In this example, we know that the remainder will be always less than 11 which the maximum remainder in this case will be 10. Hence, when we are implementing the square across right-to-left binary bits, the biggest square operation will be 10 and followed by modulus 11 & so-on

However, if we are applying this in the RSA formula. For example,

$$S^e \bmod n$$

where $n$ is the product of $p \times q$ and it can be up to 4000 over bits. Regardless of the value of $e$, using the right-to-left technique, the sub-step anyhow will involve the square of the remainder. In this case, does it mean worst case we will have 4000 bits x 4000 bits, and it will yield 8000 bits result & followed by the modulus $n$ operation. (This doesn't sound make sense to me, of course, there is also a high chance I don't 100% understand this technique)

I apologize if the question sounds silly to you. But I like to get more idea of how to practically apply this technique into the real world RSA implementation. The right-to-left technique looks like only help in the big exponential side, but there is still a big modulus number portion to be resolved which I still couldn't make sense where the most internal source is more focusing on the exponential side.

Appreciate it if you can enlighten me.

Improve this question
$\endgroup$
9
  • $\begingroup$ Any square to $\bmod 11$ is at most 100, the $3^{77} = 5474401089420219382077155933569751763$ does it make sense now! $\endgroup$
    – kelalaka
    Commented Dec 4, 2020 at 15:42
  • $\begingroup$ @kelalaka, I understand the simple example given by me where the square to mod11 is at most 100. I'm more referring when apply the same technique to the RSA formula, where the n can be up to 4096 bits. so the square for the remainder in this case will be super huge.... $\endgroup$
    – Pi-Turn
    Commented Dec 4, 2020 at 15:46
  • 2
    $\begingroup$ Not super huge, just double in the size of the bits that we can live with it. Can you devise a new method without square-then-mod and multiply-then-mod? $\endgroup$
    – kelalaka
    Commented Dec 4, 2020 at 15:50
  • $\begingroup$ @kelalaka, I'm sorry, I don't get what you mean on the second sentence. could you please elaborate more? $\endgroup$
    – Pi-Turn
    Commented Dec 4, 2020 at 16:00
  • 1
    $\begingroup$ "This doesn't sound make sense to me" - why? What's so weird (or scary) with a 8000 bit long multiplication result in your opinion? Computers have no problem handling such numbers. The 'mod n' operation will reduce it back to 4000 bits, so things never grow longer than 8000 bits. Maybe you should elaborate in your question on why exactly you find this making little sense... $\endgroup$
    – tum_
    Commented Dec 4, 2020 at 18:54

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.