RSA (cryptosystem)

RSA (cryptosystem). RSA is a widely deployed public-key cryptosystem that enables secure data transmission and is fundamental to modern Internet security. Its security relies on the computational difficulty of factoring the product of two large prime numbers, a problem central to computational number theory. Named for its creators Ron Rivest, Adi Shamir, and Leonard Adleman of the Massachusetts Institute of Technology, the algorithm was first publicly described in 1977 and has since become a cornerstone of protocols like TLS/SSL.

● Operation

The RSA algorithm involves a key generation phase that produces a matched public key and private key. A user freely distributes their public key, which consists of a modulus *n* (the product of two large primes) and an encryption exponent *e*. Anyone can use this public key to encrypt a message into ciphertext. The corresponding private key, which includes a decryption exponent *d*, is kept secret by the owner and is required to decrypt the ciphertext back into the original message. This asymmetric cryptography model eliminates the need for a pre-shared secret, solving the key distribution problem inherent in symmetric-key algorithms like the DES. The encryption and decryption processes are modular exponentiation operations performed within the modular arithmetic of the ring of integers modulo n.

● Security

The security of the system is based on the presumed difficulty of the RSA problem: deriving the plaintext from the ciphertext and the public key. This problem is intimately related to the integer factorization problem, as recovering the private key requires factoring the public modulus *n* into its two prime factors. While no efficient classical algorithm for factoring large integers is known, Shor's algorithm demonstrates that a sufficiently powerful quantum computer could break RSA. Therefore, the security level depends on key size; historically, keys of 512 bits have been factored by projects like RSA Factoring Challenge, leading to current recommendations for 2,048 or 4,096-bit keys. Additional security concerns include side-channel attacks and improper implementation, not the core mathematical problem.

● Practical considerations

In practice, RSA is rarely used to encrypt data directly due to its computational intensity and limitations on message size. Instead, it is commonly employed within hybrid cryptosystems, where it encrypts a session key for a faster symmetric-key algorithm like the AES. It is also the primary algorithm for creating digital signatures, used to verify authenticity and integrity in standards like PKCS#1 and PKI. Implementations must carefully avoid vulnerabilities such as those described in Bleichenbacher's attack on PKCS1 v1.5. Performance is a key consideration, leading to the use of a small public exponent like 65,537 and optimization techniques like the Chinese remainder theorem.

● History

The concept of public-key cryptography was first proposed by Whitfield Diffie and Martin Hellman in their 1976 paper, though they did not propose a practical implementation. In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology developed the first such practical system, which was later detailed in their 1978 Communications of the ACM paper. The algorithm was patented by the MIT and licensed commercially by RSA Security, playing a pivotal role in the early commercial Internet. An equivalent system was developed earlier in 1973 by Clifford Cocks of the GCHQ, but this work remained classified until 1997.

● Mathematical principles

The mathematics underpinning the cryptosystem derives from Euler's theorem, a generalization of Fermat's little theorem within modular arithmetic. Key generation uses two distinct large prime numbers, *p* and *q*, to compute the modulus *n = pq* and Euler's totient function φ(*n*). The public exponent *e* is chosen as an integer coprime to φ(*n*), and the private exponent *d* is computed as the modular multiplicative inverse of *e* modulo φ(*n*). Encryption of a message *m* is the computation *c ≡ m^e (mod n)*, and decryption is *m ≡ c^d (mod n)*. The correctness of decryption is guaranteed by the properties of modular exponentiation and the Chinese remainder theorem.

● Implementations

RSA is implemented in nearly all major cryptographic libraries and is integral to many security protocols. Notable software libraries include OpenSSL, GnuTLS, and the Microsoft CryptoAPI. It is specified in standards such as PKCS#1 from RSA Security, IEEE P1363, and ANSI X9.31. Hardware implementations are found in smart cards, HSMs, and the TPM. For embedded systems, optimized algorithms like Montgomery modular multiplication are used. The transition to post-quantum cryptography has prompted standards bodies like the NIST to evaluate new algorithms, though RSA remains dominant in current IETF protocols like TLS.

Category:Cryptographic algorithms Category:Public-key cryptography