Cryptography Reference
In-Depth Information
One
can
therefore
send
u
i
as
the
signature.
Verification
is
to
compute
w
=
u
i
H
(
m
)(mod
N
) and check that
w
is a perfect square in
±
(e.g., using the method of
Exercise
2.4.9
or by computing an approximation to the square root). Part 6 of Lemma
2.3.3
states
Z
<
√
N
. Hence, this approach compresses the signature to
|
r
i
−
1
u
i
|≤
N
and so
|
u
i
|
half the size.
24.2.3 Security of textbook Rabin
Since the Rabin cryptosystem involves squaring it is natural to assume the security is related
to computing square roots modulo
N
, which in turn is equivalent to factoring. Hence, an
important feature of Rabin compared with RSA is that the hardness of breaking Rabin can
be shown to be equivalent to factoring.
Definition 24.2.10
Let
S
= N
or
S
={
pq
:
p,q
≡
3(mod4)
,
primes
}
. The computa-
tional problem
SQRT-MOD-N
is: given
N
∈
S
and
y
∈ Z
/N
Z
to output
⊥
if
y
is not a
square modulo
N
, or a solution
x
to
x
2
≡
y
(mod
N
).
Lemma 24.2.11
SQRT-MOD-N is equivalent to FACTOR.
Proof
Suppose we have a FACTOR oracle and are given a pair (
N,y
). Then one can use the
oracle to factor
N
and then solve SQRT-MOD-N using square roots modulo
p
and Hensel
lifting and the Chinese remainder theorem. This reduction is polynomial-time.
Conversely, suppose we have a SQRT-MOD-N oracle
A
and let
N
be given. First, if
p
e
then we can factor
N
in polynomial-time (see Exercise
2.2.7
). Hence, we may now
assume that
N
has at least two distinct prime factors.
Choose a random
x
N
=
∈ Z
N
and set
y
x
2
(mod
N
). Call
A
on
y
to get
x
.Wehave
x
2
≡
(
x
)
2
(mod
N
) and there are at least four possible solutions
x
. All but two of these solutions
will give a non-trivial value of gcd(
x
=
x
,N
). Hence, since
x
was chosen randomly, there
is probability at least 1/2 that we can split
N
. Repeating this process splits
N
(the expected
number of trials is at most 2). As in Lemma
24.1.14
, one can repeat the process to factor
N
in
O
(log(
N
)) iterations. The entire reduction is therefore polynomial-time.
−
An important remark about the above proof is that the oracle
A
is not assumed to output
a random square root
x
of
y
. Indeed,
A
could be deterministic. The randomness comes
from the choice of
x
in the reduction.
∈ Z
N
Exercise 24.2.12
Consider the computational problem FOURTH-ROOT: given
y
compute a solution to
x
4
y
(mod
N
) if such a solution exists. Give reductions that show
that FOURTH-ROOT is equivalent to FACTOR in the case
N
≡
=
pq
with
p,q
distinct odd
primes.
It is intuitively clear that any algorithm that breaks the one-way encryption property
(or selective signature forgery) of Rabin under passive attacks must compute square roots
modulo
N
. We have seen that SQRT-MOD-N is equivalent to FACTOR. Thus we expect
