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 xe,∀x, i.e. by minimizing the number of multiplications, to save execution time.
Indeed, to calculate X8, we can :
The gap widens very quickly, between the naive method and the more advanced methods. Thus, to compute X1024, one needs to
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 is a classical technique, used in practice, to obtain the power of a given number.
This fast exponentiation iterates, for the calculation of Xe, the following operations:
in an order depending on the base 2 entry of e.
It is well understood in its recursive version :
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...
15 is written 1111 in base 2.
The previous algorithm results in the word SXSX. The steps of the calculation are then :
res = X | X | |
S | res = res * res | X2 |
X | res = res * X | X3 |
S | res = res * res | X6 |
X | res = res * X | X7 |
S | res = res * res | X14 |
X | res = res * X | X15 |
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.
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 X19 in 6 multiplications.
Make a function that performs fast exponentiation in a pyboard.
Finally, let's note that fast exponentiation doesn't always give the fastest method. For example, to compute X15, we could have proceeded like this :
a1=X | X |
a2=a1∗a1 | X2 |
a3=a2∗a1 | X3 |
a4=a3∗a3 | X6 |
a5=a4∗a3 | X9 |
a6=a4∗a4 | X15 |
Then 5 multiplications for X15, instead of 6 by the method called fast exponentiation. A better exponentiation list for X15 is: 1, 2, 3, 6, 9, 15. More efficient techniques exist, such as the addition strings detailed on another page of this wiki.