Cryptography Reference
In-Depth Information
Z
n
(for notational convenience, in order to save space) and, if necessary, we will
continue with the elements of
of
Z
n
following this one in the subsequent trials; it is
clear that this variant of the algorithm will also work and will eventually factor
n
.So
we start with
x
=
13 and we compute:
>x:=13;
y := InvRabin(Rabin(x, n), op(rkey[2 .. 5]), BW = true);
13
We see that
y
=
13
=
x
in this case, so gcd
(
x
−
y
,
n
)
=
n
and we do not obtain
a proper factor. Obviously, this was due to the fact that
x
=
13 is a quadratic residue
modulo
n
; in that case we have that
BW
−
1
n
(
R
n
(
x
))
=
x
. Let us now try with the next
value,
x
14:
>x:=14:
y := InvRabin(Rabin(x, n), op(rkey[2 .. 5]), BW = true):
igcd(x-y, n);
=
1
Again, we do not get a nontrivial factor of
n
. However, the situation is not exactly
the same as in the preceding attempt. There we obtained
y
=
x
because
x
was a
=
quadratic residue. In this attempt we see that
y
x
and hence the reason that no
=−
nontrivial factor was obtained is that
y
x
mod
n
. We can check that this is
indeed the case:
> -y mod n;
14
Let us make a further attempt with
x
=
15:
>x:=15;
y := InvRabin(Rabin(x, n), op(rkey[2 .. 5]), BW = true);
igcd(x-y, n);
1432104239533502582190206584922959879897681468268458233481122429999871892418707098\
37440435265693908870823815025795545972907790900609259306833574596025923008116062\
70432655121385588882401154001519909768170721943207004445883749592028332389151503\
2147060303617573395827409313919186027441499054928663931343845660507
Now, we have factored
n
at last. We see at a glance that the integer obtained as
output is smaller than
n
and we can check that it is really a (prime) factor of
n
:
> n mod %;
0
8.4.3 CCA Secure Rabin Encryption
In the case of RSA, the plain encryption scheme is completely insecure but there
are methods to turn it into a more secure encryption scheme, and we are going to
see that this is also the case with Rabin encryption. The Blum-Williams family is
trapdoor one-way under the assumption that factoring Blum integers is hard and, by
Theorem 3.9, the least significant bit is a hard-core predicate for this family. There
is a general method to build a CPA secure encryption scheme from such a family
with a hard-core predicate which is discussed, for example, in [109, 10.7.2]. For the
family
BW
n
with hard-core predicate
LSB
this construction is as follows:
•
Gen
: On input 1
k
run a PPT algorithm that generates two primes,
p
,
q
such that
len
(
p
)
=
len
(
q
)
=
k
and
p
≡
q
≡
3
(
mod 4
)
, compute
n
=
pq
and output the
=
=
(
,
)
public key
pk
n
and the private key
sk
p
q
.
