ELliptic Curve Cryptography

ECC — Elliptic-Curve Cryptography

Elliptic-curve cryptography is the foundation of today's Internet. It secures communication, banking, and business, and can run efficiently on small devices.

But here's the problem. Most tutorials on elliptic-curve cryptography or ECC start by saying "We will assume that you are familiar with number theory and abstract algebra." Or, worse yet, they don't even bother saying that, and they jump right into the mathematics. You're left mystified as to where the keys come from, or why the curve even exists. Other pages supposedly about elliptic-curve cryptography are really just their authors signaling that they're fascinated by crypto-currency, the tulip mania of the 21st Century.

You can understand ECC.

I'm no expert in number theory, so I'll walk you through how I figured it out. It doesn't have to be difficult.

Don't worry, there's no need for you to know advanced number theory or abstract algebra! A simple calculator will suffice if you want to play along with the examples.

PETER VENKMAN:	Ray... for a moment... pretend that I don't know anything about metallurgy, engineering, or physics, and just tell me what the hell is going on.
RAY STANTZ:	You never studied.

Ready To Jump Ahead?

If you already know about asymmetric versus symmetric encryption, what you can accomplish with asymmetric ciphers and hybrid encryption, and roughly how RSA works, then:

Jump Ahead

If not...

First Decision: Aymmetric Versus Asymmetric

Symmetric ciphers like AES require two communicating parties to securely share a secret key. Symmetric ciphers have been studied carefully and they operate efficiently, but that shared secret key is the problem.

Asymmetric ciphers use key pairs. You generate keys as a pair, call one the private key and the other the public key, and then treat them accordingly.

Data can be encrypted with either key of an asymmetric pair, turning cleartext into ciphertext. Once you do that, you must use the other key from the pair to decrypt the ciphertext and recover the original cleartext.

Because of the math involved, symmetric ciphers like AES run quickly. That's important as our data continues to grow and grow!

Well, if I'm praising symmetric for running fast, then obviously asymmetric must be signicantly slower. For algorithms of roughly the same strength, a symmetric cipher can process many times the megabytes per second that an asymmetric cipher could. What's more, asymmetric ciphers are really designed to handle small pieces of data. Typically just 256 bits or 32 bytes, either a session key for a symmetric cipher, or the output of SHA-2-256 when creating or verifying a digital signature.

Don't Worry, Speed Is Not A Concern for Asymmetric Ciphers!

We use a asymmetric cipher to solve the key management problem so we can encrypt data with fast symmetric ciphers. Let's say I'm certain that I have your public key. First, I would generate a random 256-bit key and create a short message. Note that AES is a fast symmetric cipher, a good way to protect large data files.

I am encrypting the data with the AES cipher using this randomly generated 256-bit key:
0x3a73d268cf6a9de8bd11b5ec5b833105b411cee1fe9d23ed6d783a37697d965f

Now I would use your public asymmetric key to encrypt that tiny message. Who care if it's relatively slow, because that's a tiny job!

Next I would use the fast AES cipher to do what the above describes on the large sensitive data file.

Then I would send both parts, the tiny header encrypted with your public key, and the large message encrypted with that randomly chosen symmetric session key. That makes this a hybrid cryptosystem, we use a mixture of asymmetric and symmetric encryption.

I would generate a new random session key for every message or file that I wanted to protect. If, somehow, one was illicitly decrypted (unlikely!), or the attacker managed to discovered its contents through some other leaky channel, then only that one message is compromised.

Meanwhile, you are receiving my messages or files. You have your private key, so you can decrypt those short headers. They tell you how to decrypt the data. And since you protect your private key, no one else can do that.

Trapdoors To The Rescue

The public and private key of a pair are mathematically related. The big worry is: What if someone used my public key to discover my private key?

Asymmetric ciphers are based on trapdoor functions. These are problems that are much harder to solve in one direction compared to the other.

Symmetric ciphers don't provide absolute security. In theory, someone could derive the private key from the public key. But in practice that would take so much computational time that, by the time they accomplished that, we would no longer care about the long-outdated secrets protected by that private key.

Sorry, but we need just a little grade-school-level number theory here.

To factor a number is to figure out what you could multiply together to create it. For example:

6 is built from 2 times 3.

15 is built from 3 times 5.

Or, you could say "The factors of 6 are 2 and 3; the factors of 15 are 3 and 5."

A prime number is one for which the only factors are one and itself. 2, 3, and 5 in those above examples are all prime.

10 is not prime, because 2·5 = 10.

But 11 is prime, because 1·11 = 11 is all we can do.

5 and 19 are prime. If I asked you for their product, you could very easily calculate 5·19 = 95.

But what if I asked you for the two prime factors of 91? What times what equals 91?

Look, 91 is a little smaller than 95, and you calculated that quickly. What's taking so long?

Or maybe I asked you about the prime number 11. What is 11 times 11?

You could quickly calculate 11·11 = 121.

So, what are the two prime factors of 119? What times what equals 119? Other than 1·119, of course! Again, this new challenge is a little smaller than the number you just calculated by multiplying. This should be easy, right?

Well, no. Factoring is a trapdoor function. As you just saw with 2 and 3-digit numbers, factoring is much harder than multiplying two prime factors together.

Computers can quickly multiply integers, even very large ones. Multiplying two 300-digit prime numbers together to calculate their 600-digit product actually runs pretty quickly on a computer.

But starting with the 600-digit product and working back to discover the factors would take an enormous amount of time.

The security of the RSA cipher is based on the difficulty of the factoring problem. The simplified explanation is that the public key is that 600-digit product, and discovering the private key would require finding its 300-digit prime factors.

Those would be the approximate numbers for a 2048-bit RSA key, as:
2²⁰⁴⁸ ≈ 3·10⁶¹⁶
Double them for a 4096-bit RSA key, as:
2⁴⁰⁹⁶ ≈ 1·10¹²³³

Building A Better Trapdoor

Math using multi-hundred-digit numbers runs faster than you would likely expect, but it does take a while. Elliptic curves provide a different trapdoor function that provides equivalent security with smaller keys and much faster operation.

The NSA said in 2015 that U.S. Government Top Secret data could be protected by:

• AES symmetric encryption with a 256-bit key
• RSA asymmetric encryption with at least a 3072-bit key
• Elliptic-curve asymmetric encryption with a 384-bit key

Actually, with RSA it's a 3072-bit modulus and with ECC it's a 384-bit curve definition, but close enough.

It's time to:

Investigate: What are elliptic curves