Danny Amor's Online Library

home *** CD-ROM | disk | FTP | other *** search

/ Danny Amor's Online Library / Danny Amor's Online Library - Volume 1.iso / html / faqs / faq / cryptography-faq / rsa.part1 < prev next >

Wrap

Text File | 1995-07-25 | 51.6 KB | 1,047 lines

Subject: RSA Cryptography Today FAQ (1/3) Newsgroups: sci.crypt,talk.politics.crypto,alt.security.ripem,sci.answers,talk.answers,alt.answers,news.answers From: faq-editor@rsa.com Date: 13 Nov 1994 03:48:27 GMT Archive-name: cryptography-faq/rsa/part1 Last-modified: 93/09/20 Version: 2.0 Distribution-agent: tmp@netcom.com (This document has been brought to you in part by CRAM. See the bottom for more information, including instructions on how to obtain updates.) === Answers To FREQUENTLY ASKED QUESTIONS About Today's Cryptography Paul Fahn RSA Laboratories 100 Marine Parkway Redwood City, CA 94065 Copyright (c) 1993 RSA Laboratories, a division of RSA Data Security, Inc. All rights reserved. Version 2.0, draft 2f Last update: September 20, 1993 ------------------------------------------------------------------------ Table of Contents [ part 1 ] 1 General 1.1 What is encryption? 1.2 What is authentication? What is a digital signature? 1.3 What is public-key cryptography? 1.4 What are the advantages and disadvantages of public-key cryptography over secret-key cryptography? 1.5 Is cryptography patentable in the U.S.? 1.6 Is cryptography exportable from the U.S.? 2 RSA 2.1 What is RSA? 2.2 Why use RSA rather than DES? 2.3 How fast is RSA? 2.4 How much extra message length is caused by using RSA? 2.5 What would it take to break RSA? 2.6 Are strong primes necessary in RSA? 2.7 How large a modulus (key) should be used in RSA? 2.8 How large should the primes be? 2.9 How does one find random numbers for keys? 2.10 What if users of RSA run out of distinct primes? 2.11 How do you know if a number is prime? 2.12 How is RSA used for encryption in practice? 2.13 How is RSA used for authentication in practice? 2.14 Does RSA help detect altered documents and transmission errors? 2.15 What are alternatives to RSA? 2.16 Is RSA currently in use today? 2.17 Is RSA an official standard today? 2.18 Is RSA a de facto standard? Why is a de facto standard important? 2.19 Is RSA patented? 2.20 Can RSA be exported from the U.S.? [ part 2 ] 3 Key Management 3.1 What key management issues are involved in public-key cryptography? 3.2 Who needs a key? 3.3 How does one get a key pair? 3.4 Should a public key or private key be shared among users? 3.5 What are certificates? 3.6 How are certificates used? 3.7 Who issues certificates and how? 3.8 What is a CSU, or, How do certifying authorities store their private keys? 3.9 Are certifying authorities susceptible to attack? 3.10 What if the certifying authority's key is lost or compromised? 3.11 What are Certificate Revocation Lists (CRLs)? 3.12 What happens when a key expires? 3.13 What happens if I lose my private key? 3.14 What happens if my private key is compromised? 3.15 How should I store my private key? 3.16 How do I find someone else's public key? 3.17 How can signatures remain valid beyond the expiration dates of their keys, or, How do you verify a 20-year-old signature? 3.18 What is a digital time-stamping service? 4 Factoring and Discrete Log 4.1 What is a one-way function? 4.2 What is the significance of one-way functions for cryptography? 4.3 What is the factoring problem? 4.4 What is the significance of factoring in cryptography? 4.5 Has factoring been getting easier? 4.6 What are the best factoring methods in use today? 4.7 What are the prospects for theoretical factoring breakthroughs? 4.8 What is the RSA Factoring Challenge? 4.9 What is the discrete log problem? 4.10 Which is easier, factoring or discrete log? 5 DES 5.1 What is DES? 5.2 Has DES been broken? 5.3 How does one use DES securely? 5.4 Can DES be exported from the U.S.? 5.5 What are the alternatives to DES? 5.6 Is DES a group? [part 3] 6 Capstone, Clipper, and DSS 6.1 What is Capstone? 6.2 What is Clipper? 6.3 How does the Clipper chip work? 6.4 Who are the escrow agencies? 6.5 What is Skipjack? 6.6 Why is Clipper controversial? 6.7 What is the current status of Clipper? 6.8 What is DSS? 6.9 Is DSS secure? 6.10 Is use of DSS covered by any patents? 6.11 What is the current status of DSS? 7 NIST and NSA 7.1 What is NIST? 7.2 What role does NIST play in cryptography? 7.3 What is the NSA? 7.4 What role does the NSA play in commercial cryptography? 8 Miscellaneous 8.1 What is the legal status of documents signed with digital signatures? 8.2 What is a hash function? What is a message digest? 8.3 What are MD2, MD4 and MD5? 8.4 What is SHS? 8.5 What is Kerberos? 8.6 What are RC2 and RC4? 8.7 What is PEM? 8.8 What is RIPEM? 8.9 What is PKCS? 8.10 What is RSAREF? -------------------------------------------------------------------- 1 General 1.1 What is encryption? Encryption is the transformation of data into a form unreadable by anyone without a secret decryption key. Its purpose is to ensure privacy by keeping the information hidden from anyone for whom it is not intended, even those who can see the encrypted data. For example, one may wish to encrypt files on a hard disk to prevent an intruder from reading them. In a multi-user setting, encryption allows secure communication over an insecure channel. The general scenario is as follows: Alice wishes to send a message to Bob so that no one else besides Bob can read it. Alice encrypts the message, which is called the plaintext, with an encryption key; the encrypted message, called the ciphertext, is sent to Bob. Bob decrypts the ciphertext with the decryption key and reads the message. An attacker, Charlie, may either try to obtain the secret key or to recover the plaintext without using the secret key. In a secure cryptosystem, the plaintext cannot be recovered from the ciphertext except by using the decryption key. In a symmetric cryptosystem, a single key serves as both the encryption and decryption keys. Cryptography has been around for millennia; see Kahn [37] for a good history of cryptography; see Rivest [69] and Brassard [10] for an introduction to modern cryptography. 1.2 What is authentication? What is a digital signature? Authentication in a digital setting is a process whereby the receiver of a digital message can be confident of the identity of the sender and/or the integrity of the message. Authentication protocols can be based on either conventional secret-key cryptosystems like DES or on public-key systems like RSA; authentication in public-key systems uses digital signatures. In this document, authentication will generally refer to the use of digital signatures, which play a function for digital documents similar to that played by handwritten signatures for printed documents: the signature is an unforgeable piece of data asserting that a named person wrote or otherwise agreed to the document to which the signature is attached. The recipient, as well as a third party, can verify both that the document did indeed originate from the person whose signature is attached and that the document has not been altered since it was signed. A secure digital signature system thus consists of two parts: a method of signing a document such that forgery is infeasible, and a method of verifying that a signature was actually generated by whomever it represents. Furthermore, secure digital signatures cannot be repudiated; i.e., the signer of a document cannot later disown it by claiming it was forged. Unlike encryption, digital signatures are a recent development, the need for which has arisen with the proliferation of digital communications. 1.3 What is public-key cryptography? Traditional cryptography is based on the sender and receiver of a message knowing and using the same secret key: the sender uses the secret key to encrypt the message, and the receiver uses the same secret key to decrypt the message. This method is known as secret-key cryptography. The main problem is getting the sender and receiver to agree on the secret key without anyone else finding out. If they are in separate physical locations, they must trust a courier, or a phone system, or some other transmission system to not disclose the secret key being communicated. Anyone who overhears or intercepts the key in transit can later read all messages encrypted using that key. The generation, transmission and storage of keys is called key management; all cryptosystems must deal with key management issues. Secret-key cryptography often has difficulty providing secure key management. Public-key cryptography was invented in 1976 by Whitfield Diffie and Martin Hellman [29] in order to solve the key management problem. In the new system, each person gets a pair of keys, called the public key and the private key. Each person's public key is published while the private key is kept secret. The need for sender and receiver to share secret information is eliminated: all communications involve only public keys, and no private key is ever transmitted or shared. No longer is it necessary to trust some communications channel to be secure against eavesdropping or betrayal. Anyone can send a confidential message just using public information, but it can only be decrypted with a private key that is in the sole possession of the intended recipient. Furthermore, public-key cryptography can be used for authentication (digital signatures) as well as for privacy (encryption). Here's how it works for encryption: when Alice wishes to send a message to Bob, she looks up Bob's public key in a directory, uses it to encrypt the message and sends it off. Bob then uses his private key to decrypt the message and read it. No one listening in can decrypt the message. Anyone can send an encrypted message to Bob but only Bob can read it. Clearly, one requirement is that no one can figure out the private key from the corresponding public key. Here's how it works for authentication: Alice, to sign a message, does a computation involving both her private key and the message itself; the output is called the digital signature and is attached to the message, which is then sent. Bob, to verify the signature, does some computation involving the message, the purported signature, and Alice's public key. If the results properly hold in a simple mathematical relation, the signature is verified as genuine; otherwise, the signature may be fraudulent or the message altered, and they are discarded. A good history of public-key cryptography, by one of its inventors, is given by Diffie [27]. 1.4 What are the advantages and disadvantages of public-key cryptography over secret-key cryptography?} The primary advantage of public-key cryptography is increased security: the private keys do not ever need to be transmitted or revealed to anyone. In a secret-key system, by contrast, there is always a chance that an enemy could discover the secret key while it is being transmitted. Another major advantage of public-key systems is that they can provide a method for digital signatures. Authentication via secret-key systems requires the sharing of some secret and sometimes requires trust of a third party as well. A sender can then repudiate a previously signed message by claiming that the shared secret was somehow compromised by one of the parties sharing the secret. For example, the Kerberos secret-key authentication system [79] involves a central database that keeps copies of the secret keys of all users; a Kerberos-authenticated message would most likely not be held legally binding, since an attack on the database would allow widespread forgery. Public-key authentication, on the other hand, prevents this type of repudiation; each user has sole responsibility for protecting his or her private key. This property of public-key authentication is often called non-repudiation. Furthermore, digitally signed messages can be proved authentic to a third party, such as a judge, thus allowing such messages to be legally binding. Secret-key authentication systems such as Kerberos were designed to authenticate access to network resources, rather than to authenticate documents, a task which is better achieved via digital signatures. A disadvantage of using public-key cryptography for encryption is speed: there are popular secret-key encryption methods which are significantly faster than any currently available public-key encryption method. But public-key cryptography can share the burden with secret-key cryptography to get the best of both worlds. For encryption, the best solution is to combine public- and secret-key systems in order to get both the security advantages of public-key systems and the speed advantages of secret-key systems. The public-key system can be used to encrypt a secret key which is then used to encrypt the bulk of a file or message. This is explained in more detail in Question 2.12 in the case of RSA. Public-key cryptography is not meant to replace secret-key cryptography, but rather to supplement it, to make it more secure. The first use of public-key techniques was for secure key exchange in an otherwise secret-key system [29]; this is still one of its primary functions. Secret-key cryptography remains extremely important and is the subject of much ongoing study and research. Some secret-key encryption systems are discussed in Questions 5.1 and 5.5. 1.5 Is cryptography patentable in the U.S.? Cryptographic systems are patentable. Many secret-key cryptosystems have been patented, including DES (see Question 5.1). The basic ideas of public-key cryptography are contained in U.S. Patent 4,200,770, by M. Hellman, W. Diffie, and R. Merkle, issued 4/29/80 and in U.S. Patent 4,218,582, by M. Hellman and R. Merkle, issued 8/19/80; similar patents have been issued throughout the world. The exclusive licensing rights to both patents are held by Public Key Partners (PKP), of Sunnyvale, California, which also holds the rights to the RSA patent (see Question 2.19). Usually all of these public-key patents are licensed together. All legal challenges to public-key patents have been settled before judgment. In a recent case, for example, PKP brought suit against the TRW Corporation which was using public-key cryptography (the ElGamal system) without a license; TRW claimed it did not need to license. In June 1992 a settlement was reached in which TRW agreed to license to the patents. Some patent applications for cryptosystems have been blocked by intervention by the NSA (see Question 7.3) or other intelligence or defense agencies, under the authority of the Invention Secrecy Act of 1940 and the National Security Act of 1947; see Landau [46] for some recent cases related to cryptography. 1.6 Is cryptography exportable from the U.S.? All cryptographic products need export licenses from the State Department, acting under authority of the International Traffic in Arms Regulation (ITAR), which defines cryptographic devices, including software, as munitions. The U.S. government has historically been reluctant to grant export licenses for encryption products stronger than some basic level (not publicly stated). Under current regulations, a vendor seeking to export a product using cryptography first submits an request to the State Department's Defense Trade Control office. Export jurisdiction may then be passed to the Department of Commerce, whose export procedures are generally simple and efficient. If jurisdiction remains with the State Department, further review, perhaps lengthy, is required before export is either approved or denied; the National Security Agency (NSA, see Question 7.3) may become directly involved at this point. The details of the export approval process change frequently. The NSA has de facto control over export of cryptographic products. The State Department will not grant a license without NSA approval and routinely grants licenses whenever NSA does approve. Therefore, the policy decisions over exporting cryptography ultimately rest with the NSA. It is the stated policy of the NSA not to restrict export of cryptography for authentication; it is only concerned with the use of cryptography for privacy. A vendor seeking to export a product for authentication only will be granted an export license as long as it can demonstrate that the product cannot be easily modified for encryption; this is true even for very strong systems, such as RSA with large key sizes. Furthermore, the bureaucratic procedures are simpler for authentication products than for privacy products. An authentication product needs NSA and State Dept. approval only once, whereas an encryption product may need approval for every sale or every product revision. Export policy is currently a matter of great controversy, as many software and hardware vendors consider current export regulations overly restrictive and burdensome. The Software Publishers Association (SPA), a software industry group, has recently been negotiating with the government in order to get export license restrictions eased; one agreement was reached that allows simplified procedures for export of two bulk encryption ciphers, RC2 and RC4 (see Question 8.6), when the key size is limited. Also, export policy is less restrictive for foreign subsidiaries and overseas offices of U.S. companies. In March 1992, the Computer Security and Privacy Advisory Board voted unanimously to recommend a national review of cryptography policy, including export policy. The Board is an official advisory board to NIST (see Question 7.1) whose members are drawn from both the government and the private sector. The Board stated that a public debate is the only way to reach a consensus policy to best satisfy competing interests: national security and law enforcement agencies like restrictions on cryptography, especially for export, whereas other government agencies and private industry want greater freedom for using and exporting cryptography. Export policy has traditionally been decided solely by agencies concerned with national security, without much input from those who wish to encourage commerce in cryptography. U.S. export policy may undergo significant change in the next few years. 2 RSA 2.1 What is RSA? RSA is a public-key cryptosystem for both encryption and authentication; it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman [74]. It works as follows: take two large primes, p and q, and find their product n = pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), and find its inverse, d, mod (p-1)(q-1), which means that ed = 1 mod (p-1)(q-1); e and d are called the public and private exponents, respectively. The public key is the pair (n,e); the private key is d. The factors p and q must be kept secret, or destroyed. It is difficult (presumably) to obtain the private key d from the public key (n,e). If one could factor n into p and q, however, then one could obtain the private key d. Thus the entire security of RSA is predicated on the assumption that factoring is difficult; an easy factoring method would ``break'' RSA (see Questions 2.5 and 4.4). Here is how RSA can be used for privacy and authentication (in practice, actual use is slightly different; see Questions 2.12 and 2.13): RSA privacy (encryption): suppose Alice wants to send a private message, m, to Bob. Alice creates the ciphertext c by exponentiating: c = m^e mod n, where e and n are Bob's public key. To decrypt, Bob also exponentiates: m = c^d mod n, and recovers the original message m; the relationship between e and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt. RSA authentication: suppose Alice wants to send a signed document m to Bob. Alice creates a digital signature s by exponentiating: s = m^d mod n, where d and n belong to Alice's key pair. She sends s and m to Bob. To verify the signature, Bob exponentiates and checks that the message m is recovered: m = s^e mod n, where e and n belong to Alice's public key. Thus encryption and authentication take place without any sharing of private keys: each person uses only other people's public keys and his or her own private key. Anyone can send an encrypted message or verify a signed message, using only public keys, but only someone in possession of the correct private key can decrypt or sign a message. 2.2 Why use RSA rather than DES? RSA is not an alternative or replacement for DES; rather it supplements DES (or any other fast bulk encryption cipher) and is used together with DES in a secure communications environment. (Note: for an explanation of DES, see Question 5.1.) RSA allows two important functions not provided by DES: secure key exchange without prior exchange of secrets, and digital signatures. For encrypting messages, RSA and DES are usually combined as follows: first the message is encrypted with a random DES key, and then, before being sent over an insecure communications channel, the DES key is encrypted with RSA. Together, the DES-encrypted message and the RSA-encrypted DES key are sent. This protocol is known as an RSA digital envelope. One may wonder, why not just use RSA to encrypt the whole message and not use DES at all? Although this may be fine for small messages, DES (or another cipher) is preferable for larger messages because it is much faster than RSA (see Question 2.3). In some situations, RSA is not necessary and DES alone is sufficient. This includes multi-user environments where secure DES-key agreement can take place, for example by the two parties meeting in private. Also, RSA is usually not necessary in a single-user environment; for example, if you want to keep your personal files encrypted, just do so with DES using, say, your personal password as the DES key. RSA, and public-key cryptography in general, is best suited for a multi-user environment. Also, any system in which digital signatures are desired needs RSA or some other public-key system. 2.3 How fast is RSA? An ``RSA operation,'' whether for encrypting or decrypting, signing or verifying, is essentially a modular exponentiation, which can be performed by a series of modular multiplications. In practical applications, it is common to choose a small public exponent for the public key; in fact, entire groups of users can use the same public exponent. This makes encryption faster than decryption and verification faster than signing. Algorithmically, public-key operations take O(k^2) steps, private key operations take O(k^3) steps, and key generation takes O(k^4) steps, where k is the number of bits in the modulus; O-notation refers to the an upper bound on the asymptotic running time of an algorithm [22]. There are many commercially available hardware implementations of RSA, and there are frequent announcements of newer and faster chips. The fastest current RSA chip [76] has a throughput greater than 600 Kbits per second with a 512-bit modulus, implying that it performs over 1000 RSA private-key operations per second. It is expected that RSA speeds will reach 1 Mbit/second within a year or so. By comparison, DES is much faster than RSA. In software, DES is generally at least 100 times as fast as RSA. In hardware, DES is between 1,000 and 10,000 times as fast, depending on the implementations. RSA will probably narrow the gap a bit in coming years, as it finds growing commercial markets, but will never match the performance of DES. 2.4 How much extra message length is caused by using RSA? Only a very small amount of data expansion is involved when using RSA. For encryption, a message may be padded to a length that is a multiple of the block length, usually 64 bits, since RSA is usually combined with a secret-key block cipher such as DES (see Question 2.12). Encrypting the DES key takes as many additional bits as the size of the RSA modulus. For authentication, an RSA digital signature is appended to a document. An RSA signature, including information such as the name of the signer, is typically a few hundred bytes long. One or more certificates (see Question 3.5) may be included as well; certificates can be used in conjunction with any digital signature method. A typical RSA certificate is a few hundred bytes long. 2.5 What would it take to break RSA? There are a few possible interpretations of ``breaking RSA''. The most damaging would be for an attacker to discover the private key corresponding to a given public key; this would enable the attacker both to read all messages encrypted with the public key and to forge signatures. The obvious way to do this attack is to factor the public modulus, n, into its two prime factors, p and q. From p, q, and e, the public exponent, the attacker can easily get d, the private key. The hard part is factoring n; the security of RSA depends of factoring being difficult. In fact, the task of recovering the private key is equivalent to the task of factoring the modulus: you can use d to factor n, as well as use the factorization of n to find d. See Questions 4.5 and 4.6 regarding the state of the art in factoring. It should be noted that hardware improvements alone will not weaken RSA, as long as appropriate key lengths are used; in fact, hardware improvements should increase the security of RSA (see Question 4.5). Another way to break RSA is to find a technique to compute e-th roots mod n. Since c = m^e, the e-th root of c is the message m. This attack would allow someone to recover encrypted messages and forge signatures even without knowing the private key. This attack is not known to be equivalent to factoring. No methods are currently known that attempt to break RSA in this way. The attacks just mentioned are the only ways to break RSA in such a way as to be able to recover all messages encrypted under a given key. There are other methods, however, which aim to recover single messages; success would not enable the attacker to recover other messages encrypted with the same key. The simplest single-message attack is the guessed plaintext attack. An attacker sees a ciphertext, guesses that the message might be ``Attack at dawn'', and encrypts this guess with the public key of the recipient; by comparison with the actual ciphertext, the attacker knows whether or not the guess was correct. This attack can be thwarted by appending some random bits to the message. Another single-message attack can occur if someone sends the same message m to three others, who each have public exponent e=3. An attacker who knows this and sees the three messages will be able to recover the message m; this attack and ways to prevent it are discussed by Hastad [35]. There are also some ``chosen ciphertext'' attacks, in which the attacker creates some ciphertext and gets to see the corresponding plaintext, perhaps by tricking a legitimate user into decrypting a fake message; Davida [23] gives some examples. Of course, there are also attacks that aim not at RSA itself but at a given insecure implementation of RSA; these do not count as ``breaking RSA'' because it is not any weakness in the RSA algorithm that is exploited, but rather a weakness in a specific implementation. For example, if someone stores his private key insecurely, an attacker may discover it. One cannot emphasize strongly enough that to be truly secure RSA requires a secure implementation; mathematical security measures, such as choosing a long key size, are not enough. In practice, most successful attacks will likely be aimed at insecure implementations and at the key management stages of an RSA system. See Section 3 for discussion of secure key management in an RSA system. 2.6 Are strong primes necessary in RSA? In the literature pertaining to RSA, it has often been suggested that in choosing a key pair, one should use ``strong'' primes p and q to generate the modulus n. Strong primes are those with certain properties that make the product n hard to factor by specific factoring methods; such properties have included, for example, the existence of a large prime factor of p-1 and a large prime factor of p+1. The reason for these concerns is that some factoring methods are especially suited to primes p such that p-1 or p+1 has only small factors; strong primes are resistant to these attacks. However, recent advances in factoring (see Question 4.6) appear to have obviated the advantage of strong primes; the elliptic curve factoring algorithm is one such advance. The new factoring methods have as good a chance of success on strong primes as on ``weak'' primes; therefore, choosing strong primes does not significantly increase resistance to attacks. So for now the answer is negative: strong primes are not necessary when using RSA, although there is no danger in using them, except that it takes longer to generate a key pair. However, new factoring algorithms may be developed in the future which once again target primes with certain properties; if so, choosing strong primes may again help to increase security. 2.7 How large a modulus (key) should be used in RSA? The best size for an RSA modulus depends on one's security needs. The larger the modulus, the greater the security but also the slower the RSA operations. One should choose a modulus length upon consideration, first, of one's security needs, such as the value of the protected data and how long it needs to be protected, and, second, of how powerful one's potential enemy is. It is also possible that a larger key size will allow a digitally signed document to be valid for a longer time; see Question 3.17. A good analysis of the security obtained by a given modulus length is given by Rivest [72], in the context of discrete logarithms modulo a prime, but it applies to RSA as well. Rivest's estimates imply that a 512-bit modulus can be factored with an $8.2 million effort, less in the future. It may therefore be advisable to use a longer modulus, perhaps 768 bits in length. Those with extremely valuable data (or large potential damage from digital forgery) may want to use a still longer modulus. A certifying authority (see Question 3.5) might use a modulus of length 1000 bits or more, because the validity of so many other key pairs depends on the security of the one central key. The key of an individual user will expire after a certain time, say, two years (see Question 3.12). Upon expiration, the user will generate a new key which should be at least a few digits longer than the old key to reflect the speed increases of computers over the two years. Recommended key length schedules will probably be published by some authority or public body. Users should keep in mind that the estimated times to break RSA are averages only. A large factoring effort, attacking many thousands of RSA moduli, may succeed in factoring at least one in a reasonable time. Although the security of any individual key is still strong, with some factoring methods there is always a small chance that the attacker may get lucky and factor it quickly. As for the slowdown caused by increasing the key size (see Question 2.3), doubling the modulus length would, on average, increase the time required for public-key operations (encryption and signature verification) by a factor of 4, and increase the time taken by private key operations (decryption and signing) by a factor of 8. The reason that public-key operations are affected less than private-key operations is that the public exponent can remain fixed when the modulus is increased, whereas the private exponent increases proportionally. Key generation time would increase by a factor of 16 upon doubling the modulus, but this is a relatively infrequent operation for most users. 2.8 How large should the primes be? The two primes, p and q, which compose the modulus, should be of roughly equal length; this will make the modulus harder to factor than if one of the primes was very small. Thus if one chooses to use a 512-bit modulus, the primes should each have length approximately 256 bits. 2.9 How does one find random numbers for keys? One needs a source of random numbers in order to find two random primes to compose the modulus. If one used a predictable method of generating the primes, an adversary could mount an attack by trying to recreate the key generation process. Random numbers obtained from a physical process are in principle the best. One could use a hardware device, such as a diode; some are sold commercially on computer add-in boards for this purpose. Another idea is to use physical movements of the computer user, such as keystroke timings measured in microseconds. By whichever method, the random numbers may still contain some correlations preventing sufficient statistical randomness. Therefore, it is best to run them through a good hash function (see Question 8.2) before actually using them. Another approach is to use a pseudorandom number generator fed by a random seed. Since these are deterministic algorithms, it is important to find one that is very unpredictable and also to use a truly random seed. There is a wide literature on the subject of pseudorandom number generators. See Knuth [41] for an introduction. Note that one does not need random numbers to determine the public and private exponents in RSA, after choosing the modulus. One can simply choose an arbitrary value for the public exponent, which then determines the private exponent, or vice versa. 2.10 What if users of RSA run out of distinct primes? There are enough prime numbers that RSA users will never run out of them. For example, the number of primes of length 512 bits or less exceeds 10^{150}, according to the prime number theorem; this is more than the number of atoms in the known universe. 2.11 How do you know if a number is prime? It is generally recommended to use probabilistic primality testing, which is much quicker than actually proving a number prime. One can use a probabilistic test that decides if a number is prime with probability of error less than 2^{-100}. For further discussion of some primality testing algorithms, see the papers in the bibliography of [5]. For some empirical results on the reliability of simple primality tests see Rivest [70]; one can perform very fast primality tests and be extremely confident in the results. A simple algorithm for choosing probable primes was recently analyzed by Brandt and Damgard [9]. 2.12 How is RSA used for encryption in practice? RSA is combined with a secret-key cryptosystem, such as DES, to encrypt a message by means of an RSA digital envelope. Suppose Alice wishes to send an encrypted message to Bob. She first encrypts the message with DES, using a randomly chosen DES key. Then she looks up Bob's public key and uses it to encrypt the DES key. The DES-encrypted message and the RSA-encrypted DES key together form the RSA digital envelope and are sent to Bob. Upon receiving the digital envelope, Bob decrypts the DES key with his private key, then uses the DES key to decrypt to message itself. 2.13 How is RSA used for authentication in practice? Suppose Alice wishes to send a signed message to Bob. She uses a hash function on the message (see Question 8.2) to create a message digest, which serves as a ``digital fingerprint'' of the message. She then encrypts the message digest with her RSA private key; this is the digital signature, which she sends to Bob along with the message itself. Bob, upon receiving the message and signature, decrypts the signature with Alice's public key to recover the message digest. He then hashes the message with the same hash function Alice used and compares the result to the message digest decrypted from the signature. If they are exactly equal, the signature has been successfully verified and he can be confident that the message did indeed come from Alice. If, however, they are not equal, then the message either originated elsewhere or was altered after it was signed, and he rejects the message. Note that for authentication, the roles of the public and private keys are converse to their roles in encryption, where the public key is used to encrypt and the private key to decrypt. In practice, the public exponent is usually much smaller than the private exponent; this means that the verification of a signature is faster than the signing. This is desirable because a message or document will only be signed by an individual once, but the signature may be verified many times. It must be infeasible for anyone to either find a message that hashes to a given value or to find two messages that hash to the same value. If either were feasible, an intruder could attach a false message onto Alice's signature. Hash functions such as MD4 and MD5 (see Question 8.3) have been designed specifically to have the property that finding a match is infeasible, and are therefore considered suitable for use in cryptography. One or more certificates (see Question 3.5) may accompany a digital signature. A certificate is a signed document attesting to the identity and public key of the person signing the message. Its purpose is to prevent someone from impersonating someone else, using a phony key pair. If a certificate is present, the recipient (or a third party) can check the authenticity of the public key, assuming the certifier's public key is itself trusted. 2.14 Does RSA help detect altered documents and transmission errors? An RSA digital signature is superior to a handwritten signature in that it attests to the contents of a message as well as to the identity of the signer. As long as a secure hash function (see Question 8.2) is used, there is no way to take someone's signature from one document and attach it to another, or to alter the signed message in any way. The slightest change in a signed document will cause the digital signature verification process to fail. Thus, RSA authentication allows people to check the integrity of signed documents. Of course, if a signature verification fails, it may be unclear whether there was an attempted forgery or simply a transmission error. 2.15 What are alternatives to RSA? Many other public-key cryptosystems have been proposed, as a look through the proceedings of the annual Crypto and Eurocrypt conferences quickly reveals. A mathematical problem called the knapsack problem was the basis for several systems [52], but these have lost favor because several versions were broken. Another system, designed by ElGamal [30], is based on the discrete logarithm problem. The ElGamal system was, in part, the basis for several later signature methods, including one by Schnorr [75], which in turn was the basis for DSS, the digital signature standard proposed by NIST (see Question 6.8). Because of the NIST proposal, the relative merits of these signature systems versus RSA signatures has received a lot of attention; see [57] for a discussion. The ElGamal system has been used successfully in applications; it is slower for encryption and verification than RSA and its signatures are larger than RSA signatures. In 1976, before RSA, Diffie and Hellman [29] proposed a system for key exchange only; it permits secure exchange of keys in an otherwise conventional secret-key system. This system is in use today. Cryptosystems based on mathematical operations on elliptic curves have also been proposed [43,56], as have cryptosystems based on discrete exponentiation in the finite field GF(2^n). The latter are very fast in hardware; however, doubts have been raised about their security because the underlying problem may be easier to solve than factoring [64,34]. There are also some probabilistic encryption methods [8,32], which have the attraction of being resistant to a guessed ciphertext attack (see Question 2.5), but at a cost of data expansion. In probabilistic encryption, the same plaintext encrypted twice under the same key will give, with high probability, two different ciphertexts. For digital signatures, Rabin [68] proposed a system which is provably equivalent to factoring; this is an advantage over RSA, where one may still have a lingering worry about an attack unrelated to factoring. Rabin's method is susceptible to a chosen message attack, however, in which the attacker tricks the user into signing messages of a special form. Another signature scheme, by Fiat and Shamir [31], is based on interactive zero-knowledge protocols, but can be adapted for signatures. It is faster than RSA and is provably equivalent to factoring, but the signatures are much larger than RSA signatures. Other variations, however, lessen the necessary signature length; see [17] for references. A system is ``equivalent to factoring'' if recovering the private key is provably as hard as factoring; forgery may be easier than factoring in some of the systems. Advantages of RSA over other public-key cryptosystems include the fact that it can be used for both encryption and authentication, and that it has been around for many years and has successfully withstood much scrutiny. RSA has received far more attention, study, and actual use than any other public-key cryptosystem, and thus RSA has more empirical evidence of its security than more recent and less scrutinized systems. In fact, a large number of public-key cryptosystems which at first appeared secure were later broken; see [13] for some case histories. 2.16 Is RSA currently in use today? The use of RSA is undergoing a period of rapid expansion and may become ubiquitous within a few years. It is currently used in a wide variety of products, platforms and industries around the world. It is found in many commercial software products and planned for many more. RSA is built into current or planned operating systems by Microsoft, Apple, Sun, and Novell. In hardware, RSA can be found in secure telephones, on Ethernet network cards, and on smart cards. RSA is also used internally in many institutions, including branches of the U.S. government, major corporations, national laboratories, and universities. Adoption of RSA seems to be proceeding more quickly for authentication (digital signatures) than for privacy (encryption), perhaps in part because products for authentication are easier to export than those for privacy (see Question 1.6). 2.17 Is RSA an official standard today? RSA is part of many official standards worldwide. The ISO (International Standards Organization) 9796 standard lists RSA as a compatible cryptographic algorithm, as does the Consultative Committee in International Telegraphy and Telephony (CCITT) X.509 security standard. RSA is part of the Society for Worldwide Interbank Financial Telecommunications (SWIFT) standard, the French financial industry's ETEBAC 5 standard, and the ANSI X9.31 draft standard for the U.S. banking industry. The Australian key management standard, AS2805.6.5.3, also specifies RSA. RSA is found in Internet's proposed PEM (Privacy Enhanced Mail) standard (see Question 8.7) and the PKCS standard for the software industry (see Question 8.9). The OSI Implementors' Workshop (OIW) has issued implementers' agreements referring to PKCS and PEM, which each include RSA. A number of other standards are currently being developed and will be announced over the next couple of years; many are expected to include RSA as either an endorsed or a recommended system for privacy and/or authentication. See [38] for a more comprehensive survey of cryptography standards. 2.18 Is RSA a de facto standard? Why is a de facto standard important? RSA is the most widely used public-key cryptosystem today and has often been called a de facto standard. Regardless of the official standards, the existence of a de facto standard is extremely important for the development of a digital economy. If one public-key system is used everywhere for authentication, then signed digital documents can be exchanged between users in different nations using different software on different platforms; this interoperability is necessary for a true digital economy to develop. The lack of secure authentication has been a major obstacle in achieving the promise that computers would replace paper; paper is still necessary almost everywhere for contracts, checks, official letters, legal documents, and identification. With this core of necessary paper transaction, it has not been feasible to evolve completely into a society based on electronic transactions. Digital signatures are the exact tool necessary to convert the most essential paper-based documents to digital electronic media. Digital signatures makes it possible, for example, to have leases, wills, passports, college transcripts, checks, and voter registration forms that exist only in electronic form; any paper version would just be a ``copy'' of the electronic original. All of this is enabled by an accepted standard for digital signatures. 2.19 Is RSA patented? RSA is patented under U.S. Patent 4,405,829, issued 9/20/83 and held by Public Key Partners (PKP), of Sunnyvale, California; the patent expires 17 years after issue, in 2000. RSA is usually licensed together with other public-key cryptography patents (see Question 1.5). PKP has a standard, royalty-based licensing policy which can be modified for special circumstances. If a software vendor, having licensed the public-key patents, incorporates RSA into a commercial product, then anyone who purchases the end product has the legal right to use RSA within the context of that software. The U.S. government can use RSA without a license because it was invented at MIT with partial government funding. RSA is not patented outside North America. In North America, a license is needed to ``make, use or sell'' RSA. However, PKP usually allows free non-commercial use of RSA, with written permission, for personal, academic or intellectual reasons. Furthermore, RSA Laboratories has made available (in the U.S. and Canada) at no charge a collection of cryptographic routines in source code, including the RSA algorithm; it can be used, improved and redistributed non-commercially (see Question 8.10). 2.20 Can RSA be exported from the U.S.? Export of RSA falls under the same U.S. laws as all other cryptographic products. See Question 1.6 for details. RSA used for authentication is more easily exported than when used for privacy. In the former case, export is allowed regardless of key (modulus) size, although the exporter must demonstrate that the product cannot be easily converted to use for encryption. In the case of RSA used for privacy (encryption), the U.S. government generally does not allow export if the key size exceeds 512 bits. Export policy is currently a subject of debate, and the export status of RSA may well change in the next year or two. Regardless of U.S. export policy, RSA is available abroad in non-U.S. products. -------------------------------------------- RSA Laboratories is the research and consultation division of RSA Data Security, Inc., the company founded by the inventors of the RSA public-key cryptosystem. RSA Laboratories reviews, designs and implements secure and efficient cryptosystems of all kinds. Its clients include government agencies, telecommunications companies, computer manufacturers, software developers, cable TV broadcasters, interactive video manufacturers, and satellite broadcast companies, among others. For more information about RSA Laboratories, call or write to RSA Laboratories 100 Marine Parkway Redwood City, CA 94065 (415) 595-7703 (415) 595-4126 (fax) PKCS, RSAREF and RSA Laboratories are trademarks of RSA Data Security, Inc. All other trademarks belong to their respective companies. This document is available in ASCII, Postscript, and Latex formats via anonymous FTP to rsa.com:/pub/faq. Please send comments and corrections to faq-editor@rsa.com. === DISTRIBUTION: How to obtain this document This document has been brought to you in part by CRAM, involved in the redistribution of valuable information to a wider USENET audience (see below). The most recent version of this document can be obtained via the author's instructions above. The following directions apply to retrieve the possibly less-current USENET FAQ version. FTP --- This FAQ is available from the standard FAQ server rtfm.mit.edu via FTP in the directory /pub/usenet/news.answers/cryptography-faq/rsa/ Email ----- Email requests for FAQs go to mail-server@rtfm.mit.edu with commands on lines in the message body, e.g. `help' and `index'. Usenet ------ This FAQ is posted every 21 days to the groups sci.crypt talk.politics.crypto alt.security.ripem sci.answers talk.answers alt.answers news.answers _ _, _ ___ _, __, _, _ _, ___ _ _, _, _ _ _, __, _, _ _ ___ __, | |\ | |_ / \ |_) |\/| / \ | | / \ |\ | | (_ |_) / \ | | |_ | ) | | \| | \ / | \ | | |~| | | \ / | \| | , ) | \ / |/\| | |~\ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~ ~ ~ === CRAM: The Cyberspatial Reality Advancement Movement In an effort to bring valuable information to the masses, and as a service to motivated information compilers, a member of CRAM can help others unfamiliar with Usenet `publish' their documents for widespread dissemination via the FAQ structure, and act as a `sponsor' knowledgable in the submissions process. This document is being distributed under this arrangement. We have found these compilations tend to appear on various mailing lists and are valuable enough to deserve wider distribution. If you know of an existing compilation of Internet information that is not currently a FAQ, please contact us and we may `sponsor' it. The benefits to the author include: - use of the existing FAQ infrastructure for distribution: - automated mail server service - FTP archival - automated posting - a far wider audience that can improve the quality, accuracy, and coverage of the document enormously through email feedback - potential professional inquiries for the use of your document in other settings, such as newsletters, books, etc. - with us as your sponsor, we will also take care of the technicalities in the proper format of the posted version and updating procedures, leaving you free of the `overhead' to focus on the basic updates alone The choice of who we `sponsor' is entirely arbitrary. You always have the option of handling the submission process yourself. See the FAQ submission guidelines FAQ in news.answers. For information, send mail to <tmp@netcom.com>. \ \ \ \ \ \ \ \ \ | / / / / / / / / / / _______ ________ _____ _____ _____ /// \\\ ||| \\\ /// \\\ |||\\\///||| ||| ~~ ||| /// ||| ||| ||| \\// ||| ||| __ |||~~~\\\ |||~~~||| ||| ~~ ||| \\\ /// ||| \\\ ||| ||| ||| ||| ~~~~~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ / / / / / / / / / | \ \ \ \ \ \ \ \ \ \ C y b e r s p a t i a l R e a l i t y A d v a n c e m e n t M o v e m e n t * CIVILIZING CYBERSPACE: send `info cypherwonks' to majordomo@lists.eunet.fi *