Cryptography Reference
In-Depth Information
14.2.2.2
Encryption Algorithm
Similar to the RSA asymmetric encryption system, the Rabin system can be used
to encrypt and decrypt plaintext messages that represent numbers and elements of
Z
n
=
.
The Rabin
Encrypt
algorithm is deterministic. It takes as input a public key
n
and a plaintext message
m
{
0
,...,n
−
1
}
∈
Z
n
, and it generates as output the ciphertext
m
2
(mod
n
)
.
c
=Square
n
(
m
)
≡
The ciphertext
c
is then transmitted to the recipient. Note that the Rabin
Encrypt
algorithm takes only one modular squaring,
11
and hence it is extremely
efficient.
If, in our toy example, the plaintext message is
m
= 158, then the Rabin
Encrypt
algorithm computes
c
=
m
2
(mod
n
) = 158
2
(mod 253) = 170,andthe
resulting ciphertext
c
= 170 is sent to the recipient.
14.2.2.3
Decryption Algorithm
The Rabin
Decrypt
algorithm is also deterministic. It takes as input a private key
(
p, q
) and a ciphertext
c
, and it generates as output the square root of
c
representing
the plaintext message
m
. Note that the recipient can find a square root of
c
modulo
n
only if he or she knows the prime factors
p
and
q
of
n
(this property is proven
later). Also note that there is no single square root of
c
modulo
n
, but that there are
four of them. Let
m
1
,
m
2
,
m
3
,and
m
4
be the four square roots of
c
modulo
n
.The
recipient must then decide which
m
i
(1
≤
i
≤
4) to go with (i.e., which square root
represents the correct plaintext message). This ambiguity is a major disadvantage
of the Rabin asymmetric encryption system (both from a practical and theoretical
viewpoint).
Computing square roots modulo
n
is simple if
n
is a Blum integer (this is why
we have required that
n
is a Blum integer in the first place). In this case, one usually
first computes the square roots of
c
modulo
p
and
q
.Let
m
p
be the square roots of
c
modulo
p
and
m
q
be the square roots of
c
modulo
q
. According to (3.6),
m
p
and
m
q
can be computed as follows:
c
p
+1
m
p
=
(mod
p
)
4
11
By comparison, the RSA
Encrypt
algorithm with
e
=3takes one modular multiplication and one
modular squaring, and for larger
e
many more modular operations (i.e., multiplication or squaring)
must be performed.
