Exchanging Asymmetric Keys

00:00 In the previous lesson, I improved the Flask server to use Fernet ciphers, making it secure. This introduced the problem of key management. In this lesson, I’ll be talking about asymmetric key exchange—one possible solution to this problem. Key management is hard.

00:18 You have to make sure that your keys stay secret. Asymmetric encryption uses a pair of public and private keys. Using this pair, others can encrypt private messages for you using your public key.

00:31 Only you will be able to decrypt the message.

00:34 Asymmetric encryption is expensive. Rather than use it all the time, you can use asymmetric encryption in order to exchange a symmetric key. The asymmetric encryption mechanism guards the creation of a secret key, and then you can continue to use the cheaper symmetric encryption using this generated key.

00:56 There’s some rather complicated math involved in asymmetric key exchange. Instead of starting with the math, I’m going to use an analogy. Let me introduce you to Alice and Bob.

01:06 It’s a longstanding tradition in cryptography to have Alice and Bob be the names of the people who are communicating. Both Alice and Bob have private keys.

01:15 What’s trying to be prevented is an eavesdropper from being able to see their communication. When Alice and Bob start their connection, they agree on a shared color. This is done in the clear, so a bad actor can see the shared color. Everyone has a copy of it.

01:32 Both Alice and Bob then use their private keys and combine them with the shared public key.

01:43 This generates a combined color.

01:46 They exchange the combined colors and this, of course, is still public. The eavesdropper can now see the shared public color and both Alice and Bob’s combined colors. Because this kind of encryption is done using a one-way function, it’s very, very hard to figure out Bob or Alice’s private key given the information the eavesdropper has access to.

02:09 If you think of Alice’s green or Bob’s orangey-brown there, the number of combinations of shades that could have been used to combine those is rather large.

02:19 Bob and Alice use their combined keys in conjunction with the combined color from before, and because they know their own private key, they can generate a shared secret key that turns out to be the same color as the other person’s.

02:34 This shared secret key is not broadcast. The eavesdropper has no way of figuring out what it is. This shared secret key can now be used for symmetric encryption that both Alice and Bob can decrypt using that shared secret. The HTTPS protocol both encrypts traffic and offers verification of site identity.

02:58 The authentication piece uses something called Public Key Infrastructure. This is a fancy way of saying certificate management. Cryptographic certificates act like a person’s signature, signing the identity of the site. Each certificate has three properties.

03:14 It describes who it was issued to, it describes who issued the certificate, and it describes a period of validity—a timeframe within which the certificate is valid.

03:27 These certificates are issued by a Certificate Authority. This is referred to as a Trusted Third Party. The idea behind a Trusted Third Party is two strangers who both trust the same party can use that trust to verify the identity of the other stranger.

03:44 The Certificate Authority is responsible for verifying the identity of each person it issues a certificate for, and then issues them a certificate. This is kind of like a passport issuing office. To get a certificate, you would have to create a Certificate Signing Request—this is like filling in your passport application form.

04:04 You send the Certificate Signing Request to the Trusted Third Party, like submitting your passport application to the government. The Trusted Third Party then verifies your information.

04:15 In the case of a passport, the office looks you up. If you pass this, the Trusted Third Party generates a public key. This is like the passport office signing your passport. Finally, the CA issues the public key to you.

04:29 This is you receiving your passport in the mail.

04:33 When you generate a Certificate Signing Request, you do it based on your private key. The public key issued by the Trusted Third Party is related to the Trusted Third Party’s keys and your private key.

04:46 This creates a chain of trust. The certificate can now be verified by asking the Trusted Third Party. It’s usually the website owner who is responsible for creating the CSR and dealing with the CA. Different CAs have different rules about how to verify your identity.

05:02 You need a certificate from one of these CAs in order to host a website using HTTPS. Each signed certificate states the date and time the certificate becomes valid, the date and time the certificate stops being valid, the name of the server owning the certificate—i.e.

05:22 the website—and the name of the issuing Certificate Authority.

05:27 There are dozens of CAs. Some common ones are AffirmTrust, Amazon, certSIGN, DigiCert, Mozilla, and VeriSign. Each of the browsers ships with their own list of trusted CAs.

05:40 If you dig deep into Firefox or Chrome settings, you can actually find a list of the Certificate Authorities that those browsers trust. If you visit a website that has a certificate that is expired or is issued by a CA that’s not in your trusted list, you will see an error.

05:57 Now, it’s time for a mathematically complicated tangent. If math stuff bores you, feel free to skip on to the next lesson. You won’t miss anything.

06:07 Still here? Glad to see it. I’m going to talk about the math behind RSA and how it works. RSA is one of the first public-key encryption systems. The letters stand for the names of the people who created it. This is an expensive algorithm, so it’s usually only used for the creation of symmetric keys.

