Cryptography has been used in civilizations in varying formats for thousands of years. From the ancient Egyptians to the modern Internet, the use of cryptography to encrypt and decrypt messages is a vital tool in communication.
RSA cryptography (the RSA algorithm to be exact) is the most ubiquitous asymmetric encryption algorithm in the world. Made possible by a number of cryptographic and mathematical breakthroughs, anyone who uses the Internet is utilizing RSA cryptography in some form or another.
Most cryptocurrencies employ a similar type of asymmetric encryption as RSA, known as Elliptic Curve Cryptography. While different, they are both founded on similar concepts and understanding RSA is important to furthering an understanding of cryptography employed in cryptocurrency networks.
Cryptographic Background and Symmetric vs Asymmetric Cryptography
Up until the 1970s, cryptography had primarily been based on the use of symmetric keys. In symmetric key algorithms, two users who wish to communicate a message with each other use the same cryptographic keys for both the encryption of the plaintext and decryption of the ciphertext. The keys represent a shared secret between the two parties and can be used as a private form of communication. However, there are some inherent problems with this design that leads to some serious drawbacks of its use.
For instance, both parties need to know the secret key in order to encrypt and decrypt the message. Outside of meeting in person to exchange this information, there is a substantial amount of communication overhead needed to accomplish this privately through mediums that are not secure. Third parties watching these channels may be able to obtain the secret key and thus, the method of encryption becomes compromised. Further, the concept of symmetric key encryption is not scalable. If you would like to send encrypted messages to multiple people, you would need to memorize a secret key for each one of those lines of communication. Obviously, this rapidly becomes inconvenient and clearly is not the best model to be employed by cryptocurrency networks where value is exchanged.
The solution to this came in the form of what is known as asymmetric encryption, or more popularly referred to as public-key cryptography. Asymmetric encryption uses two keys, a public key and a private key. In this model’s most basic form, a user can publish a public key, with which anyone else can use to send that person an encrypted message and only the person who published the public key and has the corresponding private key can decrypt and view this message. The use of one key cancels out the use of the other and keys to not need to be exchanged between parties who wish to communicate.
The asymmetric encryption model was made possible by 2 brilliant principles that came as a result of a breakthrough by British mathematician James Ellis in 1970. Ellis described an idea whereby encryption and decryption are inverse operations of each other based on 2 different keys.
James Ellis, image from The Telegraph.
The concept is generally represented by a padlock and a key, with the padlock representing the public key and the key representing the private key. In order to make practical use of this theory, two principles evolved.
The Trapdoor Function
A trapdoor function is a very important concept in cryptography where it is trivial to go from one state to another state, but to compute in the opposite direction by going back to the original state becomes infeasible without special information, known as the “trapdoor”.
The best known trapdoor function today, that is the basis for RSA cryptography, is called Prime Factorization. Essentially, prime factorization (also known as Integer Factorization) is the concept in number theory that composite integers can be decomposed into smaller integers. All composite numbers (non-prime numbers) that are broken down to their most basic are composed of prime numbers. This process is known as prime factorization and has serious implications when applied to cryptography.
Prime Factorization, Image used from Wikipedia
Essentially, prime factorization of extremely large prime numbers becomes infeasible to compute due to the sheer amount of trial and error required to successfully factor the number to its most basic components. Currently, no efficient factorization algorithm exists to perform this.
RSA and how it employs prime factorization is described in a later section, but first we need to understand the Diffie-Hellman Key Exchange.
The Diffie-Hellman Key Exchange
The Diffie-Hellman key exchange is one of the first public key cryptography protocols and fundamentally allows for exchanging cryptographic keys over a public medium, securely. For the sake of simplicity, attempting to conceptualize the Diffie-Hellman Key Exchange and the following section on how the RSA algorithm works is much more trivial with abstract concepts compared to pure math, so we will apply the mathematics only when necessary.
The most common example used to conceptualize the Diffie-Hellman Key Exchange is known as the Secret Color Exchange.
Diffie-Helman Key Exchange, image used from Wikipedia
The picture above represents a line of communication between Alice and Bob over a public channel where Eve can listen to everything being publicly communicated between Alice and Bob. So, how can Alice and Bob communicate a private message using asymmetric encryption without explicitly exchanging that information over the public medium?
They exchange secret information with each other without actually sharing it. The process works as follows:
Step 1
- Alice and Bob agree that Yellow is the common paint to be used. This information is broadcast over the public channel so that Eve knows this as well.
- Yellow represents the public key.
- Alice decides secretly that she is also going to use Blue along with Yellow and Bob secretly decides that he is going to use Red with Yellow.
- The Blue used by Alice and the Red used by Bob represent their secret keys.
Step 2
- Next, both Alice and Bob mix in their secret colors with yellow to create a composite color.
- Alice’s mix creates Green and Bob’s mix creates Orange.
- Now both Alice and Bob send each other their composite colors.
- Eve also receives these colors but faces a problem, these composite colors represent a trapdoor function.
- It is easy to combine two colors to make a third color, but it is infeasible to reverse this. It is very difficult to determine which colors were used to create the third color from only having the third color and the original Yellow.
Step 3
- Alice and Bob then mix in their secret colors with the received composite colors which results in the following.
- Alice mixes Blue with the composite Orange from Bob.
- Bob mixes Red with the composite Green from Alice.
- Both mixtures result in Brown.
That is the secret to the Diffie-Hellman Key Exchange. Even though both Alice and Bob ended up with Brown, they never actually exchanged that color, and Eve is left without the requisite information of the secret colors to be able to compute the secret message (Brown).
The example above is a very simple visualization of how the exchange works. With mathematics applied, assured security and integrity of messages can be achieved through RSA cryptography utilizing prime factorization as the trapdoor.
How Does The RSA Algorithm Work?
The RSA algorithm works by utilizing the prime factorization trapdoor and the Diffie-Hellman Key Exchange to achieve asymmetric encryption. Fundamentally, RSA cryptography relies on the difficulty of prime factorization as its security method. Using a very simplified example with limited math described, the RSA algorithm contains 4 steps.
- Key Generation – During this step, a user can employ an random number generator or simply pick 2 very large prime numbers (called p and q). These numbers must be kept secret. Compute n=pq where “n” is the modulus for both public and private keys and its length is known as the key length. Make “n” public. For key sizes equal to or larger than 1024 bits, there is no efficient method for solving this algorithm (factorizing the very large number “n”) efficiently. Even the largest supercomputer in the world would take thousands of years to solve it. This is known as the RSA problem, and if solved, would compromise all RSA-based cryptosystems.
- Key Distribution – Bob wants to send Alice secret information so the following steps occur.
- Bob must know Alice’s public key to encrypt the message.
- Alice must know her private key to decrypt the message.
- For Bob to be able to send his encrypted message, Alice send her public key to Bob.
- Alice never distributes her private key.
- Encryption – After Bob obtains Alice’s public key, he can send a message (M) to Alice. First, he turns (M) (at this point a plaintext message) into an integer (m) through using a agreed upon padding scheme. He then computes the ciphertext using Alice’s public key and transmits (c) to Alice.
- Decryption – Alice can recover the message (m) from the ciphertext (c) by using her private key. She can then recover the original message (M) by reversing the padding scheme from (m).
A more in-depth explanation of the mathematical operations used in RSA can be found here, but is out of the scope of this article.
Additionally, RSA encryption allows for digitally signing messages, which is paramount to cryptocurrencies and is a key component of Bitcoin’s UTXO transaction model. Alice can digitally sign a message to Bob to verify that she sent it (by validating that her private key was used) through producing a hash value of the message and attaching it to the message. This value can be verified by Bob who uses the same hash algorithm in conjunction with Alice’s public key and compares the resulting hash value with the message’s actual hash value.
Conclusion
RSA encryption is the most widely used asymmetric encryption method in the world because of its ability to provide a high level of encryption with no known algorithm existing yet to be able to solve it. Based on some brilliant breakthroughs in cryptography and mathematics including the Diffie-Hellman Key Exchange and trapdoor function, RSA encryption has become paramount to secure communication across the world.
1 Comment
In step 1, you say that “Alice decides secretly that she is also going to use Blue along with Yellow and Bob secretly decides that he is going to use Red with Yellow.”
In the second row of the diagram, it looks like Alice is using Red and Bob is using Blue.
Can you confirm?