Cryptography Reference
In-Depth Information
c
q
+1
m
q
(mod
q
)
=
4
It can easily be verified that
m
p
≡
c
(
p
+1)
/
2
m
p
+1
m
φ
(
n
)
m
2
m
2
≡
≡
≡
≡
c
(mod
p
)
and
m
q
≡
c
(
q
+1)
/
2
m
q
+1
m
φ
(
n
)
m
2
m
2
≡
≡
≡
≡
c
(mod
q
)
.
Consequently,
±
m
p
are the two square roots of
c
in
Z
p
,and
±
m
q
are the two
square roots of
c
in
Z
q
. There is a total of four possibilities to combine
±
m
p
and
±
m
q
, and these possibilities result in four different systems with two congruence
relations each. The systems are as follows:
1)
m
1
≡
+
m
p
(mod
p
)
m
1
≡
+
m
q
(mod
q
)
2)
m
2
≡−
m
p
(mod
p
)
m
2
≡−
m
q
(mod
q
)
3)
m
3
≡
+
m
p
(mod
p
)
m
3
≡−
m
q
(mod
q
)
4)
m
4
≡−
m
p
(mod
p
)
m
4
≡
+
m
q
(mod
q
)
Each system yields a possible square root of
c
modulo
n
, and we use
m
1
,m
2
,m
3
,and
m
4
to refer to them. Note that only one solution
m
i
(
i
=1
,
2
,
3
,
or 4) represents the original plaintext message
m
. To determine this message, it is
necessary to solve the four congruence relation systems and to select one of the
corresponding solutions (i.e.,
m
1
,
m
2
,
m
3
,or
m
4
).
