3
$\begingroup$

If an RSA encryption uses a modulus $n$ of 15000 bits and $e = 3$ or $e = 2^{16} + 1$, how many squarings and multiplications will we need for encryption, and for decryption? Could you please explain the concept of square and multiply as well?

I'm thinking the number of squarings is going to be equal to the number of $e$, and that the number of multiplications will be roughly half of the number of $e$, but how does the number of $n$ bits factor into that?

Also, why is it different for encryption and decryption? I thought encryption is $m^e \bmod n$, and decryption is $m^d \bmod n$, so what does the length of $e$ have to do with decryption?

|improve this question
$\endgroup$
  • $\begingroup$ You may look here for a simple explanation of square and multiply. Essentially, every $1$ in the binary expansion of the exponent costs an additional multiplication (squaring is in every of the log rounds), thats why $e=2^{16}+1$ is "sexy". $\endgroup$ – DrLecter Oct 16 '13 at 10:11
  • $\begingroup$ The second point is that if you fix $e$ and compute $d$ using extended euclidian algorithm, it is likely that the size of $d$ is the size of $n$ and you cannot control how $d$ looks. Thats why exponentiation with $d$ is far more costly. $\endgroup$ – DrLecter Oct 16 '13 at 10:18
  • 1
    $\begingroup$ The sequence of words "the number of $e$" does not make sense, but appears twice in the question. Also, you can raise to the power 3 with just one squaring and one multiplication, as $x^3= x^2\cdot x$. $\endgroup$ – fgrieu Oct 16 '13 at 10:45
  • $\begingroup$ @DrLecter I understand the second part, but that 'simple' explanation just looked a lot like lots of complicated squiggles... The mathematics of this escape me. I certainly have never seen anything as complicated as that in our lecture slides, which frankly, don't explain much of anything. $\endgroup$ – kathleenie.xx Oct 16 '13 at 11:48
2
$\begingroup$

After reading the comments on your original post, I thought I'd give you an example for exponentiating by $e$. Take for example the case $e=2^{16}+1$. Then, to calculate $x^e$ we use $16$ squaring operations and one multiply. This is because $$x^{2^{16}+1}=x \cdot x^{2^{16}} = x\cdot x^{\underbrace{2\cdot 2 \cdots 2}} =x\cdot ((x^2)^2)\cdots)^ 2$$ (where the brace contains sixteen $2$'s).

So, we use repeated squaring to calculate $x^{2^{16}}$, then having done so can simply multiply by $x$ once to find $x^e$.

If we think about the binary expansion of $e$, this techinque can be generalised to give [relatively] efficient exponentiation to any power. For example, how to we take an element to the power $e=41$? Well, first writing $e$ in terms of powers of two (ie in binary), we see that $e=32+8+1=2^5+2^3+2^0$ and thus $e=101001$. So, to evaluate this we simply initialise our answer as $1$ and set $y=x$ ($y$ will store $x^{2^i}$ as $i$ increases), then work from right to left along the binary expansion of $e$. If the digit is $1$, then we multiply by $y$. Then, we square $y$ and move on to the next digit.

The reason $e$ is chosen to be a value like $2^{16}+1$ or $3=2^1+1$ are that they each only require one multiplication. Looking back at my rather poor explanation above, we see that we have to square $x$ for each 'place' in the binary expansion of $e$, and we have to multiply our running value once for each $1$ in the binary expansion of $e$. So, if $e$ is $n$ bits long (ie $n=\lfloor\log_2(e)\rfloor+1$) we require $n-1$ squaring oparations and at most $n$ multiplications (or $n-1$ if we start our multiplication with the first value power of $x$ encountered rather than initialising with $1$ as in my example).

As mentioned by other comments, it is hard to know how many multiplications/squarings will be required to decrypt, since to do so requires knowing the binary expansion of $d$. That said, we can be pretty confident that $d$ is very unlikely to have anywhere near as nicer expansion as $e$ did with these choices, suggesting decrypting will require rather more work than encryption.

|improve this answer
$\endgroup$
  • $\begingroup$ So if my understanding is correct... if $e = 2^{16} + 1$ , we will have 16 squarings and 1 multiplication. but, if $e = 3$ and that is equivalent to $2^1 + 1$ (like you've indicated?) then for $e = 3$ we have 1 squaring and 1 multiplication? $\endgroup$ – kathleenie.xx Oct 16 '13 at 12:25
  • $\begingroup$ ps: the description of d (decryption) makes perfect sense. thanks :D $\endgroup$ – kathleenie.xx Oct 16 '13 at 12:25
  • $\begingroup$ Yep, 3=2^1+1, so we'd only have to square once, and multiply once. $\endgroup$ – figlesquidge Oct 16 '13 at 12:29
  • $\begingroup$ so if $e$ were to be another value, say... $4$. how would that add up? would we have to find the binary representation of it? square for each place, multiply by the running value? what would that gives us for something like $4$? $\endgroup$ – kathleenie.xx Oct 16 '13 at 12:32
  • 2
    $\begingroup$ For RSA, e can not be 4. It can not be a multiple of 4 either (because $\Phi(n)$ is a multiple of 4 and e has to be coprime). Regardless, if you express a number in binary, you simple count the $1$s and $0$s. The "sum (aka length)- 1" is the number of squaring. And the number of ($1$s - 1)is the number of multiplications. For a random $e$, this results in less than $\log_{2} e $ squaring operations and at most the same number of multiplications. $\endgroup$ – tylo Oct 16 '13 at 12:51

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.