Cryptography Reference
In-Depth Information
Example 9.8. We consider the ECDH with the following domain parameters. The
elliptic curve is y 2
x 3 + 2 x + 2 mod 17, which forms a cyclic group of order # E =
19. The base point is P =(5 , 1). The protocol proceeds as follows:
Alice
Bob
choose a = k pr , A = 3
choose b = k pr , B = 10
A = k pub , A = 3 P =(10 , 6)
B = k pub , B = 10 P =(7 , 11)
A
−−−−−−−−−−−−−−→
B
←−−−−−−−−−−−−−−
T AB = aB = 3 (7 , 11)=(13 , 10) T AB = bA = 10 (10 , 6)=(13 , 10)
The two scalar multiplications that each Alice and Bob perform require the Double-
and-Add algorithm.
One of the coordinates of the joint secret T AB can now be used as session key. In
practice, often the x -coordinate is hashed and then used as a symmetric key. Typ-
ically, not all bits are needed. For instance, in a 160-bit ECC scheme, hashing the
x -coordinate with SHA-1 results in a 160-bit output of which only 128 would be
used as an AES key.
Please note that elliptic curves are not restricted to the DHKE. In fact, almost all
other discrete logarithm protocols, in particular digital signatures and encryption,
e.g., variants of Elgamal, can also be realized. The widely used elliptic curve digital
signature algorithms (ECDSA) will be introduced in Sect. 10.5.1.
9.4 Security
The reason we use elliptic curves is that the ECDLP has very good one-way char-
acteristics. If an attacker Oscar wants to break the ECDH, he has the following
information: E , p , P , A , and B . He wants to compute the joint secret between Alice
and Bob T AB = a
P . This is called the elliptic curve Diffie-Hellman problem
(ECDHP). There appears to be only one way to compute the ECDHP, namely to
solve either of the discrete logarithm problems:
·
b
·
a = log P A
or
b = log P B
If the elliptic curve is chosen with care, the best known attacks against the
ECDLP are considerably weaker than the best algorithms for solving the DL prob-
lem modulo p , and the best factoring algorithms which are used for RSA attacks.
In particular, the index-calculus algorithms, which are powerful attacks against the
DLP modulo p , are not applicable against elliptic curves. For carefully selected el-
liptic curves, the only remaining attacks are generic DL algorithms, that is Shanks'
baby-step giant-step method and Pollard's rho method, which were described in
Sect. 8.3.3. Since the number of steps required for such an attack is roughly equal
Search WWH ::




Custom Search