RSA

RSA is a foundational public-key cryptosystem widely used for secure data transmission. It was first publicly described in 1977 by cryptographers Ron Rivest, Adi Shamir, and Leonard Adleman, for whom the algorithm is named. The security of RSA relies on the practical difficulty of factoring the product of two large prime numbers, known as the RSA problem.

● Overview

RSA is one of the earliest practical implementations of public-key cryptography, a concept first proposed by Whitfield Diffie and Martin Hellman. It enables secure communication over insecure channels without prior key exchange and is instrumental for digital signatures and key exchange protocols. The algorithm's versatility led to its rapid adoption in securing Internet communications, including protocols like TLS and SSL. Its development marked a pivotal moment in modern cryptography, moving beyond traditional symmetric-key algorithms.

● Mathematical foundations

The core mathematical principle of RSA is rooted in number theory, specifically the properties of modular arithmetic and Euler's totient function. The algorithm's security is based on the presumed intractability of the integer factorization problem for large semiprime numbers. Central to the process is Euler's theorem, which generalizes Fermat's little theorem and underpins the encryption and decryption operations. The difficulty of deriving the private key from the public key is equivalent to factoring a large integer, a problem studied since the era of Carl Friedrich Gauss.

● Key generation

The process begins by selecting two distinct, large prime numbers, typically using algorithms like the Miller–Rabin primality test. The product of these primes, denoted *n*, forms the modulus for both the public and private keys. A public exponent *e* is then chosen, often a small number like 65,537, which is coprime to Euler's totient of *n*. The corresponding private exponent *d* is computed as the modular multiplicative inverse of *e*, a calculation efficiently performed using the extended Euclidean algorithm. The public key consists of the pair (*n*, *e*), while the private key is (*n*, *d*).

● Encryption and decryption

For encryption, a message is first converted into an integer *m* smaller than the modulus *n*. The ciphertext *c* is computed by raising *m* to the power of the public exponent *e* and taking the result modulo *n*. Decryption is performed by the recipient using the private key, computing *m* as *c* raised to the power of the private exponent *d*, again modulo *n*. This process relies on the correctness of Euler's theorem, ensuring the original message is recovered. For digital signatures, the operations are reversed, with the private key used to sign and the public key used for verification.

● Security and practical considerations

The security of RSA depends on the key size; historically, keys of 512 bits were used, but advances in computational power and algorithms like the general number field sieve have necessitated larger keys, with 2,048 bits now a minimum standard. Direct attacks include integer factorization efforts, such as those undertaken by the GIMPS project, and side-channel attacks that exploit physical implementations. Inappropriate use, such as encrypting predictable messages or using a poorly generated random number, can lead to vulnerabilities. The emergence of quantum computing poses a future threat through Shor's algorithm, which could efficiently break RSA.

● Implementations and standards

RSA is implemented in many cryptographic libraries, including OpenSSL, GnuTLS, and Microsoft CryptoAPI. It is standardized in documents such as PKCS#1 from RSA Security and FIPS 186-4 from the NIST. The algorithm is a core component of the X.509 certificate standard used by Certificate Authorities for PKI. Widely used protocols like TLS, SSH, and PGP integrate RSA for authentication and key establishment, ensuring its continued presence in global digital security. Category:Cryptographic algorithms Category:Public-key cryptography