how elliptic curve cryptography ecdh kindof works:

i wrote this because people often ask me how cryptography works, and i wanted a simple answer using 3rd grade math

you and me want to talk privately, but we can only talk in a public

so what we do is we both agree on a prime number

in real life we’d use a very big prime number, but for fun we’ll choose the number 17 (this is called the “prime order”)

then we choose a “public point”, anywhere between 2 and 17, we call this the “generator”

in real life, this is actually a complex point with an x and a y axis, but lets ignore that for now and get back to it later

we pick a public point “7”

anyone listening can hear these two things, and it doesn't matter

then we both pick a secret between 1 and 17 and we don’t tell each other what it is

then we multiply our secrets by the public point, divide by 17 and tell each other the remainder

the remainder is our public key

we don’t tell anyone the secret stuff (in parentheses for secrecy)

(my secret is 4, 4x7=28, the remainder is 11)

i announce my public key is 11

(your secret is 8, 8x7=28, the remainder is 5)

you announce your public key is 5

nobody knows our secret keys, only our public keys. they can’t actually figure out our secret keys easily.

(figure out how to guess they my secret is 4, given only the knowledge of 11 (public key), 7 (generator) and 17 (prime order) ? it requires a complex thing called a modular inverse, which, when operating using elliptic curves, is very hard. it also requires some effort to figure out even without them. try it!)

cool, now i take my secret and multiply it by your public key, taking the remainder, i get 3 (4 * 5 = 20, 20 – 7=3)

then you take your secret and multiply it by my public key (8 * 11 = 88), divide by 17 and take the remainder, you also get 3!

in fact, no matter what numbers we start out with, we will always agree on this shared secret key

and, as long as we’re operating using sufficiently complex “multiplication” there’s no way for someone to guess the shared secret key without knowing one of the private keys, or just guessing at them all

so without once announcing our private keys we got to arrive at a shared secret

the number 3

we then use this key encrypt our messages, using some traditional encryption system (in the spirit of this article, we could make a similarly simple symmetric encryption system, but that’s a bit much right now)

now back to elliptic curves

it’s actually not that hard to figure out someone’s secret using the scheme above, but if the private key is a very very large number, instead of a small one, and if the thing we multiply by is an elliptic curve point… well then it is very hard

here’s what an elliptic curve looks like when we’re not taking the remainder:

that looks like something that a mathy person can figure out how to divide and multiply by

but here’s what it looks like when you do take the remainder:

there are a large number of complicated graphs and techniques that people have experimented with “multiplying by”, and “taking the remainder of. ”

modulo-elliptic curves are one of them, and they’re popular because no one has ever figured out a better way to calculate the private key knowing the public key, other than just “trying them all”. this is often called the “discrete log problem”

and if we use numbers are big enough (think a 1 with about 40 zeroes after it), it will take zillions of years for all the computers on earth to guess them all