06:26 SSL and early versions of TLS used RSA for the key exchange. The latest version of TLS has dropped it. Asymmetric encryption is typically based on a one-way problem—something that’s easy to do, but hard to undo.

06:41 RSA uses multiplication. Multiplication is simple for a computer to do. Factoring large numbers is hard and expensive.

06:50 The math behind RSA is based on something called modular congruence. Modular arithmetic involves integer division and what is left over if two integers don’t divide into each other cleanly.

07:03 For example, 40 is congruent with 4 (mod 12). Another way of saying that is 40 / 12 = 3 remainder 4.

07:14 Or coming at that from another way, 12 goes into 40 3 times, giving you 36, and the difference between 40 and 36 is 4, which is the remainder.

07:26 RSA uses a property of prime numbers and modular arithmetic that states that you can have three numbers—e, d, and n—such that for all integers m, where m is positive and less than n, m to the power of d to the power of e is congruent with m (mod n). Don’t worry if this isn’t immediately obvious. I’m going to run you through some examples.

07:54 Let’s say you’re trying to encrypt the letter B. First off, you have to translate that into a number. Since B is the second letter of the alphabet, I’ll represent it with the number 2. Assume that Alice has a public key consisting of the numbers 5 and 14 and a private key of 11 and 14.

08:14 Don’t worry about where these come from, yet. I’ll go over that later. Bob, knowing Alice’s public key, can encrypt a message using just 5 and 14.

08:25 Here’s how he would do that. You take the value being encrypted—in this case, the number 2—raise it to the first part of the public key, which is 5. And then do mod(14) on the result. 2^5 = 32, mod(14) = 4. The encrypted value is 4. When Alice receives the number 4, she can decrypt it using her private key.

08:51 She does this by running the same process, using her private key. Take the value being decrypted, 4, raise it to the power of 11, and then do mod(14). You’ll probably need a calculator for that one, but it turns out to be 2—the original value.

09:07 So, Bob has encrypted a message for Alice—not knowing her private key, only knowing her public key—resulting in 4. And Alice has been able to decrypt this message using her private key.

09:21 So, where did the 5, 11, and 14 come from? Well, here’s some more math for you. First off, you need to choose two prime numbers. I’m going to call them p and q. The n from the original equation is p * q.

09:37 You also need a value called L, for the length. This is (q - 1) * (p - 1). This length is actually the number of values between 1 and n with no common factors with n. The (q - 1) * (p - 1) is a shortcut formula for determining this value.

09:58 Let’s choose the prime numbers 2 and 7 for p and q. n is 2 * 7, which is 14. Here are all the numbers between 1 and 14, inclusive. Crossing out those numbers that have factors in common gives you six numbers left. 14 factors into 2 * 7. 1, 3, 5, 9, 11, and 13 have no factors in common with the factors in 14.

10:28 So you’ve got p, q, n, and L, so far. To generate the public encryption key, you need a number between 1 and L, and it has to be coprime with L and n.

10:42 Coprime means the highest common factor between the numbers is 1. They’re not multiples of each other. The values between 1 and 6 are 2, 3, 4, and 5. L is 6, and n is 14.

10:58 6 is 2 * 3, and 14 is 2 * 7. This means 2 and 4 both have common factors—they’re in 6 and 14—and 4, which is 2 * 2, also has common factors—the number 2. By subtracting the common factors, what you’re left with is just the number 5.

11:19 Hence, the public key is 5 and 14.

11:23 How about the private key? Well, you’ve already got the value of n = 14. The decrypting value must satisfy the following: D * e mod(L) must equal to 1. e is the number from the public key, 5. L is 6.

11:41 So you’re looking for a number D that satisfies this equation. 11 happens to be one such number. 55 mod(6) = 1. It is possible to have multiple valid values for D.

11:55 This makes guessing the key that much more difficult. In real life, p and q are chosen as very large prime numbers. RSA key values typically are 2048 bits, or 256 characters long.

12:10 That’s a big number. As computers have gotten faster and faster, it’s become easier and easier to brute force this algorithm. Historically, RSA used a fewer number of bits. It’s currently anticipated that 2048 bits will be enough to be secure until about 2030.

12:28 Because that’s not that far in the future, TLS 1.3 is dropping RSA for a different asymmetric key exchange mechanism.

12:36 Whether or not it’s RSA, the principles are the same. You need a one-way math function, something easy to do, but hard to undo.

12:45 Well, that was some deep math. You probably deserve a break. Go get a coffee. Next up, I’m going to discuss what’s involved in becoming a Certificate Authority.