What is RSA? How does an RSA work?

RSA

The Rivest-Shamir-Adleman (RSA) encryption algorithm is an asymmetric encryption algorithm that is widely used in many products and services. Asymmetric encryption uses a key pair that is mathematically linked to encrypt and decrypt data. A private and public key are created, with the public key being accessible to anyone and the private key being a secret known only by the key pair creator. With RSA, either the private or public key can encrypt the data, while the other key decrypts it. This is one of the reasons RSA is the most used asymmetric encryption algorithm.

How does RSA work?

The option to encrypt with either the private or public key provides a multitude of services to RSA users. If the public key is used for encryption, the private key must be used to decrypt the data. This is perfect for sending sensitive information across a network or Internet connection, where the recipient of the data sends the data sender their public key. The sender of the data then encrypts the sensitive information with the public key and sends it to the recipient. Since the public key encrypted the data, only the owner of the private key can decrypt the sensitive data. Thus, only the intended recipient of the data can decrypt it, even if the data were taken in transit.

The other method of asymmetric encryption with RSA is encrypting a message with a private key. In this example, the sender of the data encrypts the data with their private key and sends encrypted data and their public key along to the recipient of the data. The recipient of the data can then decrypt the data with the sender’s public key, thus verifying the sender is who they say they are. With this method, the data could be stolen and read in transit, but the true purpose of this type of encryption is to prove the identity of the sender. If the data were stolen and modified in transit, the public key would not be able to decrypt the new message, and so the recipient would know the data had been modified in transit.

The technical details of RSA work on the idea that it is easy to generate a number by multiplying two sufficiently large numbers together, but factorizing that number back into the original prime numbers is extremely difficult. The public and private key are created with two numbers, one of which is a product of two large prime numbers. Both use the same two prime numbers to compute their value. RSA keys tend to be 1024 or 2048 bits in length, making them extremely difficult to factorize, though 1024 bit keys are believed to breakable soon.

Who uses RSA encryption?

As previously described, RSA encryption has a number of different tasks that it is used for. One of these is digital signing for code and certificates. Certificates can be used to verify who a public key belongs to, by signing it with the private key of the key pair owner. This authenticates the key pair owner as a trusted source of information. Code signing is also done with the RSA algorithm. To ensure the owner is not sending dangerous or incorrect code to a buyer, the code is signed with the private key of the code creator. This verifies the code has not been edited maliciously in transit, and that the code creator verifies that the code does what they have said it does.

RSA was used with Transport Layer Security (TLS) to secure communications between two individuals. Other well-known products and algorithms, like the Pretty Good Privacy algorithm, use RSA either currently or in the past. Virtual Private Networks (VPNs), email services, web browsers, and other communication channels have used RSA as well. VPNs will use TLS to implement a handshake between the two parties in the information exchange. The TLS Handshake will use RSA as its encryption algorithm, to verify both parties are who they say who they are.

RSA Vulnerabilities

Though viable in many circumstances, there are still a number of vulnerabilities in RSA that can be exploited by attackers. One of these vulnerabilities is the implementation of a long key in the encryption algorithm. Algorithms like AES are unbreakable, while RSA relies on the size of its key to be difficult to break. The longer an RSA key, the more secure it is. Using prime factorization, researchers managed to crack a 768 bit key RSA algorithm, but it took them 2 years, thousands of man hours, and an absurd amount of computing power, so the currently used key lengths in RSA are still safe. The National Institute of Science and Technology (NIST) recommends a minimum key length of 2048 bits now, but many organizations have been using keys of length 4096 bits. Other ways RSA is vulnerable are:

  • Weak Random Number Generator: When organizations use weak random number generators, then the prime numbers created by them are much easier to factor, thus giving attackers an easier time of cracking the algorithm.
  • Weak Key Generation: RSA keys have certain requirements relating to their generation. If the prime numbers are too close, or if one of the numbers making up the private key is too small, then the key can be solved for much easier.
  • Side Channel Attacks: Side channel attacks are a method of attack that take advantage of the system running the encryption algorithm, as opposed to the algorithm itself. Attackers can analyze the power being used, use branch prediction analysis, or use timing attacks to find ways to ascertain the key used in the algorithm, thus compromising the data.