MFT Resource Center

RSA

RSA is one of the first and most widely used cryptosystems for securing data.

What Does RSA Stand For?

The letters in RSA represent the initials of the three people who invented the RSA algorithm in 1977: computer scientists Ron Rivest and Adi Shamir, and mathematician Leonard Adleman.

Working together as a team at the Massachusetts Institute of Technology, Rivest, Shamir, and Adleman set out to discover a one-way mathematical function, or algorithm, that would be difficult to invert. Their hope was that such a function would serve as the basis for a new kind of cryptography that had been defined in theory but not yet actualized. This theorized concept, known as an asymmetric public-private key cryptosystem, relied on the security provided by a mathematical function that could be used to generate key numbers. A person with knowledge of this function would be able to use it in the forward direction (one-way) to generate the key numbers, but no one would be able to invert the function — that is, trace it back to figure out exactly how the key numbers had been generated — in effect, cracking the code.

Rivest, Shamir, and Adleman considered different ways of constructing their function, involving the use of number theory, permutation polynomials, and other mathematical techniques, but there were inherent weaknesses in all these approaches. Ultimately, the researchers hit upon the idea of using the factorization problem of prime numbers to create a strong and secure function that has come to be known as the RSA algorithm.

How Does RSA Work?

RSA security is, in essence, an asymmetric public-private key cryptosystem. This kind of cryptosystem consists of the following elements:

Public Key

The published, publicly known key that is used to encrypt the data. Anyone can access the public key and use it to encrypt data. In RSA encryption, the public key is based on the product of two large prime numbers.

This product is known as the modulus, and it lies at the heart of the RSA algorithm. The algorithm calls for two large prime numbers, p and _q_, that are randomly generated. It is easy to multiply p and q together to generate the product, denoted by _n_. But due to the factorization problem of prime numbers, it is exceedingly difficult to factor this product. In other words, given _n_, it is nearly impossible to figure out what p and q are.

The length of n, expressed in bits, is known as the RSA key length.

Private Key

The secret key that is used to decrypt the data. In RSA, the private key consists of an exponent calculated from the two secret prime numbers using Carmichael's totient function and the extended Euclidean algorithm. This exponent is typically denoted as _d_.

Since RSA uses different keys for encrypting and decrypting messages, it is known as an asymmetric cryptosystem.

How RSA Is Used: Key Encryption & Signatures

In comparison with symmetric encryption methods, the RSA algorithm has a relatively slow processing speed. Because of its slow pace, RSA is not typically used to directly encrypt data. Rather, RSA is usually used to encrypt the keys in a faster, symmetric cryptosystem, such as AES that is then used to encrypt and decrypt the actual data.

RSA is also used extensively to validate the digital signatures of unknown senders. As an asymmetric cryptosystem, RSA offers distinct security advantages to the recipients of data sent over a network. Thus, RSA is widely used by web browsers, email applications, chat programs, VPN software, and other communication platforms that rely on the secure transmission of data to and from strangers.

Is RSA Secure?

As a rule of thumb, longer public keys make for more secure RSA encryption schemes. This is because the factorization problem increases in difficulty as its underlying prime numbers get bigger.

With enough computing speed and power, any factorization problem can eventually be solved using Shor's algorithm. 1024-bit RSA keys were once considered the industry standard for security, but experts now recommend keys with a minimum of 2048 bits to guard against brute force attacks launched using the latest generation of computer processors. Some researchers have already devised a 4096-bit key in anticipation of future advancements in processing speeds and quantum computing.