RSA stands for the initials of the three men who invented it in 1977 at MIT: Ron Rivest, Adi Shamir, and Len Adleman. The security behind RSA lies in the difficulty of factoring large numbers into their primes. The process involves selecting two large (hundreds of digits) prime numbers (p and q), and multiplying them together to get the sum, n. These numbers are pased through a mathematical algorithm to determine the public key KU = {e,n} and the private key KR = {d,n}, which are mathematically related
(the necessary equations are given at the bottom of the page). It is extremely difficult to determine e and/or d given n, thus the security of the algorithm. Once the keys have been created a message can be encrypted in blocks, and passed though the following equation:
(1)
Where C is the ciphertext, M is the plaintext, and e is the recipient's public key. Similarly, the above message could be decrypted by the following equation:
(2)
Where d is the recipient's private key.
For example: let's assume that our M is 19 (we will use smaller numbers for simplicity, normally theses numbers would be MUCH larger). We will use 7 as p and 17 as q. Thus, n = 7 * 17 = 119. Our e is then calculated to be 5 and d is calculated to be 77. Thus our KU is {5, 119} and our KR is {77, 119}. We can then pass the needed values through equation (1) to compute C. In this case C is 66. We could then decrypt C (66) to get back our original plain text. We pass the needed values through equation (2) and get 19, our original plaintext! Try it yourself with other numbers.
Note: To determine e and d, perform the following:
Calculate f(n) = (p - 1)(q - 1)
Choose e to be relatively prime to f(n) and less than f(n).
Determine d such that de = 1 mod f(n) and d < f(n).
Main Page
Caesar Cipher
Simple Substitution Cipher
Vigenere Cipher
Gronsfeld Cipher
The German Enigma Machine
RSA Public Key Encryption
PGP -- Pretty Good Protection
Information for this page was obtained from Network and Internetwork Security: Principles and Practice by William Stallings, Ph.D.; Prentice Hall, 1995.
