RSA (cryptosystem)

RSA is a type of cryptosystem—a method of encoding and decoding messages—used to send sensitive data and information over an insecure network such as the Internet. RSA was developed in the 1970s and named after its creators, Ron Rivest, Adi Shamir, and Leonard Adleman, computer scientists at the Massachusetts Institute of Technology (MIT). The RSA system is an example of asymmetric cryptography, which uses a public key to encrypt data and a private key to decrypt data. RSA data keys are derived from factors based on two large prime numbers—numbers divisible only by 1 and itself—creating a solution considered too time-consuming to decode without the accompanying key. On the strength of its complexity and ability of both public and private keys to encrypt and decrypt data, RSA is one of the most widely used asymmetric cryptosystems in computer security.

Background

Coded messages and cryptography are ancient concepts that are almost as old as language itself. Egyptian priests of the third millennium BCE used a secret language they considered divine and unworthy to be understood by the average person. This language was written in coded symbols and jealously guarded by the priests. Many early forms of cryptography—a name derived from the ancient Greek kryptos (secret) and graphe (writing)—were simple substitution ciphers. These coded messages either used a reversed alphabet or replaced one letter with another from a corresponding set of scrambled letters. While these codes were not too difficult to decipher with a little work, at a time when literacy was uncommon, they were usually sufficient.

As new ways were devised to break coded information, the methods of encryption grew in complexity over the centuries. By the late twentieth century, technology had increased to the point where a sophisticated system was necessary to protect sensitive information. Prior to the 1970s, encryption and decryption were performed using the same key. A key is a variable set of values generated by a mathematical formula called an algorithm. The key creates a unique string of encoded, or scrambled, information that can be relayed to a destination. At the destination, another version of the same key is used to unscramble the encoded data into its original form. The larger the key, the more difficult the encryption is to break. Private keys, or secret keys, remain at the source and destination of the information. Private-key cryptography is considered safe as long as the key is not stolen or intercepted.

Overview

As technology developed throughout the 1970s, it became more common for data to be transmitted through computer networks. This presented a problem for private-key cryptography since both sender and receiver needed to have the same private key for information to be transmitted securely. Sending the private key through a network was risky since the data could be intercepted. Stanford University researchers Whitfield Diffie and Martin Hellman solved that problem in 1976 by developing public-key cryptography. In this system, a public encryption key is openly published and available to be accessed by any computer. Data is encrypted using the public key, but it can only be translated by a private decryption key at the receiving computer. Computers could authenticate the source of the information by using a digital signature unique to each computer.

In 1977, MIT computer scientist Ron Rivest came up with an algorithm he felt was more practical than Diffie and Hellman's method. Rivest shared his idea with colleagues Adi Shamir and Leonard Adleman and the trio developed a new public-key cryptosystem they named using their initials—RSA. The RSA cryptosystem was published in a 1977 edition of Scientific American magazine and distributed free to anyone who submitted a stamped, self-addressed envelope to the developers. Thousands of people worldwide took them up on the offer.

The RSA cryptosystem works by running an algorithm that generates two random prime numbers. The numbers—designated as p and q—need to be large and close to each other in value. In cryptosystem terms, a number is "large" if it is 512 bits or more. A bit, which is short for binary digit, is the smallest unit of data used by a computer. A 512-bit number translates to 155 decimal digits. Multiplying p and q provides a value (n) known as the modulus. The modulus is used as the basis for both public and private keys and must be at least 1024 bits, a measure known as the key length.

The public key consists of the modulus and another prime number called the public exponent (e). The number 65537 is often chosen for the value e since it is a prime number that is not too large. The public exponent does not have to be kept secret since the public key is available to anyone. The private key uses the modulus and a private exponent (d) which is generated by an algorithm and kept secret by the decryption source.

The sending computer begins the encryption process by first obtaining the receiving computer's public key, which consists of the modulus and public exponent. The computer uses this information to convert the data—in a readable form called plaintext—into an unintelligible code known as ciphertext. The ciphertext is transmitted over the network to the receiving computer where the private key—the modulus and private exponent—decrypt the data back into plaintext. The RSA cryptosystem allows both information and the digital signature to be sent in this manner.

The effectiveness of the RSA system is based on the difficulty in factoring large prime numbers. Generating random prime numbers is an easy task, as is multiplying them to get a result. Factoring is the mathematical process of separating a number into numerical equations that make up its component parts. For example, factors of 15 would be 1, 3, 5, and 15 since 1 times 15 and 3 times 5 are the only combinations that equal 15. Prime numbers can only be factored by 1 and itself. Determining if a sufficiently large number is a prime number by testing equations to see if they match is a long, complicated process. Some estimates claim testing a 1024-bit number to determine if it is a prime number would take a multimillion-dollar computer a year to complete the task.

Bibliography

"Cryptography: RSA Algorithm." Virginia Polytechnic Institute and State University, courses.cs.vt.edu/~cs5204/fall00/protection/rsa.html. Accessed 21 June 2017.

D'Agapeyeff, Alexander. Codes and Ciphers—A History of Cryptography. Read Books, 2013.

Gupta, Prakash C. "RSA Cryptosystem." Cryptography and Network Security. PHI Learning, 2015, pp. 128–134.

"History of Encryption." SANS Institute, www.sans.org/reading-room/whitepapers/vpns/history-encryption-730. Accessed 21 June 2017.

Ireland, David. "RSA Algorithm." DI Management Services, 6 Dec. 2016, www.di-mgt.com.au/rsa‗alg.html. Accessed 21 June 2017.

Kaliski, Burt. "The Mathematics of the RSA Public-Key Cryptosystem." RSA Laboratories, www.mathaware.org/mam/06/Kaliski.pdf. Accessed 21 June 2017.

"RSA Algorithm (Rivest-Shamir-Adleman)." Tech Target, searchsecurity.techtarget.com/definition/RSA. Accessed 21 June 2017.

Weisstein, Eric W. "RSA Encryption." Wolfram MathWorld, mathworld.wolfram.com/RSAEncryption.html. Accessed 21 June 2017.