Public-Key Encryption - Introduction to Cryptography with Maple - page 434

where the second equality comes from the fact that p divides n and the last equality
follows from Fermat's little theorem (or, in other words, from the discrete logarithm
isomorphism between Z p and

Z p − 1 ; note that if p divides c then this equality is
trivial). Similarly, we have that m q =

c d q mod q and once we know m p and m q we
can use the Chinese remainder theorem to determine m as the unique solution in

Z n

of the system of congruences:

x ≡ m p ( mod p )

x ≡ m q ( mod q )

Now, if we look at the proof of Theorem 2.12, we see that the elements y j defined
therein are just the inverses of p modulo q and of q modulo p ,sousingtheCRT
in this case amounts to computing these inverses y p , y q , by applying the extended
Euclidean algorithm to p and q to obtain

y p p + y q q = 1 .

Once these elements are computed, the solution of the above system is given by

m = ( m p y q q + m q y p p ) mod n . (8.1)

Observe also that the only values in this expression that depend on m are m p and
m q , and that their coefficients may be precomputed and used to decrypt all ciphertexts
encrypted with the public key. Thus the decryption operation essentially reduces to
two exponentiations where both the exponents and the moduli have approximately
half of the size of n and hence, as indicatedwhen discussing the binary exponentiation
method in Sect. 2.7 , this method will make decryption almost four times faster.

8.3.2.3 The RSA Message Space

Another practical matter that must be considered when implementing plain RSA is
how to encrypt binary strings or, more generally, any message over an alphabet. The
natural way to do it is pretty straightforward: if the alphabet has b symbols, just
regard any string of symbols as the base- b representation of a non-negative integer
(through a suitable identification of the alphabet symbols with the base- b digits). If
this integer is Z n and

hence an RSA plaintext. If this is not the case then we may divide the message into
blocks of suitable size so that each of these blocks can be identified with an element
of

< n (where n is the RSA modulus) then it is an element of

Z n .
In more detail, we can proceed as follows. Let Σ be the alphabet and assume

that | Σ |= b . Then we may identify Σ with Z b by choosing a bijection between

these two sets and, this way, the symbols of Σ also become the digits of the base- b

number system. Then let l := log b n , so that n is an ( l + 1 ) -digit number in base b .