This Web

All Webs

brayden.org

Books RSS

Random RSS

Software RSS

Other

RSA

• RSA
  • Links
  • The Mathematical Guts of RSA Encryption
  • An Example of the RSA Algorithm

Links

• Ron Rivest's Home Page
• RSA Sample code at Oregon State
• A concise description of RSA algorithm
• Very concise description of RSA

The Mathematical Guts of RSA Encryption

... by Francis Litterio at http://world.std.com/~franl/crypto/rsa-guts.html

The RSA algorithm was invented in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman.

Here's the relatively easy to understand math behind RSA public key encryption.

Find P and Q, two large (e.g., 1024-bit) prime numbers.

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.

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.

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.

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. 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.

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.

An Example of the RSA Algorithm

P  = 61    <- first prime number (destroy this after computing E and D)
Q  = 53    <- second prime number (destroy this after computing E and D)
PQ = 3233  <- modulus (give this to others)
E  = 17    <- public exponent (give this to others)
D  = 2753  <- private exponent (keep this secret!)

Your public key is (E,PQ).

Your private key is D.

The encryption function is:

   encrypt(T) = (T^E) mod PQ
         = (T^17) mod 3233

The decryption function is:

   decrypt(C) = (C^D) mod PQ
         = (C^2753) mod 3233

To encrypt the plaintext value 123, do this:

   encrypt(123) = (123^17) mod 3233
           = 337587917446653715596592958817679803 mod 3233
           = 855

To decrypt the ciphertext value 855, do this:

   decrypt(855) = (855^2753) mod 3233
           = 123

-- DaleBrayden - 01 Dec 2002