RSA (cryptosystem)

RSA
General
DesignersRon Rivest,[1] Adi Shamir, and Leonard Adleman
First published1977
CertificationPKCS#1, ANSI X9.31
Cipher detail
Key sizesvariable but 2,048 to 4,096 bit typically
Rounds1
Best public cryptanalysis
General number field sieve for classical computers;
Shor's algorithm for quantum computers.
An 829-bit key has been broken.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.[2]

In a public-key cryptosystem, the encryption key is public and distinct from the decryption key, which is kept secret (private). An RSA user creates and publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers are kept secret. Messages can be encrypted by anyone, via the public key, but can only be decrypted by someone who knows the private key.[1]

The security of RSA relies on the practical difficulty of factoring the product of two large prime numbers, the "factoring problem". Breaking RSA encryption is known as the RSA problem. Whether it is as difficult as the factoring problem is an open question.[3] There are no published methods to defeat the system if a large enough key is used.

RSA is a relatively slow algorithm. Because of this, it is not commonly used to directly encrypt user data. More often, RSA is used to transmit shared keys for symmetric-key cryptography, which are then used for bulk encryption–decryption.

  1. ^ a b Rivest, R.; Shamir, A.; Adleman, L. (February 1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (PDF). Communications of the ACM. 21 (2): 120–126. CiteSeerX 10.1.1.607.2677. doi:10.1145/359340.359342. S2CID 2873616. Archived from the original (PDF) on 2023-01-27.
  2. ^ Smart, Nigel (February 19, 2008). "Dr Clifford Cocks CB". Bristol University. Retrieved August 14, 2011.
  3. ^ Castelvecchi, Davide (2020-10-30). "Quantum-computing pioneer warns of complacency over Internet security". Nature. 587 (7833): 189. Bibcode:2020Natur.587..189C. doi:10.1038/d41586-020-03068-9. PMID 33139910. S2CID 226243008. 2020 interview of Peter Shor.