Cryptography Reference
In-Depth Information
Choose a random integer
x
such that (
N
)
2
z
2
=−
1, e.g., let
x
=±
(mod
N
) for ran-
x
2
(mod
N
) and call
A
on (
N,
c
). The oracle computes the
unique even integer 1
<x
<N
such that (
x
)
2
)
∗
. Set
c
dom
z
∈
(
Z
/N
Z
=
c
(mod
N
) and (
x
N
)
≡
=
1. The oracle then
attempts to decode
x
to obtain the message. If 8
x
(which happens with probability 3
/
4)
then decoding succeeds and the corresponding message
m
is output by the oracle. Given
m
we can recover the value
x
as 2(2
m
1), depending on the value of (
2
m
+
1
N
+
1) or 4(2
m
+
),
and then factor
N
as gcd(
x
−
x,N
).
c
2
−
4
(mod
N
) and call the oracle
on
c
. The even integer
x
computed by the oracle is equal to
x
/
4 and so the above argument
may apply. In extremely rare cases one might have to repeat the process
x
then the oracle outputs
so we compute
c
=
If 8
|
⊥
1
2
log
2
(
N
) times,
but the expected number of trials is constant.
Exercise 24.2.16
Prove Theorem
24.2.14
.
κ
−
l
−
2
.
Exercise 24.2.17
Prove Theorem
24.2.13
when the message space is
{
0
,
1
}
The above theorems show that the hardness guarantee for the Rabin cryptosystem is
often stronger than for the RSA cryptosystem (at least, under passive attacks). Hence,
the Rabin cryptosystem is very attractive: it has faster public operations and also has a
stronger security guarantee than RSA. On the other hand, the ideas used in the proofs of
these theorems can also be used to give adaptive (CCA) attacks on the Rabin scheme that
allow the attacker to determine the private key (i.e., the factorisation of the modulus). In
comparison, a CCA attack on textbook RSA only decrypts a single message rather than
learns the private key.
Example 24.2.18
We describe a CCA attacker giving a total break of Rabin with “redun-
dancy in the message”.
As in the proof of Theorem
24.2.13
, the adversary chooses a random
x
∈ Z
N
such that
neither
x
nor
N
−
x
satisfy the redundancy scheme (i.e., the
l
least significant bits are not
x
2
(mod
N
) and call the decryption oracle on
c
. The oracle answers with
either a message
m
or
all 1). Set
c
=
.Given
m
one computes
x
such that gcd(
x
−
⊥
x,N
) splits
N
.
Exercise 24.2.19
Give CCA attacks giving a total break of Rabin when using the other two
redundancy schemes (“extra bits” and Williams).
As we have seen, the method to prove that Rabin encryption has one-way security under
a passive attack is also the method to give a CCA attack on Rabin encryption. It was
remarked by Williams [
566
] that such a phenomenon seems to be inevitable. This remark
has been formalised and discussed in detail by Paillier and Villar [
427
].
Exercise 24.2.20
Generalise Rabin encryption to
N
=
pq
where
p
≡
q
≡
1(mod3)and
m
3
(mod
N
). How can one specify redundancy? Is the security related to
factoring in this case?
encryption is
c
=
