Initialize TMP to avoid confusion by static analysis.
[gnuk/gnuk.git] / src / mod.c
1 /*
2  * mod.c -- modulo arithmetic
3  *
4  * Copyright (C) 2011, 2014 Free Software Initiative of Japan
5  * Author: NIIBE Yutaka <gniibe@fsij.org>
6  *
7  * This file is a part of Gnuk, a GnuPG USB Token implementation.
8  *
9  * Gnuk is free software: you can redistribute it and/or modify it
10  * under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * Gnuk is distributed in the hope that it will be useful, but WITHOUT
15  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
17  * License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
21  *
22  */
23
24 #include <stdint.h>
25 #include <string.h>
26 #include "bn.h"
27
28 /**
29  * @brief X = A mod B (using MU=(1<<(256)+MU_lower)) (Barret reduction)
30  *
31  */
32 void
33 mod_reduce (bn256 *X, const bn512 *A, const bn256 *B, const bn256 *MU_lower)
34 {
35   bn256 q[1];
36   bn512 q_big[1], tmp[1];
37   uint32_t carry;
38 #define borrow carry
39
40   memset (q, 0, sizeof (bn256));
41   q->word[0] = A->word[15];
42   bn256_mul (tmp, q, MU_lower);
43   tmp->word[8] += A->word[15];
44   carry = (tmp->word[8] < A->word[15]);
45   tmp->word[9] += carry;
46
47   q->word[7] = A->word[14];
48   q->word[6] = A->word[13];
49   q->word[5] = A->word[12];
50   q->word[4] = A->word[11];
51   q->word[3] = A->word[10];
52   q->word[2] = A->word[9];
53   q->word[1] = A->word[8];
54   q->word[0] = A->word[7];
55   bn256_mul (q_big, q, MU_lower);
56   bn256_add ((bn256 *)&q_big->word[8], (bn256 *)&q_big->word[8], q);
57
58   q->word[0] = q_big->word[9] + tmp->word[1];
59   carry = (q->word[0] < tmp->word[1]);
60
61   q->word[1] = q_big->word[10] + carry;
62   carry = (q->word[1] < carry);
63   q->word[1] += tmp->word[2];
64   carry += (q->word[1] < tmp->word[2]);
65
66   q->word[2] = q_big->word[11] + carry;
67   carry = (q->word[2] < carry);
68   q->word[2] += tmp->word[3];
69   carry += (q->word[2] < tmp->word[3]);
70
71   q->word[3] = q_big->word[12] + carry;
72   carry = (q->word[3] < carry);
73   q->word[3] += tmp->word[4];
74   carry += (q->word[3] < tmp->word[4]);
75
76   q->word[4] = q_big->word[13] + carry;
77   carry = (q->word[4] < carry);
78   q->word[4] += tmp->word[5];
79   carry += (q->word[4] < tmp->word[5]);
80
81   q->word[5] = q_big->word[14] + carry;
82   carry = (q->word[5] < carry);
83   q->word[5] += tmp->word[6];
84   carry += (q->word[5] < tmp->word[6]);
85
86   q->word[6] = q_big->word[15] + carry;
87   carry = (q->word[6] < carry);
88   q->word[6] += tmp->word[7];
89   carry += (q->word[6] < tmp->word[7]);
90
91   q->word[7] = carry;
92   q->word[7] += tmp->word[8];
93   carry = (q->word[7] < tmp->word[8]);
94
95   memset (q_big, 0, sizeof (bn512));
96   q_big->word[8] = A->word[8];
97   q_big->word[7] = A->word[7];
98   q_big->word[6] = A->word[6];
99   q_big->word[5] = A->word[5];
100   q_big->word[4] = A->word[4];
101   q_big->word[3] = A->word[3];
102   q_big->word[2] = A->word[2];
103   q_big->word[1] = A->word[1];
104   q_big->word[0] = A->word[0];
105
106   bn256_mul (tmp, q, B);
107   tmp->word[8] += carry * B->word[0];
108   tmp->word[15] = tmp->word[14] = tmp->word[13] = tmp->word[12]
109     = tmp->word[11] = tmp->word[10] = tmp->word[9] = 0;
110
111   borrow = bn256_sub (X, (bn256 *)&q_big->word[0], (bn256 *)&tmp->word[0]);
112   q_big->word[8] -= borrow;
113   q_big->word[8] -= tmp->word[8];
114
115   carry = q_big->word[8];
116   if (carry)
117     carry -= bn256_sub (X, X, B);
118   else
119     bn256_sub (q, X, B);
120
121   if (carry)
122     bn256_sub (X, X, B);
123   else
124     bn256_sub (q, X, B);
125
126   borrow = bn256_sub (q, X, B);
127   if (borrow)
128     memcpy (q, X, sizeof (bn256));
129   else
130     memcpy (X, q, sizeof (bn256));
131 #undef borrow
132 }
133
134 /*
135  * Reference:
136  * Donald E. Knuth, The Art of Computer Programming, Vol. 2:
137  * Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998
138  *
139  * Max loop: X=0x8000...0000 and N=0xffff...ffff
140  */
141 #define MAX_GCD_STEPS_BN256 (3*256-2)
142
143 /**
144  * @brief C = X^(-1) mod N
145  *
146  * Assume X and N are co-prime (or N is prime).
147  * NOTE: If X==0, it return 0.
148  *
149  */
150 void
151 mod_inv (bn256 *C, const bn256 *X, const bn256 *N)
152 {
153   bn256 u[1], v[1], tmp[1];
154   bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
155   uint32_t carry;
156 #define borrow carry
157   int n = MAX_GCD_STEPS_BN256;
158
159   memset (tmp, 0, sizeof (bn256));
160   memset (C, 0, sizeof (bn256));
161   memcpy (u, X, sizeof (bn256));
162   memcpy (v, N, sizeof (bn256));
163
164   while (n--)
165     {
166       int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
167
168       switch (c)
169         {
170         case 3:
171           bn256_shift (u, u, -1);
172           if (bn256_is_even (A))
173             {
174               bn256_add (tmp, A, N);
175               carry = 0;
176             }
177           else
178             carry = bn256_add (A, A, N);
179
180           bn256_shift (A, A, -1);
181           A->word[7] |= carry * 0x80000000;
182
183           bn256_shift (v, v, -1);
184           if (bn256_is_even (C))
185             {
186               bn256_add (tmp, C, N);
187               carry = 0;
188             }
189           else
190             carry = bn256_add (C, C, N);
191
192           bn256_shift (C, C, -1);
193           C->word[7] |= carry * 0x80000000;
194
195           if (bn256_is_ge (tmp, tmp))
196             {
197               bn256_sub (tmp, tmp, tmp);
198               borrow = bn256_sub (tmp, tmp, tmp);
199               if (borrow)
200                 bn256_add (tmp, tmp, tmp);
201               else
202                 bn256_add (tmp, A, N);
203             }
204           else
205             {
206               bn256_sub (tmp, tmp, tmp);
207               borrow = bn256_sub (tmp, tmp, tmp);
208               if (borrow)
209                 bn256_add (tmp, tmp, tmp);
210               else
211                 bn256_add (tmp, tmp, N);
212             }
213           break;
214
215         case 1:
216           bn256_shift (tmp, tmp, -1);
217           if (bn256_is_even (tmp))
218             {
219               bn256_add (tmp, tmp, N);
220               carry = 0;
221             }
222           else
223             carry = bn256_add (tmp, tmp, N);
224
225           bn256_shift (tmp, tmp, -1);
226           tmp->word[7] |= carry * 0x80000000;
227
228           bn256_shift (v, v, -1);
229           if (bn256_is_even (C))
230             {
231               bn256_add (tmp, C, N);
232               carry = 0;
233             }
234           else
235             carry = bn256_add (C, C, N);
236
237           bn256_shift (C, C, -1);
238           C->word[7] |= carry * 0x80000000;
239
240           if (bn256_is_ge (tmp, tmp))
241             {
242               bn256_sub (tmp, tmp, tmp);
243               borrow = bn256_sub (tmp, tmp, tmp);
244               if (borrow)
245                 bn256_add (tmp, tmp, tmp);
246               else
247                 bn256_add (tmp, A, N);
248             }
249           else
250             {
251               bn256_sub (tmp, tmp, tmp);
252               borrow = bn256_sub (tmp, tmp, tmp);
253               if (borrow)
254                 bn256_add (tmp, tmp, tmp);
255               else
256                 bn256_add (tmp, tmp, N);
257             }
258           break;
259
260         case 2:
261           bn256_shift (u, u, -1);
262           if (bn256_is_even (A))
263             {
264               bn256_add (tmp, A, N);
265               carry = 0;
266             }
267           else
268             carry = bn256_add (A, A, N);
269
270           bn256_shift (A, A, -1);
271           A->word[7] |= carry * 0x80000000;
272
273           bn256_shift (tmp, tmp, -1);
274           if (bn256_is_even (tmp))
275             {
276               bn256_add (tmp, tmp, N);
277               carry = 0;
278             }
279           else
280             carry = bn256_add (tmp, tmp, N);
281
282           bn256_shift (tmp, tmp, -1);
283           tmp->word[7] |= carry * 0x80000000;
284
285           if (bn256_is_ge (tmp, tmp))
286             {
287               bn256_sub (tmp, tmp, tmp);
288               borrow = bn256_sub (tmp, tmp, tmp);
289               if (borrow)
290                 bn256_add (tmp, tmp, tmp);
291               else
292                 bn256_add (tmp, A, N);
293             }
294           else
295             {
296               bn256_sub (tmp, tmp, tmp);
297               borrow = bn256_sub (tmp, tmp, tmp);
298               if (borrow)
299                 bn256_add (tmp, tmp, tmp);
300               else
301                 bn256_add (tmp, tmp, N);
302             }
303           break;
304
305         case 0:
306           bn256_shift (tmp, tmp, -1);
307           if (bn256_is_even (tmp))
308             {
309               bn256_add (tmp, tmp, N);
310               carry = 0;
311             }
312           else
313             carry = bn256_add (tmp, tmp, N);
314
315           bn256_shift (tmp, tmp, -1);
316           tmp->word[7] |= carry * 0x80000000;
317
318           bn256_shift (tmp, tmp, -1);
319           if (bn256_is_even (tmp))
320             {
321               bn256_add (tmp, tmp, N);
322               carry = 0;
323             }
324           else
325             carry = bn256_add (tmp, tmp, N);
326
327           bn256_shift (tmp, tmp, -1);
328           tmp->word[7] |= carry * 0x80000000;
329
330           if (bn256_is_ge (u, v))
331             {
332               bn256_sub (u, u, v);
333               borrow = bn256_sub (A, A, C);
334               if (borrow)
335                 bn256_add (A, A, N);
336               else
337                 bn256_add (tmp, A, N);
338             }
339           else
340             {
341               bn256_sub (v, v, u);
342               borrow = bn256_sub (C, C, A);
343               if (borrow)
344                 bn256_add (C, C, N);
345               else
346                 bn256_add (tmp, C, N);
347             }
348           break;
349         }
350     }
351 #undef borrow
352 }