Objectives

Various operations in cryptography require the calculation of a multiple or a power: for example, as we will see, the way to encrypt and decrypt for the RSA, and a cryptographically secure pseudo-random number generator such as the BBS boils down to iterating a power calculation modulo $p$. These operations must therefore be able to be done efficiently, especially since the objects considered here (wireless sensors) are low-powered and battery-powered.

Also, given an exponent $e$, we want to calculate here as efficiently as possible $x^e, \forall x$, i.e. by minimizing the number of multiplications, to save execution time.

Indeed, to calculate $X^8$, we can :

• Calculate $X \times X \times ... \times X$, which makes 7 multiplications. The list of calculated exponents is: 1, 2, 3, 4, 5, 6, 7, 8.
• Calculate :
  • $Y = X \times X$, which corresponds to $X^2$,
  • then $Z = Y \times Y$, which corresponds to $X^4$,
  • finally $T = Z \times Z$, which gives the result.

The gap widens very quickly, between the naive method and the more advanced methods. Thus, to compute $X^{1024}$, one needs to

• 1023 multiplications, for the naive method,
• 10 multiplications for the fast exponentiation method.

When we know that in the RSA method, in order to encrypt the plain text, we must raise our message (a number) to the power "a large prime number" (including: an exponent of several hundred digits), we understand the interest of shortening the calculation time of a power.

Fast exponentiation

Presentation

Fast exponentiation is a classical technique, used in practice, to obtain the power of a given number.

This fast exponentiation iterates, for the calculation of $X^e$, the following operations:

• the square elevation,
• multiplication by $X$,

in an order depending on the base 2 entry of $e$.

It is well understood in its recursive version :

• if $e$ is even, we calculate (recursively) $X^{e/2}$, which we multiply by itself,
• otherwise, we calculate (recursively) $X^{e-1}$, which we multiply by $X$.

The algorithm

As the above technique is recursive, its implementation in a sensor may be problematic. But as the operations to be done are determined by the parity of the number following a division by 2, or has a division by 2 after a deletion of 1, we deduce that the binary writing of the number contains exactly the operations to be done.

More precisely...

• We write $e$ in base 2,
• We remove the first 1 of this writing,
• One replaces then, in this writing,
  • the 0 by $S$,
  • the 1 by $SX$,

• We start from the number $X$.
  • if the first letter is $S$, we raise to the square
  • otherwise, multiply by $X$.
• Start again with the following letters, until the end of the word.

Examples

First example

15 is written 1111 in base 2.

The previous algorithm results in the word $SXSX$. The steps of the calculation are then :

The last result (res) thus contains the power sought, in only 6 operations (compared to 14 in the naive method).

The list of exponents is here: 1, 2, 3, 6, 7, 14, 15.

Second example

19 is written 10011 in base 2, which provides the word $SSSXSX$.

After work, the list of exponents is here: 1, 2, 4, 8, 9, 18, 19.

We could therefore calculate $X^{19}$ in 6 multiplications.

Practical work

Make a function that performs fast exponentiation in a pyboard.

The best exponentiation ?

Finally, let's note that fast exponentiation doesn't always give the fastest method. For example, to compute $X^{15}$, we could have proceeded like this :

Then 5 multiplications for $X^{15}$, instead of 6 by the method called fast exponentiation. A better exponentiation list for $X^{15}$ is: 1, 2, 3, 6, 9, 15. More efficient techniques exist, such as the addition strings detailed on another page of this wiki.