Twenty-six years ago Elliptic Curve Cryptography (ECC) was suggested as a alternative to previous methods of public key cryptography. In 1985 Neil Koblitz and Victor S. Miller independently co-suggested the idea. You may recognize Professor Koblitz as he is actually a professor here at the University of Washington. Previous methods of cryptography relied on the fact that it is very difficult to factor a value which is composed to two or more large primes. Analogously, at the heart of elliptic curve cryptography is the discrete logarithm problem. The basic idea here is that finding the discrete logarithm of a random point on an elliptic curve with respect to a know basis point (i.e. public key) is incredibly difficult. However, because of the very nature in which elliptic curves are defined, ECC can achieve comparable levels of security to other cryptography systems while only using a faction of the resources of the latter. This makes it a much more favorable system which are on a limited set of resources such as embedded systems and mobile phones. Since the creation of ECC, many people have worked on implementing the system and finding ways in which it can be made even more secure. One company in particular, Certicom, has actually built their entire business off of ECC and have actually patented some implementations of ECC and even some elliptic curves which are optimized for ECC. This behavior has actually spawned some tensions from within the community.
Being an ACMS major I am very interested in the mixing of Mathematics and Computer Science. Elliptic Curve Cryptography is a beautiful blending of the two which has very relvent applications. I have always been interested in security and in particular cryptography. However, I have had no prior experience in cryptography, so this was a very interesting project which really allowed me to learn a lot about both elliptic curves, but also about the basics of cryptography.
First off I wanted to start by showing how the system works over a very basic curve. In this example I will demonstrate how two people can generate public and private keys for exchanging in order to come up with a commonly shared key without compromising their private keys. This example uses the Diffie-Hellman key-exchange algorithm. We first start off by finding our private keys. Basically, this can be any integer from [1,p-1]. In this example each person simply selects a random integer on those bounds. Now we need a representation of this key on our curve. We get this by multiplying our each private keys by a random public point selected from the curve. These two values become the public keys of each of the people. Each of these values represents a different point on the curve. After they exchange their respective keys, they can multiply these keys by their own private keys in order to generate the same final key. Although these operations seems relatively simple to complete, looking at the graph it is impossible to see any real relation between the two points and the final key. It is also important to note how quickly the graph becomes very complex as we increase the modulus of the field.
{{{id=50| @interact def elliptic_test(p=23,A=9,B=17): if (4*A^3 + 27*B^2) % p == 0: raise ValueError('The equation for the elliptic curve may not contain repeated factors.') F = GF(p) test_curve = EllipticCurve(F,[A,B]) T = test_curve.plot() P = test_curve.random_element() while P[1] == 0: P = test_curve.random_element() a = randrange(1,p) b = randrange(1,p) aP = a * P bP = b * P while aP[1] == 0: aP = randrange(1,p) * P while bP[1] == 0: bP == randrange(1,p) * P aKey = bP*a bKey = aP*b if aKey == bKey: key = aKey T += points([(aP[0],aP[1]),(bP[0],bP[1]),(key[0],key[1])], pointsize=30, color='red', zorder=-5) T += text("A", (float(aP[0]) + .5,float(aP[1]) + .5), color='black') T += text("B", (float(bP[0]) + .5,float(bP[1]) + .5), color='black') T += text("Key", (float(key[0]) + .5,float(key[1]) + .5), color='black') T.show(gridlines=True, aspect_ratio=1) /// }}}The following code illustrates a basic generation and exchange of keys using the Diffie-Hellman Protocol. This is identical to the method used in the graph above however the following moves a lot closer to how the protocol actually works in the real world. First we generate the curve over Fp to be used for the exchange. It should be noted here that there must not be any repeated factors in the right hand side of the elliptic curve equation . That is x3 + ax + b has no repeated factors, or (4a3 + 27b2) % p does not equal 0. For this example we will use one of the Certicom recommened curves. After we have the curve, a person, in this case Alice, gets a random element from the curve, P. It is important that the y-value of this element is not 0, since n*P equals the point at infinity in this case. After we have our random point on the curve, Alice generates her private key. This just needs to be an integer between [1,p-1]. After she has this, she multiplies this by P to get a new point, aP. Alice's public key is thus defined by the tuple (p,E,P,aP). She then exchanges this information with Bob. Bob then computes his private key in similar fashion as Alice and then his point bP = B * P. His public key is now (p,E,P,bP) which he sends back to Alice. Now Alice and Bob can both generate the shared key by multiplying their private key by bP and aP respectively (i.e., shared key = A*bP = A * B * P = B * aP.) This completes the key generation process and Alice and Bob can now securely exchange information using their shared-key.
{{{id=32| def generateCurve(p,a,b): r""" This function returns an elliptic curve bound by the given values. INPUT: - ``p`` - integer -- the value the field is modded by. - ``a`` - integer -- coefficent of x. - ``b`` - integer -- coefficent of 1. OUTPUT: EllipticCurve -- y^2 % p = (x^3 + ax + b) % p . EXAMPLES: This example illustrates the basic uses of generateCurve :: sage: generateCurve(23, 19, 7) Elliptic Curve defined by y^2 = x^3 + 19*x + 7 over Finite Field of size 23 It is an error to pass values for a and b such that (4*a^3 + 27*b^2) % p == 0 :: sage: generateCurve(23, 19, 15) Traceback (click to the left of this block for traceback) ... ValueError: the equation for the elliptic curve may not contain repeated factors. AUTHORS: - Michael Snider (2011-06-3) """ if (4*a^3 + 27*b^2) % p == 0: raise ValueError('the equation for the elliptic curve may not contain repeated factors.') F = GF(p) return EllipticCurve(F,[a,b]) /// }}} {{{id=33| #Diffie-Hellman Implementation of key sharing. def keyExchangeExample(E,p): r""" This function simulates Diffie-Hellman key sharing and checks to make sure the keys match. INPUT: - ``E`` - EllipticCurve -- The elliptic curve to use. - ``p`` - integer -- the value the field is modded by. OUTPUT: Boolean -- whether or not the keys match. EXAMPLES: This example illustrates the basic uses of keyExchangeExample :: sage: keyExchangeExample(generateCurve(23,19,7), 23) True AUTHORS: - Michael Snider (2011-06-3) """ #Alice P = E.random_element() while P[1] == 0: P = test_curve.random_element() A = randrange(1,p) aP = A*P #Bob B = randrange(1,p) bP = B*P #Alice Computes aKey = A*bP #Bob computes bKey = B*aP return aKey == bKey /// }}}The following is one of the curves owned by certicom for use with elliptic curve cryptography. This particular curve is one of the two they recommend for 128-bit encryption over Fp. This particular curve was generated from the Seed:
0x00E0D4D696E6768756151750CC03A4473D03679{{{id=64| #Certicom 128-bit Encryption Recommended Curve 1. p = 2^128 - 2^97 -1 a = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC b = 0xE87579C11079F43DD824993C2CEE5ED3 params = (p,a,b) /// }}}
This final example is a method used to encypt and decrypt messages using the ElGamal method of key sharing. The method used to actually encode the message is very terrible and should mostly be ignored as this example is mostly to showcase how to use ECC to encode data. Also, since this example requires a greater deal of exchange of information, to prevent further convolution I created a Person class which basically is used to generate and keep track of the public and private keys of a user. Further more the generation of the public and private keys is identical to the Diffie-Hellman, so I won't take the time to go over that. So lets say that someone wants to send an encrypted message to Alice. First Alice must generate her public and private keys, n and (p,E,B,nB). The person wishing to the encrypt a message must first generate their own private key, r, and their differing parts of the public key, rB. For the encryption method, the message is encoded from a point P on the curve. So the person wishing to send the message now selects a point P. (In order to do a basic for of encryption, I simply added the x-coordinate of P to a integer representation of the message. This also limits the messages to the maximum size of an unsigned integer.) Now the point P is encrypted as (rB, P + r*nB) and sent off to Alice along with the encrypted message. Once Alice recieves this, she can calculate P using her private key, n, and the point sent by the person. This is done simply by subtracting the value of her private key, n, multipled by x-coordinate of the point sent from the y-coordinate: (P + r*nB) - n*rB = P + r*n*B - n*r*B = P. From here all that Alice has to do is subtract P from the message and convert it back to text from the decimal form.
{{{id=52| class Person: def __init__(self, p, a, b): r""" This function generates the public and private keys for a user. INPUT: - ``p`` - integer -- the value the field is modded by. - ``a`` - integer -- coefficent of x of the elliptic curve. - ``b`` - integer -- coefficent of 1 of the elliptic curve. OUTPUT: Person -- the user object containing their keys. AUTHORS: - Michael Snider (2011-06-3) """ self.private_key = randrange(p) self.public_key = self.generate_public_key(p, a, b) def generate_public_key(self,p,a,b): r""" This function generates the public and private keys for a user. INPUT: - ``p`` - integer -- the value the field is modded by. - ``a`` - integer -- coefficent of x of the elliptic curve. - ``b`` - integer -- coefficent of 1 of the elliptic curve. OUTPUT: Tuple -- the user's public key. EXAMPLES: This example illustrates the basic uses of generate_public_key :: sage: generate_public_key(self,23,19,7) (23, Elliptic Curve defined by y^2 = x^3 + 19*x + 7 over Finite Field of size 23, (12 : 13 : 1), (8 : 2 : 1)) AUTHORS: - Michael Snider (2011-06-3) """ F = GF(p) E = EllipticCurve(F,[a,b]) B = E.random_element() while B[1] == 0: B = E.random_element() nB = self.private_key * B return (p,E,B,nB) /// }}} {{{id=17| def encrypt(message, public_key): r""" This function encrypts a given message using the given key. INPUT: - ``message`` - string -- the message to be encrypted. - ``public_key`` - Tuple -- the components of the public key. OUTPUT: Tuple -- the encrypted message and encoded point. EXAMPLES: This example illustrates the basic uses of encrypt :: sage: Alice = Person(23,17,9) sage: decrypt('test', Alice.public_key) (8, ((13 : 14 : 1), (17 : 6 : 1))) AUTHORS: - Michael Snider (2011-06-3) """ r = randrange(1,public_key[0]) rB = r * public_key[2] P = public_key[1].random_element() while P[1] == 0: P = public_key[1].random_element() message = unicode(message).encode('utf-8').encode('hex') h_message = int(message,16) + P[0] cipher = (rB, P + (r * public_key[3])) return (h_message, cipher) /// }}} {{{id=63| def decrypt(message, cipher, public_key, private_key): r""" This function decrypts a given message a given cipher and keys. INPUT: - ``message`` - integer -- the message to be decrypted. - ``cypher`` - EllipticCurvePoint -- the encoded point used for decrypting. - ``public_key`` - Tuple -- the users public key. - ``private_key`` - integer -- the users private key. OUTPUT: Tuple -- the encrypted message and encoded point. EXAMPLES: This example illustrates the basic uses of encrypt :: sage: p = 2^128 - 2^97 -1 sage: a = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC sage: b = 0xE87579C11079F43DD824993C2CEE5ED3 sage: Alice = Person(p,a,b) sage: s = encrypt('test',Alex.public_key) sage: decrypt(s[0],s[1],Alex.public_key, Alex.private_key) 'test' AUTHORS: - Michael Snider (2011-06-3) """ P = cipher[1] - (cipher[0]*private_key) d_message = int(message - P[0]) h_message = hex(d_message) return h_message[2:-1].decode('hex') /// }}}Again here we are using the certicom recommended curve.
{{{id=20| #Certicom 128-bit Encryption Recommended Curve 1. p = 2^128 - 2^97 -1 a = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC b = 0xE87579C11079F43DD824993C2CEE5ED3 /// }}} {{{id=44| Alice = Person(p,a,b) /// }}} {{{id=45| secret = encrypt("Merry Christmas", Alice.public_key) /// }}} {{{id=46| decrypt(secret[0],secret[1],Alice.public_key,Alice.private_key) /// 'Merry Christmas' }}} {{{id=71| /// }}}