Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 174

Block Size
We cannot properly encipher the plaintext message unit if it is a numerical
value m n . (The reader may try an example, say, m = 72892588, in Example

4.5, and see that information is lost (under modular reduction) and the system
fails.) When m

≥

≥

n , we must subdivide the plaintext numerical equivalents into
blocks of equal size, a process called message blocking . If we are dealing with
numerical equivalents of the plaintext in base N integers for some fixed N> 1,
then message blocking is accomplished by choosing that unique integer such
that N <n<N +1 . Then we write the message as blocks of -digit, base
N integers (with zeros packed to the right in the last block if necessary), and
encipher each separately. Since N <n , each block of plaintext corresponds to
an element of . Therefore, since n<N +1 , then each ciphertext message

unit can be uniquely written as an ( +1)-digit, base N integer in

Z /n Z

C = Z /n Z = M .

Modulus Size
For the modern day and the near future, an RSA modulus of 1024 to 2048
bits would be considered secure. Certain RSA moduli of n digits that are a
product of two primes of approximately the same size are denoted by RSA- n ,
called an RSA challenge number . These are published on the Internet and the
reader may request the list from [e-mail] . These are numbers
for which rewards are offered to factor them. We will return to some concrete
examples of these numbers shortly.

Security
In the RSA cipher, the four items d, p, q, φ ( n ) form the trapdoor and knowl-
edge of any one of them reveals the remaining three items. In other words, they
are not independent items. Also, to ensure a secure cryptosystem, there must be
“preprocessing” of plaintext message units before the enciphering stage. In [37],
it is shown that implementing the RSA cryptosystem as described on page 173,
which we will call plain RSA (namely, without any preprocessing of plaintext
message units) is insecure in the following sense. The attack against plain RSA
given in [37] shows that even though an m -bit key is used in plain RSA, the
effective security is m/ 2 bits. Hence, it is essential that, before encryption, a
preprocessing step be implemented that uses the Optimal Asymmetric Encryp-
tion Padding (OAEP) (introduced in [15]) such as [185], a recent standard from
RSA Labs. There are methods for adding randomness to the enciphering stage
in RSA (see [15] for instance). In order to obtain a secure RSA cryptosystem
from a plain RSA cryptosystem, there should be an application of a preprocess-
ing function to the plaintext before enciphering . In [15], there are new standards
for “padding” plain RSA so that it is secure against certain chosen ciphertext
attacks (see Footnote 4.3 on page 176).
One example that is pertinent at this juncture is the following. Suppose
that Alice and Bob use the RSA cryptosystem but they choose the same
RSA modulus n , and enciphering (public) keys e A and e B , respectively, with
gcd( e A ,e B ) = 1. Suppose that Eve intercepts two cryptograms m e A and m e B ,
enciphering the same message m , sent by a third entity to Alice and Bob, re-