RSA (cryptosystem)
Introduction
The RSA (Rivest-Shamir-Adleman) Cryptosystem is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem.
History
The RSA algorithm was first publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames, listed in the same order as on the paper. The idea of an asymmetric public-private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman, who published this concept in 1976. They also introduced digital signatures and attempted to apply number theory. Their formulation used a shared secret key created from exponentiation of some number, modulo a prime number, but they couldn't figure out how to do encryption and decryption. Rivest, Shamir, and Adleman developed what is now known as RSA as a solution to the key exchange problem, and it has become one of the most widely used encryption and authentication algorithms.
Mathematical Background
RSA involves a public key and a private key. The public key can be known by everyone, and it is used for encrypting messages. The intention is that messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The public key consists of two numbers where one number is multiplication of two large prime numbers. And private key is also derived from the same two prime numbers. So the security of the RSA depends on the secrecy of the prime numbers used at the time of key generation.
RSA Algorithm
The RSA algorithm involves four steps: key generation, key distribution, encryption and decryption.
Key Generation
The key generation algorithm is the most complex part of RSA. The aim of the key generation algorithm is to generate the RSA public key and RSA private key. The RSA public key consists of two integers, and the RSA private key is also two integers. The key generation algorithm works as follows:
1. Generate two distinct prime numbers randomly. 2. Compute the modulus for both public and private keys. 3. Compute the totient of the modulus. 4. Choose an integer for the public key exponent. 5. Compute the private key exponent. 6. Validate the keys.
Key Distribution
After the keys have been generated, the process of encryption and decryption are relatively straightforward and computationally easy. The public key is made publicly available and is distributed widely. The private key is kept secret.
Encryption
The encryption process is simple and efficient. The sender represents the plaintext message as a series of numbers m. Each number is less than n (the receiver's public key modulus). The ciphertext c is computed from the plaintext m as follows:
c = m^e mod n
Decryption
The receiver uses his private key (n, d) to compute the plaintext m from the ciphertext c as follows:
m = c^d mod n
Security of RSA
The security of RSA is based on the fact that it is easy to calculate the product of two large primes, but factoring that product is believed to be computically infeasible. As of 2009, the largest known prime number has 17,425,170 digits. RSA key sizes are typically 1024 or 2048 bits. However, RSA is not used to directly encrypt messages. Instead, RSA is used to encrypt a key which is then used to encrypt the plaintext.
Applications of RSA
RSA is widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys and the use of up-to-date implementations. As an example, RSA is used to secure credit card information in Apple Pay. Other examples include Secure Socket Layer (SSL), Transport Layer Security (TLS), and Secure Shell (SSH).