Cryptography Reference
In-Depth Information
x
2
mod
n
.
•
The family of Rabin functions
R
n
, where
R
n
(
)
=
x
Associated with a security parameter 1
k
, two parameters
s
0
,
s
1
such that if
l
•
=
k
−
s
0
−
s
1
, we have that
l
+
s
0
≤
k
/
2. Typical values for these parameters,
mentioned in [34], are
k
384, although larger values
may be used for added security as in the Maple implementation we give below.
=
1024,
s
0
=
128 and
l
=
l
. Note that
l
•
The plaintext space is
384 is sufficient for the most common
usage of a scheme like this one, which is to encrypt symmetric keys that typically
have 256 bits or less.
{
0
,
1
}
=
s
0
.Asinthe
case of OAEP, these functions are modeled as independent random oracles in the
security analysis of the scheme and in practice they will be derived from a hash
function such as SHA-256.
l
+
s
1
s
0
,
H
s
1
l
+
•
Two functions
G
:{
0
,
1
}
→{
0
,
1
}
:{
0
,
1
}
→{
0
,
1
}
Definition 8.15
Rabin-SAEP
+
is the public encryption scheme
(
Gen
,
Enc
,
Dec
)
,
with these algorithms defined as follows:
Gen
: On input 1
k
, with
k
even, a modulus
n
•
=
pq
is computed, where
p
and
q
k
2
k
+
1
2
k
+
1
2
k
are
-bit
integer whose two most significant bits are '10'. The output of
Gen
is the public
key
n
and the private key
(
2
+
1
)
-bit Blum primes and
n
∈[
,
+
)
, i.e.,
n
is a
(
k
+
2
)
(
,
)
p
q
.
l
and the public key
n
, the following values
•
∈{
,
}
Enc
: Given the message
m
0
1
are successively computed:
s
1
(
r
is a randomly chosen bit string of length
s
1
).
1.
r
←{
0
,
1
}
s
0
.
2.
t
:=
G
(
m
||
r
)
∈{
0
,
1
}
l
+
s
0
.
3.
v
:=
m
||
t
∈{
0
,
1
}
l
+
s
0
.
4.
x
:=
v
⊕
H
(
r
)
∈{
0
,
1
}
k
.
5.
y
:=
x
||
r
∈{
0
,
1
}
y
2
mod
n
6.
c
Z
n
given by its
binary representation, and encrypted with the Rabin function using the public
key. In particular, as an integer,
y
:=
∈ Z
n
(Here,
y
is regarded as a
k
-bit element of
2
k
<
<
n
/
2. The resulting ciphertext
c
∈ Z
n
may also be regarded as a bit string of length
k
2 completing with zeros on the
left if necessary). The output of
Enc
is the ciphertext
c
.
+
•
Dec
: Given the ciphertext
c
∈ Z
n
and the private key
(
p
,
q
)
, the following steps
are performed:
c
(
p
+
1
)
4
mod
p
and
m
q
c
(
q
+
1
)
4
mod
q
which, as explained in
1. Compute
m
p
:=
:=
Z
p
and
Z
q
, respectively.
Algorithm 8.3, are square roots of
c
in
2. Check that
m
p
≡
and that
m
q
(
)
≡
(
)
. If either condition does
not hold then
c
is not a quadratic residue modulo
n
and it is rejected as an invalid
ciphertext.
3. Use the Chinese remainder theorem as in Algorithm 8.3 to compute the four
square roots of
c
in
c
mod
p
c
mod
q
Z
n
,say
{±
y
1
,
±
y
2
}
. Two of these square roots are greater
than
n
y
2
be the two
remaining square roots. We know that the plaintext is a
k
-bit integer so if none of
/
2 and hence they are discarded (since
y
<
k
/
2). Let
y
1
,
