Cryptography Reference
In-Depth Information
Exercise 8.21
Prove that the algorithm that factors the modulus of a Rabin key
given oracle access to the decryption algorithm has, for a randomly chosen
x
∈ Z
n
,
a probability of success equal to 1
/
2.
We will see that there are variants of Rabin encryption that are resistant to CCA
attacks but, as it has often been remarked, the fact that plain Rabin is so completely
vulnerable to CCA attacks is probably the reason why even the more secure variants
of this scheme are seldom used in practice despite the fact that there is no reason to
assume that they are less secure than, say, the corresponding RSA variants and, on
the other hand, they may have other advantages such as a faster encryption algorithm.
8.4.2 Plain Rabin Encryption in Maple
We are going to implement in Maple the Rabin functions
R
n
and their inverses, for
a Blum integer
n
. These functions are not permutations, so we cannot speak of the
inverse function in the strict sense but we will see how to compute the four preimages
of each quadratic residue, i.e., its four square roots modulo
n
, using Algorithm
8.2, and we will loosely speak of the 'inverse Rabin functions' all the same. As a
particular case we will also have an implementation of
BW
n
and its inverse, which
can be used to implement plain Rabin encryption as described above. We will leave
as an exercise for the reader the implementation of this scheme, including the key
generation algorithm (which can be derived from the one used to generate RSA keys)
and other minor details. Later, we will use the Rabin functions as cryptographic
primitives to implement a more secure version of Rabin encryption.
The function
R
n
is just squaringmodulo
n
and
BW
n
is its restriction to the subgroup
QR
n
of
∈ Z
n
is a quadratic
residue modulo
n
may be hard, but quadratic residues are easily obtained in a natural
way by just squaring elements of
Z
n
. As we have remarked, determining whether an
x
Z
n
.
The Rabin functions are given by the following Maple function in which we
assume that
n
is the product of two distinct Blum primes:
> Rabin := proc(m::posint, n::posint)
mˆ2 mod n
end proc:
The 'inverse Rabin functions'—and the inverse Blum-Williams permutations—
are computed by the nextMaple procedure. The input parameters are
c
, for a quadratic
residue modulo
n
whose square roots are computed by the function,
p
and
q
, which
serve to specify the primes whose product is the modulus
n
and, finally,
pinv
and
qinv
, where the inverse of
p
modulo
q
and the inverse of
q
modulo
p
, respectively,
can be specified. These two last parameters are used to speed up the computation
but they are not really necessary and, if not supplied, they will be computed inside
the function by means of the extended Euclidean algorithm. In addition, there is
an optional keyword parameter
BW
that serves to specify whether the function to
invert is the Blum-Williams permutation. If
BW = true
then the unique square
root of
c
which is a quadratic residue modulo
n
is returned, so that the function acts
