What is Public Key Cryptography?

What is Public Key Cryptography?

From TLS to authentication, “crypto” is used for a lot more than just currencies. Security should be part of every developer's toolkit and cryptography a fundamental building block for the libraries and tools we use to protect our data and applications. This post will dive into public key cryptography, also known as asymmetric cryptography, an overview of how it works, and its everyday use cases — including how Twilio uses public-key crypto in our Verify API and to secure our API.

Let's start with some context and history.

Meet Alice and Bob

Alice and Bob have a history of illicit dealings. We're not really sure what they're up to, but they don't want us, or the ever-curious Eve, to know. Before the internet, Alice and Bob could pass secret messages by encrypting text with an agreed upon cipher. Maybe that was through letter substitution or shifting or other sophisticated methods. They agreed on the method in advance and both knew how to encode and decode the end message.

This is known as symmetric cryptography — the same key is used in both directions. This worked well for World War II spies, but what happens when our secret messengers can't agree on the key in advance?

We invented public-key, or asymmetric, cryptography so that two people like Alice and Bob could communicate securely without meeting first to agree on a shared encryption key or risk an eavesdropper like Eve to intercept the key over unsecured communication channels. This is an incredibly necessary advancement because of the internet — we are no longer only transacting and communicating with people we know and trust.

What is Public Key Cryptography?

In public-key cryptography, also known as asymmetric cryptography, each entity has two keys:

• Public Key — to be shared
• Private Key — to be kept secret

These keys are generated at the same time using an algorithm and are mathematically linked. When using the RSA algorithm, the keys are used together in one of the following ways:

1. Encrypting with a public key

Use case: sending messages only the intended recipient can read.

Bob encrypts a plaintext message with Alice's public key, then Alice decrypts the ciphertext message with her private key. Since Alice is the only one with access to the private key, the encrypted message cannot be read by anyone besides Alice.

2. Signing with your private key

Use case: verifying that you're the one who sent a message.

Alice encrypts a plaintext message with her private key, then sends the ciphertext to Bob. Bob decrypts the ciphertext with Alice's public key. Since the public key can only be used to decrypt messages signed with Alice's private key, we can trust that Alice was the author of the original message.

These methods can also be combined to both encrypt and sign a message with two different key pairs.

Use Cases of Public-Key Cryptography

Public-key cryptography is used in a lot of scenarios:

• SSH
• TLS (HTTPS, formerly SSL)
• Bitcoin
• PGP and GPG
• Authentication
• Public Key Infrastructure (PKI) used for things like SHAKEN/STIR

How Twilio Uses Public-Key Cryptography

Push Authentication

Verify Push API

One of the ways Twilio uses public-key cryptography is with the Verify Push SDK and API for push authentication (seen above). The Verify SDK generates a new RSA key pair on your device and only sends the public key to our servers — your private key never leaves your device. When you "Approve" or "Deny" a request on your device, the Verify API validates:

• That the request comes from the sender who is in control of the private key
• That the authorization request has not been modified in transit

SHAKEN/STIR

SHAKEN (Signature-based Handling of Asserted information using toKENs) / STIR (Secure Telephone Identity Revisited) is a new industry standard to combat call spoofing and be able to track down spam callers more effectively. SHAKEN/STIR uses a public-key infrastructure with centralized Certificate Authorities (CAs) similar to how TLS is managed. With this technology, Twilio will sign your calls to add authentication. Learn more about enabling SHAKEN/STIR.

PKCV

Twilio also offers Public Key Client Validation as an added layer of security for making API requests. When you send a request with Public Key Client Validation, Twilio validates:

• That the request comes from a sender who is in control of the private key
• That the message has not been modified in transit

You can read more about PKCV and how to implement it here.

How Does Public Key Crypto Work? Trapdoor Functions for Security

Think about mixing together two paint colors: it's simple to combine them, but challenging to factor back out into the original colors. We see this idea all the time in physical security: things like zip ties, locks, tamper proof screws, sealed packages, and more. It's possible to undo these things without detection, but it's difficult enough that most people don't take the time or money to try. Cryptography relies on the same principle, using calculations that are easy to do in one direction and really hard to reverse unless you have a key. We call these trapdoor one-way functions.

