Call Today 716.688.4675

Theory of RSA

The RSA algorithm is fairly simple and straightforward, which has perhaps added to its widespread adoption. Find two large prime numbers, p and q and multiply these together to give N. Therefore,

N = p * q

Select a number e which is less than N and prime to (p – 1) * (q – 1), so that e and (p – 1) * (q – 1) have no common factors. Select another number d, where (ed – 1) is divisible by (p -1) * (q – 1). The public key is (N, e) and the private key is (N, d), where e is the public exponent and d is the private exponent. Primes p and q are no longer needed but cannot be disclosed. It is standard to refer to the bit length of the modulus N as the size of the RSA key.

In order to successfully encrypt a message m, create the ciphertext c (with e and N as defined previously) such that

c = me modN

The cipher text c may now be sent securely. It may be decrypted by calculating

m = cd modN

From this it could be seen that if factors p and q could be determined from N, it would be possible to obtain d. Therefore, for RSA to be considered secure it is necessary that the efficient factoring of sufficiently large integers is not possible.

VOCAL Technologies, Ltd.
520 Lee Entrance, Suite 202
Amherst New York 14228
Phone: +1-716-688-4675
Fax: +1-716-639-0713