1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
From 0e6788517eac6f508fa32ec5d5c1cada7fb980bc Mon Sep 17 00:00:00 2001
From: NIIBE Yutaka <gniibe@fsij.org>
Date: Sat, 24 Jun 2017 20:46:20 +0900
Subject: [PATCH 2/5] Same computation for square and multiply.
* mpi/mpi-pow.c (_gcry_mpi_powm): Compare msize for max_u_size. Move
the assignment to base_u into the loop. Copy content refered by RP to
BASE_U except the last of the loop.
--
Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
(backport from master commit:
78130828e9a140a9de4dafadbc844dbb64cb709a)
---
mpi/mpi-pow.c | 50 +++++++++++++++++++++++++++++---------------------
1 file changed, 29 insertions(+), 21 deletions(-)
diff --git a/mpi/mpi-pow.c b/mpi/mpi-pow.c
index 7b3dc318..3cba6903 100644
--- a/mpi/mpi-pow.c
+++ b/mpi/mpi-pow.c
@@ -573,6 +573,8 @@ _gcry_mpi_powm (gcry_mpi_t res,
MPN_COPY (precomp[i], rp, rsize);
}
+ if (msize > max_u_size)
+ max_u_size = msize;
base_u = mpi_alloc_limb_space (max_u_size, esec);
MPN_ZERO (base_u, max_u_size);
@@ -619,6 +621,10 @@ _gcry_mpi_powm (gcry_mpi_t res,
{
int c0;
mpi_limb_t e0;
+ struct gcry_mpi w, u;
+ w.sign = u.sign = 0;
+ w.flags = u.flags = 0;
+ w.d = base_u;
count_leading_zeros (c0, e);
e = (e << c0);
@@ -652,29 +658,31 @@ _gcry_mpi_powm (gcry_mpi_t res,
count_trailing_zeros (c0, e0);
e0 = (e0 >> c0) >> 1;
- /*
- * base_u <= precomp[e0]
- * base_u_size <= precomp_size[e0]
- */
- base_u_size = 0;
- for (k = 0; k < (1<< (W - 1)); k++)
- {
- struct gcry_mpi w, u;
- w.alloced = w.nlimbs = precomp_size[k];
- u.alloced = u.nlimbs = precomp_size[k];
- w.sign = u.sign = 0;
- w.flags = u.flags = 0;
- w.d = base_u;
- u.d = precomp[k];
-
- mpi_set_cond (&w, &u, k == e0);
- base_u_size |= ( precomp_size[k] & ((mpi_size_t)0 - (k == e0)) );
- }
-
for (j += W - c0; j >= 0; j--)
{
- mul_mod (xp, &xsize, rp, rsize,
- j == 0 ? base_u : rp, j == 0 ? base_u_size : rsize,
+
+ /*
+ * base_u <= precomp[e0]
+ * base_u_size <= precomp_size[e0]
+ */
+ base_u_size = 0;
+ for (k = 0; k < (1<< (W - 1)); k++)
+ {
+ w.alloced = w.nlimbs = precomp_size[k];
+ u.alloced = u.nlimbs = precomp_size[k];
+ u.d = precomp[k];
+
+ mpi_set_cond (&w, &u, k == e0);
+ base_u_size |= ( precomp_size[k] & (0UL - (k == e0)) );
+ }
+
+ w.alloced = w.nlimbs = rsize;
+ u.alloced = u.nlimbs = rsize;
+ u.d = rp;
+ mpi_set_cond (&w, &u, j != 0);
+ base_u_size ^= ((base_u_size ^ rsize) & (0UL - (j != 0)));
+
+ mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
mp, msize, &karactx);
tp = rp; rp = xp; xp = tp;
rsize = xsize;
--
2.11.0
|
