# 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:

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^{2048} ≈ 3·10^{616}

Double them for a 4096-bit RSA key, as:

2^{4096} ≈ 1·10^{1233}

## 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: