Cryptography Reference
In-Depth Information
KeyGen
(
κ
): Generate two random
κ/
2-bit primes
p
and
q
such that
p
≡
q
≡
3 (mod 4) and
set
N
=
pq
. Output the public key
pk
=
N
and the private key
sk
=
(
p,q
).
The message space and ciphertext space depend on the redundancy scheme (suppose for the
moment that they are
C
κ
=
M
κ
=
(
Z
/N
Z
)
∗
).
m
2
(mod
N
) (with some redundancy or padding scheme).
Decrypt
(
c
,
(
p,q
)): We want to compute
√
c
(mod
N
), and this is done by the following
method: compute
m
p
=
c
(
p
+
1)
/
4
(mod
p
)and
m
q
=
c
(
q
+
1)
/
4
(mod
q
) (see Section
2.9
). Test that
m
p
≡
c
(mod
p
)and
m
q
≡
c
(mod
q
), and if not then output
⊥
. Use the Chinese remainder
theorem (Exercise
2.6.3
) to obtain 4 possibilities for
m
(mod
N
) such that
m
≡±
m
p
(mod
p
)
and
m
≡±
m
q
(mod
q
). Use the redundancy (see later) to determine the correct value
m
and
return
⊥
if there is no such value.
=
Encrypt
(
m
,N
): Compute
c
Sign
(
m
,
(
p,q
)): Ensure that (
N
)
=
1 (possibly
by
adding some randomness). Then either
m
or
N
−
=
√
±
m
is a square modulo
N
. Compute
s
m
(mod
N
) by computing
±
m
)
(
p
+
1)
/
4
±
m
)
(
q
+
1)
/
4
(
(mod
p
), (
(mod
q
) and applying the Chinese remainder theorem.
Verify
(
m
,
s
,N
): Check whether
m
≡±
s
2
(mod
N
).
Box 24.2
Textbook Rabin
of
p,q
3 (mod 4) is to simplify the taking of square roots (and is also used in the
redundancy schemes below); the Rabin scheme can be used with other moduli.
≡
24.2.1 Redundancy schemes for unique decryption
To ensure that decryption returns the correct message it is necessary to have some redun-
dancy in the message, or else to send some extra bits. We now describe three solutions to
this problem.
Redundancy in the message for Rabin
: For example, insist that the least significant
l
bits (where
l>
2 is some known parameter) of the binary string
m
are all ones. (Note 8.14
of [
376
] suggests repeating the last
l
bits of the message.) If
l
is big enough then it is
unlikely that two different choices of square root would have the right pattern in the
l
bits.
A message
m
is encoded as
x
=
2
l
m
+
(2
l
−
1), and so the message space is
M
κ
=
m
<N/
2
l
,
gcd(
N,
2
l
m
(2
l
κ
−
l
−
2
). The
{
m
:1
≤
+
−
1))
=
1
}
(alternatively,
M
κ
={
0
,
1
}
x
2
(mod
N
). Decryption involves computing the four square roots of
c
.
If none, or more than one, of the roots corresponds to an element of
M
κ
then decryption
fails (return
ciphertext is
c
=
x/
2
l
.
This method is a natural choice, since some padding schemes for CCA security (such
as OAEP) already have sections of the message with a fixed pattern of bits.
Note that, since
N
is odd, the least significant bit of
N
⊥
). Otherwise output the message
m
=
−
x
is different to the least
significant bit of
x
. Hence, the
l
≥
1 least significant bits of
x
and
N
−
x
are never equal.
