Real Cryptography Has Curves: Making The Case For ECC

Consider yourself a fascinating person if you've ever heard the term "Elliptic Curve Cryptography" (ECC).  Consider yourself a cryptographic crackerjack if you actually know what it does and how it all works.  If you are a mere mortal like the rest of us, you might not understand every single aspect of ECC.  Nonetheless, many web applications are (or soon will be) using ECC to secure online transactions, so I wanted to spend some time discussing the details behind this relevant and important topic.

 

A Walk Down Memory Lane

Before diving into Elliptic Curve Cryptography (ECC), let's take a quick stroll down the cryptography memory lane that brought us to the point of even caring about ECC.  Prior to the 1970s, cryptography was based primarily on securing communications using a shared secret key.  This secret key was used to both encrypt and decrypt communications.  This type of encryption is called “symmetric” because the same key is used to encrypt and decrypt.  Symmetric encryption is still used widely today because of its speed and efficiency.  In fact, you are using it right now to read this article!

As computers grew in popularity and our reliance on secure communications became more and more necessary for everyday life, experts began to see a significant issue with symmetric encryption.  This issue dealt with key distribution and exchange.  Back in the day, people would have to find creative ways to share the secret encryption/decryption key so that no one else got their hands on it.  Imagine the headache of trying to figure out how to share a secret key with someone on the other side of the world.  And, what if the key was compromised?  How do you re-share a new key?  You can see how this could turn into a frustrating situation. 

Fortunately, in 1977, a new era of viable cryptography was introduced.  Rather than dealing with the hassle of distributing symmetric keys, a few really smart dudes introduced what we now know as Public Key Cryptography.  In Public Key Cryptography, two keys are used…a private key and a public key.  Anyone in the world can get a copy of the public key, but only the user has a copy of his/her private key.  The genius of it all is that the private key can decrypt a message that has been encrypted with the public key…in fact, the private key is the ONLY key that can decrypt a message that has been encrypted with the associated public key.  Today, we use Public Key Cryptography to share symmetric encryption keys.  That way, we can still realize the efficiency and speed of symmetric encryption without the headache of sharing the symmetric keys.

 

Is That A Trapdoor?

Public Key Cryptography is awesome because it allows you to literally share half of your encryption key with anyone and everyone.  But, the question is…how in the world does that even work?  How can you give away half of your encryption information and still have a viable and secure form of communication?  The fundamental approach to solving this problem comes in the form and what’s called a “trapdoor” function.  A trapdoor function is one that’s really easy to solve in one direction, but really difficult to solve the other direction. 

For example, if I could create a mathematical function that makes it super easy to get to point “B” given a value for point “A” but makes it almost impossible to figure out where point “A” is if I only know the value of point “B” then I have a good trapdoor function…easy one direction but hard the other.  A good trapdoor function is absolutely critical in the implementation of Public Key Cryptography.  But that begs another question…do we have any good trapdoor functions lying around?

 

Rivest, Shamir, and Adleman…Oh My!

Remember when I talked about that 1977 date?  Well, that’s the year that three really smart dudes from MIT described their approach to what has proven to be a very popular and successful Public Key Cryptosystem.  The name, RSA, is derived from the first letters of each of their last names (Rivest, Shamir, and Adleman).  As it turns out, RSA uses very large prime numbers, along with the “modulo” function, to do its thing.  Of course, it gets pretty complicated when you break it all the way down to the crazy details.  But the overall idea is that it’s really easy to multiply two random prime numbers together to get a really big number, but it’s really hard to guess the prime factors of the really big number if all you have is the really big number. 

Everything in RSA starts with two prime numbers (p and q).  All other RSA values are derived from calculations based on those two prime numbers.  Here’s an explanation of how it all works.

Pick two random prime numbers, “p” and “q”. 

Next, calculate the value for “n” by multiply the two prime numbers together.  The value “n” is also called the “modulus” and is also the encryption key size.  So, if you use RSA 2048 bit, that means you have chosen two numbers “p” and “q” that, when multiplied together, result in a number that is 2,048 bits in size.  That’s a pretty big number!

Next, you calculate what’s called the “totient” of n, written as Φ(n).  You do that by multiplying p-1 and q-1 together.  Stay tuned for more from this value…it will prove to be extremely valuable!

