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

Then each l -symbol message represents an integer of at most l digits in base b and
hence an element of

Z n . Thus if we have a message m we may divide it into l -symbol
blocks and encrypt it by encrypting the elements of

Z n corresponding to these blocks.
Note that the ciphertext corresponding to a block is an element of Z n and hence it

may have l 1 digits, so this produces a slight size-expansion. Also, in order to

represent the ciphertext unambiguously as a string of symbols of

+

Σ , one may use

exactly l 1 symbols to represent each ciphertext block, completing with 0-digits

if necessary. Of course, the plaintext space may also be identified with the set of
l -symbol strings in a similar manner.
For example, if

+

Σ is the 8-bit ASCII character set and the RSA modulus n is a

2048-bit integer, then 255. Thus if we have a string of 8-bit ASCII

characters, we partition it into 255-character blocks (except the last one, which can
have fewer characters) and each of these blocks produces a ciphertext consisting of
256 characters (if padded with zeros to the left). This is the approach we are going to
use when implementing RSA in Maple, except that ciphertexts will be represented
in the hexadecimal alphabet for convenience.
As already mentioned, RSA is seldom used in practice to encrypt long messages
and is typically used instead to encrypt encapsulated symmetric session keys by
means of a hybrid scheme. These keys are much shorter than the currently used RSA
moduli and hence they are usually encapsulated into a single element of

log 256 n =

Z n ,sofor

this usage blocks are not necessary.

Exercise 8.7 Amessage consisting of 60 characters over the 26-letter English alpha-
bet is numerically coded as follows. Each alphabet letter is identified with an element
of

Z 26 in the standard way, the message is divided into six 10-letter blocks, and each
block is regarded as an integer in the base-26 numeration system. Then the message
blocks are encrypted with plain RSA using a 2048-bit modulus n . Explain how to
recover the message from the ciphertext without factoring n .

8.3.3 Plain RSA in Maple

Let us now implement plain RSA in Maple following the guidelines just outlined.
This will then allow us to perform some experiments with keys of realistic size.
We start with the key generation algorithm. As mentioned above, we will select the
primes with a variant of the previously given function PseudoRandomPrime .This
variant is given in the next function, RSAPrime , which uses the Blum-Blum-Shub
pseudo-random bit generator to select the prime candidates in the appropriate inter-
vals. The required parameters are the same as in PseudoRandomPrime , namely,
one for the number k of bits that the prime should have and another for the seed that,
for security reasons, should be an integer obtained from a random string of at least
128 bits.