Editing RSA cryptosystem (section)

{{short description|Algorithm for public-key cryptography}}
{{about|a cryptosystem|the company|RSA Security}}
{{Infobox block cipher
| name          = RSA cryptosystem
| designers     = [[Ron Rivest]],<ref name="rsa"/> [[Adi Shamir]], and [[Leonard Adleman]]
| publish date  = 1977
| type          = Public-Key
| derived from  =
| derived to    =
| related to    =
| certification = [[PKCS1|PKCS#1]], [[ANSI X9.31]]
| key size      = variable but typically 2,048 to 4,096 bits
| block size    =
| structure     =
| rounds        = 1
| cryptanalysis = [[General number field sieve]] for classical computers;<br />[[Shor's algorithm]] for quantum computers.<br />An [[RSA-250|829-bit key]] has been broken.
}}

The '''RSA''' ('''Rivest–Shamir–Adleman''') '''cryptosystem''' is a [[public-key cryptography|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 [[classified information|declassified]] in 1997.<ref>{{cite web |url=http://www.bristol.ac.uk/graduation/honorary-degrees/hondeg08/cocks.html |first=Nigel |last=Smart |title=Dr Clifford Cocks CB |access-date=August 14, 2011 |date=February 19, 2008 |publisher=[[Bristol University]]}}</ref>

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 number]]s, 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.<ref name="rsa">{{cite journal
 | last1 = Rivest | first1 = R.
 | last2 = Shamir | first2 = A.
 | last3 = Adleman | first3 = L.
 | s2cid = 2873616
 | url = http://people.csail.mit.edu/rivest/Rsapaper.pdf
 | title = A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
 | journal = [[Communications of the ACM]]
 | volume = 21 | issue = 2 | pages = 120–126 | date = February 1978
 | doi = 10.1145/359340.359342| citeseerx = 10.1.1.607.2677
 | archive-url = https://web.archive.org/web/20230127011251/http://people.csail.mit.edu/rivest/Rsapaper.pdf
 | archive-date = 2023-01-27
 | url-status = dead
 }}</ref>

The security of RSA relies on the practical difficulty of [[factorization|factoring]] the product of two large [[prime number]]s, 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.<ref>{{Cite journal|last=Castelvecchi|first=Davide|date=2020-10-30|title=Quantum-computing pioneer warns of complacency over Internet security|url=https://www.nature.com/articles/d41586-020-03068-9|journal=Nature|language=en|volume=587|issue=7833|pages=189|doi=10.1038/d41586-020-03068-9|pmid=33139910 |bibcode=2020Natur.587..189C |s2cid=226243008 |url-access=subscription}} 2020 interview of [[Peter Shor]].</ref> 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 algorithm|symmetric-key]] cryptography, which are then used for bulk encryption–decryption.