Introduction to Asymmetric Encryption for the Working Developer

In this post, we are going to look at asymmetric encryption. As mentioned in the previous post on symmetric encryption, encryption is the cryptographic primitive that guarantees confidentiality, by which we mean the ability for two or more authorized parties to communicate, without an unauthorized person being able to decipher the messages being communicated.

In symmetric encryption, both parties need to use the same key for encryption and decryption. This leads to the problem of how to securely get the communicating parties to use the same key. A solution to this is the Key exchange protocol that was discussed in Introduction to Key Exchange for the Working Developer

Asymmetric encryption is different. Unlike symmetric encryption, it does not have the requirement that the same key needs to be used for encryption and decryption. Hence why it is called asymmetric. It makes use of key pairs instead. One is called the private key, the other called the public key.

In this post, we will be looking at how to use asymmetric encryption and what other general information to be aware of. As always it is targeted at the working developer who needs a grounded understanding of these cryptographic primitives without necessarily covering the internals of these primitives.

Asymmetric Cryptography and Asymmetric Encryption

Oftentimes when private/public keys are mentioned, it is often done so in the context of encryption, that is, asymmetric encryption. The reality is that the use of public and private keys is not restricted to encryption and decryption alone, there are other primitives in cryptography that make use of private/public keys.

For example, the Diffie-Hellman Key Exchange, which I wrote about in Introduction to Key Exchange for the Working Developer is an example of a cryptographic primitive that makes use of asymmetric keys but has nothing to do with encryption.

Asymmetric cryptography is the broad term that refers to all the various cryptosystems that do not depend on having two identical secret keys to function. Asymmetric encryption falls under asymmetric cryptography but so do other primitives. I believe this tidbit needs to be highlighted to prevent the assumption that when public and private keys are used, they are always used in encryption and decryption.

With that clarification out of the way, let us dig into asymmetric encryption by taking a broad look at the different asymmetric encryption algorithms.

Asymmetric Encryption Algorithms

Asymmetric encryption makes use of key pairs. A private key and a public key. This pair of keys can be used to achieve confidentiality. This is because messages encrypted by a key in the pair can be decrypted by the other key.

This is how it usually works. The public key, as the name implies, is made public. This can be shared at the beginning of confidential message exchange, or it can be made available free via any other means: email, on a website, etc. The private portion, on the other hand, is kept secret. To communicate confidentially, the public key is used to encrypt a message, which is then sent to the entity that controls the corresponding private key. This encrypted message can only be decrypted by the owner of the corresponding private key.

A two-way encrypted communication then involves the communicating parties using each other's public key to encrypt messages. That is Alice uses Bob's public key to encrypt messages she wants to send to Bob. Bob can then decrypt these messages from Alice. To reply to Alice's confidentiality, Bob also makes use of Alice's public key to encrypt replies that are sent to Alice.

There are a couple of algorithms that implement the ability to encrypt and decrypt using private/public key pairs. For example ElGamal, Paillier cryptosystem, and Cramer–Shoup cryptosystem but by far, the most popular and most used algorithm is RSA cryptosystem.

The acronym "RSA" is from the last names of the three cryptographers Ron Rivest, Adi Shamir, and Leonard Adleman, who proposed the algorithm in 1977.

Like with most asymmetric cryptosystems, the underpinning of RSA and its security is based on mathematics. But since the aim of this post is to provide the necessary information needed for a working developer to form a working mental model of asymmetric encryption, we will avoid a rigorous take but gloss over the mathematical details instead. Readers who are interested in digging more into mathematics can check the additional section of this post. There, I share links that cover some of the mathematics that is fundamental to RSA.

For now, we take a bird's eye view of the RSA algorithm.

How RSA Works

RSA is based on factorization problem. Factorization is the mathematical operation of splitting an integer into products of smaller integers. For example, the numbers 21, 7, and 3 are its factors.

The factorization problem is the observation that it is easy to find an integer given its factors, but the reverse, that is finding the factors of a given number is hard. A small number like 21 in the example above does not demonstrate this difficulty, but given a substantial large integer, finding its individual factors is extremely hard, with no algorithm to speed up the process, and finding such factors essentially involves brute force.

"Can the reader say what two numbers multiplied together will produce the number 8,616,460,799? I think it unlikely that anyone but myself will ever know."

The above challenge was posed by William Stanley Jevons in his 1874 book, Principles of Science. The number becomes known as Jevon's number. It is essentially a factorization problem challenge. It took 15 years to crack. It was factored by Charles J. Busk in 1889 who found that 89,681 and 96,079 are factors of 8,616,460,799.

