This article was kindly provided by www.goodbit101.com
As the name suggests, cryptocurrencies rely heavily on cryptography to support network security. There are many important topics in this sphere, but three of the most important are public key cryptography, elliptic curve cryptography, and cryptographic hash functions.
Public Key Cryptography
Public key cryptography was introduced in the late 70’s, and has revolutionized the way that we communicate securely. Public key cryptography is what allows us to use digital signatures with cryptocurrency transactions. The cryptography is composed of two parts:
- The public key shared with everyone.
- The private (secret) key held only by one entity.
In reality, the public and private keys are entirely digital, and represented by strings of 1’s and 0’s. But to craft a clearer picture of how exactly public key cryptography works, let’s assume for a moment that these are real keys.
You own a super sturdy, unbreakable treasure chest. It’s bolted to the floor in your office, and it has a big lock installed on it. As it turns out, the lock on the chest is a special lock with three positions. Turning the lock to the left is position 1 (locked), turning it to the center is position 2 (unlocked), and turning it to the right is position 3 (locked). Only in the middle position is the chest unlocked.
You find a talented locksmith who makes you two different kinds of keys. One key only turns to the right, from position 1 to 2 to 3. You keep this key safe. It’s yours. It’s your “private key.”
The other key turns only to the left, from position 3 to 2 to 1. You make a ton of copies of this key and give them out to friends, family, and coworkers. It’s your “public key.”
You might get some pretty important, um, mail n’ stuff at your office building. You don’t want anyone to steal it! You come up with the idea to have everyone leave their packages and notes for you in the totally secure, indestructible chest.
“If you want to give me anything when I’m not around, put it in the chest and lock it!” you declare. Then, you put the lock into the center position (2), unlocking it.
Anyone with a public key can deposit important information into the chest and turn left (to position 1, locking the chest). However, you are the only one who can turn the lock back towards the center (your private key turns to the right).
In this system, anyone can leave you packages and lock the chest. No one besides you can unlock the chest.
This piece of our analogy gives you an idea of how public key cryptography can be used to protect sensitive information from prying eyes, while still allowing anyone to send you information.
This system has another advantage. Let’s say that rather than receiving information from others, you want to send a message to someone–and you want them to know for certain that it was you (and only you) who sent it.
You can use your private key to turn the lock on the chest all the way to the right, at position 3. This way, anyone with a public key can turn the lock to the left, back to position 2, and unlock the message. And because you’re the only person who can turn the lock to position 3, the recipient will know that it must have been you who left the message. Assuming you are the only one with a private key, only you could have turned the lock to position 3.
So, the recipient of a package will know for certain that it was you who sent it.
This process is what underlies the idea of digital signatures, which is discussed in the Mining section.
How does this apply to cryptocurrencies? Well, each crypto transaction must have a digital signature. A digital signature is equivalent to you turning the lock to position 3, because only you have the power to do that.
Public and private keys are ubiquitous in the crypto world. Everyone has your public key, and can leave things in your chest. Only you can unlock the chest and take things out. Instead of using metal keys, we use digital ones, made of long, random strings of numbers.
Public key cryptography was the basis for much of what would eventually make up Bitcoin.
Elliptic Curve Cryptography
The system of public and private keys lays the groundwork for a cryptographically secure way of transfering value or information, but first another problem must be solved. Namely, how do we stop people from determining a person’s private key from their public key?
Hopefully you now know that your private key should never be shared with anyone. So if a bad actor could find out your private key by looking at your public key, the entire system would be ruined. So how exactly are “public and private key pairs”, as they are known, generated?
Prepare for some math!
The private key generation is easy: pick a number. Any number between 1 and 115792089237316195423570985
4382605163141518161494337 (including 1, but not the big long one). Convert that to 256 bits of binary, and bam. Private key generated.
How did we arrive at that number? Private keys are 256 bits. That gives 2 to the power of 256 possible options, with a couple of numbers at the ends off limits.
At this point, you might be thinking:
Well, shoot. Private key generation is easy. Hopefully making the public key is a bit more complicated and… cryptographic-y? Isn’t this whole thing supposed to be super complex and unbreakable?
Strap in, folks. This is where the mathematicians got to have some fun, because generating a public key from a private key is both deceptively simple to do and mind-bendingly difficult to keep straight in your head.
The method used to generate a public key from a private key (remember, that’s just a number) is known as Elliptic Curve Cryptography. An elliptic curve has an equation of the form:
y^2 = x^3 + ax + b
When we plot that out, it looks something like the Lulu Lemon logo on its side, or the Greek letter omega. We can use some of the strange properties of prime numbers and this graph to generate a seemingly hopelessly unrelated value to serve as our public key.
There are two very important things about these elliptical curves:
- They are symmetrical about the x-axis, meaning they are mirrored lengthwise.
- A line drawn between any two points can be extended to intersect the curve at a third point
Ready for the mind bending part? To generate our public key, we use the following rules:
- Pick a starting point on the graph (this point is predetermined in the case of Bitcoin). In the gif this is point A.
- Draw a line to a second point on the graph, point B.
- Follow the line you’ve drawn so it intersects a third point on the graph (unmarked point when you follow B).
- Flip this point over the x axis to point C. If it was above, draw a line straight down. If it was below, draw a line straight up. Once you find this “flipped” point, cycle 1 has been completed.
- Begin cycle 2 by creating a line connecting the original starting point (A) and the new point (point C).
- Repeat steps 3-5 for n cycles.
- The final end coordinate is your public key.
How many cycles do we perform, though? The number of cycles is your private key, which is just a random number! It is likely that this process will have happened for trillions and trillions of cycles. Likely more cycles than seconds the universe has existed, by far.
The purpose of repeating this process a random number of times is to make going backwards extremely difficult. If you know someone's private key, figuring their public key is doable. If you only know their public key, it might as well be impossible.
Your public key is, well, public. You don’t care if people know what it is, unless elliptic curve cryptography is broken. What’s actually important about this process is how many cycles you perform, because that number is your private key.
This is mind-numbingly complicated math. Take it slow, and please use the form below if you have any questions!
Does your brain hurt yet? That's the point of cryptography. But, it's time to add another level of complexity.
Just to make this whole thing hopelessly unsolvable: let’s remove all of the points on the curve that aren’t whole numbers (no decimals allowed). This leaves us with a field of points, still symmetric about the x axis.
Because the curve extends infinitely (and computers tend to have a hard time with the whole infinity thing), we’re going to set the boundaries of the graph on both sides at a huge prime number, say 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 – 1.
Go back to step 3, above. If the intersection of our line with the third point on the graph doesn’t happen before we hit the boundary, we wrap back around to the other side of our range. Imagine a game of Pacman, where running off screen on one side brings you back on the other side. Eventually, we’ll hit our third point, reflect it over the x-axis, and continue our process.
So we have a complex, multistep process performed with roughly a billion billion billion billion billion billion billion billion cycles, on average. All to generate a public key from a private key. Well then.
Note that if you know the private key, figuring out the public key is doable. If you only have the public key… good luck.
Let’s imagine we’re a hacker. We know a rich person’s public key, and we want to steal all the bitcoins she has. So, we take a look at the above rules and do some digging to find the starting point of the elliptical curve (the curve for Bitcoin happens to be y^2 = x^3 +7).
We have no better way to guess how many cycles were gone through than to run through every cycle backwards, until we get to the same known starting point. And as it turns out, going in reverse is pretty darn hard. In fact, it’s hard enough that this whole process could be categorized as a trapdoor function…except it doesn’t have a trapdoor.
Oh, trapdoor functions? They’re very easy to compute in one direction given certain information, and almost impossibly difficult without this information, known as the trapdoor. The thing is, the cryptography discussed above is so efficient that there isn’t even a trapdoor for it. It’s just plain tough to go backwards, no matter how you look at it.
And by the way, our public key isn’t even what we go around giving out to people. We give out our public address, which is a hash (explained next) of the public key. Ultimately, the public key will need to be revealed if you spend money from an address, so that miners can verify your digital signature of the transaction.
But until then, you have not one, but two layers of near impenetrable security. And if you wanted, you could then transfer the remainder of your funds to a different address to reestablish the second layer of security (your hidden public key). In fact, many wallets do this for you by default.
Let’s review. We generate a private key at random. We use a ridiculously complicated system to figure out the public key. We hash the public key to get a public address, which is where people can send you bitcoins.
The bottom line is… this stuff is pretty darn secure, right now. Quantum computing will undoubtedly change things, but the Bitcoin protocol is open source. Thus, the encryption methodologies and protocols can be updated as attackers become more sophisticated.
Cryptographic Hash Functions
We mentioned at the end of the last section that our public keys are hashed to produce public addresses. Hashing also plays a critical role in mining blocks, and in the creation of our digital signatures, used to sign off on transactions. So what exactly is a cryptographic hash function, anyway?
They are complicated math-y instructions designed to produce outputs that are seemingly unrelated to their inputs, making it impossible to determine the input from the output. For example, if you enter the number “1” into a hash function, it would return an output of 1’s and 0’s that appears completely unrelated. The same would happen if you entered “3”– and importantly, the hash output from “1” bears no correspondence to the output from “3.” The outputs mirror randomness.
Honestly, that sums it up pretty well. When we hash something, we make it incredibly difficult to go backwards. However, plugging something into a hash function is quick and easy, and importantly, it is consistent. If you plug the same number into a hash function multiple times, it will produce the same result each time.
Hashing is used both in mining and in public address generation.
To wrap up our this section on cryptography, we’d like to take a second to really look at the large numbers we’ve been tossing around.
SHA-256 has 256 “bits”–1’s or 0’s. Meaning 2^256 possible combinations.
The truly mind boggling enormousness of 2^256 can’t be fully appreciated on any scale we, as humans, are familiar with. 2^256 is more atoms than there are in the observable universe. 2^256 is way, way, WAY larger than the number of miliseconds that the universe has existed. It’s stupidly, unimaginably big.
However, it implies something very important: 2^256 is so large that every person on Earth could generate a million private keys without checking against the network to see if they are already taken. The odds of a “collision,” or two people randomly generating the same private key, is so unbelievably small that we can assume it will never happen.
Is it mathematically possible? Yes. Is it likely? It’s so unlikely that we can assume it is impossible.
This is has important implications–when you want to create an “account” on the blockchain, you don’t need to check if the number you chose for your private key is the same as anyone else’s number.
This property allows us to generate private and public keys offline as long as we have the cryptography protocols loaded onto some hardware, making it impossible for a hacker to steal your private key through your internet access. This is the basis of cold storage, which we discuss further in the Wallets section.
If you want to further investigate the specific cryptography standards utilized by the Bitcoin protocol, “secp256k1” is a good place to start!