3.2 Encrypting and Decrypting RSA messages

We assume for the moment that someone (an ``oracle'') gives us a modulus N and two numbers p (the public key) and s (the secret key) with the information that in m is any (invertible) element in $\mathbb {Z}$/N$\mathbb {Z}$, then m^ps = m in $\mathbb {Z}$/N$\mathbb {Z}$. In order to send a message, the message is broken into chunks m of size N - 1 and each block is encrypted as c = m^p (we will see shortly why we do not expect a problem from non-invertibility of m). This is then sent over the public channel. At the receiving end the operation m = c^s recovers the original message blocks. Thus, the algorithms of the earlier subsection (especially the one about taking powers) can usefully be applied in implementing this encryption/decryption process.

One question is how the triple (N, p, s) is chosen. Clearly, if M is the order of the group of units in $\mathbb {Z}$/N$\mathbb {Z}$, then one way to recover s given p is by the relation ps = 1(mod M). Thus, one consideration is that given only N and p it should not be easy to determine M (or else s is not secret at all!). Clearly, if a complete factorisation of N is known then this M can be easily determined. However, note that if k is the exponent of the group of units in $\mathbb {Z}$/N$\mathbb {Z}$ (i. e. the least common multiple of the order of all elements) then it is enough to know k rather than M, since solving ps = 1(mod k) is adequate.

A related consideration is that there should not be too many elements in $\mathbb {Z}$/N$\mathbb {Z}$ which are not units. The encrypter/decrypter should not have to worry about checking for this while constructing messages.

Both these considerations lead us to take for N = ab a product of two large primes a and b (we will see some additional constraints on the pair (a, b) as we go along). It is generally expected (and in the next section we will see some evidence of this) that factoring a number which has all factors of size (in terms of ``log'') r or more is much harder than checking that a number of size r is prime. Thus, it should be easier to construct key triples than it is to ``break'' keys (by determining s given N and p). Note that M = (p - 1)(q - 1) in this case and in general there does not seem to be a way to determine M (or the exponent k for that matter) without determining a factoring of N. The only elements m in $\mathbb {Z}$/N$\mathbb {Z}$ that are not units are p and q, thus this choice is also good from this point of view.