version 1, including all changes.
.
Rev |
Author |
# |
Line |
1 |
CraigBox |
1 |
RSA is a cryptographic algorithm, named after its authors, [Rivest, Shamir, and Adleman|Acronym]. (Also an acronym for the [Returned Serviceman's Association|http://www.rsa.org.nz/]. Ask your grandfather, if he's sober.) |
|
|
2 |
|
|
|
3 |
This is commonly the algorithm used in PublicKeyEncryption. |
|
|
4 |
|
|
|
5 |
Loosely described, this is how it works. |
|
|
6 |
|
|
|
7 |
# Find P and Q, two large (e.g., 1024-bit) prime numbers. |
|
|
8 |
# Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are __relatively prime__, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number. |
|
|
9 |
#. Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D. |
|
|
10 |
# The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ. |
|
|
11 |
# The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. |
|
|
12 |
|
|
|
13 |
Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent. |
|
|
14 |
|
|
|
15 |
You can publish your public key freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (your public key). If P and Q are each 1024 bits long, the sun will burn out before the most powerful computers presently in existence can factor your modulus into P and Q. |
|
|
16 |
|
|
|
17 |
[An example of RSA encryption|http://world.std.com/~franl/crypto/rsa-example.html]. Go read t - it makes all the above stuff make sense. Note, it's only reversable because the numbers are tiny. |
|
|
18 |
|
|
|
19 |
I'm not sure how much [RSA Secyurity|http://www.rsasecurity.com] have to do with the RSA algorithm; I assume they either hired the inventors and/or bought the name. |
|
|
20 |
|
|
|
21 |
|
|
|
22 |
---- |
|
|
23 |
CategoryAlgorithm |