Introduction to Cryptography: Part 1
Hello everyone! Welcome to part one of cryptoeconomics.study’s three part introduction to cryptography!
You don’t have to be a hardcore math or cryptography expert. The goal is to get a flavor of what kind of tomfoolery goes in to all this magic! You won’t be able to make these dishes on your own after this chapter but you will gain a high level understanding and a deep appreciation for the mechanics of it. Those who want to dive really deep will be provided with a list of recommended resources at the end of each part. A background in mathematics will be very helpful but not necessary to understanding the following content.
Part 1) Cryptography 101
Part 2) Digital Signatures
Part 3) Attacks
In this post, we’re going to go over some foundational concepts in cryptography, get a taste of number theory and group theory by going through how public key cryptography works.
In part 2, we’ll look through a thoroughly commented implementation of digital signatures so those who don’t code can follow along as well. We’ll also examine other common signature types used in cryptocurrencies.
In part 3, we will hammer home the lesson of “don’t roll your own crypto,” by examining some fantastically obscure and potentially devastating real-life cryptography bugs by using the tools we learned in part 1 and 2.
What is Cryptography?
The word itself is derived from the Greek roots for “hidden” and “writing”. Cryptography is a tool that allows us to achieve a number of information security objectives. There are four main goals of cryptography:
- Integrity: The message I send will arrive at its intended destination intact and unchanged.
- Authenticity: I can ascertain that the sender and the recipient of the message are the correct ones.
- Non-repudiation: An event that has taken place cannot be denied.
- Confidentiality: That which is intended to be private will be kept private.
Public Key Cryptography
Public Key Cryptography is also known as asymmetric key cryptography, due to the use of a pair of keys — one that is private (a secret key, sk) and one that is public (a public key, pk). The public key is generated from the secret key (we will call it secret key because later on, it will be easier to distinctly abbreviate public key as pk and secret key as sk).
Public key cryptography allows you to encrypt a message using somebody’s public key and broadcast it to the whole world… in a way where it can only be read by the person who has the secret key corresponding to the public key used to encrypt the message.
Additionally, one can use a secret key to sign a message, and the recipient of the message can use the sender’s public key to verify the signature. Let’s take a look at how this all works, starting with the concept of ‘key exchanges’!
Diffie-Hellman Key Exchange
In the early 1900s, a man named Arthur Scherbius developed a machine called the Enigma machine. It allowed people to send scrambled messages and soon, the German military was mass producing Enigma machines for secure communications during World War II. The only problem with the Enigma machine was that in order to decipher the encrypted messages, you needed the decryption key, or the secret key… but there was no way to transport this secret key securely. If the secret key was intercepted by malicious adversaries, then Enigma communications were pretty much kaput.
Hope is on the horizon: in come Whitfield Diffie and Martin Hellman, who took Ralph Merkle’s conceptualization of a method to transmit secure information over insecure means. This method, dubbed Diffie-Hellman key exchange, is popularly explained with a color-mixing analogy, as follows. (Skip past these images if you want to get straight in to the ~*MATH*~)
Alice and Bob want to share a secret with each other so later they can use the same secret to encrypt and decrypt messages with each other. However, they want to transmit this secret securely — so securely that they can do it over a public channel without the secret getting leaked. So, they each choose a secret color.
Together, they agree on a common color that will act as a carrier for their secret colors. They will mix the common color with their secret colors.
Combining the colors is key to being able to transport it safely, because separating colors is very difficult and very expensive.
Now, Alice can send Bob her mixed color, and Bob can do the same. It’s ok if other people see these mixed colors. They won’t be able to separate out the secret, even if they know what the common color is.
Next, Alice will combine her secret color with Bob’s mixed color and Bob will combine his secret color with Alice’s mixed color:
The resulting color is a combination of Alice’s secret, Bob’s secret, and the common color. As long Alice doesn’t leak her individual secret and Bob doesn’t leak his either, then they now both share a secret color..
Now they can encrypt and decrypt messages to each other with this shared secret key!
The Math-y Explanation
No math background required! All you need to know is how multiplication and exponents work.
The starting color should be kept a secret, but it is assumed that it can be leaked. In practice, this “common color” is actually two numbers, p and g that Alice and Bob agree to beforehand. p is used as the modulus, and g is the base. (A modulus is a point at which a number wraps around itself. You can think of it like a clock, which is “mod 12”. There are 12 numbers on a clock, but the day has 24 hours, so the 13th hour of the day is 13 mod 12, which is congruent to 1. As such, we often represent the time 13:00 as 1:00). The p and g that are chosen must satisfy the following conditions:
- p and g are coprime, meaning that their greatest common divisor is 1.
- g is a primitive root modulo p which means that for every number a that is coprime to p, there exists an exponent x where g^x mod p is congruent to a mod p that cycles through periods of arrangements of all the remainders modulo p.
The primitive root modulo n, along with other number theory concepts you will learn later, are important because grouping numbers together with elegant characterizations allows us to generate concise proofs and calculations. The above characteristics enable us to easily manipulate these numbers into a result that is difficult to reverse engineer, in the same way that the colors in the color mixing example are difficult to separate.
By doing our math over finite algebraic structures we 1) prevent our outputs from blowing up in size, and 2) prevent the length of our outputs from revealing information about the inputs.
We’ll use some very small numbers to demonstrate this math. In practice, these numbers are enormous so that brute forcing the inputs becomes computationally infeasible.
Let’s say Alice and Bob agree to p = 7 and g = 3. (It’s ideal for these values to stay secret but we will show that this works even if a malicious adversary gets ahold of them).
Quick check: do these numbers fulfill our above requirements?
- Coprime? The greatest common divisor of 7 and 3 is 1. Check.
- Primitive root? 3 is a primitive root modulo 7. Check!
3⁰ mod 7 ≡ 1 mod 7
3¹ mod 7 ≡ 3 mod 7
3² mod 7 ≡ 2 mod 7
3³ mod 7 ≡ 6 mod 7
3⁴ mod 7 ≡ 4 mod 7
3⁵ mod 7 ≡ 5 mod 7
Alice and Bob each pick a secret value, represented in the above diagram by the secret color and then “mix” this with the common colors (p and g) to generate the public value.
Bob undergoes this same process to generate his public value B from the secret value he selects b = 8:
Alice and Bob each calculate the shared secret, s, by taking their own secret values and combining it with the public values shared by the other person.
Woah! Both Alice and Bob now have the same shared secret. A spying adversary who has the all of the values p, g, A and B would have to brute force guesses of a and b in order to find the shared secret. When our values are large enough, this brute force guessing becomes computationally infeasible.
Why does this work?
Remember our earlier requirements for the characteristics of p and g? Those characteristics allowed us to generate a multiplicative group. In formal terms, we would call g the generator of the multiplicative group modulo p, and in the cases that p is a prime, we get the cyclic characteristics demonstrated in step one. We call this group multiplicative because the elements of the group are identified through multiplication. This means that two elements of the group combined with the group operation (multiplication in this case) form a third element of the group.
This group of integers also counts as an abelian group meaning that the group operation (in this case, multiplication) performed on two elements of the group is agnostic to the ordering of those two elements:
This is important because Alice and Bob want to achieve the same result, although their order of operations differ — Alice is taking g to the power of a first, whereas Bob takes it to the power of b.
Don’t strain *too* hard to remember this but it will be helpful later in part 3, when we examine some cryptography bugs in cryptocurrencies.
Thanks for reading!
Stay tuned for Part 2: Digital Signatures
For more educational fun, visit https://cryptoeconomics.study
I’d like to thank everyone who contributed to part 1: Matthew Di Ferrante, Vitalik Buterin, Karl Floersch, Kelsie Nabben, Sophia Sokolowski and Hanna Hayden!