Factoring is the underlying, presumably hard problem upon which the RSA algorithm is based. An in-depth explanation is beyond the scope of this post, but the general algorithm is outlined below.

Note that the outline below is often referred to as textbook RSA and this is not how RSA is implemented in practice because it is insecure. There are slight improvements mainly in the area of padding that fortifies the algorithm.

The general outline of the algorithm is as follows:

• Choose very two large prime numbers. Let's call them p and q
• Let N = p * q N is usually referred to as the modulus
• Find the Euler totient of p and q, that is T = (p-1)(q-1)
• Choose another number e where 1 < e < T and e do not share any factors with N and T
• e is used for the encryption process.
• Choose another number d where e * d mod T = 1
• d is used for the decryption process.
• The pair N and e is the public key. This is published
• The pair N and d is the private key. This is kept a secret.
• To encrypt, a message, represent the message as a numeric value, say m
• Then calculate m ^ e mod N = ciphertext c
• To decrypt ciphertext c back to m calculate c ^ d mod N

That is the general outline. To see this in practice, let's try it out with 2 prime numbers that are small enough to make demonstration possible. We choose p = 2 and q = 7

• Choose very two large prime numbers. Let's call them p and q
  • p = 2 and q = 7
• Let N = p * q N is usually referred to as the modulus
  • N = 2 * 7 = 14
• Find the Euler coefficient of p and q, that is T = (p-1)(q-1)
  • T = (2-1)(7-1) = 1 * 6 = 6
• Choose another number e where 1 < e < T and e do not share any factors with N and T
  • e = 5
• e is used for the encryption process.
• Choose another number d where e * d mod T = 1
  • d = 11 because:
  • 5 * 11 mod 6 = 55 mod 6 = 1
• d is used for the decryption process.
• The pair N and e is the public key. This is published
  • Public key is (5, 14)
• The pair N and d is the private key. This is kept a secret.
  • Private key is (11, 14)
• To encrypt, a message, represent the message as a numeric value, say m
  • Let the message be B which in numeric form we have as 2
• Then calculate m ^ e mod N = ciphertext c
  • 2 ^ 5 mod 14 = 4
  • Cipher text is 4
  • Which in our encoding scheme is D
• To decrypt ciphertext c back to m calculate c ^ d mod N
  • 4^ 11 mod 14 = 2
  • Plain text is 2
  • Which in our encoding is B - which is the original value encrypted

The underlying security of this algorithm is the fact that given the value N which is public, it is practically impossible to figure out the factors p and q. If it were possible then it would be possible to derive d which would make the whole scheme insecure.

As mentioned earlier, textbook RSA is not used in practice as it is not secure. For example, using textbook RSA to encrypt small messages is insecure, because an eavesdropper can encrypt all the small numbers and quickly observe if any of their encrypted numbers match the ciphertext. This is why in practice, RSA makes use of padding schemes that pad the message before encryption.

The very first such a padding scheme in PKCS#1. This padding scheme has been shown to also be insecure and should not be used. Hence in practice, the padding scheme recommended to be used with RSA is the Optimal Asymmetric Encryption Padding (OAEP). Hence RSA-OAEP

Let's now see how RSA-OAEP looks with a working code example.

Example of RSA-OAEP using web crypto API

In the code sample below, we generate a private/public key pair, use it to encrypt a text, and then decrypt it to retrieve the original plaintext. The code makes use of web crypto API so it should work in most browsers, Deno, or the latest version of node.

let plainText = "Hello world!";

const keys = await window.crypto.subtle.generateKey({
   name: "RSA-OAEP",
   // The length in bits of the RSA modulus
   modulusLength: 2048,
   // The public component e. Recommended value is 65537
   publicExponent: new Uint8Array([1, 0, 1]),
   // hash function required by OAEP
   hash: "SHA-256",
},
   // A boolean value indicating whether it will be possible
   // to export the key using SubtleCrypto.exportKey() or
   // SubtleCrypto.wrapKey().
   true,
   // An Array indicating what can be done
   // with the newly generated key
   ["encrypt", "decrypt"]
)

// We encrypt
const ciphertext = await window.crypto.subtle.encrypt(
   { name: "RSA-OAEP" },
   keys.publicKey,
   new TextEncoder().encode(plainText)
)


// We convert ciphertext to a hex string and console logged it
console.log(buf2hex(ciphertext))

