Cryptography Reference
In-Depth Information
as the inverse of the Blum-Williams permutation in this case. If, on the contrary,
BW = false
, which is the default value, then the four preimages of
c
by the Rabin
function are computed and returned as a list (whose first element is the only one that is
a quadratic residue). The function produces a different output (when
BW = false
)
in case
c
is found to be a quadratic non-residue modulo
n
, for reasons that are
explained below.
> InvRabin := proc(c, p, q, pinv, qinv, {BW::truefalse := false})
local n, mp, mq, reject, yp, yq, r, s;
reject := false;
n := p*q;
mp := Power(c, iquo(p+1, 4)) mod p;
mq := Power(c, iquo(q+1, 4)) mod q;
if mpˆ2 mod p <> c mod p or mqˆ2 mod q <> c mod q then
reject := true
end if;
if BW and reject then
error "%1 is not a quadratic residue", c
end if;
if _params['pinv'] = true and _params['qinv'] = true then
yp := pinv;
yq := qinv
else
igcdex(p, q, 'yp', 'yq')
end if;
r := (yp*p*mq+yq*q*mp) mod n;
s := (yp*p*mq-yq*q*mp) mod n;
if BW then
r
elif reject then
[r, n-r, s, n-s, 0]
else
[r, n-r, s, n-s]
end if;
end proc:
An important feature of this function is the way it handles
c
whenever
c
is a
quadratic non-residue modulo
n
. Whether this is the case can be checked by comput-
ing the Legendre symbols of
c
with respect to
p
and
q
and applying Proposition 2.14.
However, since in the implementation of the function we have to try to compute the
square roots of
c
modulo
p
and modulo
q
anyway (which are called
mp
and
mq
in the
code of the function), it is simpler and more efficient to square
mp
modulo
p
and
mq
modulo
q
and check that these values are equal to
c
mod
p
and
c
mod
q
respectively.
The subtle point here is that it would be a mistake to reject
c
with an error message
at this point if it is discovered not to be a quadratic residue. Indeed, we will later use
this function to implement a more secure version of Rabin encryption and, as we will
see, these messages could help an adversary in a CCA attack. Because of this, the
function
InvRabin
completes the computation—i.e., it tries to compute the square
roots of
c
—even in this case and returns an augmented list of 5 terms where the last
one is equal to 0. The values in the list are meaningless in this case but this makes it
possible to produce the error message at the end of the computation, which will take
time similar to the case when there is no error. The idea is to prevent an attacker from
distinguishing rejections at the different steps of a decryption using, for example,
timing analysis.
