Build the future of communications.
Start building for free

What is Public Key Cryptography?

19DfiKodi3T25Xz7g9EDTyvF9di2SzvJo6JebRJaCN-1P_c1fMqGtrAyZzxGGucG0bcmR8UwNes-gSQUhQwsHxuApvTTq6vJGYAuMkURP6LqSwKeD-QTtOv6o6RMVxADID1QkCOy

From TLS to authentication, “crypto” is used for a lot more than just currencies. In 2018, 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 modern cryptography, an overview of how it works, and its everyday use cases — including how Twilio uses public-key crypto in our Authy application 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.

symmetric-key cryptography

This is known as symmetric-key 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 asymmetric, or public-key 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 you don't want anyone else to read.

Bob encrypts a message with Alice's public key, then Alice decrypts the 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 message with her private key, then sends the message to Bob. Bob decrypts the message 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:

How Twilio Uses Public-Key Cryptography

authy push authentication

Authy Push Authentication

Authy

One of the ways Twilio uses public-key cryptography is in Authy applications for push authentication (seen above). For every site you enable on Authy, your device 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 Authy app 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

PKCV

Twilio also offers Public Key Client Validation as an added layer of security for making API requests. Like Authy, 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.

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. You can follow along in python code below or find the whole script on my GitHub.

1. Pick two prime numbers:

p = 67
q = 71

2. Multiply your primes

n = p * q
# n = 67 * 71
# n = 4757

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

import math

def lcm(a, b):
   return a * b // math.gcd(a, b)

x = lcm(p - 1, q - 1)
# x = lcm(67 - 1, 71 - 1)
# x = lcm(66, 70)
# x = 2310

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

e = 23

5. Compute the modular multiplicative inverse of e:

def inverse_mod(e, x):
   t = 0
   newt = 1
   r = x
   newr = e
   while newr != 0:
       q = r // newr
       t, newt = newt, t - q * newt
       r, newr = newr, r - q * newr
   if r > 1:
       return None
   if t < 0:
       t += x
   return t

d = inverse_mod(e, x)
# d = 1607

Now we have all we need to create our keys!

public_key = (4757, 23) # (n, e)
private_key = (4757, 1607) # (n, d)

We can use the public key to encrypt a message:

message = 123
encrypted = pow(message, e, n)
# encrypted = pow(123, 23, 4757)
# encrypted = 418

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

decrypted = pow(encrypted, d, n)
# decrypted = pow(418, 1607, 4757)
# decrypted = 123

...which gives us the original message! 🤯

Public Key Cryptography Algorithms and Key Size

public key cryptography joke

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

RSA

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, one of the most common algorithms used for public-key cryptography. You've probably used it if you've ever generated a GitHub SSH key, for example:

ssh-keygen -t rsa -b 4096 -C "your_email@example.com"

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 DiffieHellman method works.

diffie-hellman key exchange

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 cryptography

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.

Authors
Sign up and start building
Not ready yet? Talk to an expert.