Making Sense of Public Key Cryptography

If you write web applications (and the authentication for them) or work in the space of cryptocurrency, understanding the basics of asymmetric cryptography (also known as "Public Key Cryptography") is a must.

Whether you are authenticating users via an authentication server that issues JWTs (JSON web tokens) or you are sending cryptocurrency, there are three basic dimensions of this subject you must understand:

1. Protecting data
2. Verifying an identity
3. Certificate Authorities

How do these have anything to do with each other? In this post, I will walk through each and explain their relationships. By the end, you will have a firm understanding of basic Public Key Cryptography.

Creating a Public/Private keypair

To make this post come to life a little bit, we are going to mesh together both the theory and the actual implementations into one. For implementation, I will be using the NodeJS crypto library. Please note that I have not chosen this library because it is the best or worst, but because it is simple and easy to use.

Public and private keys come in "pairs" because they are mathematically linked. By that statement, we could say that a Private:Public key could be the following:

const privateKey = 2;
const publicKey = privateKey * 10;

Sure, these are mathematically linked, but not in the way that cryptography works. Public and private keys are mathematically linked with a one-way multiplication formula called "elliptic curve multiplication". Since elliptic curve multiplication is an entire post on its own, I will not get into the details.

Elliptic curve multiplication makes it impossible to derive the private key from the public key. With our simple example above, we could derive the private key like so:

const derivedPrivateKey = publicKey / 10;

In the real world, a private key is generated with a large, random number, and then the public key is generated by using an elliptic curve crypto algorithm. In other words, we can apply this algorithm to the private key and get the same answer (public key) every time. On the opposite end, a hacker could obtain the public key and spends hundreds of thousands of years running a powerful computer trying to figure out the private key without success.

So now that you understand how this works, let's generate a keypair. For this tutorial, I will be working with RSA keypairs, which are commonly used on the web for things like SSH authentication. There are additional types of keypairs that are not relevant to this basic discussion.

// file: createKey.js
// https://github.com/zachgoll/making-sense-of-public-key-cryptography/blob/master/createKey.js

const crypto = require("crypto");
const fs = require("fs");

function genKeyPair() {
  // Generates an object where the keys are stored in properties `privateKey` and `publicKey`
  const keyPair = crypto.generateKeyPairSync("rsa", {
    modulusLength: 4096, // bits - standard for RSA keys
    publicKeyEncoding: {
      type: "pkcs1", // "Public Key Cryptography Standards 1"
      format: "pem", // Most common formatting choice
    },
    privateKeyEncoding: {
      type: "pkcs1", // "Public Key Cryptography Standards 1"
      format: "pem", // Most common formatting choice
    },
  });

  // Create the public key file
  fs.writeFileSync(__dirname + "/id_rsa_pub.pem", keyPair.publicKey);

  // Create the private key file
  fs.writeFileSync(__dirname + "/id_rsa_priv.pem", keyPair.privateKey);
}

// Generates the keypair
genKeyPair();

The above module creates a public and private RSA key and saves both to files within the directory you execute the script from. Go ahead and run the script to generate a keypair.

# Console

node createKey.js

Your keys are generated. It's now time to see what we can do with these keys!

Protecting Data through "encryption"

With these two keys, we are capable of doing two things, depending on which key we "sign" with:

1. Encrypt data (sign with your public key)
2. Verify an identity (sign with your private key--also referred to as a "digital signature")

We will start with the function of encrypting data, because in my opinion, it is the easiest of the two.

The entire goal with encrypting data is to make it impossible for an attacker to read something that you are sending over an insecure channel. Despite most of the internet that we use communicating over SSL, it can still be considered "insecure", especially in areas where there is a lot of local traffic (i.e. a coffee shop with an open wifi network).

With a public/private keypair, we turn an insecure channel to a secure one.

Think of it like a padlock and key. Let's imagine a highly unrealistic example that will simplify this concept. My friend Jim, who lives across the country from me wants me to send him several ounces of gold that I have been storing for him. Since we will be sending it via the postal service, he's worried that it will be intercepted and tampered with. Because of this, he first sends me a small, indestructible steel box with a latch (for locking it with a padlock). He also sends me a highly secure padlock. The padlock is currently unlocked, so all I have to do is put the gold in the steel box, lock the box with the padlock, and send it in the mail.

Think of the padlock as Jim's "public key". Jim has his private key at home, which means that nobody in the world can open that box except for him (again, we assume that the padlock cannot be picked and nobody has a copy of Jim's private key).

