Week 3 of network security continued our introduction to Elliptic Curve cryptology. Specifically the mathematical operations and rationale behind this public key encryption method. At the moment I am implementing the RSA requirements for assignment 1 so did not get a chance to do much practical experiment with ECC. For me, understanding how the algorithms work can only be achieved by implementing them.
The lecture began with a definition of the Discrete Logarithm Problem [DLP]. Put simply:
Given a group of elements [a,B] Find the integer such that B = a ^ x
In this scenario it is relatively easy to compute B. However, given a and B, computing x is computationally expensive.
The operation of log(B,base a) to find x is not dissimilar in computational complexity to finding p and q given n (n = pq). Note that the logarithmic function is only particularly expensive in a discrete domain.
Moving from a definition of elliptic curves we related this to encryption.
Given an elliptic curve function and and infinite point O a set G can be established:
Take two points, P and Q and the intersect of the line PQ, is R -> P + Q = R (remembering these are co-ordinates).
For every P, P + (-P), a tangent on point P will intersect with -(R).
ECC operation definitions:
P + Q -> (-Xr) = s^2 – Xp – Xq, -(Yr) = s(Xp – Xr) – Yp
where s = (Yp – Yq) / (Xp – X q)
P + P (2P) -> (-Xr) = s^2 – 2Xp, Yr = s(Xp – Xr) – Yp
I am going to begin using the Python Library, Sage (http://www.sagemath.org/) to test these operations and hopefully get a graphical representation. Java also has an elliptic curve library (http://download.oracle.com/javase/1,5.0/docs/api/java/security/spec/EllipticCurve.html). I don’t have a good understanding as yet of how these operations fit into the elliptic curve cryptology algorithm.
Of the two common elliptic curve families, Binary and Prime number curves, I will be focusing on Prime number curves as it is most relevant to our assignment requirements, and hopefully the most understandable.
As the field needs to be discrete, we defined a group (Zp, mod) = {0,1, p -1} where p is a prime number.
The elliptic field will be defined as y^2 = x^3 +ax + b mod p where a, b, y and x are all members of Zp.
Example:
p=11, Zp=Z(11) – > y^2 = x^3 + x + 6 (mod 11)
E (Z11, mod) = {(2,4),(2,7), (3,5),(3,6), (5,2),(5,9), (7,2),(7,9), (8,3),(8,8), (10,2),(10,9)}
The next step is to select a generate, say g = (2,7).
Using the operation defined above for P + P we can calculate a set of G, 2G ….nG:
g=(2,7), 2g=(5,2), 3g=(8,3), 4g=(10,2) 5g=(3,6), 6g=(7,9), 7g=(7,2), 8g=(3,5), 9g=(10,9), 10g=(8,8),11g=(5,9),12g=(2,4)
Now, both parties know the elliptic curve and the generator g (2,7) -each party (lets say Alice and Bob) must now create a public key.
Alice generates a random number, say 2. Her public key becomes 2g (see the set above) -> (5, 2).
Bob also has a public key, random number say 3. His public key becomes 3g -> (8,3).
Alice wants to send the encrypted message -> (3,6)
Here is a major difference to the RSA algorithm. Instead of only using Bob’s public key to encrypt a message, Alice must use both Bo and her own public key.
So, to encrypt the message (3,6) for transmission to Bob, Alice must complete the following operation:
Cypher = (AlicePubKey(5,2), AliceRandomNubmber(4) *BobPublicKey(8,3) + m(3,6))
= ((5,2), 4(8,3) + (3,6) => (5,2),( (8,3) + (8,3) +(8,3) +(8,3) + (3,6)
See the operation definitions in bold above for how to calculate the point additions.
Cypher ready for transmission from Alice to Bob = ((5,2), (5,9))
Now, Bob receives the cypher text and must decrypt using the elliptic curve, AlicePublicKey(5,2) and his Random(3).
The operation is:
(Cypher excl. AlicePubKey) – (AlicePubKey * Bob’sRandom)
= (5,9) – ((5,2) + (5,2) + (5,2)) => (5,9) – (7,9)
Again from the operations above P + Q is defined so lets turn P -Q -> (5,9) – (7,9) into P + Q -> (5,9) + (7, -9).
Which will output the message – (3,6)!
So, we can see that encryption and decryption is not that difficult in terms of operations. With that in mind how can we be sure that if we are transmitting our the elliptic curve, the generator and our publickey, an attacker can’t find our RandomNumber (which is in fact the private key).
The attacker will know:
Alices Public Key was found by taking the set generated using the Elliptice curve and generator (2, 7).
Her public key (Q) can be defined as -> Q = kP -> where k is here secret random number and P is the generator (2,7).
Finding k given Q and P is the equivalent of a Discrete Logarithm problem which as mentioned is computationally expensive.
The safety of Alice’s secret random is source in the Elliptic Curve Logarithm Problem presented above.
For an elliptic curve modeling tool http://www.certicom.com/ecc_tutorial/ecc_javaCurve.html