| General | |
|---|---|
| Designers | Ron Rivest,Adi Shamir, andLeonard Adleman |
| First published | 1977 |
| Certification | PKCS#1,ANSI X9.31 |
| Cipher detail | |
| Key sizes | variable but typically 2,048 to 4,096 bits |
| Rounds | 1 |
| Best publiccryptanalysis | |
| General number field sieve for classical computers; Shor's algorithm for quantum computers. An829-bit key has been broken. | |
TheRSA (Rivest–Shamir–Adleman)cryptosystem is a family ofpublic-key cryptosystems, one of the oldest widely used for secure data transmission. Theinitialism "RSA" comes from the surnames ofRon Rivest,Adi Shamir andLeonard Adleman, who publicly described the algorithm in 1977.[1][2][3] An equivalent system was developed secretly in 1973 atGovernment Communications Headquarters (GCHQ), the Britishsignals intelligence agency, by the English mathematicianClifford Cocks. That system wasdeclassified in 1997.[4]
RSA is used indigital signature such asRSASSA-PSS orRSA-FDH,[5][6][7][8][9][10]public-key encryption of very short messages (almost always a single-usesymmetric key in ahybrid cryptosystem) such asRSAES-OAEP,[11][12][13][10]andpublic-key key encapsulation.[14][15][16]
In RSA-based cryptography, a user'sprivate key—which can be used to sign messages, or decrypt messages sent to that user—is a pair of large prime numbers chosen at random and kept secret.A user'spublic key—which can be used to verify messages from the user, or encrypt messages so that only that user can decrypt them—is the product of the prime numbers.
The security of RSA is related to the difficulty offactoring the product of two largeprime numbers, the "factoring problem". Breaking RSA encryption is known as theRSA problem. Whether it is as difficult as the factoring problem is an open question.[17] There are no published methods to defeat the system if a large enough key is used.
The idea of an asymmetric public-private key cryptosystem is attributed toWhitfield Diffie andMartin Hellman, who published this concept in 1976. They also introduced digital signatures and attempted to apply number theory. Their formulation used a shared-secret-key created from exponentiation of some number, modulo a prime number. However, they left open the problem of realizing a one-way function, possibly because the difficulty of factoring was not well-studied at the time.[18] Moreover, likeDiffie-Hellman, RSA is based onmodular exponentiation.
Ron Rivest,Adi Shamir, andLeonard Adleman at theMassachusetts Institute of Technology made several attempts over the course of a year to create a function that was hard to invert. Rivest and Shamir, as computer scientists, proposed many potential functions, while Adleman, as a mathematician, was responsible for finding their weaknesses. They tried many approaches, including "knapsack-based" and "permutation polynomials". For a time, they thought what they wanted to achieve was impossible due to contradictory requirements.[19] In April 1977, they spentPassover at the house of a student and drank a good deal of wine before returning to their homes at around midnight.[20] Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one-way function. He spent the rest of the night formalizing his idea, and he had much of the paper ready by daybreak. The algorithm is now known as RSA – the initials of their surnames in same order as their paper.[21]
Clifford Cocks, an Englishmathematician working for theBritish intelligence agencyGovernment Communications Headquarters (GCHQ), described a similar system in an internal document in 1973.[22] However, given the relatively expensive computers needed to implement it at the time, it was considered to be mostly a curiosity and, as far as is publicly known, was never deployed. His ideas and concepts were not revealed until 1997 due to its top-secret classification.
Kid-RSA (KRSA) is a simplified, insecure public-key cipher published in 1997, designed for educational purposes. Kid-RSA gives insight into RSA and other public-key ciphers, analogous tosimplified DES.[23][24][25][26][27]
Apatent describing the RSA algorithm was granted toMIT on 20 September 1983:U.S. patent 4,405,829 "Cryptographic communications system and method". FromDWPI's abstract of the patent:
The system includes a communications channel coupled to at least one terminal having an encoding device and to at least one terminal having a decoding device. A message-to-be-transferred is enciphered to ciphertext at the encoding terminal by encoding the message as a number M in a predetermined set. That number is then raised to a first predetermined power (associated with the intended receiver) and finally computed. The remainder or residue, C, is... computed when the exponentiated number is divided by the product of two predetermined prime numbers (associated with the intended receiver).
A detailed description of the algorithm was published in August 1977, inScientific American'sMathematical Games column.[2][21] This preceded the patent's filing date of December 1977. Consequently, the patent had no legal standing outside theUnited States. Had Cocks' work been publicly known, a patent in the United States would not have been legal either.
When the patent was issued,terms of patent were 17 years. The patent was about to expire on 21 September 2000, butRSA Security released the algorithm to the public domain on 6 September 2000.[28]
The RSA algorithm involves four steps:key generation, key distribution, public-key operation (used for encryption or verifying a signature), and private key operation (used for decryption or signing a message).
A basic principle behind RSA is the observation that it is practical to find three very large positive integerse,d, andn, such that for all integersx (0 ≤x <n), both(xe)d andx have the sameremainder when divided byn (they arecongruent modulon):However, when given onlye andn, it is infeasible to computeeth roots modulon; that is, for uniform randomy (0 ≤y <n), it is extremely difficult to findx such thatxe ≡y (modn).
The integersn ande form the public key andd is the private key. Themodular exponentiation to the power ofe is used in encryption and in verifying signatures, and exponentiation to the power ofd is used in decryption and in signing messages.
The keys for the RSA algorithm are generated in the following way:
Thepublic key consists of the modulusn and the public exponente. Theprivate key consists of the private exponentd, which must be kept secret.p,q, andλ(n) must also be kept secret because they can be used to calculated. In fact, they can all be discarded afterd has been computed.[31]
In the original RSA paper,[3] theEuler totient functionφ(n) = (p − 1)(q − 1) is used instead ofλ(n) for calculating the private exponentd. Sinceφ(n) is always divisible byλ(n), the algorithm works as well. The possibility of usingEuler totient function results also fromLagrange's theorem applied to themultiplicative group of integers modulopq. Thus anyd satisfyingd⋅e ≡ 1 (modφ(n)) also satisfiesd⋅e ≡ 1 (modλ(n)). However, computingd moduloφ(n) will sometimes yield a result that is larger than necessary (i.e.d >λ(n)). Most of the implementations of RSA will accept exponents generated using either method (if they use the private exponentd at all, rather than using the optimized decryption methodbased on the Chinese remainder theorem described below), but some standards such asFIPS 186-4 (Section B.3.1) may require thatd <λ(n). Any "oversized" private exponents not meeting this criterion may always be reduced moduloλ(n) to obtain a smaller equivalent exponent.
Note: The authors of the original RSA paper carry out the key generation by choosingd and then computinge as themodular multiplicative inverse ofd moduloφ(n), whereas most current implementations of RSA, such as those followingPKCS#1, do the reverse—choosee and computed from it. Sincee can safely be small and fixed, whereasd must be chosen from a large enough space to resist attack, the modern approach can reduce the cost of the public-key operation without loss of security.[3][32]
Suppose thatBob wants to send secret messages toAlice, or verify messages from Alice. If they decide to use RSA, Bob must know Alice's public key to encrypt his secret messages or verify Alice's messages, and Alice must use her private key to decrypt Bob's secret messages or sign her own messages.
To enable Bob to send his encrypted messages or verify her future messages, Alice transmits her public key(n,e) to Bob via a reliable, but not necessarily secret, route. Alice's private key(d) is never distributed.
After Bob obtains Alice's public key, he can send a messageM to Alice.
To do it, he first turnsM into an integerm, thepadded plaintext, such that0 ≤m <n, by using an agreed-upon reversible protocol known as apadding scheme. He then computes the ciphertextc, using Alice's public keye, by:
This can be done reasonably quickly, even for very large numbers, usingmodular exponentiation. Bob then transmitsc to Alice. Note that at least nine values ofm will yield a ciphertextc equal tom,[b] but this is very unlikely to occur in practice.
Alice can recoverm fromc by using her private key exponentd by computing
Givenm, she can recover the original messageM by reversing the padding scheme, or discard it as corrupted if the padding is invalid.
Alicemust discardm if the padding is invalid: if she reveals any information aboutm when it has invalid padding, an adversary could exploit this to decrypt (or sign) messages without knowing the private key, by sending her random or maliciously crafted ciphertexts and observing how she responds.[33]
Here is an example of RSA encryption and decryption, ignoring the details of padding:[c]
Thepublic key is(n = 3233,e = 17). For a paddedplaintext messagem, the encryption function is
Theprivate key is(n = 3233,d = 413). For an encryptedciphertextc, the decryption function is
For instance, in order to encryptm = 65, one calculates
To decryptc = 2790, one calculates
Both of these calculations can be computed efficiently using thesquare-and-multiply algorithm formodular exponentiation. In real-life situations the primes selected would be much larger; in our example it would be trivial to factorn = 3233 (obtained from the freely available public key) back to the primesp andq.e, also from the public key, is then inverted to getd, thus acquiring the private key.
Practical implementations use theChinese remainder theorem to speed up the calculation using modulus of factors (modpq using modp and modq).
The valuesdp,dq andqinv, which are part of the private key are computed as follows:
Here is howdp,dq andqinv are used for efficient decryption (encryption is efficient by choice of a suitabled ande pair):
Suppose Alice wishes to send a signed messagem to Bob. She produces ahash valueh = hash(m) of the messagem, raises it to the power ofd (modulon), and attachess =hd modn as a "signature" to the message.
When Bob receives the messagem and signatures, he uses the same hash algorithm in conjunction with Alice's public key to computeh = hash(m). He raises the signatures to the power ofe (modulon), and compares the resulting hash value with the message's hash value: If the two agree, he knows that the author of the message was in possession of Alice's private key and that the message has not been tampered with since being sent.
This equation is satisfied whens =hd modn because ofexponentiation rules:
The modular exponentiation for signing and verification is the same underlying mathematics as for decryption and encryption, but all the other details of padding scheme for securepublic-key encryption and hashing for securedigital signature are different.[32]
The use of a hash, first proposed in 1978 byMichael O. Rabin in the relatedRabin signature algorithm,[34][35]and the security of the hash, is essential for security of the signature:[36][37] if Alice and Bob skipped the hash, and Bob checked forse ≡m (modn) instead, then anyone could forge the signatures = 1 on the messagem = 1, or take two signed messages(m1,s1) and(m2,s2) from Alice and then forge a third by multiplication,(m1m2,s1s2), without knowledge of the private key.
The proof of the correctness of RSA is based onFermat's little theorem, stating thatap − 1 ≡ 1 (modp) for any integera and primep, not dividinga.[note 1]
We want to show thatfor every integerm whenp andq are distinct prime numbers ande andd are positive integers satisfyinged ≡ 1 (modλ(pq)).
Sinceλ(pq) =lcm(p − 1,q − 1) is, by construction, divisible by bothp − 1 andq − 1, we can writefor some nonnegative integersh andk.[note 2]
To check whether two numbers, such asmed andm, are congruentmod pq, it suffices (and in fact is equivalent) to check that they are congruentmod p andmod q separately.[note 3]
To showmed ≡m (modp), we consider two cases:
The verification thatmed ≡m (modq) proceeds in a completely analogous way:
This completes the proof that, for any integerm, and integerse,d such thated ≡ 1 (modλ(pq)),
Although the original paper of Rivest, Shamir, and Adleman used Fermat's little theorem to explain why RSA works, it is common to find proofs that rely instead onEuler's theorem.
We want to show thatmed ≡m (modn), wheren =pq is a product of two different prime numbers, ande andd are positive integers satisfyinged ≡ 1 (modφ(n)). Sincee andd are positive, we can writeed = 1 +hφ(n) for some non-negative integerh.Assuming thatm is relatively prime ton, we have
where the second-last congruence follows fromEuler's theorem.
More generally, for anye andd satisfyinged ≡ 1 (modλ(n)), the same conclusion follows fromCarmichael's generalization of Euler's theorem, which states thatmλ(n) ≡ 1 (modn) for allm relatively prime ton.
Whenm is not relatively prime ton, the argument just given is invalid. This is highly improbable (only a proportion of1/p + 1/q − 1/(pq) numbers have this property), but even in this case, the desired congruence is still true. Eitherm ≡ 0 (modp) orm ≡ 0 (modq), and these cases can be treated using the previous proof.
There are a number of attacks against plain RSA as described below.
To avoid these problems, practical RSA implementations typically embed some form of structured, randomizedpadding into the valuem before encrypting it. This padding ensures thatm does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts.
Standards such asPKCS#1 have been carefully designed to securely pad messages prior to RSA encryption. Because these schemes pad the plaintextm with some number of additional bits, the size of the un-padded messageM must be somewhat smaller. RSA padding schemes must be carefully designed so as to prevent sophisticated attacks that may be facilitated by a predictable message structure. Early versions of the PKCS#1 standard (up to version 1.5) used a construction that appears to make RSA semantically secure. However, atCrypto 1998, Bleichenbacher showed that this version is vulnerable to a practicaladaptive chosen-ciphertext attack. Furthermore, atEurocrypt 2000, Coron et al.[42] showed that for some types of messages, this padding does not provide a high enough level of security. Later versions of the standard includeOptimal Asymmetric Encryption Padding (OAEP), which prevents these attacks. As such, OAEP should be used in any new application, and PKCS#1 v1.5 padding should be replaced wherever possible. The PKCS#1 standard also incorporates processing schemes designed to provide additional security for RSA signatures, e.g. the Probabilistic Signature Scheme for RSA (RSA-PSS).
Secure padding schemes such as RSA-PSS are as essential for the security of message signing as they are for message encryption. Two USA patents on PSS were granted (U.S. patent 6,266,771 andU.S. patent 7,036,014); however, these patents expired on 24 July 2009 and 25 April 2010 respectively. Use of PSS no longer seems to be encumbered by patents.[original research?] Note that using different RSA key pairs for encryption and signing is potentially more secure.[43]
For efficiency, many popular crypto libraries (such asOpenSSL,Java and.NET) use for decryption and signing the following optimization based on theChinese remainder theorem.[44][citation needed] The following values are precomputed and stored as part of the private key:
These values allow the recipient to compute the exponentiationm =cd (modpq) more efficiently as follows:
,
,
,[d]
.
This is more efficient than computingexponentiation by squaring, even though two modular exponentiations have to be computed. The reason is that these two modular exponentiations both use a smaller exponent and a smaller modulus.
The security of the RSA cryptosystem is based on two mathematical problems: the problem offactoring large numbers and theRSA problem. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems arehard, i.e., no efficient algorithm exists for solving them. Providing security againstpartial decryption may require the addition of a securepadding scheme.[45]
TheRSA problem is defined as the task of takingeth roots modulo a compositen: recovering a valuem such thatc ≡me (modn), where(n,e) is an RSA public key, andc is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulusn. With the ability to recover prime factors, an attacker can compute the secret exponentd from a public key(n,e), then decryptc using the standard procedure. To accomplish this, an attacker factorsn intop andq, and computeslcm(p − 1,q − 1) that allows the determination ofd frome. No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists; seeinteger factorization for a discussion of this problem.
The first RSA-512 factorization in 1999 used hundreds of computers and required the equivalent of 8,400 MIPS years, over an elapsed time of about seven months.[46] By 2009, Benjamin Moody could factor an 512-bit RSA key in 73 days using only public software (GGNFS) and his desktop computer (a dual-coreAthlon64 with a 1,900 MHz CPU). Just less than 5 gigabytes of disk storage was required and about 2.5 gigabytes of RAM for the sieving process.
Rivest, Shamir, and Adleman noted[3] that Miller has shown that – assuming the truth of theextended Riemann hypothesis – findingd fromn ande is as hard as factoringn intop andq (up to a polynomial time difference).[47] However, Rivest, Shamir, and Adleman noted, in section IX/D of their paper, that they had not found a proof that inverting RSA is as hard as factoring.
As of 2020[update], the largest publicly known factoredRSA number had 829 bits (250 decimal digits,RSA-250).[48] Its factorization, by a state-of-the-art distributed implementation, took about 2,700 CPU-years. In practice, RSA keys are typically 1024 to 4096 bits long. In 2003,RSA Security estimated that 1024-bit keys were likely to become crackable by 2010.[49] As of 2020, it is not known whether such keys can be cracked, but minimum recommendations have moved to at least 2048 bits.[50] It is generally presumed that RSA is secure ifn is sufficiently large, outside of quantum computing.
Ifn is 300 bits or shorter, it can be factored in a few hours on apersonal computer, using software already freely available. Keys of 512 bits have been shown to be practically breakable in 1999, whenRSA-155 was factored by using several hundred computers, and these are now factored in a few weeks using common hardware. Exploits using 512-bit code-signing certificates that may have been factored were reported in 2011.[51] A theoretical hardware device namedTWIRL, described by Shamir and Tromer in 2003, called into question the security of 1024-bit keys.[49]
In 1994,Peter Shor showed that aquantum computer – if one could ever be practically created for the purpose – would be able to factor inpolynomial time, breaking RSA; seeShor's algorithm.
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "RSA cryptosystem" – news ·newspapers ·books ·scholar ·JSTOR(October 2017) (Learn how and when to remove this message) |
Finding the large primesp andq is usually done by testing random numbers of the correct size with probabilisticprimality tests that quickly eliminate virtually all of the nonprimes.
The numbersp andq should not be "too close", lest theFermat factorization forn be successful. Ifp −q is less than2n1/4 (n =p⋅q, which even for "small" 1024-bit values ofn is3×1077), solving forp andq is trivial. Furthermore, if eitherp − 1 orq − 1 has only small prime factors,n can be factored quickly byPollard'sp − 1 algorithm, and hence such values ofp orq should be discarded.
It is important that the private exponentd be large enough. Michael J. Wiener showed that ifp is betweenq and2q (which is quite typical) andd <n1/4/3, thend can be computed efficiently fromn and e.[52]
There is no known attack against small public exponents such ase = 3, provided that the proper padding is used.Coppersmith's attack has many applications in attacking RSA specifically if the public exponente is small and if the encrypted message is short and not padded.65537 is a commonly used value for e; this value can be regarded as a compromise between avoiding potential small-exponent attacks and still allowing efficient encryptions (or signature verification). The NIST Special Publication on Computer Security (SP 800-78 Rev. 1 of August 2007) does not allow public exponentse smaller than 65537, but does not state a reason for this restriction.
In October 2017, a team of researchers fromMasaryk University announced theROCA vulnerability, which affects RSA keys generated by an algorithm embodied in a library fromInfineon known as RSALib. A large number ofsmart cards andtrusted platform modules (TPM) were shown to be affected. Vulnerable RSA keys are easily identified using a test program the team released.[53]
A cryptographically strongrandom number generator, which has been properly seeded with adequate entropy, must be used to generate the primesp andq. An analysis comparing millions of public keys gathered from the Internet was carried out in early 2012 byArjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung and Christophe Wachter. They were able to factor 0.2% of the keys using only Euclid's algorithm.[54][55][self-published source?]
They exploited a weakness unique to cryptosystems based on integer factorization. Ifn =pq is one public key, andn′ =p′q′ is another, then if by chancep =p′ (butq is not equal toq'), then a simple computation ofgcd(n,n′) =p factors bothn andn', totally compromising both keys. Lenstra et al. note that this problem can be minimized by using a strong random seed of bit length twice the intended security level, or by employing a deterministic function to chooseq givenp, instead of choosingp andq independently.
Nadia Heninger was part of a group that did a similar experiment. They used an idea ofDaniel J. Bernstein to compute the GCD of each RSA keyn against the product of all the other keysn' they had found (a 729-million-digit number), instead of computing eachgcd(n,n′) separately, thereby achieving a very significant speedup, since after one large division, the GCD problem is of normal size.
Heninger says in her blog that the bad keys occurred almost entirely in embedded applications, including "firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones" from more than 30 manufacturers. Heninger explains that the one-shared-prime problem uncovered by the two groups results from situations where the pseudorandom number generator is poorly seeded initially, and then is reseeded between the generation of the first and second primes. Using seeds of sufficiently high entropy obtained from key stroke timings or electronic diode noise oratmospheric noise from a radio receiver tuned between stations should solve the problem.[56]
Strong random number generation is important throughout every phase of public-key cryptography. For instance, if a weak generator is used for the symmetric keys that are being distributed by RSA, then an eavesdropper could bypass RSA and guess the symmetric keys directly.
Kocher described a new attack on RSA in 1995: if the attacker Eve knows Alice's hardware in sufficient detail and is able to measure the decryption times for several known ciphertexts, Eve can deduce the decryption keyd quickly. This attack can also be applied against the RSA signature scheme. In 2003,Boneh andBrumley demonstrated a more practical attack capable of recovering RSA factorizations over a network connection (e.g., from aSecure Sockets Layer (SSL)-enabled webserver).[57] This attack takes advantage of information leaked by theChinese remainder theorem optimization used by many RSA implementations.
One way to thwart these attacks is to ensure that the decryption operation takes a constant amount of time for every ciphertext. However, this approach can significantly reduce performance. Instead, most RSA implementations use an alternate technique known ascryptographic blinding. RSA blinding makes use of the multiplicative property of RSA. Instead of computingcd (modn), Alice first chooses a secret random valuer and computes(rec)d (modn). The result of this computation, after applyingEuler's theorem, isrcd (modn), and so the effect ofr can be removed by multiplying by its inverse. A new value ofr is chosen for each ciphertext. With blinding applied, the decryption time is no longer correlated to the value of the input ciphertext, and so the timing attack fails.
In 1998,Daniel Bleichenbacher described the first practicaladaptive chosen-ciphertext attack against RSA-encrypted messages using the PKCS #1 v1padding scheme (a padding scheme randomizes and adds structure to an RSA-encrypted message, so it is possible to determine whether a decrypted message is valid). Due to flaws with the PKCS #1 scheme, Bleichenbacher was able to mount a practical attack against RSA implementations of theSecure Sockets Layer protocol and to recover session keys. As a result of this work, cryptographers now recommend the use of provably secure padding schemes such asOptimal Asymmetric Encryption Padding, and RSA Laboratories has released new versions of PKCS #1 that are not vulnerable to these attacks.
A variant of this attack, dubbed "BERserk", came back in 2014.[58][59] It impacted the Mozilla NSS Crypto Library, which was used notably by Firefox and Chrome.
A side-channel attack using branch-prediction analysis (BPA) has been described. Many processors use abranch predictor to determine whether a conditional branch in the instruction flow of a program is likely to be taken or not. Often these processors also implementsimultaneous multithreading (SMT). Branch-prediction analysis attacks use a spy process to discover (statistically) the private key when processed with these processors.
Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a non-statistical way. In their paper, "On the Power of Simple Branch Prediction Analysis",[60] the authors of SBPA (Onur Aciicmez and Cetin Kaya Koc) claim to have discovered 508 out of 512 bits of an RSA key in 10 iterations.
A power-fault attack on RSA implementations was described in 2010[61]The author recovered the key by varying the CPU power voltage outside limits; this caused multiple power faults on the server.
The CRT implementation is sensitive tofault injection attacks. If an attacker can obtain 1 faulty signature, the private key can be calculated.[62]
There are many details to keep in mind in order to implement RSA securely (strongPRNG, acceptable public exponent, etc.). This makes the implementation challenging, to the point that the bookPractical Cryptography With Go suggests avoiding RSA if possible.[63]
Some cryptography libraries that provide support for RSA include:
