eli5: what do elliptical curves have to do with cryptography?
In: Mathematics
I’m not a cryptographer so I’m probably gonna butcher this, but hey it’s reddit, let’s go.
what you want for public key cryptography are two related numbers, a private one which can be chosen at random, and a public one that can be easily derived from the private one. however, it must be near impossible to derive the private number from the public number, otherwise it’s all pointless.
the idea is that you can give your public number to anyone, and they can use it as a key to encrypt some data to send to you. the data can only be decrypted using your private number as a key, which you never give out.
how these two numbers are related is critical. what you’re looking for are elliptic curves (not elliptical). these curves are graphed, like a line graph. between a certain range, you can choose an x value and read off a positive or negative y value. this will make much more sense if you google a diagram.
the nice property for some of these curves, is that if you choose an arbitrary x value, and get the slope of the line at that x value, you can extend that slope and it points to one other location on the curve. it’s very hard to go backwards, there’s no formula, you basically have to search “could this x location have pointed here”.
it’s not *too* difficult, however, so what you do is you choose your x value, find the slope, find the intersection of her slope with the line, then *invert* the y value, find the slope at that point, find where that slope intersects with the line again and so on. doing that a few thousand times is very very fast with a computer. however, if you do enough iterations, going back that other way would take billions of years even if you used all the computers in the world.
there’s other obfuscations they employ too, such a chopping the curve up into tiny segments and rearranging them, etc.
what you end up with, is your first x value, which you chose pretty much at random, and your final x’ value, which is derived from x, but you can’t go from x’ to get x.
then they use some maths that’s beyond me to combine those values into a multiplication that you apply to your data to do the encryption, such that anyone can encrypt data with x’, but only x can be used to decrypt it.
Many cryptographic schemes use arithmetic to conceal information. For instance, if you and a buddy share a secret number (say, 803) and you want to securely tell them your credit card pin (say, 3829) then you can just tell them 4632. They can subtract the shared number to retrieve the actual pin but no one else who sees the message really can.
Real cryptographic schemes are more sophisticated and work differently but the important thing is that arithmetic structure – like addition and multiplication – can be used to encode information.
The RSA cryptosystem is a widely used one and it relies on “modular multiplication” to encode things. This is an arithmetic operation which is uses a base reference number to switch things up a bit. This base number is the product of two prime numbers and the security of the RSA algorithm is due to the fact that it is hard to factor such numbers.
Elliptic curves are very important objects in math and number theory. This is because if you have two points on an elliptic curve then you can create a third point in a natural way. That is, elliptic curves have their own unique arithmetic on them. And this arithmetic is, in ways, fundamentally more complex than addition and multiplication so they see quite a bit of attention in math to unlock their secrets.
For cryptography, however, this gives more options for arithmetic to encode things and so we have things like Elliptic Curve RSA Cryptography. Now we might think that elliptic curves are just more secure than ordinary RSA, but what happens is that the sophistication of elliptic curve arithmetic is to encode things more effectively using less space. If you would need a 512-bit key in regular RSA cryptography, then you could get the same security with something like a 64-bit key in elliptic curve cryptography. This results in speed and space saving security measures.
—
Elliptic curves have been used in other fundamentally different ways. There was a proposed post-quantum algorithm, a cryptosystem that would remain secure even under attacks from quantum computers, which used exotic features of large collections of very special elliptic curves laid out in a net to encode things as paths between different curves. It was a pretty cool algorithm but, unfortunately, a classical (non-quantum) algorithm was found that cracks it. But, ultimately, cryptographers and number theorists and modern geometers are all interested in elliptic curves because of their elevated arithmetic sophistication.
Latest Answers