RSA cryptosystem

The RSA cryptosystem is a foundational family of public-key cryptosystems. It is one of the oldest methods used for secure data transmission. This system allows users to communicate privately across insecure networks. It is used for digital signatures, such as RSASSA-PSS or RSA-FDH. It also provides public-key encryption for very short messages. These messages are often single-use symmetric keys in a hybrid cryptosystem. The system relies on complex number theory to protect information.

To understand RSA, one must understand the mechanism of key generation. A user begins by choosing two large prime numbers, p and q. These numbers are chosen at random and kept strictly secret. The user then computes the modulus, n, by multiplying p and q together. This modulus, n, is used in both the public and private keys. Next, the user calculates Carmichael's totient function, which is denoted as λ(n). This is calculated as the least common multiple of (p - 1) and (q - 1). The user then selects a public exponent, e, such that 1 < e < λ(n). This exponent must be coprime to λ(n), meaning they share no common factors. Finally, the user calculates the private exponent, d, as the modular multiplicative inverse of e modulo λ(n). The public key consists of the pair (n, e). The private key consists of the pair (n, d).

Once the keys are ready, the process of encryption and decryption begins. Suppose Bob wants to send a secret message to Alice. Bob first obtains Alice's public key, which includes n and e. Bob converts his message into an integer, m, using a padding scheme. He then computes the ciphertext, c, using the formula c = m^e mod n. This process is called modular exponentiation. After Bob sends the ciphertext, Alice receives it. Alice uses her private key, d, to recover the message. She calculates m = c^d mod n. This mathematical operation reverses the encryption. Alice then reverses the padding scheme to read the original message.

RSA can also be used for digital signatures to prove identity. In this process, Alice produces a hash value of her message. She then raises this hash to the power of her private exponent, d, modulo n. This result is her digital signature. Bob can verify the signature using Alice's public key, e. He raises the signature to the power of e modulo n. If the result matches the hash of the message, the signature is valid. This ensures the message was truly sent by Alice and was not changed.

The history of RSA involves a fascinating race of discovery. The concept of asymmetric public-private key systems was attributed to Whitfield Diffie and Martin Hellman in 1976. They introduced digital signatures and attempted to use number theory. However, they did not fully realize a one-way function. In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman worked at MIT. They spent a year trying to create a function that was hard to invert. Rivest and Shamir proposed functions, while Adleman searched for mathematical weaknesses. In April 1977, Rivest had a breakthrough. He worked through the night to formalize the idea. By daybreak, much of the RSA paper was ready.

A secret history exists involving the British signals intelligence agency, GCHQ. In 1973, mathematician Clifford Cocks developed an equivalent system. Because computers were very expensive then, his work was considered a curiosity. It was never deployed and remained top-secret. His work was not declassified until 1997. Meanwhile, MIT was granted a patent for the RSA algorithm in 1983. This patent only had legal standing in the United States. The patent was set to expire in 2000. On September 6, 2000, RSA Security released the algorithm into the public domain.

The security of RSA is tied to the factoring problem. This is the difficulty of finding the prime factors of a very large number. It is easy to multiply two large primes to get a product. However, it is extremely difficult to work backward from the product to the primes. Breaking RSA encryption is known as the RSA problem. Scientists are still debating if the RSA problem is as hard as factoring. If a large enough key is used, there are no known published methods to defeat it. This mathematical barrier is what keeps modern digital communication secure.