Cryptography Reference
In-Depth Information
over RSA). The Rabin cryptosystem with the Williams padding is sometimes called the
Rabin-Williams cryptosystem
.
Exercise 24.2.4
Prove all the unproved claims in the above discussion of the Williams
redundancy scheme.
(2
59
21)(2
20
Exercise 24.2.5
7). The three ciphertexts below are Rabin
encryptions for each of the three redundancy schemes above (in the first case,
l
Let
N
=
+
+
=
5).
Determine the corresponding message in each case.
273067682422
,
(309135051204
,
−
1
,
0)
,
17521752799
.
Exercise 24.2.6
(Freeman-Goldreich-Kiltz-Rosen-Segev) This is a variant of the “extra
bits” method. Let
N
be a Williams integer. Let
u
1
=−
1 and
u
2
=
2. To encrypt message
)
∗
one first determines the bits
b
1
and
b
2
of the “extra bits” redundancy scheme
∈
(
Z
/N
Z
m
1 if and only if (
m
(i.e.,
b
1
=
N
)
=+
1 and
b
2
is the least significant bit of
m
). Compute the
ciphertext
m
2
u
1
−
b
1
1
u
b
2
=
(mod
N
)
.
c
Show how a user who knows
p
and
q
can decrypt the ciphertext. Show that this scheme still
leaks the least significant bit of
m
(and hence is still not IND-CPA secure), but no longer
leaks (
N
).
24.2.2 Variants of Rabin
In terms of computational performance, Rabin encryption is extremely fast (as long as
encryption does not require Jacobi symbols) while decryption, using the Chinese remainder
theorem, is roughly the same speed as RSA decryption.
Exercise 24.2.7
Describe and analyse the Rabin cryptosystem using moduli of the form
N
pqr
where
p
,
q
and
r
are distinct primes. What are the advantages and disadvantages
of Rabin in this setting?
=
Exercise 24.2.8
(Takagi-Rabin) Describe and analyse the Rabin cryptosystem using mod-
uli of the form
N
=
p
r
q
s
(
r
=
s
). Is there any advantage from using Rabin in this setting?
We now discuss compression of Rabin signatures. For further discussion of these ideas,
and an alternative method, see Gentry [
230
].
Example 24.2.9
(Bleichenbacher) Suppose
s
is a Rabin signature on a message
m
, so that
s
2
H
(
m
)(mod
N
). To compress
s
to half the size one uses the Euclidean algorithm on
(
s
,N
) to compute a sequ
en
ce of values
r
i
,u
i
,v
i
∈ Z
≡±
such that
r
i
=
u
i
s
+
v
i
N
.Let
i
be the
<
√
N<
index such that
|
r
i
|
|
r
i
−
1
|
. Then
r
i
≡
u
i
s
(mod
N
) and so
r
i
≡
u
i
s
2
u
i
H
(
m
)(mod
N
)
.
≡±
