rsa-faq.txt

汇聚各种应用密码学密码算法技术源码

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.