12.7 Elliptic Curve Cryptography
217
Now Alice and Bob can use elliptic curves to determine a shared secret S that is
practically impossible to find out by Eve. This method is called elliptic curve DiffieHellman (ECDH). Alice and Bob agree on an elliptic curve with parameters a and
b, a finite field of prime order p, and a generator point G. Alice chooses a private key
d A and Bob chooses d B and both publish their respective public keys P A = d A G
and P B = d B G, which are two points on the curve. Alice then calculates S A =
d A P B = (d A d B ) G and Bob calculates S B = d B P A = (d B d A ) G, where
all calculations are performed modulo n. We see that they arrive at the same secret
S = S A = S B which they can use to encrypt subsequent communication with, for
example, AES.
But elliptic curves can also be used to sign documents, for example, the hash value
h of message m? This method is called the elliptic curve digital signature algorithm
(ECDSA). Given the curve parameters a and b, the starting point G, and the order
of the group n, Alice chooses her secret, the private key d. Then she calculates a
point P = d G on the curve. This is her public key, which she makes publicly
known. Knowing a point P on the curve, it is practically impossible to determine
how many iterations d are needed to get there from the generator G, which ensures
the security of the system. In order to sign the hash h, she picks a random number k in
the range from 1 to n − 1, which determines another point R = k G on the curve.
We stress that k must be truly random, and, in particular, must not be reused in a
second transaction, which would make it possible to determine the private key d. The
horizontal coordinate r (mod n) of the point R = (r, ·) is one part of the signature.
The second part of the signature s is constructed from the hash h, the private key d,
the random value k, and coordinate r by calculating s = (h + rd)/k(mod n). Alice
then transmits the message m and the signature (r, s) to Bob.
Bob verifies the signature by calculating the hash h of m using the same hashing
function as Alice. Using h and the signature (r, s), he then calculates Q = (h/s)
G + (r/s) P(mod n). Let us determine what he should find, if the signature is
valid
Q =
h
s
G +
r
s
P =
h
s
G +
rd
s
G =
h + rd
(h + rd)/k
G = kG = R ,
(12.35)
where all calculations are performed modulo n and we omitted the . In the second
equality we used P = d G and in the third we inserted the definition of the signature s. We find that the signature is valid, if the horizontal coordinate of Q is the same
as the horizontal coordinate of R, which is r . Note that the purpose of constructing
the signature (r, s) in such a convoluted way is to make reverse-engineering the private key practically impossible, while making the validation through the calculation
of Q rather easy.
In this way Alice can send messages m to Bob and he can verify that they actually
came from her, and nobody else. Also, once a message is signed, any changes to
m will invalidate the old signature, and we have to sign again. This is one of the
key feature that prevents falsifying the records in the database of transactions in the
bitcoin infrastructure.
217
Now Alice and Bob can use elliptic curves to determine a shared secret S that is
practically impossible to find out by Eve. This method is called elliptic curve DiffieHellman (ECDH). Alice and Bob agree on an elliptic curve with parameters a and
b, a finite field of prime order p, and a generator point G. Alice chooses a private key
d A and Bob chooses d B and both publish their respective public keys P A = d A G
and P B = d B G, which are two points on the curve. Alice then calculates S A =
d A P B = (d A d B ) G and Bob calculates S B = d B P A = (d B d A ) G, where
all calculations are performed modulo n. We see that they arrive at the same secret
S = S A = S B which they can use to encrypt subsequent communication with, for
example, AES.
But elliptic curves can also be used to sign documents, for example, the hash value
h of message m? This method is called the elliptic curve digital signature algorithm
(ECDSA). Given the curve parameters a and b, the starting point G, and the order
of the group n, Alice chooses her secret, the private key d. Then she calculates a
point P = d G on the curve. This is her public key, which she makes publicly
known. Knowing a point P on the curve, it is practically impossible to determine
how many iterations d are needed to get there from the generator G, which ensures
the security of the system. In order to sign the hash h, she picks a random number k in
the range from 1 to n − 1, which determines another point R = k G on the curve.
We stress that k must be truly random, and, in particular, must not be reused in a
second transaction, which would make it possible to determine the private key d. The
horizontal coordinate r (mod n) of the point R = (r, ·) is one part of the signature.
The second part of the signature s is constructed from the hash h, the private key d,
the random value k, and coordinate r by calculating s = (h + rd)/k(mod n). Alice
then transmits the message m and the signature (r, s) to Bob.
Bob verifies the signature by calculating the hash h of m using the same hashing
function as Alice. Using h and the signature (r, s), he then calculates Q = (h/s)
G + (r/s) P(mod n). Let us determine what he should find, if the signature is
valid
Q =
h
s
G +
r
s
P =
h
s
G +
rd
s
G =
h + rd
(h + rd)/k
G = kG = R ,
(12.35)
where all calculations are performed modulo n and we omitted the . In the second
equality we used P = d G and in the third we inserted the definition of the signature s. We find that the signature is valid, if the horizontal coordinate of Q is the same
as the horizontal coordinate of R, which is r . Note that the purpose of constructing
the signature (r, s) in such a convoluted way is to make reverse-engineering the private key practically impossible, while making the validation through the calculation
of Q rather easy.
In this way Alice can send messages m to Bob and he can verify that they actually
came from her, and nobody else. Also, once a message is signed, any changes to
m will invalidate the old signature, and we have to sign again. This is one of the
key feature that prevents falsifying the records in the database of transactions in the
bitcoin infrastructure.