Then, you choose a number “e” (also called the “exponent”) that is between 1 and Φ(n).  Not only does “e” have to fall between 1 and Φ(n), it also has to be a number whereby the Greatest Common Divisor (GCD) of “e” and Φ(n) is 1.

The last thing to do is calculate the ever-important private value.  The private value is typically represented by the letter “d” and is determined by calculating the multiplicative inverse of e (modulo φ(n)).  The “modulo” or “mod” operation is a math function that finds the remainder value after dividing two numbers together in a division problem.  The value for “d” is often found using the Extended Euclidean Algorithm.

Once you have the value for “d”, you have all the pieces you need for a fully functional RSA public key cryptosystem! 

 

 

Check out the picture on the right to see the hexadecimal representation of the public key value used for the f5.com website.  By the way, if you’ve ever wondered how to decipher that crazy long hexadecimal number into something more readable, check out this post and you’ll see how you can do it.  What you’ll find is that the public key hexadecimal number shown in your certificate details actually includes two values…one for “n” and one for “e”.  You’ll also find this website useful for converting large hexadecimal numbers to decimal.

Did you know?  Most applications choose the number 65,537 (0x10001) as the value for “e” 

 

 

As a refresher, the components of the RSA cryptosystem are:

p = random prime number

q = random prime number

n = p * q

Φ(n) = (p-1) * (q-1)

e = number between 1 and Φ(n)

d = e^-1 (modulo Φ(n))

 

Public Key = key pair (e, n)

Private Key = key pair (d, n)

 

RSA Encryption…

All the pieces are in place, but how do we use them all to do the encrypting and decrypting?  To encrypt something using the public key, you start with a plain text value (let’s call it “m”) and then encrypt it using the following math calculation:

m^e mod n

Notice that all we need to encrypt something are the original plain text value and the public key values (e, n).  When you complete this calculation, you have magically completed the encryption, and now you have your coveted encrypted value (called cipher text). 

 

RSA Decryption…

In order to decrypt this cipher text value and get back to the original plain text, you take the cipher text (let’s call it “c”) and complete the following calculation using the private key values (d, n).  Notice that you only need the cipher text value and the private key values in order to complete the decryption.  It’s also interesting to note that, if this cipher text was derived by anything other than your own public key encryption values, your private key decryption won’t work!

c^d mod n

 

RSA Working Example…

Now that all the pieces are in place and we have the formulas needed to encrypt and decrypt, let’s run through a working example of the RSA public key cryptosystem.  We will start with the random prime numbers of 11 and 13.  Using all the calculations above, we have:

p = 11

q = 13

n = 11 x 13 = 143

Φ(n) = 10 x 12 = 120

e = 7 (it turns out that 7 is between 1 and 120, and the GCD of 7 and 120 is 1…so, it fits all the criteria to be our public key value)

d = 7⁻¹ (mod 120) = 103

 

The public key is represented by the key pair (7, 143)

The private key is represented by the key pair (103, 143)

 

Let’s start with a plain text value of “9” and let’s encrypt it because, you know, it’s super-sensitive information.  Using the key values that were generated above, we find that the encrypted value is:

9⁷ mod 143 = 48

So, the encrypted value for “9” is “48” using all the RSA numbers we chose above.  Obviously, the encrypted values will change given different values for p, q, n, etc. 

To decrypt the value, we use our handy-dandy decryption formula and find that:

48¹⁰³ mod 143 = 9

And, just like that, we are back at our original value of 9.  It’s mathematical magic, and I personally think it’s completely fascinating.

 

Looking back on all the math of it, you can see that it’s totally possible to share the values for “e” and “n” without giving away any of the information needed to calculate the private key.  That’s because “d” is calculated using the “totient of n” rather than the value for “n” itself.  It’s super easy to calculate the “totient of n” (and, thus, the private key) if you have the factors of “n”…and that’s what the entire foundation of the security of RSA is built on. 

It’s really easy to multiply prime numbers together, but it’s really hard to factor a number into its component primes.  In our example, if you were given the number 143 (the value of n), then could you figure out that the prime numbers used to generate that number were 11 and 13?  Maybe so, but could you do it if the value for “n” was 2,048 bits long?