One way we achieve this in digital security by using really large prime numbers and multiplying them together. It's easy for a computer to compute the product of two 600-digit prime numbers, but really hard to take the result and find its factors.

Your Challenge: find the two prime factors of 4,757

There are a few ways to do this, including brute force trial and error. For a 4-digit number you could write a script that loops through known prime numbers, but once that target number becomes 1000 digits long that's going to take a long time.

Your Next Challenge: multiply 67 and 71

Now that is much easier!

Your Final Challenge: let's build a key pair together! Don't worry, we'll walk you through this one. The numbers we use in our example are intentionally small.

Note: this example is for instructional purposes. Please don't roll your own cryptography for your application!

This example uses the RSA algorithm, one of many options for calculating key pairs for asymmetric encryption. You can follow along in python code below or find the whole script on my GitHub.

1. Pick two prime numbers:

2. Multiply your primes

3. Find the least common multiple (lcm) of p -1 and q -1

4. Pick a number less than x that is not a divisor of x:

5. Compute the modular multiplicative inverse of e:

Now we have all we need to create our keys!

We can use the public key to encrypt a message:

And we can use the private key to decrypt the message:

...which gives us the original message! 🤯

Public Key Cryptography Algorithms and Key Size

https://twitter.com/kayandrae07/status/1042026591856017408

RSA (Rivest–Shamir–Adleman)

The example showed how these trapdoor one-way functions are incorporated into common cryptography algorithms. Most of our explanation so far has focused on RSA, named for the researchers Rivest, Shamir, and Adleman, and one of the most common encryption algorithms used for public-key cryptography. You've probably used it if you've ever generated a GitHub SSH key, for example:

This is how you generate an RSA key pair for real. Let's break down what's happening in this command.

ssh-keygen is a command included in MacOS and Linux (and in Git Bash for Windows) used for "authentication key generation, management and conversion."

-t rsa tells it to use the rsa algorithm. Other options include dsa (Digital Signature Algorithm) and ecdsa (Elliptic Curve DSA).

https://xkcd.com/538/

-b 4096 specifies the key size in bits to use. Key size impacts the security strength, measured in bits of security. Security strength is "a number associated with the amount of work (that is, the number of operations) that is required to break a cryptographic algorithm or system" according to the NIST Recommendation for Key Management. For example, an RSA key size of 2048 gives 112 bits of security while a key size of 3072 gives 128 bits of security.

The current NIST recommendations for RSA is to use at least 2048 bits for your key. These recommendations take into account advancements in hardware and computation power, so if you want your keys to be secure past 2030 NIST recommends 3072-bit encryption.

Once you run this command on your computer, you'll have two files: a public key and a private key. It's important that you do this on your own computer so that you only have to copy the public key to GitHub's servers. Now, every time you push code to GitHub, it signs the request with your private key, which GitHub authenticates by using your public key. Note: ssh authentication is different from signing git commits, which uses GPG, another form of public-key cryptography. It's everywhere!

Other common algorithms you might encounter include:

Diffie–Hellman

This is the foundation for public-key cryptography. The Diffie–Hellman approach involves two people building a shared secret key together. It's pretty neat. Here's a great video that explains how the Diffie–Hellman method works.

Elliptic-Curve Cryptography (ECC)

This has gained a lot of recent traction because the Elliptic Curve DSA algorithm can achieve the same level of security as RSA but with smaller key sizes. ECC is also what cryptocurrencies like Bitcoin use. I like this explainer for how ECC works if you want to learn more.

Elliptic Curve Addition (Image By SuperManu [GFDL or CC BY-SA 3.0], via Wikimedia Commons)

Cryptography in Your Applications

As a general rule, you should never roll your own crypto. Use libraries that implement well-accepted encryption schemes like RSA. If you're building common security workflows, like login, most major frameworks will already have encryption built-in.

Now that you have some security fundamentals under your belt, it might be time to audit your password requirements or implement two-factor authentication. If you have any questions about cryptography, leave me a comment or find me on Twitter @kelleyrobinson.