RSA gets its security from the difficulty of factoring large numbers. The public and private keys are functions of a pair of large (100 to 200 digits or even larger) prime numbers. Recovering the plaintext from the public key and the ciphertext is conjectured to be equivalent to factoring the product of the two primes.
To generate the two keys, choose two random large prime numbers, p and q. For maximum security, choose p and q of equal length. Compute the product:
n = pq
Then randomly choose the encryption key, e, such that e and (p - 1)(q - 1) are relatively prime. Finally, use the extended Euclidean algorithm to compute the decryption key, d, such that
ed =- 1 (mod (p - 1)(q - 1))[Scanner's note: the above equals was an equivalence] In other words,
d = e-1 mod ((p - 1)(q - 1))Note that d and n are also relatively prime. The numbers e and n are the public key; the number d is the private key. The two primes, p and q, are no longer needed. They should be discarded, but never revealed.
To encrypt a message m, first divide it into numerical blocks smaller than n (with binary data, choose the largest power of 2 less than n). That is, if both p and q are 100-digit primes, then n will have just under 200 digits and each message block, m, should be just under 200 digits long. (If you need to encrypt a fixed number of blocks, you can pad them with a few zeros on the left to ensure that they will always be less than n. The encrypted message, c, will be made up of similarly sized message blocks, ci, of about the same length. The encryption formula is simply
ci = mie mod n
To decrypt a message, take each encrypted block ci and compute
mi = cid mod n
Since
cid = ( mie ) dthe formula recovers the message. This is summarized in Table 19.2.
= mied
= mik(p - 1)(q - 1) + 1
= mimik(p - 1)(q - 1)
= mi * 1
= mi ; all ( mod n )
The message could just as easily have been encrypted with d and decrypted with e; the choice is arbitrary. I will spare you the number theory that proves why this works; most current texts on cryptography cover it in detail. A short example will probably go a long way to making this clearer. If p = 47 and q = 71, then
n = pq = 3337
The encryption key, e, must have no factors in common with
(p - 1)(q - 1) = 46 * 70 = 3220
Choose e (at random) to be 79. In that case
d = 79-1 mod 3220 = 1019This number was calculated using the extended Euclidean algorithm (see Section 11.3). Publish e and n, and keep d secret. Discard p and q.
To encrypt the message
m = 6882326879666683first break it into small blocks. Three-digit blocks work nicely in this case. The message is split into six blocks, mi, in which
m1 = 688 m2 = 232 m3 = 687 m4 = 966 m5 = 668 m6 = 003
The first block is encrypted as
68879 mod 3337 = 1570 = c1
Performing the same operation on the subsequent blocks generates an encrypted message:
c = 1570 2756 2091 2276 2423 158
Decrypting the message requires performing the same exponentiation using the decryption key of 1019, so
15701019 mod 3337 = 688 = m1The rest of the message can be recovered in this manner.