Future Beacon

RSA Encryption

by James Adrian


      To understand RSA encryption, you will need to know the meaning of expressions like (57)MOD 12. It is rather simple. You divide 57 by 12 and throw away everything but the remainder. You surely have seen things like "57 divided by 12 is 4 with a remainder of 9." We can verify that this is true because 4 x 12 = 48, and when you add 9, you get 57. Well, (57)MOD 12 = 9. It's as simple as that. MOD is short for Modulo. Modulo arithmetic can be thought of a clock arithmetic if you replace the 12 with a zero and remember that the Modulus, as it is called (in this case it is 12), can be any integer greater than 1. Here are some examples:

            (16)MOD 7 = 2.

            (10)MOD 10 = 0

            (2 + 9)MOD 6 = (11)MOD 6 = 5

            ((3)(8))MOD 7 = (24)MOD 7 = 3

            (24)MOD 15 = (16)MOD 15 = 1

      On to RSA:

      This explanation of RSA encryption uses very small numbers in order to demonstrate the math more clearly; but in any real case, the selected and calculated numbers are very large. It is difficult for an unauthorized person to decrypt RSA messages because it is difficult to factor a number which is the product of very large prime numbers.

      Communication by means of RSA encrypted email begins when a sender requests secure communication with a receiver who uses RSA encryption. In this example, the sender's message (the Plaintext) is 4 and the following steps are taken:

      1.   The receiver sends his or her Public Key, e = 5, and a Modulus, n = 35, to the sender.

      2.   The sender encrypts the message using the modulus and the public key this way:

            E = encrypted message = ((Plaintext)e)MOD n

            E = encrypted message = (45)MOD 35

            E = (1024)MOD 35 = 9

      3.   The message, 9, is then sent to the receiver. This message, E = 9, is also called the Ciphertext.


      The receiver uses the modulus, n = 35, and a Secret Key, d = 5, to decrypt the message this way:

            Plaintext = (Ed)MOD n

            Plaintext = (95)MOD 35 = (59049)MOD 35 = 4

      In this example, the public key is coincidentally the same as the secret key. Normally, the keys and the modulus are very large numbers that are very different. If the secret key were to be coincidentally the same as the public key, only the receiver would know. The fact that they are both 5 in the example above is of no importance.

      Any sender who knows e and n can send a message that only the receiver can decrypt. The secret key, d, is kept secret by the receiver. It is calculated by the receiver before sending the sender the modulus and the public key. The secret key is successful in decrypting the ciphertext because n, e, and d are all related.

      If your RSA software does not provide new sets of keys at the push of a button or with a click of the mouse, you will need to calculate them. Here's how:

      1.   Choose two large primes, p and q, and multiply them together to produce the modulus, n. The example shown above is based on p = 5 and q = 7, giving us a modulus, n, of (5)(7) = 35. For the encryption to be effective, these numbers need to be large. They are small for the sake of making the arithmetic clear.

      2.   Calculate T = (p-1)(q-1). This is (4)(6). Thus T = 24. T is not used by the sender and is not communicated to the sender. It is used by the receiver to calculate the keys.

      3.   Choose a public key, e, that shares no factors with T, is greater than 1, and is less than T. The number 5 is just such a number. It is less than T and it is a prime number, so it could not possibly have factors in common with T.

      4.   Find a secret key, d, such that ((d)(e))MOD T = 1. Just as in the case where (A)(B) = 1, where B is the multiplicative inverse of A, d is the multiplicative inverse of e in MOD T. This can be hard to calculate, but in this case, the solution can be seen by inspection:

            ((5)(5))MOD 24 = (25)MOD 24 = 1

    However, if the numbers were larger, d would be much harder to find. Consider this problem:

            ((d)(e))MOD T = ((d)(11))MOD 288 = 1

      In this case, d = 131. Consider e and T in the millions, billions, or trillions. We need an straightforward way of determining d in realistic cases. If this is done my hand without a computer program, the Extended Euclidean Algorithm would do the job, but if the numbers are more than five or six digits long, it would take a great deal of time. For numbers 100 digits long, a program is required. There are programs on line like this one here for calculating the multiplicative inverse in a modulo of your choice. Equipped with a list of very large prime numbers and access to an inverse calculator, you're all set to go.


Contact

      Please feel free to write to me directly for more information or to make suggestions or comments. My email address is jim@futurebeacon.com. You can also go to my contact page to get my full contact information. Suggestions, questions, additional information and critiques are very welcome.