RSA is still an extremely viable and strong public key cryptosystem, but with the increased power of computers and their ability to crunch through numbers, it’s becoming more necessary to increase the key size in RSA to achieve a usable degree of security.  Easily put, if you want more security, increase the key size.  That’s all well and good, but it comes at a price.  Of course, something has to chunk through all those crazy huge RSA numbers, and it has to do it every time you establish a secure connection (which is pretty much all the time nowadays).  Let’s say you have a large population of mobile device users…do you think their smartphones are custom-built to handle the intense calculations needed for large RSA key sizes?  Probably not.  What if there was a way to use much smaller key sizes but keep the same level of security?  Lucky for you (and everyone else), there is…

 

What is Elliptic Curve Cryptography?

Elliptic Curve Cryptography (ECC) is a public key cryptosystem much like RSA in that it is used as the mechanism to create a public key and a private key in order to encrypt/decrypt data.  While RSA is founded on the mathematical difficulty of factoring prime numbers, ECC is based on the mathematical difficulty of solving what is called the elliptic curve discrete logarithm problem.  I’ll get into more detail on what that is, but it essentially deals with the problem of knowing how many steps it takes to move from one point on an elliptic curve to another point on that curve.  Turns out, even if you know the equation for the curve and the point to start hopping around the curve, you can be presented with another point on the curve and still have no idea how many hops it took to get from the starting point to the point you were just presented with.  Pretty crazy, huh?  That’s the difficulty of the elliptic curve discrete logarithm problem, and that’s what the entire security of ECC is built on. 

To understand this “hopping around the curve”, let’s begin with a few interesting characteristics about elliptic curves as well as a concept known as Point Addition.  Elliptic curves have symmetry about the x-axis, and any non-vertical line will intersect the curve in at most 3 points.  The elliptic curves used in cryptography today are typically defined by the following algebraic function:

 

y² = x³ + ax + b

 

The variables x and y are the standard variables used in any algebraic function and are used to define the points on the x-axis and y-axis on a standard graph.  The curve parameters a and b are coefficient values (constant numbers) that define what the curve will actually look like on a graph.  As the values for a and b change, the graph will take on a different look when it is graphed.  Here’s one example of an elliptic curve on a graph.  This particular graph has the values a = -6  and b = 10.

 

y² = x³ – 6x + 10

 

Point Addition is an operation on an elliptic curve that allows you to start with one point and ultimately arrive at another point on the curve.  Here’s how Point Addition works: given two points on the curve (P and Q), draw a straight line through them and intersect the curve at a third point (called -R).  Then, follow the value for -R along a vertical line until you intersect the curve again.  This intersecting point is the value for R.  So, P+Q = R … you just have to find -R first in order to ultimately find the value for R.  Once you have the value for R, you can then draw a line from P to R and you’ll find that the line intersects the graph again at a third point.  You can then take that point and move along a vertical line until you intersect the graph again.  This becomes the Point Addition for points P and R.  You can continue this Point Addition as many times as you need.  The graph below shows an example of Point Addition:

 

 

 

 

Another operation used in ECC is called Point Doubling.  Point Doubling is similar to Point Addition except that in point doubling, you add P to itself rather than add P to another point on the curve.  When you have two different points on the elliptic curve (P and Q), it’s easy to draw a straight line between them, but when you only have one point, how do you draw a straight line so that it intersects with another point on the curve? 

The answer is to draw the tangent line to the point (P) and then let the tangent line intersect the curve at another point.  At the intersecting point, you follow along a vertical line until you intersect the curve again (exactly the same concept as the P + Q operation above).  At that intersecting point, you find the value for P + P.  The Point Doubling operation is shown on the graph below.  Notice that the resulting value for P + P is labeled R.  This resultant point is also commonly referred to as 2P. 

In order to find the value for 3P, though, you go back to the Point Addition operation and add P + 2P.  Then, to find 4P, you use Point Addition again to add P + 3P, and so on…   

 

 

 

Point Addition and Point Doubling are important because they form the basis for finding values that are used for encryption using ECC.  They also highlight the basis for the Elliptic Curve Discrete Logarithm Problem that was mentioned above.  This problem states that, given point P and Q where Q is a multiple of P…find k such that Q = kP.  In other words, continue to Point Double/Point Add P a random number of times to land on a point on the curve.  Then, knowing the starting point P and the current point on the curve, tell how many times you Point Doubled/Point Added in order to get from P to the current point.  It sounds fairly straightforward, but it turns out to be extremely difficult.  And, it’s the one way function needed for the basis of using ECC for public key encryption.

