Coverage Report

Created: 2023-09-25 06:08

/src/dropbear/libtommath/bn_s_mp_exptmod.c
Line
Count
Source (jump to first uncovered line)
1
#include "tommath_private.h"
2
#ifdef BN_S_MP_EXPTMOD_C
3
/* LibTomMath, multiple-precision integer library -- Tom St Denis */
4
/* SPDX-License-Identifier: Unlicense */
5
6
#ifdef MP_LOW_MEM
7
#   define TAB_SIZE 32
8
#   define MAX_WINSIZE 5
9
#else
10
#   define TAB_SIZE 256
11
465
#   define MAX_WINSIZE 0
12
#endif
13
14
mp_err s_mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y, int redmode)
15
465
{
16
465
   mp_int  M[TAB_SIZE], res, mu;
17
465
   mp_digit buf;
18
465
   mp_err   err;
19
465
   int      bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
20
465
   mp_err(*redux)(mp_int *x, const mp_int *m, const mp_int *mu);
21
22
   /* find window size */
23
465
   x = mp_count_bits(X);
24
465
   if (x <= 7) {
25
126
      winsize = 2;
26
339
   } else if (x <= 36) {
27
51
      winsize = 3;
28
288
   } else if (x <= 140) {
29
159
      winsize = 4;
30
159
   } else if (x <= 450) {
31
129
      winsize = 5;
32
129
   } else if (x <= 1303) {
33
0
      winsize = 6;
34
0
   } else if (x <= 3529) {
35
0
      winsize = 7;
36
0
   } else {
37
0
      winsize = 8;
38
0
   }
39
40
465
   winsize = MAX_WINSIZE ? MP_MIN(MAX_WINSIZE, winsize) : winsize;
41
42
   /* init M array */
43
   /* init first cell */
44
465
   if ((err = mp_init(&M[1])) != MP_OKAY) {
45
0
      return err;
46
0
   }
47
48
   /* now init the second half of the array */
49
4.25k
   for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
50
3.79k
      if ((err = mp_init(&M[x])) != MP_OKAY) {
51
0
         for (y = 1<<(winsize-1); y < x; y++) {
52
0
            mp_clear(&M[y]);
53
0
         }
54
0
         mp_clear(&M[1]);
55
0
         return err;
56
0
      }
57
3.79k
   }
58
59
   /* create mu, used for Barrett reduction */
60
465
   if ((err = mp_init(&mu)) != MP_OKAY)                           goto LBL_M;
61
62
465
   if (redmode == 0) {
63
335
      if ((err = mp_reduce_setup(&mu, P)) != MP_OKAY)             goto LBL_MU;
64
335
      redux = mp_reduce;
65
335
   } else {
66
130
      if ((err = mp_reduce_2k_setup_l(P, &mu)) != MP_OKAY)        goto LBL_MU;
67
130
      redux = mp_reduce_2k_l;
68
130
   }
69
70
   /* create M table
71
    *
72
    * The M table contains powers of the base,
73
    * e.g. M[x] = G**x mod P
74
    *
75
    * The first half of the table is not
76
    * computed though accept for M[0] and M[1]
77
    */
78
465
   if ((err = mp_mod(G, P, &M[1])) != MP_OKAY)                    goto LBL_MU;
79
80
   /* compute the value at M[1<<(winsize-1)] by squaring
81
    * M[1] (winsize-1) times
82
    */
