全部博文（68）
分类： 系统运维
2005-05-18 13:07:31
RSA Algorithm
The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977 . The basic technique was first discovered in 1973 by Clifford Cocks of (part of the British GCHQ) but this was a secret until 1997 - see .
The RSA algorithm can be used for both public key encryption and digital signatures. Its security is based on the difficulty of factoring large integers.
Contents
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Key Generation Algorithm
1. Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits. [See note 1].
2. Compute n = pq and (φ) phi = (p-1)(q-1).
3. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1. [See note 2].
4. Compute the secret exponent d, 1 < d < phi, such that
ed ≡ 1 (mod phi). [See note 3].
5. The public key is (n, e) and the private key is (n, d). The values of p, q, and phi should also be kept secret.
· n is known as the modulus.
· e is known as the public exponent or encryption exponent.
· d is known as the secret exponent or decryption exponent.
Encryption
Sender A does the following:-
1. Obtains the recipient B's public key (n, e).
2. Represents the plaintext message as a positive integer m [see note 4].
3. Computes the ciphertext c = m^e mod n.
4. Sends the ciphertext c to B.
Decryption
Recipient B does the following:-
1. Uses his private key (n, d) to compute m = c^d mod n.
2. Extracts the plaintext from the integer representative m.
Digital signing
Sender A does the following:-
1. Creates a message digest of the information to be sent.
2. Represents this digest as an integer m between 0 and n-1. [See note 5].
3. Uses her private key (n, d) to compute the signature s = m^d mod n.
4. Sends this signature s to the recipient, B.
Signature verification
Recipient B does the following:-
1. Uses sender A's public key (n, e) to compute integer v = s^e mod n.
2. Extracts the message digest from this integer.
3. Independently computes the message digest of the information that has been signed.
4. If both message digests are identical, the signature is valid.
Notes on practical applications
1. To generate the primes p and q, generate a random number of bit length b/2 where b is the required bit length of n; set the low bit (this ensures the number is odd) and set the two highest bits (this ensures that the high bit of n is also set); check if prime (use the Rabin-Miller test); if not, increment the number by two and check again. This is p. Repeat for q starting with an integer of length b-b/2. If p
2. In practice, common choices for e are 3, 17 and 65537 (2^16+1). These are Fermat primes and are chosen because they make the modular exponentiation operation faster. Also, having chosen e, it is simpler to test whether gcd(e, p-1)=1 and gcd(e, q-1)=1 while generating and testing the primes in step 1. Values of p or q that fail this test can be rejected there and then. (Even better: if e is prime and greater than 2 then you can do the less-expensive test (p mod e)!=1 instead of gcd(p-1,e)==1.)
3. To compute the value for d, use the Extended Euclidean Algorithm to calculate d = e^-1 mod phi (this is known as modular inversion).
4. When representing the plaintext octets as the representative integer m, it is usual to add random padding characters to make the size of the integer m large and less susceptible to certain types of attack. If m = 0 or 1 there is no security as the ciphertext has the same value. For more details on how to represent the plaintext octets as a suitable representative integer m, see . It is important to make sure that m < n otherwise the algorithm will fail. This is usually done by making the first octet 0x01
5. Decryption and signing are identical as far as the mathematics is concerned as both use the private key. Similarly, encryption and verification both use the same mathematical operation with the public key. However, note these important differences in implementation:-
o The signature is derived from a message digest of the original information. The recipient will need to follow exactly the same process to derive the message digest.
o The recommended methods for deriving the representative integers are different for encryption and signing.
Summary of RSA
|
Computational Efficiency and the Chinese Remainder Theorem (CRT)
Key generation is only carried out occasionally and so computational efficiency is less of an issue.
The calculation a = b^e mod n is known as modular exponentiation and one efficient method to carry this out on a computer is the binary left-to-right method. To solve y = x^e mod n let e be represented in base 2 as
e = e(k-1)e(k-2)...e(1)e(0)
where e(k-1) is the most significant non-zero bit and bit e(0) the least.
set y = x
for bit j = k - 2 downto 0
begin
y = y * y mod n /* square */
if e(j) == 1 then
y = y * x mod n /* multiply */
end
return y
The time to carry out modular exponentation increases with the number of bits set to one in the exponent e. For encryption, an appropriate choice of e can reduce the computational effort required to carry out the computation of c = m^e mod n. Popular choices like 3, 17 and 65537 are all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.
The bits in the decryption exponent d, however, will not be so convenient and so decryption using the standard method of modular exponentiation will take longer than encryption. An alternative method of representing the private key uses the Chinese Remainder Theorem (CRT). The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT method of decryption is four times faster overall than calculating m = c^d mod n. For more details, see . The extra values for the private key are:-
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p where p > q
These are pre-computed and saved along with p and q as the private key. To compute the message m given c do the following:-
m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq
Even though there are more steps in this procedure, the modular exponentation to be carried out uses much shorter exponents and so it is less expensive overall.
Theory and proof of the RSA algorithm
Every man and his dog seems to have a proof of the RSA algorithm out there, all requiring varying degrees of understanding of number theory. (updated Sept 2004). If your browser won't print that properly, try this . Thanks to an anonymous contributor who pointed out that x and p are not coprime when x is a multiple of p.
A very simple example of RSA encryption
This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 can probably even do it by hand on paper).
1. Select primes p=11, q=3.
2. n = pq = 11.3 = 33
phi = (p-1)(q-1) = 10.2 = 20
3. Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check gcd(e, q-1) = gcd(3, 2) = 1
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
4. Compute d such that ed ≡ 1 (mod phi)
i.e. compute d = e^-1 mod phi = 3^-1 mod 20
i.e. find a value for d such that phi divides (ed-1)
i.e. find d such that 20 divides 3d-1.
Simple testing (d = 1, 2, ...) gives d = 7
Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
5. Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).
This is actually the smallest possible value for the modulus n for which the RSA algorithm works.
Now say we want to encrypt the message m = 7,
c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.
To check decryption we compute
m' = c^d mod n = 13^7 mod 33 = 7.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that a = bc mod n = (b mod n).(c mod n) mod n so we can break down a potentially large number into its components and comb