// We decrypt
const decrypted = await window.crypto.subtle.decrypt(
   {
       name: "RSA-OAEP"
   },
   keys.privateKey,
   ciphertext
)

// We convert to string
const decryptedPlaintext = new TextDecoder().decode(decrypted);
console.log(`Encrypting and decrypting was successful: ${plainText === decryptedPlaintext}`)

// utility to convert ArrayBuffer to hex string
function buf2hex(buffer: ArrayBuffer) {
   return [...new Uint8Array(buffer)]
       .map(x => x.toString(16).padStart(2, '0'))
       .join('');
}

Executing the following code, for example using Deno should give the following output:

deno run index.ts
Check file:///Users/dadepoaderemi/Documents/delete/blogging/assymmetric/index.ts
3b69df6eee76c660b8c9c307f89c4a023f455b06cf8da6622c9ff2073...
Encrypting and decrypting was successful: true

Drawbacks of RSA and Introduction to Hybrid Encryption

RSA is inefficient. It can only encrypt a small amount of plaintext at a time, and the speed of encryption and decryption is quite slow. This drawback is not limited to RSA but applies to most asymmetric encryption algorithms. This is mainly because these algorithms implement math operations.

Because of these drawbacks, asymmetric encryption is usually not used to encrypt messages. Instead, it is used as part of what is usually referred to as hybrid encryption constructions.

The general idea behind hybrid encryption is this: use symmetric encryption for the actual encryption since symmetric encryption is more efficient while asymmetric cryptography is used to exchange the symmetric keys. The part where asymmetric cryptography is used to ensure the parties communicating have the same key is usually called key encapsulation, while the actual encryption via symmetric encryption is called data encapsulation.

Asymmetric encryption is an example of asymmetric cryptography that can be used for key encapsulation. In this case, if Alice wants to communicate confidentially with Bob, she generates a symmetric key and then encrypts it using Bob's public key. This ensures Bob can decrypt with his private key and retrieve the symmetric key to be used for encryption.

Another scheme is to use Diffie Hellman key exchange, as the asymmetric cryptography system used in exchanging the symmetric key used for actual encryption and decryption.

The idea of hybrid encryption is very practical, this has led to the creation of well-defined schemes that makes use of hybrid encryption but only expose the typical asymmetric encryption interface to the use. This means the user of such schemes only need to worry about the private and public keys, while internally the scheme makes use of symmetric encryption. This also means the user does not have to manually perform multiple steps that consist of key encapsulation and data encapsulation but only uses the private and public keys to encrypt and decrypt.

There are many hybrid encryption schemes in existence, although arguably the most widely adopted standard is Elliptic Curve Integrated Encryption Scheme (ECIES). Hence I will quickly show how ECIES looks in practice.

Unfortunately, Web Crypto API does not support ECIES, so for this demonstration, I will use nodejs and the eciesjs package.

Create a new node js project and install eciesjs by running the following command

npm init ecies_demo -y
npm install eciesjs

Then in the index.js have the following code:

import { encrypt, decrypt, PrivateKey } from 'eciesjs'

const prvKey = new PrivateKey()
const pubKey = prvKey.publicKey
const message = Buffer.from('message to b')

// encrypt the message
const encryptedToB = encrypt(pubKey.toHex(), message);

// console log the encrypted message as hex
console.log(encryptedToB.toString('hex'))

// decrypt the message
const decrypted = decrypt(prvKey.toHex(), encryptedToB).toString()

// confirm original message and decrypted message is same
const isSame = message.toString() === decrypted
console.log(`decrypted and original message is same: ${isSame}`)

This code uses a generated public key to encrypt a message which is then decrypted with the corresponding private key and confirmed that the original message and decrypted message are the same.

As can be seen, the interface only exposes the usage of public-private key pairs and hides the fact that symmetric encryption is being used. In fact, the ECIES scheme is more complex and makes use of other cryptographic primitives like key-derivation function (KDF) and HMAC,

A functional diagram of ECIES can be seen below:

Source https://core.ac.uk/download/pdf/36042967.pdf

The good thing is that the end-user does not need to deal directly with this complexity. A simpler interface based on private and public keys is exposed. This is the advantage of using a hybrid encryption scheme like ECIES.

Additional Resources

Here are some of the link that covers some of the fundamental mathematics that makes asynchronous encryption work

• GCD
• Relative Prime 
• Primitive Root
• Euler’s ϕ-function
• Modular Arithmetic
• Prime Numbers & RSA Encryption Algorithm - Computerphile