Cryptology - RSA Overview
Here is how the RSA algorithm works, in a nutshell:
- Find 2 prime numbers, call them P and Q. Choose larger values if you like.
- Mulltiply them together, call it N (that is, N=P * Q)
- 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.
- 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.) - 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)
- 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
- You can unravel the encrypted message (C) using your pivate key (D) and the decrypt foruma : M = C * D mod N
- Login to post comments