Penguin
Recent Changes
Annotated edit history of RSA version 1, including all changes. View license author blame.
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