RSA Cryptography Today FAQ (1/3)
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 *