A Primer on Public-Key Cryptography

Apr 4, 2021

---

In preparation for a future post discussing Elliptic curve cryptography (ECC), I'd like to introduce the broader concept of public-key cryptography first. Though these concepts are general, I'll use the RSA algorithm as an example of a public-key cryptography system. This will also help us motivate our discussion of ECC in the follow-up post.

Introduction

Cryptography is a branch of math and computer science that deals with securing information using codes or ciphers. It's a crucial technology for the modern internet. Though not infallible, cryptography allows us to securely browse the web, shop, or make online banking transactions. And–as you may know–cryptography is also behind cryptocurrencies and blockchains, such as Bitcoin and Ethereum.

When the information is secured or encrypted, it can then be transmitted without worrying about the presence of third parties, called adversaries. The intended receiver will have a key that allows for the decryption of the original message.

For example, when buying on Amazon, our information–such as our credit card number–gets encrypted and then transmitted through the internet. Even if a malicious agent collects this information, it will be nearly impossible to decipher without the appropriate key.

But, we can also use cryptography to digitally sign information or messages. The signature is verified by the message's recipient, thereby confirming that it came from the legitimate sender. This form of secure data exchange is also called public-key cryptography.

Working With a Public-Key Cryptosystem

We need two keys to work with a public-key cryptosystem. One is a public key and the other is a private key–a key is nothing but a long sequence of numbers and characters (e.g. a large hexadecimal number). The private key is to be kept secure, while the public key can be shared with others.

Our goal is to find a one-way mathematical operation or function that will map a value into another. A good one-way operation makes it (computationally) easy to go from value $A$ to value $B$. But, going the other way around, from $B$ to $A$, should be non-trivial.

A silly example would be multiplication. If we let $A = 6$, then multiply $6 \times 3$, we get $B = 18$. To get $A$ back again, we use the inverse operation of multiplication–that is division. So we just divide $B$ by $3$ ($18 \div 3 = 6$) to get $A$ back. This may be an oversimplification of the process, but it serves for illustration. Multiplication is, of course, not a good one-way operation.

In practice, the original message or information is represented by the value we are trying to map into another. The process of "passing" that value through our one-way operation corresponds to encrypting the message. The resulting value represents the encrypted message. Finally, obtaining the original message back–going from $B$ to $A$ in our example above–corresponds to decrypting the message. In this scenario, the information is encrypted using the public key and decrypted using the private key.

Encryption and decryption of a message using public-key cryptography (public domain).

As I mentioned earlier, encryption and decryption of information are not the only use case of public-key cryptography. We can also generate cryptographic digital signatures. This is one of the main uses of public-key cryptography in blockchains and cryptocurrency systems. Cryptographic signatures allow us to sign pieces of information. By verifying the signature, we can prove the origin of said information–i.e. the owner of the private key.

$$\cdots$$

One of the first public-key cryptosystems is the RSA algorithm created in 1977. The RSA name comes from the last name initials of its creators, Ron Rivest, Adi Shamit, and Leonard Adleman from MIT.

Looking at the RSA algorithm will give us a better understanding of public-key cryptography systems.

The RSA Algorithm

The RSA algorithm is based on prime factorization, which is a computationally hard operation. From the fundamental theorem of arithmetic, we know that any number can be decomposed into the product of unique primes–this is called prime factorization. Current prime factorization algorithms are not efficient when dealing with large numbers. And, as the numbers get larger, the algorithm takes longer to complete.

Let's see how the RSA algorithm generates the cryptographic keys.

Public/Private Key Generation

Since we're dealing with physical computers, we need to determine the maximum value that our keys can take. This value represents the modulus which is used with modular arithmetic to keep our numbers within our range.

The keys are generated as follows: ¹

1. Take two random prime numbers, $p$ and $q$, and multiply them together to get the maximum value, which will represent our modulus $n$.

   $n = p \cdot q$

2. For the public key $K$, we choose an integer number such that $1 < K < n$.

3. The private key $k$ is obtained using the Extended Euclidean algorithm, with $p$ and $q$ as inputs.

Once we have our public key $K$ and private key $k$, we can use them to encrypt/decrypt, or sign messages.

Encryption/Decryption

Let's say you want to receive an important message–containing private information–from your friend Bob. So you decide to use RSA encryption. First, you generate the key pair as described above. You then share the public key with Bob, who will use it to encrypt the information as follows.

Let the plaintext message be $M$ (internally, the computer represents the message as a large number). Then we obtain the encrypted message $m$ as:

$M^K = m \pmod n$

where $K$ is the public key and $mod$ is the modulo operation. Notice that we're just multiplying $M$ by itself $K$ times and using the modulo operation to keep the value within bounds.

When you receive the message, you use your private key to decrypt it. Since you are the only one who has the private key–and it only works in combination with the public key–you are the only one who can access the information.

To recover the original message from $m$, you use the private key $k$ as follows.

$m^k = M \pmod n$

In this case, we're multiplying $m$ by itself $k$ times and, again, applying the modulo operation.

Cryptographic Signatures

Now, suppose you want to send an encrypted message to your friend Alice. You will use Alice's public key to encrypt the message. However, she needs to make sure the message came from you. To accomplish this, you can use RSA to cryptographically sign the message. Then Alice can check the signature in the message to verify it came from you.

To sign a message you use your private key $k$ as follows. First, you generate a hash value of the message and then rise it to the power of $k \pmod n$ (similar to encrypting a message). The result is attached to the message as the signature and sent to Alice.

When Alice receives the message, she uses the same hashing function and your public key to verify the signature. She first raises the signature to the power of $K$–your public key (similar to decrypting the message). This will result in the hash value that you obtained when sending the message to her. Then Alice computes the hash value of the original message. She then compares both hash values–the one from the signature and the one from the original message. If they are the same, that means the message's author was the owner of your private key $k$.

Shortcomings of the RSA Algorithm

As I mentioned earlier, the RSA algorithm relies on the problem of prime factorization being computationally hard. Prime factoring becomes increasingly hard as the number to factor gets larger. However, as more computing power is available, breaking the RSA cryptosystem–i.e. guessing the private key from the public key–is now possible if the numbers are not large enough.

This problem is mitigated by establishing a minimum recommended length for the keys. As of this writing, the recommendation is 2048 bits minimum. However, this is just an arms race between the RSA cryptosystem and malicious agents. Eventually, the required length will be infeasible in practice.

Fortunately, there are alternatives to RSA. A superior public-key cryptosystem is Elliptic curve cryptography or ECC. Modern browsers and practically every cryptocurrency and blockchain application use ECC today.

$$\cdots$$

In the next post, I will take a look at Elliptic curve cryptography–another form of public-key cryptography. Hopefully, this discussion served as an introduction–or refresher–of the basic concepts.

Notes