RSA encryption is a public key encryption technology that enables a sender to transmit secret messages to a recipient over insecure networks, like the internet. RSA encryption is facilitated by the RSA algorithm, one of the earliest asymmetric encryption algorithms. The security of RSA encryption ensured by the intractability of finding the prime factors of very large composite numbers.
In this article, we’ll look at why the creation of RSA encryption was a major breakthrough in modern communications. We’ll explore how the RSA algorithm uses mathematics to maintain security. Finally, we’ll highlight RSA encryption’s usage in real-world applications and known security vulnerabilities.
Challenges To Secret Communications
To truly understand the importance of RSA encryption, It’s crucial to know about the fundamental problems it solves. For thousands of years, the goal of cryptography had been to establish and maintain secret communications between a sender and a recipient. While some encryption techniques were more successful than others, they all ultimately failed due to the private key exchange problem and the sender verification problem.
Private Key Exchange Problem
Prior to the creation of RSA encryption, both sender and receiver needed to share a private key because that same private key was used to both encrypt and decrypt messages. This is what’s known as the private key exchange problem. If two people are separated geographically, how can they establish a private key for encrypted communications? They would have to transmit the private key to one another in an unencrypted format, which makes it easy for someone else to intercept and eavesdrop on all future encrypted communications.
Sender Verification Problem
If someone intercepts a private key, this person could also use it to send new encrypted messages. Anyone who has access to the private key could pretend to be the original sender. To make matters worse, it’s very difficult for anyone to detect whether the private key has been intercepted. This means the recipient can’t confidently verify the identity of the sender. As a result, the recipient can’t confidently verify that messages weren’t altered by someone else.
Precursors To RSA
Solving these two challenges required taking complex ideas and applying them to a real-world encryption algorithm. This was definitely not a trivial task. Researchers at the United Kingdom’s Government Communications Headquarters (GCHQ) had first published an idea for such an algorithm in 1969. They later shared this information with the United States National Security Agency (NSA). Neither government organization was able to turn the idea into a working algorithm.
In 1976, the Diffie-Hellman key exchange made it possible to send private keys over an insecure public network. However, Diffie-Hellman was still only a partial solution since it required private key sharing and didn’t attempt to solve the sender verification problem. Finally, in 1977, the RSA algorithm would emerge as a complete solution for secret communications.
What Is RSA (Rivest–Shamir–Adleman) Encryption?
In 1977, three scientists at Massachusetts Institute of Technology (MIT) named Ron Rivest, Adi Shamir, and Leonard Adleman published the RSA algorithm. The algorithm’s namesake is derived from the first letter of each of their last names. They implemented two new technologies— private-public key pairs and digital signatures— to solve both the private key exchange problem and the sender verification problem.
Private-Public Key Pairs
RSA encryption overcomes the private key exchange problem by giving each person their very own private-public key pair, where the public key is used to encrypt and the private key is used to decrypt. This is commonly known as asymmetric encryption. The RSA public key is used as a public identifier to determine the destination for encrypted messages. Each person can share their own RSA public key with literally anyone they want to receive messages from. The RSA private key is used exclusively by the intended recipient as a means of decrypting encrypted messages. Each person has a responsibility to keep their own RSA private key a secret to ensure secret communications.
Digital Signatures
RSA encryption overcomes the sender verification problem by requiring senders to create digital signatures when sending encrypted messages. Digital signatures are crucially important because they allow recipients of encrypted messages to verify both the identity of the sender and the integrity of the message itself with almost complete certainty. Since a unique digital signature is created for every correspondence, using the sender’s private key and a cryptographic hash of the correspondence itself, it’s virtually impossible to counterfeit or forge a digital signature.
A Breakthrough In Cryptography
It’s hard to overstate the importance of RSA encryption. Anyone who uses the Internet today is interacting with RSA in one way or another. Whether you are shopping on e-commerce stores, signing electronic documents, or just visiting web pages, you are likely utilizing RSA encryption. It has proven to be a revolutionary cryptographic breakthrough. Two main factors have contributed to the widespread adoption of RSA. Since it was the first modern algorithm to ensure secret communications with nearly complete certainty, RSA gained a first-mover advantage. Additionally, its design is supported by time-tested mathematics to provide a predictable, high level of security.
How Does RSA Encryption Work?
RSA encryption is truly remarkable because it uses mathematical concepts that had been around for centuries to solve modern problems in cryptography. In particular, RSA uses modular arithmetic, the integer factorization problem, and large prime numbers to create an incredibly secure cryptosystem. Let’s look at how RSA makes secure communication not only possible but also practical for nearly everyone.
Modular Arithmetic
RSA encryption, like many other asymmetric encryption algorithms, relies upon modular arithmetic. While modular arithmetic might sound like a complex concept, it is actually quite simple.
Modular arithmetic is a special type of equation that divides two numbers and produces only the remainder. For instance, 5 divided by 2 is equal to 2 with a remainder of 1. Thus, the modular equation for this is 5 mod 2 = 1. Notice that, in this very simple example of a modular equation, there are only two possible outputs: 0 or 1. Let’s run through some inputs to make this point clear.
If the value of the input is even, then the input is divided by 2 an even number of times, leaving a remainder of 0. If the number is odd, then there can only be a remainder of 1. The output values alternate between 0 and 1, going round and round in circles, for all real numbers.
It’s important to note that most mathematical processes have an inverse operation, but modular equations do not. For example, if you take X and add 9, you can always reverse that operation by subtracting 9 to get back to X. Or if you multiply X by 5, you can always return to X by simply dividing by 5. This is true even if you have no idea what X is. However, no inverse operation exists for a modular equation. There is nothing you can do to the output to get back to X.
Let’s say you know that X mod 2 = 1. What values of X would produce an output of 1? Is there an operation you can use to determine what X is, given that X mod 2 is equal to 1?
There is not. The possibilities are literally infinite. X could be 5, 13, 37, 2000001, or any other number that produces a remainder of 1 when placed into the equation X mod 2.
With X mod 2 = 1, we can’t easily find X. However, we can easily determine that 5 could be a possible answer but 6 couldn’t. That’s because the modulus in our example is very small. It’s easy to guess the correct answer for X with a powerful computer that can quickly run through the possible answers, creating a major issue. If someone can correctly solve for X in the modular equation, RSA encryption is easily broken. This is why real-world implementations of RSA use a very, very large modulus.
Prime Numbers And The Integer Factorization Problem
The goal of the RSA algorithm is to produce a modulus so large that it prevents people or computers from knowing its possible factors. With the RSA algorithm, this is accomplished through very large prime numbers and the integer factorization problem.
The integer factorization problem states that multiplying two factors together to find the product is really easy, but using the product to find its two factors is very difficult. Finding two equally-sized (or nearly equally-sized) large prime factors given only the product is exponentially more difficult. Because of this, large prime factors form the basis of RSA modulus generation.
In RSA, the product of two large prime factors becomes the modulus, which can be publicly known because it’s used to calculate an RSA public key. In contrast, the two large prime factors must be kept secret at all times because they are used to compute the corresponding RSA private key.
When Rivest, Shamir, and Adleman published the RSA algorithm in 1977, their implementation (RSA-129) was a 129-digit modulus that consisted of one 64-digit prime factor and one 65-digit prime factor. While modern implementations of RSA now need to use a much larger modulus to ensure a high level of security, the concept remains the same. RSA implementations for real-world applications use a modulus so enormous that no computer in existence has enough storage to index and utilize a list of all the possible prime factors. This means an encrypted message can’t be decrypted without having the corresponding private key. As long as the modulus is sufficiently large, a computer can’t guess the correct prime factors in a reasonable amount of time.
Although the RSA algorithm’s application of complex mathematical theories is impressive, it wasn’t exactly clear how this innovation would be utilized in 1977. However, as computer technology began to advance, RSA gained relevance and would become a vital part of modern data security.
Real-World Adoption Of RSA Encryption
In 1982, Rivest, Shamir, and Adleman went on to found a company called RSA Data Security. In the early 1980s, most computers still weren’t powerful enough to perform RSA calculations quickly. In fact, RSA Data Security quickly faced bankruptcy. However, the company would eventually turn things around and propel the mainstream adoption of RSA in the late 1980s. Nearly all major American computer companies, including Motorola, Apple, Novell, and Microsoft, incorporated RSA software in their products by the early 1990s. The US Department of Defense also licensed the company’s encryption software. Hybrid encryption schemes and digital signatures were (and still are) two common use cases for the RSA algorithm.
Hybrid Encryption Schemes
Many applications implement hybrid encryption schemes, which use a combination of symmetric and asymmetric encryption. Using RSA (or any other asymmetric encryption algorithms) is much slower than symmetric encryption algorithms. While RSA is sufficient for very short messages, its inefficiencies become apparent when encrypting longer messages that require many operations.
Hybrid encryption enables users to perform one RSA encrypt operation on a symmetric key. The remaining work is done using a much faster symmetric encryption algorithm such as AES. One common example of an RSA/AES hybrid cryptosystem is HTTPS encryption, which ensures secure communication between web browsers and websites.
Digital Signatures
Besides data encryption, the RSA algorithm is also used for applications that use digital signatures for identity verification. In 1988, Lotus Notes 1.0 implemented the RSA digital signature scheme. This was the first widely-marketed software package to offer digital signatures. Although more robust algorithms for digital signatures (e.g. ECDSA) are available today, RSA digital signatures are still used in many applications today. For example, Alipay implements RSA for API data transmission.
Vulnerabilities In RSA Encryption
RSA encryption has gained widespread adoption, yet it actually has a number of well-known weaknesses. Some of these issues are inherent, meaning they were originally known about when the algorithm was first published in 1977. Others were discovered over time through cryptographic research and advances in computing.
Inherent Inefficiencies
RSA is considered to be a slow algorithm. One major flaw is that RSA can only be used to encrypt data that is no longer than the RSA key size. A possible solution for this is to increase the RSA key size. However, this would make encryption even slower. Each RSA "round" can encrypt 117 bytes (936 bits) of data. Encrypting more data requires a chaining mode, which hasn't been scrutinized on RSA as much as other encryption algorithms. Thus, there are security concerns about relying upon chaining mode to increase the capabilities of RSA. In essence, RSA encryption is powerful but really only meant to encrypt small amounts of data.
Security Threats Arise
RSA encryption faces several known security threats. Timing attacks and faulty key generation are two examples. In 1995, Paul Kocher first described timing attacks on RSA as well as other algorithms such as Diffie-Hellman and DSS. These attacks can be executed by an attacker who knows enough details about another user’s hardware to measure decryption times for several known ciphertexts. The attacker can use this information to decrypt RSA messages and also exploit the RSA digital signature scheme. In 2003, Dan Boneh and David Brumley demonstrated a more practical attack capable of recovering RSA factorizations over a network connection (e.g. an SSL-enabled webserver).
In 2017, researchers from Masaryk University announced the discovery of the ROCA vulnerability. This affected RSA keys generated by an algorithm embodied in a library from Infineon known as RSALib. This vulnerability allows the private key to be recovered from the public key in keys generated by certain devices. A number of smart cards and trusted platform modules (TPMs) were impacted.
Other potential RSA encryption security vulnerabilities include adaptive chosen ciphertext attacks, side-channel analysis attacks, and rainbow tables attacks.
RSA Factoring Challenge
As discussed above, RSA encryption relies upon the difficulty of finding the prime factors of very large composite numbers. There was a widespread belief in 1977 that a message encrypted with the original RSA implementation (RSA-129) would take millions of years to break. It turns out that the original implementation wasn’t nearly as secure as Rivest, Shamir, and Adleman had initially thought. In 1994, a distributed network of computers was able to break RSA-129 encryption.
The current state of the integer factorization problem as it relates to RSA encryption is indicated via the RSA Factoring Challenge. In this competition, participants are only given the modulus and have to solve for its two prime factors. This challenge was run by RSA Laboratories from 1991 to 2007. Although the challenge isn’t active today, cryptographers are still trying to factor the larger digit RSA numbers found on the RSA number list.
As of the time of this writing, RSA-250 is the largest factored RSA number. It was factored in February 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann.
The factoring of larger RSA numbers is inevitable, given advances in technology and ample time. That’s why it’s generally recommended that RSA implementations use at least RSA-2048 prior to 2030. RSA implementations used in 2030 and beyond should use at least RSA-3072. The lengths of RSA keys will need to continually increase to prevent security risks. Researchers project that RSA will likely be vulnerable to quantum attacks sometime around 2045. As quantum computers become a practical threat, it could be possible to break RSA-2048 encryption in only 8 hours.
New Public-Key Cryptosystems Emerge
During the 1990s, there was a movement to develop newer asymmetric encryption algorithms to replace RSA. Elliptic-curve cryptography (ECC) became a more favorable approach.
According to an article published in 1999, there were several reasons why ECC gained momentum. ECC is able to use much shorter keys for the same level of security as RSA. An RSA signature requires 1,024 bits, whereas an ECC signature requires 320 bits for the same level of security. Because of ECC's size advantage, it’s a better choice for less powerful devices such as mobile phones and smart cards. An RSA implementation in a mobile phone or a smart card required a cryptographic coprocessor, adding extra production costs. In contrast, no cryptographic coprocessor is needed with ECC.
Newer encryption techniques offer improved performance and greater security. As a result, they are more practical and used more frequently than RSA encryption. Regardless, the RSA algorithm’s continued high level of security performance and widespread adoption is impressive, especially considering it was one of the very first asymmetric encryption algorithms.
📧Komodo Newsletter
If you'd like to learn more about blockchain technology and keep up with Komodo's progress, subscribe to our newsletter. Begin your blockchain journey with Komodo today.
