0x01b: The Elliptic Curve Diffie Hellman KE Protocol & Its Mathematical DLP Analysis
[ DESCRIPTIVE REFERENCE ]
Elliptic curve Diffie-Hellman (ECDH) is an anonymous key agreement protocol based on the conventional Diffie-Hellman key exchange protocol, but with the use of elliptic curves. This allows two parties, each having an elliptic curve public-private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a key, or to derive another key which can then be used to encrypt subsequent communications using a symmetric key cipher. It is a variant of the Diffie-Hellman protocol using elliptic curve cryptography.
[ PICTORIAL REPRESENTATION ]
Where m is Alice's private key, and mG is her public key. And where n is Bob's private key, and nG is his public key.
[ ANALYSIS ]
The Elliptic Curve Diffie-Hellman (ECDH) key exchange protocol offers the same secret key establishment as proposed by the mechanisms of the conventional Diffie-Hellman key exchange protocol (D-H) that I discussed previously here. However, the difference is that the former incorporates Elliptic Curve Cryptography (ECC), as opposed to integers, over Galois fields (finite fields).
Therefore, in complete analogy to the conventional D-H key exchange protocol, it is feasible to realize a key exchange incorporating elliptic curves. Hence the derived name, Elliptic Curve Diffie-Hellman (ECDH) key exchange protocol.
[ ECDH DOMAIN PARAMETERS ]
Initially, to compute such a key exchange domain parameters must be agreed upon.
In Elliptic Curve Cryptography (ECC), the domain parameters, elements defining the elliptic curve, can be mathematically agreed upon through either prime fields (p, a, b, G, n, h), or binary fields (m, f(x),a, b, G, n, h); prime (denoted as p) or is a power of two (2^{m}). The latter being the binary case, and also necessitates the choice of an auxiliary curve denoted by f. Thus the field is defined by p in the prime case and the pair of m and f in the binary case. The example demonstrated below will incorporate the former prime field methodology:
$$\color{#20c20e}\textit{(p, a, b, G, n, h)}$$
Commonly agreed selections of the following are chosen, and are all publicly available:
- The field parameter: p. (This specifies which finite field our curve will be defined over)
- The curve parameters: a & b. (These parameters along with parameter p define our curve)
- The base point (generator): G.
- The prime order of G: n. (The smallest prime number such that n multiplied by G via scalar multiplication will equal the elliptic identity)
[ UNDERSTANDING THE MECHANICS ]
All parties Alice, Bob and Eve (an eavesdropper) are aware of the domain parameters p, a, b, G, n, h as these are the public values.
Alice randomly selects a secret integer (ɑ), where ɑ is between 1 and n - 1. No one else but Alice knows this value. Likewise, Bob also randomly selects a secret integer (β), where β is between 1 and n - 1, which is strictly known to Bob only. Both Alice and Bob now have their own private key values.
Following the above, through the means of the domain parameters:
Bob computes his public value (B) via scalar multiplication to obtain a result of a point that lies on the curve: B = βG
Likewise, Alice computes her public value (A) in the same manner as Bob via: A = ɑG
The resulting co-ordinate point values (A and B) are then publicly transmitted across the publicly insecure communication medium, where Bob receives Alice's public value (A), and Alice receives Bob's public value (B).
Bob takes Alice's public value (A) and multiplies it by his private value (β):
$$\color{#20c20e}P = \beta A \cong P = \beta aG$$
Alice takes Bob's public value (B) and multiplies it by her private value (ɑ):
$$\color{#20c20e}P = \alpha B \cong P = \alpha \beta$$
$$\color{#20c20e}\therefore P = \beta \alpha G = P = \beta A \cong P = \alpha \beta G = P = \alpha B$$
This generates the same point (P on the curve. Alice and Bob now have a mutually agreed shared secret, a point of a curve. This point consists of an ordered pair, the x and y co-ordinate (x, y).
[ DEMONSTRATING GROUP OPERATIONS AND MECHANICS OF THE CURVE ]
For the purpose of demonstrating the Elliptic Curve Diffie-Hellman protocol's mechanism, the incorporated parameters contain small numerical values (similar to the example I demonstrated for the conventional D-H protocol). Initially, a multiplex of group operations needs to occur prior to establishing the key exchange with ECDH.
The curve:
$$\color{#20c20e}y^2 = x^3 + 2x + 2 \textit{ (mod 17)}$$
From this curve's structure, a cyclic group will need to be generated. Therefore, a generator (G) is required. For the curve, y2 = x3 +2x + 2 (mod 17), the point (5, 1) is a generator. Therefore, G = (5, 1).
$$\color{#20c20e}\textit{Given }y^2=x^3+2x+2\textit{ mod }17 \textit{ and point }G=(5,1) \textit{ compute }2G=G+G=(5,1)+(5,1)=(x_3,y_3)$$
>_Generating the Cyclic Group
The cyclic group is generated via computing multiples of the generator point (G). Therefore, the first step would be to compute 2G. However, in order to do this the slope of the tangent line through G must be computed. This is achieved via the following formula:
$$\color{#20c20e}s = \frac {3x2G + a} {2yG} \textit{ mod p} $$
$$\color{#20c20e}s=\frac{{3x_{1}}^{2}+a}{2y_{1}}\textit{mod p}$$
$$\color{#20c20e}\therefore s=\frac{{3x_{1}}^{2}+a}{2y_{1}}\textit{mod p} = (2\cdot 1)^{-1}(3\cdot 5^2+2)=2^{-1}\cdot 9=9 \cdot 9=13 \textit{ mod 17}$$
>_The x co-ordinate can now be computed for 2G via the following formulae:
$$\begin{equation*} \color{#20c20e}x_{3} = (s^2 - x_{1} - x_{2}) \text{ mod p } \end{equation*} $$
$$\begin{align*} \color{#20c20e}x_{3} &\color{#20c20e}= s^2 - x_{1} - x_{2} \\ \color{#20c20e}x_{3} &\color{#20c20e}= 13^2 - 5 - 5 \\ \color{#20c20e}x_{3} &\color{#20c20e}= 169 - 10 \text{ mod 17 } \\ \color{#20c20e}x_{3} &\color{#20c20e}=159 \text{ mod 17 } \\ \color{#20c20e}x_{3} &\color{#20c20e}= 6 \\ \color{#20c20e}\therefore \quad (x_{2G}, y_{2G}) &\color{#20c20e}= (6, y_{2G}) \end{align*}$$
$$\color{#20c20e}x_{2G} \color{#20c20e}= s^2 - 2x_G \\$$
$$\begin{align*} \color{#20c20e}x_{2G} &\color{#20c20e}= 13^2 - 2(5) \\ \color{#20c20e}x_{2G} &\color{#20c20e}= 169 - 10 \\ \color{#20c20e}x_{2G} &\color{#20c20e}= 159 \text{ mod 17 } \\ \color{#20c20e}x_{2G} &\color{#20c20e}= 6 \\ \color{#20c20e}\therefore \quad (x_{2G}, y_{2G}) &\color{#20c20e}= (6, y_{2G}) \end{align*}$$
>_The y co-ordinate can now be computed for 2G via the following formulae.
$$\color{#20c20e}y_{3}=s(x_{1}-x_{3})-y_{1} \mod{p}$$
$$\begin{align*} \color{#20c20e}y_{3} &\color{#20c20e}= s(x_{1} - x_{3}) - y_{1} \\ \color{#20c20e}y_{3} &\color{#20c20e}= 13(5 - 6) - 1 \text{ mod 17 } \\ \color{#20c20e}y_{3} &\color{#20c20e}= -14 \text{ mod 17 } \\ \color{#20c20e}y_{3} &\color{#20c20e}= 3 \\ \color{#20c20e}\therefore \quad (x_{2G}, y_{2G}) &\color{#20c20e}= (6, 3) \end{align*}$$
$$\color{#20c20e}y_{2G} \color{#20c20e}= s(x_{G} - x_{2G}) - y_{G} \bmod{p}$$
$$\begin{align*} \color{#20c20e}y_{2G} &\color{#20c20e}= 13(5 - 6) - 1 \\ \color{#20c20e}y_{2G} &\color{#20c20e}= -13 - 1 \\ \color{#20c20e}y_{2G} &\color{#20c20e}= -14 \text{ mod 17 } \\ \color{#20c20e}y_{2G} &\color{#20c20e}= 3 \\ \color{#20c20e}\therefore \quad (x_{2G}, y_{2G}) &\color{#20c20e}= (6, 3) \color{#20c20e}\end{align*}$$
We can verify that (6,3) is a point on the curve by:
$$\color{#20c20e}3^2=9, 6^3+12+2=36\cdot6+14\equiv2\cdot6+14=26\equiv9 \text{ mod 17 }$$
Calculating the (x, y) co-ordinate for 3G:
$$\color{#20c20e}G+2G=(5,1)+(6,3)=(10,6) \textit{ since }s=\frac{y_2-y_1}{x_2-x_1}\textit{ mod }p=\frac{3-1}{6-5}=2(1)^{-1}\equiv2\textit{ mod }17$$
$$\color{#20c20e}x_3=s^2-x_1-x_2=4-11=-7\equiv10\textit{ mod }17$$
$$\color{#20c20e}y_3=s(x_1-x_3)-y_1=-10-1=-11\equiv6\textit{ mod }17$$
$$\color{#20c20e}\therefore G+2G = 3G = (10,6)$$
In order to completely generate the cyclic group, this process is repeated for 4G, 5G, 6G and onwards until we compute a point of infinity. This particular curve has a cardinality of 19, mathematically represented as;
$$\color{#20c20e}\textit{#E}=\left|E \right|=19$$
The below presents all 19 point values within this demonstrated cyclic group set:
G = (5, 1 ), 2G = (6, 3), 3G = (10, 6), 4G = (3, 1), 5G = (9, 16), 6G = (16, 13), 7G = (0, 6), 8G = (13, 7), 9G = (7, 6), 10G = (7,11), 11G = (13, 10), 12G = (0, 11), 13G = (16, 4), 14G = (9, 1), 15G = (3, 16), 16G = (10, 11), 17G = (6, 14), 18G = (5, 16), 19G = θ
>_Finding the order of G (n):
Count the number of points in the cyclic group; in this case the order of G is 19. ∴ n = 19
>_Finding the co-factor (h):
The co-factor of the curve: y2 = x3 +2x + 2 (mod 17) with generator point G = (5, 1) is 1.
∴ h = 1. This co-factor of 1 is ideal as a smaller number represents better point distribution across the curve. It is stated that any co-factor greater then 4 promotes an increase of being more susceptible to attacks.
>_The key exchange can now commence:
Bob randomly devises his private value (β). In this case, β = 9. Bob then computes his public value (B = βG), via B = 9•G = 9G, which is equivalent to point (7, 6) in the above devised cyclic group of the curve.
Simultaneously, Alice randomly selects her private value via (ɑ). In this case, ɑ = 3. Alice then computes her public value (A = ɑG), via A = 3•G = 3G, which is equivalent to point (10,6).
A and B are then transmitted across the public channel where Bob receives A, and Alice receives B. It is now possible to compute the shared secret point (P):
Alice takes Bob's public value (B) and computes P = ɑB. The resulting computation is:
$$\color{#20c20e}P = 3B = 3(9G) = 27G$$
However, given that the order of G is n = 19 (defining the extent of our cyclic group), we apply a modulo operation to the scalar. This operation ensures that the exponent employed in scalar multiplication remains within the allowable range defined by the cyclic group's order. Consequently, we perform the counting up to 19 and then initiate anew from the initial generator (G), much like the process of counting in base16 (hexadecimal), but baseG in this case. We can achieve this by taking the modulo of the value of n, where n = 19. Consequently, the result should be P = ɑB mod n, representing 27G mod 19. This yields P = 8G, signifying P = (13, 7).
The same operation is computed with Bob simultaneously, but using Alice's public value (A):
$$\begin{align*} \color{#20c20e}P &\color{#20c20e}= \beta A \text{ mod n} \\ &\color{#20c20e}= 9G(3) \equiv 27G \pmod{19} \\ &\color{#20c20e}= 8G \\ \color{#20c20e}\therefore\ P &\color{#20c20e}= (13, 7) \end{align*}$$
The shared secret point is (13, 7). Therefore, it remains only to convert this point to a bit string suitable for use as a secret key.
[ EVE'S OBSERVATION : INTERCEPTING THE PUBLIC CHANNEL DURING THE EXCHANGE ]
Eve would see the public domain parameters, including Alice and Bob's public values:
y2 = x3 +2x + 2 mod 17 (p), G = (5, 1), n = 19, h = 1, A = (10, 6) and B = (7, 6)
Even with these public values, Eve is unable to compute the point of P. This is the elliptic curve discrete logarithm problem and is addressed in greater detail below. This discrete logarithm problem is derived from the trap door (one-way) functions implemented as a successor product of elliptic curve point multiplicative notation and additive notation.
Therefore, for Eve to obtain the shared secret P, she would need either β (Bob's private value) or ɑ (Alice's private value), or alternatively, Eve would need to solve the elliptic curve discrete logarithm problem. For small-scaled numeric variables this wouldn't be mathematically overwhelming. However, for large-scaled numeral values... Good luck to Eve.
[ THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM (ECDLP) ]
Revising back to the conventional D-H protocol, of which, being in the multiplicative group Ζp*, where p is a prime. The discrete logarithm problem is:
$$\color{#20c20e}\textit{"Given elements y and g of the group, and a prime p, find k such that y = gk mod p"}$$
When the elliptic curve group is defined via the notation of scalar multiplication or additive notation, then the elliptic-curve discrete logarithm problem is as follows:
$$\color{#20c20e}\textit{"Given points G and P in the group, find a number that Gk = P"}$$
k is called the discrete logarithm of P to the base G if P = kG.
An example (small-scaled variables) in the elliptic curve group defined by:
$$\color{#20c20e}y^2 = x^3 + 9x + 17 \textit{ over } \mathbb{F}_{23}$$
$$\color{#20c20e}\textit{What is the discrete logarithm k of P = (12,17) to the base G = (16,5)?}$$
Practically, in this demonstration, k can be trivially solved by computing multiples of G until P being (12, 17) is found. For example: The first few multiples of G are as follows:
Since 8G = (12,17) which is = P (as P = (12, 17)), the discrete logarithm of P to the base G is k = 8.
However, in a real world application, the value k (in the above demonstration) would (you'd hope) be large enough that it become computationally intractable to solve in this manner, thus making the elliptic curve discrete logarithm problem mathematically overwhelming with large secure values.
In addition to the above there is an abundance of known algorithms based on group/number theory that can solve the ECDLP when implemented with small values, two of which include: the baby-step giant-step, which is, a Meet-In-The-Middle space-time trade-off algorithm. Another is Pollard's Rho algorithm, of which, is an integer factorization algorithm.
In saying this however, when implementing such large-scaled values in conjunction to the ECDH protocol, even with mass-computational power, it would take millenniums to solve for k. This is based on the assumption that the protocol has been implemented correctly.
This very principle defines the security of this protocol (and the conventional D-H protocol) as its security is measured by the time it takes to reverse the computations achieved via the algorithm's trap-door functions.
[ SAMPLE PYTHON IMPLEMENTATION FOR DEMONSTRATION ]
1 from elliptic import *
2 from finitefield.finitefield import FiniteField
3 import os
4
5 def generateSecretKey(numBits):
6 return int.from_bytes(os.urandom(numBits // 8), byteorder='big')
7
8 def sendDH(privateKey, generator, sendFunction):
9 return sendFunction(privateKey * generator)
10
11 def receiveDH(privateKey, receiveFunction):
12 return privateKey * receiveFunction()
13
14 def slowOrder(point):
15 Q = point
16 i = 1
17 while True:
18 if type(Q) is Ideal:
19 return i
20 else:
21 Q = Q + point
22 i += 1
23
24 if __name__ == "__main__":
25 F = FiniteField(3851, 1)
26
27 # Totally insecure curve: y^2 = x^3 + 324x + 1287
28 curve = EllipticCurve(a=F(324), b=F(1287))
29
30 # order is 1964
31 basePoint = Point(curve, F(920), F(303))
32
33 aliceSecretKey = generateSecretKey(8)
34 bobSecretKey = generateSecretKey(8)
35 print('Secret keys are %d, %d' % (aliceSecretKey, bobSecretKey))
36
37 alicePublicKey = sendDH(aliceSecretKey, basePoint, lambda x:x)
38 bobPublicKey = sendDH(bobSecretKey, basePoint, lambda x:x)
39
40 sharedSecret1 = receiveDH(bobSecretKey, lambda: alicePublicKey)
41 sharedSecret2 = receiveDH(aliceSecretKey, lambda: bobPublicKey)
42
43 print('Shared secret is %s == %s' % (sharedSecret1, sharedSecret2))
44 print('extracting x coordinate to get an integer shared secret: %d' % (sharedSecret1.x.n))
[ BREAKING DOWN THE SOURCE ]
The above is a Python implementation representing the ECDH key exchange protocol. This implementation presented is a segment of source-code that calculates the shared-secret in accordance to the multiplex of sub-scripts that perform and compute the group operations. Again, this source-code is incorporated for demonstration purposes using insecure values, including the curve that can easily be broken.
In short, as opposed to outlining the obvious and self-explanatory semantics of code line by line, a general overview of what is happening within this implementation is as follows:
The program initially imports subscripts and modules, including computations resulting from the sub-script elliptic.py, as well as Python's os module, which allows access to the operating system's Random Number Generator (RND) via the 'urandom' function that is used to generate both Alice and Bob's private keys.
Three functions are then defined: generateSecretKey, SendDH, and RecieveDH, all of which are later called.
5 def generateSecretKey(numBits):
6 return int.from_bytes(os.urandom(numBits // 8), byteorder='big')
7
8 def sendDH(privateKey, generator, sendFunction):
9 return sendFunction(privateKey * generator)
10
11 def receiveDH(privateKey, receiveFunction):
12 return privateKey * receiveFunction()
The generateSecretKey function is called upon via, 'generateSecretyKey(8)' to generate a secret key each for Alice (aliceSecretKey) and Bob (bobSecretKey):
37 aliceSecretKey = generateSecretKey(8)
38 bobSecretKey = generateSecretKey(8)
The '8' is accepted as input to instruct the function to generate 8 random bytes (via os.urandom) to output a byte string object that is then converted to an integer value. Thus, a random value is generated for Alice and Bob's secret key.
The simple and therefore non-secure elliptic curve being used in the protocol's implementation is defined by:
$$\color{#20c20e}y^2 = x^3 +324x + 1287 \textit{ over the prime field }\mathbb{Z}_{3851}$$
25 F = FiniteField(3851, 1)
26
27 # Totally insecure curve: y^2 = x^3 + 324x + 1287
28 curve = EllipticCurve(a=F(324), b=F(1287))
A base point (basePoint) is chosen (920, 303) that will be used as a generator:
30 # order is 1964
31 basePoint = Point(curve, F(920), F(303))
These values are then called within the relevant functions with placeholders for actual network transmission functions. These functions are SendDH, and RecieveDH. These two functions mimic 'SendData' and have been derived for the purpose of simulating such network transmission. Both Alice and Bob call these functions as seen below:
37 alicePublicKey = sendDH(aliceSecretKey, basePoint, lambda x:x)
38 bobPublicKey = sendDH(bobSecretKey, basePoint, lambda x:x)
39
40 sharedSecret1 = receiveDH(bobSecretKey, lambda: alicePublicKey)
41 sharedSecret2 = receiveDH(aliceSecretKey, lambda: bobPublicKey)
alicePublicKey is computed with variables: aliceSecretKey and basePoint where the result is transmitted to Bob to compute sharedSecret1 with his private value (bobSecretKey). Likewise, bobPublicKey is computed with variables: bobSecretKey and basePoint where it is then transmitted to Alice to compute sharedSecret2 with her private value (aliceSecretKey). A shared secret point (x and y co-ordinate) on the curve has now been devised between Alice and Bob.
The x co-ordinate is extracted, and the corresponding integer is now the shared secret between Bob and Alice.
[ FINAL COMMENTS ON IMPLEMENTATION ]
The above implementation is successful with its accuracy in demonstrating a representation that portrays how the Elliptic Curve D-H key exchange mechanism works. Though it is not an applicable implementation that should be implemented.
The implementation offers insight as to how the protocol works. It's similar to the conventional D-H protocol, though the mathematical functions differ. These functions have been clearly showcased within the vast implementation scripts of the ECDH implementation.
Similarly to the conventional D-H, for this implementation to contain a higher level of security, the following must be considered:
1. The use of insecure curves are not be used. Instead, Curves that have been assessed and tested
by mathematical professionals should be incorporated for security.
2. The use of small integers and values are not be used. Again, this relates to the security of
the secret values devised by the ECDH protocol.
3. The saving, printing or transmission of secret values should not occur.
4. In a real-world simulation, no values are ever printed as seen in the implementation.
Instead they are transmitted between the two parties (Alice and Bob).
5. Public keys/values would actually functionally transmit across a network medium.
6. Once devised, the shared secret value should parse hash functions.
7. Finally, I would like to clarify that while it is true that the ECDH protocol is secure
against attacks based on the ECDLP, it may be vulnerable to other types of attacks, such
as side-channel attacks or implementation errors. Therefore, it is important to use proper
security measures and to ensure that the protocol is implemented correctly.