rsa-faq.txt

应用密码学密码算法源代码 应用密码学密码算法源代码

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