Previous | Table of Contents | Next |
RSA is a public key encryption system invented by Rivest, Shamir, and Adleman in 1978. Under this technique, both encryption and decryption are performed using exponentiation. RSA obtains security from the difficulty associated with factoring large prime numbers. As you will shortly note, public and private keys are functions of a pair of large prime numbers. Thus, the ability to decipher plaintext from the use of a public key and ciphertext is the equivalent of factoring two large primes.
Using the RSA system, each party generates a public key and a corresponding private key. To do so, two large primes of equal length are selected, p and q. To facilitate security, each prime should be a minimum of 32 bytes, or 256 bits, in length. Once the two primes are selected, you multiply them together and find their product n, which is referred to as the modulus of pq.
To generate a public key, each person using the RSA algorithm generates their encryption (e) and decryption (d) keys. The encryption key, e, is selected such that it is less than n and relatively prime to (p-1)(q-1), which represents the totient function 0(n). This means that e and (p-1)(q-1) have no common factors other than 1. Your public key then becomes the pair <e,n>.
To compute your private key, you will find another number d, such that (ed-1) is divisible by (p-1)(q-1). That is, d represents the multiplicative inverse of e mod 0(n). Then, the private key becomes the pair <d,n>. Once your public and private keys are selected, the primes p and q are no longer needed. Although it is safe to discard them, they should not be revealed.
To encipher a message m you would first subdivide it into blocks smaller than n (m<n). When working with binary data this would be equivalent to selecting the largest power of 2 less than n. You would then use your public key (e) to compute ciphertext (c) as follows:
c = mie mod n
where mi represents block I of message m.
To decrypt a message you would use your private key (d) on each ciphertext block ci as follows:
mi = cid mod n
To illustrate the use of RSA, lets use a few small primes to facilitate observing the relevant computations. First, lets assume you selected p = 53 and q = 61. Then:
n = p*q = 53*61 = 3233
Next you would randomly select an encryption key, e, such that it has no common factors with 3233. For our example, lets select e to be 41. Then, the private key d would be:
d = 41-1 mod 3233
To compute d, you must obtain the multiplicative inverse of 41 mod 3233. That is, you must determine the number which when multiplied by 41 mod 3233 yields a result of unity. Based upon Eulers application of the totient function, if n is a prime, the 0(n) = n-1. If p and q are primes and n = pq, then 0(n) = (p-1)(q-1). Thus, if the gcd (a,n) = 1, where x is not a multiple of n, then:
x0(n) mod n = 1
This means you can compute the multiplicative inverse x-1 mod n as follows:
X = x0(n)-1 mod n
Returning to your computation, you need to determine the private key d, such that:
d = 41-1 mod 3233
Since 3233 is prime, then 0(3233) = 3233-1 = 3232. Thus, the inverse of 41 mod 3233 becomes:
413232-1 mod 3233 = 413231 mod 3233
Previous | Table of Contents | Next |