214
12 Cryptocurrencies
First we select the two primes p, q and the encryption key e and then calculate n and
ϕ(n) before solving Bézout’s equation to find the decrypton key d, while the next
line ensures that d is positive. After the call to gcd() we display an error message
if e is not coprime to ϕ(n). In the last three lines we first define a message, encode
it, and decode it again. Here we use the powermod() function which works well
for moderately large values of e and d. We emphasize that the system is secure as
long as Eve cannot factor n into its prime factors.
These built-in functions work well for moderately-sized integers, but in practice
and in order to prevent factorization of n into the underlying primes p and q, the
numbers typically have more than a hundred digits, which requires special functions to handle the arithmetic. These large-integer routines are often not very fast,
which is a limiting factor on mobile devices, such as smartphones. Therefore, other
algorithms are desired, which use smaller integers, yet provide equal or improved
security compared to the original RSA algorithm.
12.7 Elliptic Curve Cryptography
Although already proposed in the 1980s for efficient cryptographic applications,
elliptic curves only became popular in the past two decades. This method is based
on mapping two points A and B that lie on an elliptic curve, which is given by
y
2
= x
3
+ ax + b
(12.30)
onto a third point C = A ⊕ B. The left-hand side in Fig. 12.6 illustrates the construction. The elliptic curve secp256k1, which is used in the Bitcoin cryptocurrency and
defined by y
2
= x
3
+ 7, is shown as the black line. The two points A and B lie on the
curve and the straight line that connects them is extended until it intersects the curve
again, which defines the point C
. Reflecting C
on the horizontal axis intersects the
curve, which is symmetric, at point C = =C
where we define C to be the “negative”
of C
in an abstract sense and likewise C = A ⊕ B in an equally abstract sense. The
operations, denoted by and ⊕, describe how to find a new point, here C, from
some previously defined points. We emphasize that finding the third point on the
curve is almost always possible. A special case is given by the limiting case B → A
in which case two points that define the slope of the straight become the tangent to
the curve. Moreover, we need to artificially add a point ˆ
0 at infinity to the curve in
order to make the equation C C = ˆ
0 meaningful. The point at infinity thus takes
the role as a “zero.”
The mapping of two points A and B to the third one is easily found by calculating
the intersection of the elliptic curve from (12.30) and the straight line that passes
through points A and B. It is given by y = s(x − x A ) + y A and has slope s = (y B −
y A )/(x B − x A ). Equating the equations leads to
12 Cryptocurrencies
First we select the two primes p, q and the encryption key e and then calculate n and
ϕ(n) before solving Bézout’s equation to find the decrypton key d, while the next
line ensures that d is positive. After the call to gcd() we display an error message
if e is not coprime to ϕ(n). In the last three lines we first define a message, encode
it, and decode it again. Here we use the powermod() function which works well
for moderately large values of e and d. We emphasize that the system is secure as
long as Eve cannot factor n into its prime factors.
These built-in functions work well for moderately-sized integers, but in practice
and in order to prevent factorization of n into the underlying primes p and q, the
numbers typically have more than a hundred digits, which requires special functions to handle the arithmetic. These large-integer routines are often not very fast,
which is a limiting factor on mobile devices, such as smartphones. Therefore, other
algorithms are desired, which use smaller integers, yet provide equal or improved
security compared to the original RSA algorithm.
12.7 Elliptic Curve Cryptography
Although already proposed in the 1980s for efficient cryptographic applications,
elliptic curves only became popular in the past two decades. This method is based
on mapping two points A and B that lie on an elliptic curve, which is given by
y
2
= x
3
+ ax + b
(12.30)
onto a third point C = A ⊕ B. The left-hand side in Fig. 12.6 illustrates the construction. The elliptic curve secp256k1, which is used in the Bitcoin cryptocurrency and
defined by y
2
= x
3
+ 7, is shown as the black line. The two points A and B lie on the
curve and the straight line that connects them is extended until it intersects the curve
again, which defines the point C
. Reflecting C
on the horizontal axis intersects the
curve, which is symmetric, at point C = =C
where we define C to be the “negative”
of C
in an abstract sense and likewise C = A ⊕ B in an equally abstract sense. The
operations, denoted by and ⊕, describe how to find a new point, here C, from
some previously defined points. We emphasize that finding the third point on the
curve is almost always possible. A special case is given by the limiting case B → A
in which case two points that define the slope of the straight become the tangent to
the curve. Moreover, we need to artificially add a point ˆ
0 at infinity to the curve in
order to make the equation C C = ˆ
0 meaningful. The point at infinity thus takes
the role as a “zero.”
The mapping of two points A and B to the third one is easily found by calculating
the intersection of the elliptic curve from (12.30) and the straight line that passes
through points A and B. It is given by y = s(x − x A ) + y A and has slope s = (y B −
y A )/(x B − x A ). Equating the equations leads to