: This article is about the RSA cryptosystem. For other meanings, see RSA (disambiguation).RSA is a cipher algorithm. It is an asymmetric algorithm and plays a key role in public key cryptography. It is widely used in electronic commerce protocols. The algorithm was described in 1977 by Ron Rivest, Adi Shamir and Len Adleman who were all at MIT at the time; the letters RSA are the initials of their surnames.
Clifford Cocks, a British mathematician working for GCHQ, described an equivalent system in an internal document in 1973. His discovery, however, was not revealed until 1997 due to its top-secret classification.
The security of the RSA system relies on the difficulty of factoring very large numbers; were such factorization to be quick, cryptanalysis of RSA messages would be quick as well. New fast algorithms in this field could render the RSA algorithm insecure. A working quantum computerMolecule of alanine used in NMR implementation of error correction. Qubits are implemented by spin states of carbon atoms. A quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superp implementing Shor's algorithmShor's algorithm is a quantum algorithm for factoring a number N in O((log N 3) time and O(log N space, named after Peter Shor. Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum could render RSA insecure through fast factorization. However, this is generally considered not a problem in the short term. At the moment, just as for all ciphers, inadequately long RSA keys are vulnerable to a brute force search approach. The likely effect of an improvement in factoring technique will be to increase the size of adequately long RSA keys. As of 2004, there is no known method of attack which is feasible against the basic algorithm, and sufficiently longIn cryptography, the key size (alternatively key length is a measure of the number of possible keys which can be used in a cipher. Because modern cryptography uses binary keys, the length is usually specified in bits. The length of a key is critical in de RSA keys make brute force attacks infeasible -- that is, effectively impossible.
The algorithm was patented by MIT in 1983Events January January 1 Beat Raaflaub became Basel Boys Choir's new conductor January 1 the ARPANET officially changes to use the Internet Protocol, creating the Internet. January 1 compulsory wearing of seat belts becomes law in the UK. January 2 The mu in the United States of AmericaThe United States of America also referred to as the United States U. America ¹ or the States is a federal republic in central North America, stretching from the Atlantic in the east to the Pacific Ocean in the west. It shares land borders with Canada in. The patent expired 21 September 2000This page is about the year 2000. See 2000 AD for the UK comic book, Number 2000 for other uses. 2000 is a leap year starting on Saturday (see link for calendar), and also the International Year for a Culture of Peace''. Events Y2K passes without the seri. Since the algorithm had been published prior to patent application, patent filing regulations in much of the rest of the world precluded patents elsewhere. Had Cocks' work been publicly known, a patent in the US would not have been possible either.
1 Operation
1.1 Key generation
Suppose a user Alice wishes to allow Bob to send her a private message over an insecure transmission medium. She takes the following steps to generate a public key and a private key:
- Choose two large prime numbersIn mathematics, a prime number or prime for short, is a natural number whose only distinct positive divisors are 1 and itself; otherwise it is called a composite number . Hence a prime number has exactly two divisors. The number 1 is neither prime nor com p ≠ q randomly and independently of each other. Compute N = p q.
- Choose an integer 1 < e < N which is coprime to (p-1)(q-1).
- Compute d such that d e ≡ 1 (mod (p-1)(q-1)).
- (Steps 2 and 3 can be performed with the extended Euclidean algorithm; see modular arithmetic.)
- (Step 3, rewritten, can also be found by finding integer x which causes d = (x(p-1)(q-1) + 1)/e to be an integer, then using the value of d (mod (p-1)(q-1)).
N and e are the public key, and N and d are the private key. Note that only d is a secret as N is known to the public. Alice transmits the public key to Bob, and keeps the private key secret. p and q are also very sensitive since they are the factors of N, and allow computation of d given e. They are sometimes securely deleted, and sometimes kept secret along with d in order to speed up decryption and signing using the Chinese Remainder Theorem.
