Cryptology - RSA Overview

Here is how the RSA algorithm works, in a nutshell:


  1. Find 2 prime numbers, call them P and Q.  Choose larger values if you like.
  2. Mulltiply them together, call it N (that is, N=P * Q)
  3. Choose a number or your public value that is less than N and don't share a common factor between the value of (P-1) and (Q-1).  Call it E.  (For example, if N is 21, you can choose any values between 3-20 that don't share a common factor.  For example, 6 and 20 would not work, since you can divide both by 2.  7 and 20 would work because they have no common  factors (7 is a prime, so that helps).  9 and 20 would also work (9 only has 3 as a factor, 20 doesn't have 3 as a factor.  9 and 15 wouldn't work, since both are divisible by 3... you get the idea.  Choose a single number that is "relatively prime" (no common factors) with both P-1 and Q-1.
  4. Now calculate your private value (we'll call it D) by working out the following: E * D = 1 mod (P-1)*(Q-1).
    (MOD = Modulus, it is the remainder after division. 2 mod 7 is 1 because 2 goes into 7 3 times with 1 left over.  7 mod 20 is 6 because 7 goes into 20 2 times (for 14) with 6 (20-6) left over.)
  5. At this point, you have everything you need.  Make N and E public, keep D, P and Q secret (literally, watch your p's and q's as well as your privates.  Sorry, couldn't resist)
  6. At this point, anyone can send you an encrypted message (M) by turning it into Ciphertext (C) using your public key (D) and the encrypt formula of C = M * E mod N
  7. You can unravel the encrypted message (C) using your pivate key (D) and the decrypt foruma :  M = C * D mod N