Cryptography Reference
In-Depth Information
Algorithm 8.7:
Vigilant's algorithm
Input
:
M
=
0
,
p
,
q
,
d
p
,
d
q
,
i
q
Output
:
M
d
mod
N
or
error
1
begin
2
Choose a 32-bit random integer
r
, four 64-bit random integers
R
1
,
R
2
,
R
3
and
R
4
;
p
∗
=
pr
2
M
mod
p
∗
;
,
M
p
=
3
p
−
1
mod
r
2
−
β
p
mod
p
∗
;
i
pr
=
,β
p
=
p
·
i
pr
and
α
p
=
1
4
M
p
=
α
p
M
p
+
β
p
(
1
+
r
)
mod
p
∗
;
5
M
p
if
=
M
mod
p
then
6
Return error
7
end
8
d
p
=
d
p
+
R
1
(
p
−
1
)
;
9
d
p
=
M
mod
p
∗
;
S
pr
10
p
if
d
p
=
d
p
mod
p
−
1
then
11
Return error
12
end
13
=
β
p
(
1
+
d
p
r
)
mod
p
∗
then
if
β
p
S
pr
14
Return error
15
end
16
S
p
=
d
p
r
S
pr
−
β
(
1
+
−
R
3
)
;
17
p
q
∗
=
qr
2
M
mod
q
∗
;
,
M
q
=
18
q
−
1
mod
r
2
q
mod
q
∗
;
i
qr
=
,β
=
q
·
i
qr
and
α
=
1
−
β
19
q
q
M
q
=
α
q
M
q
+
β
q
(
1
+
r
)
mod
q
∗
;
20
M
q
if
=
M
mod
q
then
21
Return error
22
end
23
if
M
p
mod
r
2
M
q
mod
r
2
=
then
24
Return error
25
end
26
d
q
=
d
q
+
R
2
(
q
−
1
)
;
27
d
q
=
M
mod
q
∗
;
S
qr
28
q
if
d
q
=
d
q
mod
q
−
1
then
29
Return error
30
end
31
if
β
q
S
qr
=
β
q
(
1
+
d
q
r
)
mod
q
∗
then
32
Return error
33
end
34
S
q
d
q
r
=
S
qr
−
β
(
1
+
−
R
4
)
;
35
q
S
=
S
q
+
q
(
i
q
(
S
p
−
S
q
)
mod
p
∗
)
;
36
N
=
pq
;
37
mod
Nr
2
if
N
[
S
−
R
4
−
q
·
i
q
(
R
3
−
R
4
)
] =
then
38
Return error
39
end
40
1mod
p
then
42
Return error
43
end
44
Return
S
mod
N
45
end
if
q
·
i
q
=
41
