The RSA Encryption algorithm is a highly mathematical, commonly used method to encrypt digital pieces of information. The security of this algorithm is dependent on one thing alone: The sheer difficulty of factoring large integers.

The algorithm for RSA public key encryption follows:

A) Select P and Q, where P and Q are prime numbers. As an example, we’ll select P = 61 and Q = 53.

B) Choose a third integer E, such that E > 1, E < PQ, and E and (P-1) * (Q-1) are relatively prime. This is extremely simple with the aid of a computer, but otherwise, you can use the Euclidean algorithm to make sure that the GCD of E and (P-1)(Q-1) is 1. In this instance, (P-1)(Q-1) is 3120. A suitable E, is 17.

C) Compute D, such that DE = 1 mod (P-1)(Q-1). In this example, we want to solve

17E = 1 mod 3120. This can be solved as a linear congruence by hand, or a computer can be used to find a suitable value. One possible value for D in this case, is 2753.

At this point, all the values needed have been generated, in order to define the encryption algorithm, and the decryption algorithm.

The encryption algorithm is defined as C = (T^E) mod PQ. C is the “ciphertext”, which will be some positive integer. Words and phrases are typically broken into manageable sizes, and converted into some numerical representation. Let’s pretend that the number “123” is representative of some letter. Thus, we let T = 123, and the encryption algorithm then produces (123 ^ 17) mod (3233), which can be deduced to be 855.

In general, the value of (PQ) and E are published openly, while the individual values of P, Q, and D are kept secret. This way, anybody can use the known values of PQ and E to send encrypted messages, but only the creator of these values can decipher these messages.

To decrypt the message, one must simply solve T = (C^D) mod PQ. So, to decrypt 855, solve (855^2753) mod 3233. The solution to this, as expected, is 123, the original number.

It is widely accepted that the only way to “break” the security of RSA, is to factor the public number PQ, into its factors, P and Q. Once P and Q are known, it is a simple matter of using the known E to solve for D, and the decryption algorithm is then known. However, when P and Q are individually, hundreds of digits long, it is virtually impossible to factor PQ in a reasonable amount of time.

The RSA encryption algorithm is a wonderful modern application of modular arithmetic!

Sources:

http://www.di-mgt.com.au/rsa_alg.html - “RSA Algorithm”

http://world.std.com/~franl/crypto/ - “Cryptography”