Add ST_DONGLE and ST_NUCLEO_F103
[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   uint32_t borrow_next;
40
41   memset (q, 0, sizeof (bn256));
42   q->word[0] = A->word[15];
43   bn256_mul (tmp, q, MU_lower);
44   tmp->word[8] += A->word[15];
45   carry = (tmp->word[8] < A->word[15]);
46   tmp->word[9] += carry;
47
48   q->word[7] = A->word[14];
49   q->word[6] = A->word[13];
50   q->word[5] = A->word[12];
51   q->word[4] = A->word[11];
52   q->word[3] = A->word[10];
53   q->word[2] = A->word[9];
54   q->word[1] = A->word[8];
55   q->word[0] = A->word[7];
56   bn256_mul (q_big, q, MU_lower);
57   bn256_add ((bn256 *)&q_big->word[8], (bn256 *)&q_big->word[8], q);
58
59   q->word[0] = q_big->word[9] + tmp->word[1];
60   carry = (q->word[0] < tmp->word[1]);
61
62   q->word[1] = q_big->word[10] + carry;
63   carry = (q->word[1] < carry);
64   q->word[1] += tmp->word[2];
65   carry += (q->word[1] < tmp->word[2]);
66
67   q->word[2] = q_big->word[11] + carry;
68   carry = (q->word[2] < carry);
69   q->word[2] += tmp->word[3];
70   carry += (q->word[2] < tmp->word[3]);
71
72   q->word[3] = q_big->word[12] + carry;
73   carry = (q->word[3] < carry);
74   q->word[3] += tmp->word[4];
75   carry += (q->word[3] < tmp->word[4]);
76
77   q->word[4] = q_big->word[13] + carry;
78   carry = (q->word[4] < carry);
79   q->word[4] += tmp->word[5];
80   carry += (q->word[4] < tmp->word[5]);
81
82   q->word[5] = q_big->word[14] + carry;
83   carry = (q->word[5] < carry);
84   q->word[5] += tmp->word[6];
85   carry += (q->word[5] < tmp->word[6]);
86
87   q->word[6] = q_big->word[15] + carry;
88   carry = (q->word[6] < carry);
89   q->word[6] += tmp->word[7];
90   carry += (q->word[6] < tmp->word[7]);
91
92   q->word[7] = carry;
93   q->word[7] += tmp->word[8];
94   carry = (q->word[7] < tmp->word[8]);
95
96   memset (q_big, 0, sizeof (bn512));
97   q_big->word[8] = A->word[8];
98   q_big->word[7] = A->word[7];
99   q_big->word[6] = A->word[6];
100   q_big->word[5] = A->word[5];
101   q_big->word[4] = A->word[4];
102   q_big->word[3] = A->word[3];
103   q_big->word[2] = A->word[2];
104   q_big->word[1] = A->word[1];
105   q_big->word[0] = A->word[0];
106
107   bn256_mul (tmp, q, B);
108   tmp->word[8] += carry * B->word[0];
109   tmp->word[15] = tmp->word[14] = tmp->word[13] = tmp->word[12]
110     = tmp->word[11] = tmp->word[10] = tmp->word[9] = 0;
111
112   borrow = bn256_sub (X, (bn256 *)&q_big->word[0], (bn256 *)&tmp->word[0]);
113   borrow_next = (q_big->word[8] < borrow);
114   q_big->word[8] -= borrow;
115   borrow_next += (q_big->word[8] < tmp->word[8]);
116   q_big->word[8] -= tmp->word[8];
117
118   carry = q_big->word[8];
119   if (carry)
120     carry -= bn256_sub (X, X, B);
121   else
122     bn256_sub (q, X, B);
123
124   if (carry)
125     carry -= bn256_sub (X, X, B);
126   else
127     bn256_sub (q, X, B);
128
129   borrow = bn256_sub (q, X, B);
130   if (borrow)
131     memcpy (q, X, sizeof (bn256));
132   else
133     memcpy (X, q, sizeof (bn256));
134 #undef borrow
135 }
136
137 /*
138  * Reference:
139  * Donald E. Knuth, The Art of Computer Programming, Vol. 2:
140  * Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998
141  *
142  * Max loop: X=0x8000...0000 and N=0xffff...ffff
143  */
144 #define MAX_GCD_STEPS_BN256 (3*256-2)
145
146 /**
147  * @brief C = X^(-1) mod N
148  * 
149  * Assume X and N are co-prime (or N is prime).
150  * NOTE: If X==0, it return 0.
151  *
152  */
153 void
154 mod_inv (bn256 *C, const bn256 *X, const bn256 *N)
155 {
156   bn256 u[1], v[1], tmp[1];
157   bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
158   uint32_t carry;
159 #define borrow carry
160   int n = MAX_GCD_STEPS_BN256;
161
162   memset (C, 0, sizeof (bn256));
163   memcpy (u, X, sizeof (bn256));
164   memcpy (v, N, sizeof (bn256));
165
166   while (n--)
167     {
168       int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
169
170       switch (c)
171         {
172         case 3:
173           bn256_shift (u, u, -1);
174           if (bn256_is_even (A))
175             {
176               bn256_add (tmp, A, N);
177               carry = 0;
178             }
179           else
180             carry = bn256_add (A, A, N);
181
182           bn256_shift (A, A, -1);
183           A->word[7] |= carry * 0x80000000;
184
185           bn256_shift (v, v, -1);
186           if (bn256_is_even (C))
187             {
188               bn256_add (tmp, C, N);
189               carry = 0;
190             }
191           else
192             carry = bn256_add (C, C, N);
193
194           bn256_shift (C, C, -1);
195           C->word[7] |= carry * 0x80000000;
196
197           if (bn256_is_ge (tmp, tmp))
198             {
199               bn256_sub (tmp, tmp, tmp);
200               borrow = bn256_sub (tmp, tmp, tmp);
201               if (borrow)
202                 bn256_add (tmp, tmp, tmp);
203               else
204                 bn256_add (tmp, A, N);
205             }
206           else
207             {
208               bn256_sub (tmp, tmp, tmp);
209               borrow = bn256_sub (tmp, tmp, tmp);
210               if (borrow)
211                 bn256_add (tmp, tmp, tmp);
212               else
213                 bn256_add (tmp, tmp, N);
214             }
215           break;
216
217         case 1:
218           bn256_shift (tmp, tmp, -1);
219           if (bn256_is_even (tmp))
220             {
221               bn256_add (tmp, tmp, N);
222               carry = 0;
223             }
224           else
225             carry = bn256_add (tmp, tmp, N);
226
227           bn256_shift (tmp, tmp, -1);
228           tmp->word[7] |= carry * 0x80000000;
229
230           bn256_shift (v, v, -1);
231           if (bn256_is_even (C))
232             {
233               bn256_add (tmp, C, N);
234               carry = 0;
235             }
236           else
237             carry = bn256_add (C, C, N);
238
239           bn256_shift (C, C, -1);
240           C->word[7] |= carry * 0x80000000;
241
242           if (bn256_is_ge (tmp, tmp))
243             {
244               bn256_sub (tmp, tmp, tmp);
245               borrow = bn256_sub (tmp, tmp, tmp);
246               if (borrow)
247                 bn256_add (tmp, tmp, tmp);
248               else
249                 bn256_add (tmp, A, N);
250             }
251           else
252             {
253               bn256_sub (tmp, tmp, tmp);
254               borrow = bn256_sub (tmp, tmp, tmp);
255               if (borrow)
256                 bn256_add (tmp, tmp, tmp);
257               else
258                 bn256_add (tmp, tmp, N);
259             }
260           break;
261
262         case 2:
263           bn256_shift (u, u, -1);
264           if (bn256_is_even (A))
265             {
266               bn256_add (tmp, A, N);
267               carry = 0;
268             }
269           else
270             carry = bn256_add (A, A, N);
271
272           bn256_shift (A, A, -1);
273           A->word[7] |= carry * 0x80000000;
274
275           bn256_shift (tmp, tmp, -1);
276           if (bn256_is_even (tmp))
277             {
278               bn256_add (tmp, tmp, N);
279               carry = 0;
280             }
281           else
282             carry = bn256_add (tmp, tmp, N);
283
284           bn256_shift (tmp, tmp, -1);
285           tmp->word[7] |= carry * 0x80000000;
286
287           if (bn256_is_ge (tmp, tmp))
288             {
289               bn256_sub (tmp, tmp, tmp);
290               borrow = bn256_sub (tmp, tmp, tmp);
291               if (borrow)
292                 bn256_add (tmp, tmp, tmp);
293               else
294                 bn256_add (tmp, A, N);
295             }
296           else
297             {
298               bn256_sub (tmp, tmp, tmp);
299               borrow = bn256_sub (tmp, tmp, tmp);
300               if (borrow)
301                 bn256_add (tmp, tmp, tmp);
302               else
303                 bn256_add (tmp, tmp, N);
304             }
305           break;
306
307         case 0:
308           bn256_shift (tmp, tmp, -1);
309           if (bn256_is_even (tmp))
310             {
311               bn256_add (tmp, tmp, N);
312               carry = 0;
313             }
314           else
315             carry = bn256_add (tmp, tmp, N);
316
317           bn256_shift (tmp, tmp, -1);
318           tmp->word[7] |= carry * 0x80000000;
319
320           bn256_shift (tmp, tmp, -1);
321           if (bn256_is_even (tmp))
322             {
323               bn256_add (tmp, tmp, N);
324               carry = 0;
325             }
326           else
327             carry = bn256_add (tmp, tmp, N);
328
329           bn256_shift (tmp, tmp, -1);
330           tmp->word[7] |= carry * 0x80000000;
331
332           if (bn256_is_ge (u, v))
333             {
334               bn256_sub (u, u, v);
335               borrow = bn256_sub (A, A, C);
336               if (borrow)
337                 bn256_add (A, A, N);
338               else
339                 bn256_add (tmp, A, N);
340             }
341           else
342             {
343               bn256_sub (v, v, u);
344               borrow = bn256_sub (C, C, A);
345               if (borrow)
346                 bn256_add (C, C, N);
347               else
348                 bn256_add (tmp, C, N);
349             }
350           break;
351         }
352     }
353 #undef borrow
354 }