Question

Alice and Bob setup an elliptic curve Diffie-Hellman key exchange protocol with thesame field, curveEand pointPas given in Problem 1.Suppose that Alice selected random numbera= 3and Bob selectedb= 4, show the stepsperformed by Alice and Bob to obtain their shared key. What isthe key?

Answer 1

Answer:

Elliptic Curve Cryptography (ECC) is an approach to public-key cryptography, based on the algebraic structure of elliptic curves over finite fields. ECC requires a smaller key as compared to non-ECC cryptography to provide equivalent security (a 256-bit ECC security have an equivalent security attained by 3072-bit RSA cryptography).

For a better understanding of Elliptic Curve Cryptography, it is very important to understand the basics of Elliptic Curve. An elliptic curve is a planar algebraic curve defined by an equation of the form

                                                  y² = x³ +ax+b        

where ‘a’ is the co-efficient of x and ‘b’ is the constant of the equation

The curve is non-singular; that is its graph has no cusps or self-intersections (when the characteristic of the co-efficient field is equal to 2 or 3).

Elliptic curves could intersect atmost 3 points when a straight line is drawn intersecting the curve. As we can see that elliptic curve is symmetric about the x-axis, this property plays a key role in the algorithm.

                                                   Diffie-Hellman algorithm

The Diffie-Hellman algorithm is being used to establish a shared secret that can be used for secret
communications while exchanging data over a public network using the elliptic curve to generate points and get the secret key using the parameters.

• For the sake of simplicity and practical implementation of the algorithm, we will consider only 4 variables one prime P and G (a primitive root of P) and two private values a and b.
• P and G are both publicly available numbers. Users (say Alice and Bob) pick private values a and b and they generate a key and exchange it publicly, the opposite person received the key and from that generates a secret key after which they have the same secret key to encrypt.

Now according to question,

Step 1: Alice and Bob get public numbers P = 23, G=9

Step 2: Alice selected a private key a = 3 and Bob selected a private key b = 4

Step 3: Alice and Bob compute public values:

Alice -> x=(9^3 mod 23) = ( 729 mod 23) = 16

Bob -> y =(9^4 mod 23) = ( 6561 mod 23) = 6

Step 4: Alice and Bob exchange public numbers

Step 5: Alice receives public key y =6 and Bob receives public key x = 16

Step 6: Alice and Bob compute symmetric keys :

Alice -> ka = y^a mod p = 216 mod 23 = 9

Bob -> kb = x^b mod p = 65536 mod 23 = 9

Step 7:   9 is the shared secret key.

Hence, shared key is 9.