216
12 Cryptocurrencies
Fig. 12.7 Addition on elliptic curves over a finite field with p = 113 and generator point G =
(13, 31) on the left and G = (15, 52) on the right
set of number P = {1, . . . , p − 1} by some arbitrary integer k, thus {k, . . . , k( p −
1)}(mod p), results in the same set P albeit with the order of the numbers scrambled.
Most operations, such as addition and multiplication are well-defined when using
modular arithmetic; only divisions, used in the calculation of the slope in (12.32),
require special attention. We can, however, calculate the inverse of a number in a finite
field by exploiting Fermat’s little theorem, which states that for any number a the
equation a
p−1
= 1(mod p) is valid. Rewriting it as a
−1
= a
−1 1 = a
−1 a
p−1
= a
p−2
where all equations are understood modulo p, we find
a
−1
= a
p−2
(mod p) ,
(12.34)
which provides us with a method to calculate the inverse of a number a in a finite
field and allows us to calculate the divisions in (12.32).
We use the MATLAB scripts from Appendix B.11 to iterate (12.32) and (12.33)
over a finite field with p = 113 which leads to the plots shown in Fig. 12.7. On the
left-hand side, the starting position, indicated as a red asterisk, is G = (13, 31); on
the right-hand side it is G = (15, 52). Here we denote the starting point by the letter
G to signify that it is the generator of the group of dots, which show the traversed
points. They are scattered all over the admissible range between 0 and p − 1 = 112.
We observe that there are many more points on the on the left-hand plot than on the
right-hand plot. As a matter of fact, the points repeat after a number of additions; on
the left-hand side there are n = 114 distinct points and on the right-hand side there
are only n = 19 distinct points, including one point at infinity. It turns out that the
“addition” of points on the curve imposes the structure of a group G G on the points,
which are the elements of G G . The point at infinity serves as a “zero” of the group.
Note that the group depends on the starting point G. Moreover, the number of distinct
elements n is called the order of the group. In order to be useful for cryptograpy n
must be a prime number. It is the number of distinct ciphertexts that can be encoded
in this scheme. The elements in G G are indeed a group because it is then possible
to reach an element B of the group from any other element A by adding G a finite
number j of times, which we denote by B = A ⊕ ( j G).
12 Cryptocurrencies
Fig. 12.7 Addition on elliptic curves over a finite field with p = 113 and generator point G =
(13, 31) on the left and G = (15, 52) on the right
set of number P = {1, . . . , p − 1} by some arbitrary integer k, thus {k, . . . , k( p −
1)}(mod p), results in the same set P albeit with the order of the numbers scrambled.
Most operations, such as addition and multiplication are well-defined when using
modular arithmetic; only divisions, used in the calculation of the slope in (12.32),
require special attention. We can, however, calculate the inverse of a number in a finite
field by exploiting Fermat’s little theorem, which states that for any number a the
equation a
p−1
= 1(mod p) is valid. Rewriting it as a
−1
= a
−1 1 = a
−1 a
p−1
= a
p−2
where all equations are understood modulo p, we find
a
−1
= a
p−2
(mod p) ,
(12.34)
which provides us with a method to calculate the inverse of a number a in a finite
field and allows us to calculate the divisions in (12.32).
We use the MATLAB scripts from Appendix B.11 to iterate (12.32) and (12.33)
over a finite field with p = 113 which leads to the plots shown in Fig. 12.7. On the
left-hand side, the starting position, indicated as a red asterisk, is G = (13, 31); on
the right-hand side it is G = (15, 52). Here we denote the starting point by the letter
G to signify that it is the generator of the group of dots, which show the traversed
points. They are scattered all over the admissible range between 0 and p − 1 = 112.
We observe that there are many more points on the on the left-hand plot than on the
right-hand plot. As a matter of fact, the points repeat after a number of additions; on
the left-hand side there are n = 114 distinct points and on the right-hand side there
are only n = 19 distinct points, including one point at infinity. It turns out that the
“addition” of points on the curve imposes the structure of a group G G on the points,
which are the elements of G G . The point at infinity serves as a “zero” of the group.
Note that the group depends on the starting point G. Moreover, the number of distinct
elements n is called the order of the group. In order to be useful for cryptograpy n
must be a prime number. It is the number of distinct ciphertexts that can be encoded
in this scheme. The elements in G G are indeed a group because it is then possible
to reach an element B of the group from any other element A by adding G a finite
number j of times, which we denote by B = A ⊕ ( j G).