Asymmetric Encryption Systems - Contemporary Cryptography - page 347

is not clear how much the RSA asymmetric encryption system is weakened (in the
sense that there may be simpler ways to break the RSA problem than to solve the
IFP) if a very small public exponent e is used. Consequently, one should be cautious
with very small public exponents and use them only if necessary. For all practical
purposes, the use of e =2 16 +1=65 , 537 seems to be appropriate.
In either case, the RSA asymmetric encryption system should not be used
natively (i.e., in raw form). Instead, messages should be preprocessed and encoded
prior to applying the RSA function. The use of OAEP (see Section 14.3.2) is highly
recommended for this purpose.

14.2.2 Rabin

As mentioned earlier, the RSAP is not known to be computationally equivalent to
the IFP. This means that it is theoretically possible to break the security of the RSA
public key cryptosystem without solving the IFP. This possibility is worrisome,
and—since the beginning of public key cryptography—people have been looking
for public key cryptosystems that can be shown to be computationally equivalent to
a hard problem, such as the IFP. As mentioned in Section 1.2.2, Michael O. Rabin
was the first person who found and proposed such a system in 1979 [11]. 10 The
Rabin asymmetric encryption system is based on the Square family of trapdoor
permutations overviewed and discussed in Section 7.2.3. As addressed later, the
security of the Rabin system can be proven to be computationally equivalent to the
IFP, meaning that there is provably no easier way to break the Rabin system than to
solve the IFP.

14.2.2.1 Key Generation Algorithm

The Rabin Generate algorithm takes as input a security parameter, and it generates
as output a Blum integer of about this size. More specifically, it randomly selects
two primes p and q that are both equivalent to 3 modulo 4 and that are each about
half of the size specified by the security parameter. It then computes n = pq ,and
outputs the modulus n to represent the public key and the prime factors ( p, q ) of n
to represent the private key.
Let us consider a toy example to illustrate what is going on (in this and in the
other algorithms of the Rabin asymmetric encryption system). The Rabin Generate
algorithm randomly selects p =11and q =23(note that 11 and 23 are both
equivalent to 3 modulo 4), computes the Blum integer n = pq =11

· 23 = 253,and

outputs the public key 253 and the private key (11 , 23).

10 At this time, Rabin was also working at MIT (like Rivest, Shamir, and Adleman).