Cryptography Reference
In-Depth Information
2.
m
≡−
x
(mod
p
) and
m
≡−
x
(mod
q
): In this case,
m
=
n
−
x
and
gcd
(
m
−
x, n
)=1, and this is not useful to find a prime factor of
n
.
3.
m
≡
x
(mod
p
) and
m
≡−
x
(mod
q
): In this case,
p
divides
m
−
x
but
q
does not divide
m
−
x
. This is useful to find a prime factor of
n
. In fact,
p
=
gcd
(
m
−
x, n
).
4.
m
≡−
x
(mod
p
) and
m
≡
x
(mod
q
): In this case,
p
does not divide
m
−
x
but
q
divides
m
−
x
. Again, this is useful to find a prime factor of
n
. In fact,
q
=
gcd
(
m
−
x, n
)=
q
.
In summary, we have two cases that are useful to find a prime factor of
n
(i.e., cases 3 and 4) and two cases that are not (i.e., cases 1 and 2). Consequently,
the adversary can find a prime factor of
n
in each iteration of the algorithm with
a probability of 1
/
2.In
k
iterations, the prime factors of
n
can be found with a
probability of 1
(1
/
2)
k
, so we conclude that the adversary can can solve the IFP.
−
The outline of the proof may be better understood if one looks at a simple
example. Let
n
= 253 and
O
Rabin
the Rabin oracle that finds square roots modulo
253. The adversary randomly selects
x
=17and verifies that
gcd
(17
,
253) = 1.He
or she then computes
x
2
(mod
n
)
17
2
(mod 253) = 36
c
≡
≡
and
m
=
O
Rabin
(36)
.
The oracle returns one of the four square roots of 36 modulo 253 (i.e., 6, 17,
236, or 247). In two of the four cases, the adversary can determine a prime factor of
253. For 6 and 247, he or she gets
gcd
(6
−
17
,
253) = 11 and
gcd
(247
−
17
,
253) =
23. These are the prime factors of 253.
We mentioned earlier that one can add redundancy to the original plaintext
message prior to encryption for easy identification among the four possible square
roots and to simplify (or automate) the decryption process accordingly. Suppose
that the Rabin asymetric encryption system is modified this way. If the adversary
has access to a Rabin oracle
O
Rabin
that takes advantage of redundancy to always
select the correct plaintext message from the four square roots of a given ciphertext,
then he or she can no longer use
O
Rabin
to factorize
n
. This is because the oracle