One other important characteristic of the elliptic curve is the concept of a finite field.  Imagine, as you continue to Point Double/Point Add on the elliptic curve, that some of the points will land at a very large value on the x-axis.  In reality, you can’t allow every single value to be included in your calculations (you can’t go all the way out to infinity), so the way to limit these values is to establish a “max” value on the x-axis.  This value is represented as “p” in the ECC cryptosystem, and it is also called the “modulo” value for the system.  Effectively, it defines the finite field that the curve is defined over.  This value is also the key size for the ECC system.  Many ECC implementations choose a prime number for “p” thus making them a “prime” curve.

As you increase the value for “p” then you open up the possibilities for more usable values on the curve, and you effectively increase the security of the system using that particular curve.  That’s why an increased key size results in a more secure curve.

Now that we know all this goodness, let’s go over the values you need in order to fully define the ECC cryptosystem.  These are:

Curve equation :  y² = x³ +ax + b

p:  Specifies the finite field that the curve will be defined over (modulo value)

a:  Coefficient that defines the curve

b:  Coefficient that defines the curve

G:  Generator point on the curve.  This is the point where all the Point operations begin.

n:  Order of G.  The number of Point operations on the curve until the resultant line is vertical.

h:  Cofactor – the number of points on the elliptic curve divided by the order of G (ideally this value is 1 or very close to 1)

All of these values are known in advance.  In fact, for a given elliptic curve used for encryption today, you’ll want to choose a curve and all the associated values based on recommendations from the really smart mathematicians and scientists who have worked all these values out and tested them thoroughly for their use in encryption.  In other words, don’t define your own elliptic curve and expect it to be secure.

 

Diffie Hellman Using ECC

Now that we know all the ECC parameters, let’s walk through the implementation of ECC using the Diffie Hellman key exchange protocol.  Imagine that Alice wants to establish a secure connection with Bob and she chooses ECC Diffie Hellman as the mechanism to exchange encryption keys.  First, Alice will choose a random number between 1 and n-1.  We will call it ⍺.  At the same time, Bob is choosing a random number between 1 and n-1 as well.  We’ll call Bob’s value β.  Now we have:

⍺: randomly chosen number between 1 and n-1.  This is the private key for Alice

β: randomly chosen number between 1 and n-1.  This is the private key for Bob

 

Next, Bob computes the value B = β (G).  Bob can compute this value because he knows the values for β and G.  At the same time, Alice computes A = ⍺ (G).  Alice can compute this value because she knows the values for ⍺ and G.

Next, Bob sends Alice the point on the curve (x_B, y_B), and Alice sends Bob the point on the curve (x_A, y_A).  These two points on the curve are the public key values for Bob and Alice.  Still, neither person knows the other person’s private key value (⍺ or β).  They only know A and B (public keys) because they were sent those respective points on the curve.  A malicious eavesdropper would have all the values except for ⍺ and β (the private keys).  While a man in the middle could verify that A and B are points on the given elliptic curve, he would not know how many hops the points are from the initial generator point (G).  He would need the value for ⍺ or β to know the number of hops.  Again, this is the foundation of the Elliptic Curve Discrete Logarithm Problem.

Next, Bob and Alice then compute the value P by multiplying their respective private key value by the value received by the other person.  So,

Bob computes:  P = β * A   or, substituting ⍺ (G) for A, you get  P = β * ⍺ * G

Alice computes:  P = ⍺ * B  or, substituting β (G) for B, you get  P = ⍺ * β * G

 

Now, Bob and Alice both have the point P that they can use as their symmetric key encryption value!

 

A Working Example…

Let’s take all this goodness and actually work through an example with real numbers!  Keep in mind, the values for this curve and all the other associated parameters have been worked out in advance.  This curve uses very small numbers for p and n, so you wouldn’t want to use this specific curve in real life.

Here are the values for our ECC cryptosystem using the Diffie Hellman key exchange protocol:

Curve: y² = x³ + 2x + 2 (mod 17)

p: 17 (notice this is a prime number, so this is considered a “prime” curve)

a: 2

