Cryptography Reference
In-Depth Information
The simplest way to find the four solutions is to use the CRA as introduced
in Section 3.3.3. First, one uses the extended Euclid algorithm to compute
y
p
≡
p
−
1
(mod
q
) and
y
q
≡
q
−
1
(mod
p
). These computations do not depend on the
plaintext message or ciphertext. They only depend on the prime factorization of
n
,
and hence they can be done once and for all during the key generation process. Using
y
p
and
y
q
, one can then compute the following values
r
and
s
:
r
=
y
p
pm
q
+
y
q
qm
p
(mod
n
)
s
=
y
p
pm
q
−
y
q
qm
p
(mod
n
)
s
. They represent the four
possible solutions
m
1
,
m
2
,
m
3
,and
m
4
. It is now up to the recipient to decide
which solution is the correct one (i.e., which solution represents the correct plaintext
message).
In our toy example, the recipient gets the ciphertext
c
= 170 and wants to
decrypt it with the public key (
p, q
)=(11
,
23). He or she therefore computes
y
p
=
The four square roots of
c
in
Z
n
are
±
r
and
±
−
2 and
y
q
=1, and computes the square roots
m
p
and
m
q
as follows:
c
(
p
+1)
/
4
(mod
p
)=
c
3
(mod 11) = 4
m
p
=
c
(
q
+1)
/
4
(mod
q
)=
c
6
(mod 23) = 3
m
q
=
Using these values, the recipient can determine
r
and
s
:
r
=
y
p
pm
q
+
y
q
qm
p
(mod
n
)=
−
2
·
11
·
3+1
·
23
·
4(mod
n
)=26
s
=
y
p
pm
q
−
y
q
qm
p
(mod
n
)=
−
2
·
11
·
3
−
1
·
23
·
4(mod
n
)=95
Consequently, the square roots of
c
= 170 modulo 253 are 26, 95, 158, and
227, and one of these values must be the correct plaintext message (in this example
it is 158).
An obvious drawback of the Rabin asymmetric encryption system is that the
recipient must select the correct plaintext message
m
from four possible values.
This ambiguity in decryption can be overcome by adding redundancy to the original
plaintext message prior to encryption. Then, with high probability, exactly one of
the four square roots of
c
modulo
n
possesses this redundancy, and the recipient
can easily (and automatically) select this value to represent the original plaintext
message.