The package travels in the mail, Jim picks it up from his doorstep, and uses his private key to unlock the gold.

If you think about it, this is exactly how data encryption works with public key cryptography.

I, the sender of data need the receiver of data's public key. I then "lock" (encrypt) the message with the receiver's public key (like locking the box with Jim's padlock). Finally, the receiver of data "unlocks" (decrypts) the message with his/her private key.

In summary, we can write the following formulas for our public key cryptography use case #1--Data Encryption:

const encrypted = encrypt(receiverPublicKey, message);

const decrypted = decrypt(receiverPrivateKey, message);

Lets take a quick look at how this is implemented in the real world. Below is the encrypt.js file where I define a function that encrypts a secret message using the receiver's public key.

// file: encrypt.js
// https://github.com/zachgoll/making-sense-of-public-key-cryptography/blob/master/encrypt.js

const crypto = require("crypto");

function encryptWithPublicKey(publicKey, message) {
  const bufferMessage = Buffer.from(message, "utf8");

  return crypto.publicEncrypt(publicKey, bufferMessage);
}

module.exports.encryptWithPublicKey = encryptWithPublicKey;

The crypto.publicEncrypt() method takes the Buffer version of our message, encrypts it, and returns a Buffer version of the encrypted message. Let's run it.

// file: main.js
// https://github.com/zachgoll/making-sense-of-public-key-cryptography/blob/master/main.js

const fs = require("fs");
const encrypt = require("./encrypt");

const publicKey = fs.readFileSync(__dirname + "/id_rsa_pub.pem", "utf8");

// Stores a Buffer object
const encryptedMessage = encrypt.encryptWithPublicKey(
  publicKey,
  "Super secret message"
);

// If you try and "crack the code", you will just get gibberish
console.log(encryptedMessage.toString());

Run the file.

node main.js

encryptedMessage is a Buffer, and if we convert it to a String, it contains characters that make no sense. We could send this data over an insecure network and be confident that no hacker could ever decrypt it.

Since we have the private key, we can decrypt it! Let's do that below:

// file: decrypt.js
// https://github.com/zachgoll/making-sense-of-public-key-cryptography/blob/master/decrypt.js

const crypto = require("crypto");

function decryptWithPrivateKey(privateKey, encryptedMessage) {
  return crypto.privateDecrypt(privateKey, encryptedMessage);
}

module.exports.decryptWithPrivateKey = decryptWithPrivateKey;

Remember, since we encrypted with the public key, we must decrypt with the corresponding private key. The above function decrypts the encrypted Buffer using the private key.

// file: main.js
// https://github.com/zachgoll/making-sense-of-public-key-cryptography/blob/master/main.js

const fs = require("fs");
const encrypt = require("./encrypt");
const decrypt = require("./decrypt");

// ==========================================
// ========= PART 1: Encrypt ================

const publicKey = fs.readFileSync(__dirname + "/id_rsa_pub.pem", "utf8");

// Stores a Buffer object
const encryptedMessage = encrypt.encryptWithPublicKey(
  publicKey,
  "Super secret message"
);

// ==========================================

// Imagine that this message is now sent over a network to another person...

// ==========================================
// ========= PART 2: Decrypt ================

const privateKey = fs.readFileSync(__dirname + "/id_rsa_priv.pem", "utf8");

const decryptedMessage = decrypt.decryptWithPrivateKey(
  privateKey,
  encryptedMessage
);

// Convert the Buffer to a string and print the message!
console.log(decryptedMessage.toString());

// ==========================================

I know the above code might seem trivial since we are encrypting and decrypting a message within the same file, but if you could imagine this happening on two different computers in two different geographical locations, you can begin to see the power of it.

Verifying an Identity through "Digital Signatures"

In the first part, we explored the first of two use cases with public key cryptography--encrypting data.

With that first use case, we can encrypt the data and ensure that only the holder of the private key can read the data, but we cannot ensure that the sender of data is who they say they are.

With our previous example, Jim is the only person that can open the box with gold in it, but anyone could have locked that box. Let's say that while Jim's padlock and box were in the mail coming to me, someone intercepted it, put fake gold in the box, locked the box, and sent it back to Jim.

Jim knows for certain that after the box was locked, nobody tampered with the contents of it, but doesn't know for sure who locked the box or what they put in the box.

In other words, encrypting data ensures that a message is not altered "in transport", but doesn't guarantee that the message was valid in the first place.

To properly identify the sender of some data, we need to use the second form of public key cryptography--digital signatures.

The primary difference to understand here is the fact that the message we are sending is not being protected in any way. In addition, the message is now being decrypted with the signer's public key.

To me, this is where things get confusing. If public key cryptography ensures that a public key can be derived from a private key, but a private key cannot be derived from a public key, then you might wonder, how can a public key decrypt a message signed with a private key without the sender exposing the private key to the recipient?

Since the answer to this is not so simple, I'll defer to a StackOverflow answer that I wrote explaining it. For the rest of this post, all you need to know is the following:

In public key cryptography, you always encrypt and decrypt with opposite keys (hence the "asymmetric" part).

In other words:

1. Encrypt with public key, decrypt with matching private key
2. Encrypt with private key, decrypt with matching public key

The components of a digital signature

Unlike basic encryption as explained in the previous section, digital signatures are a bit more complicated. The goal of digital signatures is twofold:

1. Ensure that the data sent has not been tampered with
2. Ensure that the sender of the data is who he says he is

To create a digital signature, we need the following components:

1. A hashing algorithm
2. Some data to send
3. Your private key

Before I show the code, here are the basic steps that need to happen:

1. The sender of data must take a "hash" of that data
2. The sender of data must encrypt the hashed data with their private key
3. The sender of data must send a "package" of data containing the original data, the signed and encrypted data, and the hashing algorithm used.

When the receiver of data receives the data, they will perform the following steps:

1. Decrypt the signed and encrypted data, which should represent the "hash" of the original data
2. Take a hash (using the algorithm specified) of the original data
3. Compare the value in step 1 with the value in step 2.

If the two values do not match, then you (as the receiver of data) know that either the data was tampered with, or the sender of this data is not the same person whose public key you are decrypting everything with.

If the two values do match, then you know the data has not been tampered with. You know this because the data was hashed before being sent. Since a hash function is a one-way function, if the data payload was altered in any way, taking a hash of it would equal a different result than what you decrypted from the signed data. Finally, you know that the sender of this data matches the public key you possess.

Phewww....

Let's take a look at a practical example. First, we have a module that signs a message and encrypts it. This is the "sender" of data:

// file: signMessage.js
// https://github.com/zachgoll/making-sense-of-public-key-cryptography/blob/master/signMessage.js

const crypto = require("crypto");
const hash = crypto.createHash("sha256");
const fs = require("fs");
const encrypt = require("./encrypt");
const decrypt = require("./decrypt");

const myData = {
  firstName: "Zach",
  lastName: "Gollwitzer",
  socialSecurityNumber:
    "NO NO NO.  Never put personal info in a digitally \
  signed message since this form of cryptography does not hide the data!",
};

// String version of our data that can be hashed
const myDataString = JSON.stringify(myData);

// Sets the value on the hash object: requires string format, so we must convert our object
hash.update(myDataString);

// Hashed data in Hexidecimal format
const hashedData = hash.digest("hex");

const senderPrivateKey = fs.readFileSync(
  __dirname + "/id_rsa_priv.pem",
  "utf8"
);

const signedMessage = encrypt.encryptWithPrivateKey(
  senderPrivateKey,
  hashedData
);

// This module will return the "package of data", which is what is sent over the network
module.exports = {
  algorithm: "sha256",
  originalData: myData,
  signedAndEncryptedData: signedMessage,
};

You can see that this module returns the entire "package" of data that we will send over the network. Now imagine this data was sent over some insecure network, and the receiver of the data used the following module to verify it:

// file: verifyIdentity.js
// https://github.com/zachgoll/making-sense-of-public-key-cryptography/blob/master/verifyIdentity.js

const crypto = require("crypto");
const fs = require("fs");
const decrypt = require("./decrypt");

// This is the data that we are receiving from the sender
const receivedData = require("./signMessage");

// Use the hash function provided!
const hash = crypto.createHash(receivedData.algorithm);

// We have the sender's public key here:
const publicKey = fs.readFileSync(__dirname + "/id_rsa_pub.pem", "utf8");

// ==================================
// Step 1: Decrypt the signed message
// ==================================
const decryptedMessage = decrypt.decryptWithPublicKey(
  publicKey,
  receivedData.signedAndEncryptedData
);

// By default, returns a Buffer object, so convert to string
const decryptedMessageHex = decryptedMessage.toString();

// ========================================
// Step 2: Take a hash of the original data
// ========================================
const hashOfOriginal = hash.update(JSON.stringify(receivedData.originalData));
const hashOfOriginalHex = hash.digest("hex");

// ========================================
// Step 3: Check if two hashes match
// ========================================
if (hashOfOriginalHex === decryptedMessageHex) {
  console.log(
    "Success!  The data has not been tampered with and the sender is valid."
  );
} else {
  console.log(
    "Uh oh... Someone is trying to manipulate the data or someone else is sending this!  Do not use!"
  );
}

If you run this file, you should get the success message, because we are using the correct keypair!

Seems like a lot of data to send over a network...

In our above example, you might have wondered why we are sending such a large piece of data over a network:

const dataToSend = {
  algorithm: "sha256",
  originalData: myData,
  signedAndEncryptedData: signedMessage,
};

Isn't there a more efficient way to do this?

The answer is yes, and you have just discovered the power of JWTs (JSON Web Tokens).

JWTs are becoming the de-facto method of authenticating users in web applications, and many JWTs use the method described above to transfer user data in a verifiable way. Since the purpose of this post is not to explain JWTs, I'll spare you the details, but take a quick look at the structure of a JWT:

eyJhbGciOiJSUzI1NiIsInR5cCI6IkpXVCJ9.eyJzdWIiOiIxMjM0NTY3ODkwIiwibmFtZSI6IkpvaG4gRG9lIiwiYWRtaW4iOnRydWUsImlhdCI6MTUxNjIzOTAyMn0.POstGetfAytaZS82wHcjoTyoqhMyxXiWdR7Nn7A29DNSl0EiXLdwJ6xC6AfgZWF1bOsS_TuYI3OG85AmiExREkrS6tDfTQ2B3WXlrr-wp5AokiRbz3_oB4OxG-W9KcEEbDRcZc0nH3L7LzYptiy1PtAylQGxHTWZXtGz4ht0bAecBgmpdgXMguEIcoqPJ1n3pIWk_dUZegpqx0Lka21H6XxUTxiy8OcaarA8zdnPUnV6AmNP3ecFawIFYdvJB_cm-GvpCSbr8G8y_Mllj8f4x9nBH8pQux89_6gUY618iYv7tuPWBFfEbLxtF2pZS6YC1aSfLQxeNe8djT9YjpvRZA

You'll notice that a JWT has 3 parts (separated by periods). The first part is the header, the second part is the payload, and the third part is the digital signature. If you pasted the above JWT into this tool and select the RS256 algorithm, you would get the following data back:

Notice anything similar to our example??

I think so! Within this JWT, we have a header that specifies which JWT algorithm was used (which also inherently indicates which hashing function to use on the data), a body that carries our data, and a signature that represents the following (pseudocode below):

var signature = encrypt(priv_key, hash(header + payload))

Again, this is not a definitive tutorial on JWTs, but I wanted to show the basics of them to demonstrate one of the many common use cases of public-key cryptography!!

What is a Certificate Authority?

To wrap up this discussion, we might ask one more question...

In the last example, how do we know that a hacker didn't act like the sender of data?

A hacker could sign some data with his private key and convince the receiver that his public key is the correct one! When the receiver of the data receives it, he will go through the process of verification described in the previous section, and since the hacker signed with his private key and you decrypted it with his public key, you would be none the wiser!

That is where Certificate authorities come in.

Since this is certainly a potential problem with digital signatures, we must use a Certificate authority who will "issue" a private/public keypair to someone who can then use this keypair.

Using the same verification method described above, a receiver of data can not only verify that the sender of data is who he says he is, but the receiver of data can also verify that the public key they are using has been issued by a trusted Certificate Authority. For example, if you are creating a website that runs the HTTPS protocol, you need to register for a certificate. A common tool installed on many Apache2 servers is the letsencrypt utility, which allows you to register a free certificate with the company, Lets Encrypt.

Since the web trusts this company, we know that any web traffic being sent over TLS (HTTPS) registered with Lets Encrypt is valid.

Summary

Public Key Cryptography allows data traveling on an insecure channel to either be encrypted (sign with public key) or signed (sign with private key). By browsing the internet, you are indirectly using both of these use cases on a daily basis.

By finishing this post, you now know more about cryptography than 99% of people. Useful knowledge? Not sure. Knowledge that makes you feel smart? Yup. Have a great day and drop me a comment if you enjoyed this post.