Xref: news.lut.fi sci.crypt:26901 talk.politics.crypto:6723 alt.security.ripem:1005 sci.answers:1433 talk.answers:298 alt.answers:3891 news.answers:26400
Path: news.lut.fi!news.funet.fi!news.eunet.fi!EU.net!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!news2.near.net!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!faqserv
From: faq-editor@rsa.com
Newsgroups: sci.crypt,talk.politics.crypto,alt.security.ripem,sci.answers,talk.answers,alt.answers,news.answers
Subject: RSA Cryptography Today FAQ (1/3)
Supersedes: <cryptography-faq/rsa/part1_775371303@rtfm.mit.edu>
Followup-To: poster
Date: 19 Aug 1994 02:26:37 GMT
Organization: none
Lines: 1040
Approved: news-answers-request@mit.edu
Expires: 23 Sep 1994 02:26:02 GMT
Message-ID: <cryptography-faq/rsa/part1_777263162@rtfm.mit.edu>
Reply-To: faq-editor@rsa.com
NNTP-Posting-Host: bloom-picayune.mit.edu
X-Last-Updated: 1994/06/13
Originator: faqserv@bloom-picayune.MIT.EDU

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 *