b: 2

G: (5,1)

n: 19

To find n, you Point Double/Point Add starting from G until you reach a point at infinity.  That is, the operations continue until the resultant line is vertical.  In this case, n = 19.  Here are the first few operations for this particular curve; starting at the Generator Point (5,1):

2G = G + G = (6,3)  Note: this point is found using Point Doubling

3G = 2G + G = (10,6)  Note: the remaining points are found using Point Addition

4G = 3G + G = (3,1)

…

19G =

h = 1 (which is the ideal value for h)

 

Now we are ready to start computing values for ⍺ and β. 

Alice picks a value for ⍺.  The value for ⍺ must be between 1 and n-1 (18).

⍺ = 3

Next, Alice computes the value for A:

A = ⍺ * G = 3G

A = (10,6)   Note: compare this point 3G to the 3G point listed above in the calculations for “n”.  This is how you know what point is represented by 3G.

Notice that the value for A is not a single number.  Rather, it is the point on the curve represented by Point Doubling/Point Addition operations conducted ⍺ times.

 

Bob picks a value for β.  The value for β must be between 1 and n-1 (18). 

β = 9

B = β * G = 9G

B = (7,6)

 

They share the values A and B with each other and are then ready to both compute the value for P.

Bob computes P = β * A = β * 3G = 9 * 3G = 27G.  Because the order of the curve (n) is 19, 27G reduces to 8G.  If the value for P results in a number higher than the order of the curve, you use the modulo operation to find the resulting value.  In this example, 27 mod 19 = 8.  So, 27G becomes 8G because 27 is larger than 19.

Alice computes P = ⍺ * B = ⍺ * 9G = 3 * 9G = 27G.  Alice uses the same logic as Bob in reducing 27G to 8G.

 

So, P = 8G = (13,7)

 

Now, Bob and Alice both have the point (13,7) as their shared secret, and the man in the middle has no idea what the value for P is.  They don’t need to use both the x-value and the y-value, so they can just throw away one of the values (let’s say they throw away the y-value).  Now, they have the value 13 as a shared secret and they can use this to encrypt all further communication. 

 

Why Is ECC So Popular?

ECC provides a way of exchanging encryption keys (which is hugely necessary on the Internet these days), and it does it much more efficiently than RSA.  This allows for lower CPU utilization, less memory usage, faster key generation, faster certificate processing, etc.  The following table shows a comparison between RSA key sizes and ECC key sizes that provide the same level of security. 

Notice a couple of things.  First, the key size for ECC is significantly smaller than that of RSA for the equal level of security.  Second, the key size for RSA gets proportionately much larger as increased strength is needed compared to ECC.  For example, if you want triple the level of security for RSA, you have to triple the key size (1024 to 3072).  But, for ECC if you want triple the level of security, you only have to increase the key size by 1.6 times (160 to 256).  These are the primary reasons ECC is so desirable in web application security today.

 

RSA Key Size	ECC Key Size
1024	160
2048	224
3072	256
7680	384
15360	512

 

Real Life Curves

Remember how I mentioned that you shouldn’t create an elliptic curve on your own because it probably wouldn’t actually be secure and efficient?  Well, the good news is that other really smart people have already created a bunch of curves for you.  The National Institute of Standards and Technology (NIST) has developed five recommended “prime” curves called: p192, p224, p256, p384, and p521. Other curves are also recommended by Certicom in the Standards for Efficient Cryptography (SEC2) in which the curves are named secp192r1, secp224r1, secp256r1, secp384r1, secp521r1.

With any of these curves, a good random number generator is needed to provide proper security.  It’s interesting to me that all these curves and sophisticated cryptography is in place only to fully rely on the need for a quality random number generator.  Be sure your cryptosystem is using a good one!

 

What Curves Are Supported By F5?

Currently, F5 provides support for curves p256 and secp384r1.  But, other curves are in the process of being supported with future version releases.  BIG-IP supports ECC for use in the Digital Signature Algorithm and Diffie Hellman key exchange protocols. 

For more info on how to configure SSL ciphers, check out our WhiteBoard Wednesday video on SSL Ciphers.  Also, check out our Lightboard Lesson video on ECC to see a graphical presentation on all this goodness.

 

Well, that’s it.  Now you can get out there and get crazy with all that ECC!