Cryptography Reference
In-Depth Information
y
q
qm
p
)
QR
n
and hence we set
m
:=
∈
QR
n
mod
n
belongs to
r
. Indeed, since
c
c
(
p
+
1
)/
4
mod
p
∈
QR
p
. Similarly,
m
q
is a quadratic residue modulo
q
, i.e.,
m
q
∈
QR
q
.Now,
r
obviously satisfies:
∈
QR
p
and hence
m
p
=
we have that
c
mod
p
r
≡
m
p
(
mod
p
)
r
≡
m
q
(
mod
q
)
and hence
r
∈
QR
n
by Proposition 2.14.
This leads to the following encryption scheme:
Definition 8.14
The
plain Rabin Encryption Scheme
is the public-key encryption
scheme
(
Gen
,
Enc
,
Dec
)
defined by the following algorithms:
Gen
: On input 1
k
•
run a PPT algorithm that generates two primes,
p
,
q
such that
len
(
p
)
=
len
(
q
)
=
k
and
p
≡
q
≡
3
(
mod 4
)
, compute
n
=
pq
and output the
public key
n
and the private key
(
p
,
q
)
.
•
Enc
: On input a public key
pk
=
n
and a message
m
∈
QR
n
, compute the
ciphertext:
m
2
mod
n
c
:=
Enc
(
pk
,
m
)
=
BW
n
(
m
)
=
∈
QR
n
.
•
Dec
: On input a private key
sk
=
(
p
,
q
)
and a ciphertext
c
∈
QR
n
, compute the
message:
BW
−
1
n
m
:=
Dec
(
sk
,
c
)
=
(
c
)
∈
QR
n
.
Remarks 8.10
There are other variants of plain Rabin encryption. For example, the
use of Blum primes is not strictly necessary and it merely simplifies things by making
the squaring function a permutation of
QR
n
and alsomakes decryptionmore efficient
because the computation of square roots modulo a prime
p
is simpler in case
p
is a
Blum prime. However, these roots can be computed in probabilistic polynomial time
even if
p
≡
1
(
mod 4
)
, as we have seen in Algorithm 2.8 (when
p
≡
1
(
mod 8
)
,no
deterministic polynomial-time algorithm is known for computing these roots).
Another possibility consists of taking
Z
n
as the plaintext space and encrypting
m
2
mod
n
(as with RSA encryption, we may safely assume that
m
∈ Z
n
as
c
=
∈ Z
n
, and hence
c
c
reveals
the private key and, on the other hand, this occurs with negligible probability if
m
is randomly chosen in
∈
QR
n
because otherwise if
c
=
0, then gcd
(
c
,
n
)
Z
n
). This has the inconvenience that, by Corollary 2.7,
Z
n
and only one of them is equal to the plaintext
m
.As
already mentioned, it is not a sound method to rely on semantic concepts such as
'meaningful' to determine
m
—after all,
m
might be a symmetric key which should
necessarily look random. The problem can be remedied by adding some redundancy
to
m
before encryption—such as a given bit string of sufficient length appended to
the message—so that the plaintext space actually becomes a sparse subset of
c
has four square roots in
Z
n
and
the probability that more than one square root of
c
belongs to this subset becomes
negligible.
