Blockchain Basics Part 2: Public Key Encryption
How keeping secrets help us send secret messages.
Introduction
I first heard about Bitcoin in 2012. I was in the first year of college and I remember browsing obscure internet forums to figure out how to create my bitcoin wallet and the mathematics behind how it works. The technology has come a long way since then. Cryptocurrencies are now a real market with huge trading volumes, hundreds of different coins, and notoriously volatile prices. In addition, modern blockchains are also capable of executing arbitrary logic - called “smart contracts” that in my opinion have the same revolutionary potential today as the internet had in the early 1990s.
The first half of 2022 has not been kind to the world of crypto. Firms are announcing layoffs and several famous bankruptcies and wallet hacks have soured the public view of crypto. Despite these setbacks, I think the technology has enormous potential and is worth learning about. Even if cryptocurrencies fall out of favor, the technology behind blockchains will likely endure in some form for the foreseeable future.
The mathematics of cryptography is the foundation upon which modern blockchain systems are built. A public, decentralized blockchain that nobody controls raises some questions:
If I send a request to transfer some of my bitcoin to my friend, how can the network of computers know that I was the one who sent the request without having a human verify my ID?
How can a smart contract that logs your attendance verify confidently that you are who you claim to be?
How does Solana know that the person who sent a transaction sent it at a specific time?
How does a bitcoin miner prove that they did the work to verify a block of transactions?
The answer to all these questions lies in the math of cryptography. Cryptographic systems let us encrypt data, prove the origin of documents and provide several mechanisms for blockchains to reach consensus. In this article series, I’ll do a deep dive into many of the components of the cryptographic systems that make blockchains tick.
Part 2 - Public Key Encryption
Public Key Encryption
Imagine you want to communicate privately with someone over a public channel where anyone can examine the message. You want to encode the message somehow so that only the intended recipient can decode the message. This is a hard problem because even highly a secure encryption scheme like the One Time Pad requires that you meet the recipient of the secret message in person to securely exchange coding keys.
Enter public key encryption (PKE). This cryptographic technique allows you to exchange secret messages on a public channel without ever exposing any secret information. It’s hard to overstate how foundational public key encryption has become in the modern world. The security of pretty much every transaction and communication you participate in over the internet depends on it. PKE is responsible for ensuring that you’re actually visiting the website that the address bar displays, for securing your credit card details when you buy something over the internet, and for making sure that your WhatsApp messages can only be read by the recipient.
Keep a Secret to Send a Secret
PKE works by using a set of two numbers (called keys). One key - called the private key - must be kept a secret from everyone. The other key - called the public key - can be made publicly available alongside your name. If I wanted to send a secret message to Albert Einstein, both Einstein and I need our own pair of public and private keys.
To send a secret message to Einstein, I would use Einstein’s public key to encrypt the secret message and send the message over the public channel. Einstein is able to decrypt the message using his private key. To everyone else, the message looks like random noise.
The RSA Algorithm
The RSA algorithm is one example of a commonly used public key cryptographic system. Named after its inventors - Ron Rivest, Adi Shamir, and Leonard Adleman - it was first publicly described in 1977. Before the invention of public key cryptography, you and the person you’re sending the message to needed a shared secret key send secret messages to each other.
Integer Factorization is Hard
Like the cryptographic hash functions described in Part 1, RSA is based on mathematical operations that are easy to calculate but difficult to reverse. In the case of RSA, the operation in question is integer factorization. In general, it’s easy to multiply two large prime numbers. The reverse - finding the primes that are factors of a large composite number - is hard to do. Even the best-known classical algorithm to perform prime factorization - General Number Field Sieve - cannot feasibly factor large primes in a short amount of time.
Generating Public and Private Keys
Encryption and decryption using RSA is based on modular arithmetic. Modular arithmetic studies the properties of integers that wrap around a value. A good example of modular arithmetic are 8 bit integers in computers. When an 8 bit integer reaches 256 it wraps around back to 1. Numbers larger than 255 cycle back to the smaller values. So 260 modulo 256 is 4. This is called a congruence relation in modular arithmetic. Modulo 256, the numbers 260 and 4 are “equivalent” in some way.
Certain functions from modular arithmetic are used to calculate two more numbers d and e with certain properties. The number d must be kept a secret and together with the product of the primes, forms the private key. The number e together with n forms the public key.
Briefly, the procedure to find e and d:
The Carmichael’s Totient function λ(n) is calculated.
The number e is chosen as a value between 1 and λ(n) and co-prime to λ(n).
The number d is the modular multiplicative inverse of e modulo n.
More details can be found in the Wikipedia article and in the various open source implementations of RSA.
Encryption and Decryption
Encryption and decryption of the message and the cipher text is also based on modular arithmetic operations. To encrypt the message, a numeric representation of the message m is raised to the public exponent e but wrapped around the product of the primes n. For decryption, the encrypted message is raised to the private exponent d wrapped around the product of the primes n.
In principle, this is all there is to encrypt a message in a way that only the intended recipient can read it. In practice, implementing the RSA securely is tricky as the secret numbers can be leaked in a variety of ways due to bugs in the code. In encryption, it’s imperative to never DIY unless you really know what you’re doing. As a programmer without deep knowledge of cryptography, security is best achieved by using crypto libraries that have been tried and tested by others.
In addition to tricky implementation, key sizes also need to be chosen carefully. Due to cheap and easily available computing, it is possible to break the security of RSA if the chosen primes are too small. For instance, it is already possible to factor primes up to 512 bits in length using publicly available software in about 7 hours. Key sizes of 1024 bits and longer are recommended for good security.
Summary
To sum up, public key encryption allows you to send a secret message to someone over a public channel as long as you know their public key. The person you’re sending the message to can decrypt the message with their private key. To everyone else, the message is indistinguishable from random noise.
In addition to encrypting messages, Public Key Encryption can also be used to sign messages. Creating and verifying digital signatures is a fundamental operation on many blockchains. The next article will go into how digital signatures work and how they are used in blockchains.