83
465
   if ((err = mp_copy(&M[1], &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU;
84
85
1.68k
   for (x = 0; x < (winsize - 1); x++) {
86
      /* square it */
87
1.22k
      if ((err = mp_sqr(&M[(size_t)1 << (winsize - 1)],
88
1.22k
                        &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU;
89
90
      /* reduce modulo P */
91
1.22k
      if ((err = redux(&M[(size_t)1 << (winsize - 1)], P, &mu)) != MP_OKAY) goto LBL_MU;
92
1.22k
   }
93
94
   /* create upper table, that is M[x] = M[x-1] * M[1] (mod P)
95
    * for x = (2**(winsize - 1) + 1) to (2**winsize - 1)
96
    */
97
3.79k
   for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
98
3.32k
      if ((err = mp_mul(&M[x - 1], &M[1], &M[x])) != MP_OKAY)     goto LBL_MU;
99
3.32k
      if ((err = redux(&M[x], P, &mu)) != MP_OKAY)                goto LBL_MU;
100
3.32k
   }
101
102
   /* setup result */
103
465
   if ((err = mp_init(&res)) != MP_OKAY)                          goto LBL_MU;
104
465
   mp_set(&res, 1uL);
105
106
   /* set initial mode and bit cnt */
107
465
   mode   = 0;
108
465
   bitcnt = 1;
109
465
   buf    = 0;
110
465
   digidx = X->used - 1;
111
465
   bitcpy = 0;
112
465
   bitbuf = 0;
113
114
39.1k
   for (;;) {
115
      /* grab next digit as required */
116
39.1k
      if (--bitcnt == 0) {
117
         /* if digidx == -1 we are out of digits */
118
1.10k
         if (digidx == -1) {
119
465
            break;
120
465
         }
121
         /* read next digit and reset the bitcnt */
122
644
         buf    = X->dp[digidx--];
123
644
         bitcnt = (int)MP_DIGIT_BIT;
124
644
      }
125
126
      /* grab the next msb from the exponent */
127
38.6k
      y     = (buf >> (mp_digit)(MP_DIGIT_BIT - 1)) & 1uL;
128
38.6k
      buf <<= (mp_digit)1;
129
130
      /* if the bit is zero and mode == 0 then we ignore it
131
       * These represent the leading zero bits before the first 1 bit
132
       * in the exponent.  Technically this opt is not required but it
133
       * does lower the # of trivial squaring/reductions used
134
       */
135
38.6k
      if ((mode == 0) && (y == 0)) {
136
7.86k
         continue;
137
7.86k
      }
138
139
      /* if the bit is zero and mode == 1 then we square */
140
30.7k
      if ((mode == 1) && (y == 0)) {
141
8.44k
         if ((err = mp_sqr(&res, &res)) != MP_OKAY)               goto LBL_RES;
142
8.44k
         if ((err = redux(&res, P, &mu)) != MP_OKAY)              goto LBL_RES;
143
8.44k
         continue;
144
8.44k
      }
145
146
      /* else we add it to the window */
147
22.3k
      bitbuf |= (y << (winsize - ++bitcpy));
148
22.3k
      mode    = 2;
149
150
22.3k
      if (bitcpy == winsize) {
151
         /* ok window is filled so square as required and multiply  */
152
         /* square first */
153
26.5k
         for (x = 0; x < winsize; x++) {
154
21.8k
            if ((err = mp_sqr(&res, &res)) != MP_OKAY)            goto LBL_RES;
155
21.8k
            if ((err = redux(&res, P, &mu)) != MP_OKAY)           goto LBL_RES;
156
21.8k
         }
157
158
         /* then multiply */
159
4.70k
         if ((err = mp_mul(&res, &M[bitbuf], &res)) != MP_OKAY)  goto LBL_RES;
160
4.70k
         if ((err = redux(&res, P, &mu)) != MP_OKAY)             goto LBL_RES;
161
162
         /* empty window and reset */
163
4.70k
         bitcpy = 0;
164
4.70k
         bitbuf = 0;
165
4.70k
         mode   = 1;
166
4.70k
      }
167
22.3k
   }
168
169
   /* if bits remain then square/multiply */
170
465
   if ((mode == 2) && (bitcpy > 0)) {
171
      /* square then multiply if the bit is set */
172
666
      for (x = 0; x < bitcpy; x++) {
173
459
         if ((err = mp_sqr(&res, &res)) != MP_OKAY)               goto LBL_RES;
174
459
         if ((err = redux(&res, P, &mu)) != MP_OKAY)              goto LBL_RES;
175
176
459
         bitbuf <<= 1;
177
459
         if ((bitbuf & (1 << winsize)) != 0) {
178
            /* then multiply */
179
359
            if ((err = mp_mul(&res, &M[1], &res)) != MP_OKAY)     goto LBL_RES;
180
359
            if ((err = redux(&res, P, &mu)) != MP_OKAY)           goto LBL_RES;
181
359
         }
182
459
      }
183
207
   }
184
185
465
   mp_exch(&res, Y);
186
465
   err = MP_OKAY;
187
465
LBL_RES:
188
465
   mp_clear(&res);
189
465
LBL_MU:
190
465
   mp_clear(&mu);
191
465
LBL_M:
192
465
   mp_clear(&M[1]);
193
4.25k
   for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
194
3.79k
      mp_clear(&M[x]);
195
3.79k
   }
196
465
   return err;
197
465
}
198
#endif