bd4de243e6669657aeb7e72e0c55855ee592d1b5
[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 (C, 0, sizeof (bn256));
160   memcpy (u, X, sizeof (bn256));
161   memcpy (v, N, sizeof (bn256));
162
163   while (n--)
164     {
165       int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
166
167       switch (c)
168         {
169         case 3:
170           bn256_shift (u, u, -1);
171           if (bn256_is_even (A))
172             {
173               bn256_add (tmp, A, N);
174               carry = 0;
175             }
176           else
177             carry = bn256_add (A, A, N);
178
179           bn256_shift (A, A, -1);
180           A->word[7] |= carry * 0x80000000;
181
182           bn256_shift (v, v, -1);
183           if (bn256_is_even (C))
184             {
185               bn256_add (tmp, C, N);
186               carry = 0;
187             }
188           else
189             carry = bn256_add (C, C, N);
190
191           bn256_shift (C, C, -1);
192           C->word[7] |= carry * 0x80000000;
193
194           if (bn256_is_ge (tmp, tmp))
195             {
196               bn256_sub (tmp, tmp, tmp);
197               borrow = bn256_sub (tmp, tmp, tmp);
198               if (borrow)
199                 bn256_add (tmp, tmp, tmp);
200               else
201                 bn256_add (tmp, A, N);
202             }
203           else
204             {
205               bn256_sub (tmp, tmp, tmp);
206               borrow = bn256_sub (tmp, tmp, tmp);
207               if (borrow)
208                 bn256_add (tmp, tmp, tmp);
209               else
210                 bn256_add (tmp, tmp, N);
211             }
212           break;
213
214         case 1:
215           bn256_shift (tmp, tmp, -1);
216           if (bn256_is_even (tmp))
217             {
218               bn256_add (tmp, tmp, N);
219               carry = 0;
220             }
221           else
222             carry = bn256_add (tmp, tmp, N);
223
224           bn256_shift (tmp, tmp, -1);
225           tmp->word[7] |= carry * 0x80000000;
226
227           bn256_shift (v, v, -1);
228           if (bn256_is_even (C))
229             {
230               bn256_add (tmp, C, N);
231               carry = 0;
232             }
233           else
234             carry = bn256_add (C, C, N);
235
236           bn256_shift (C, C, -1);
237           C->word[7] |= carry * 0x80000000;
238
239           if (bn256_is_ge (tmp, tmp))
240             {
241               bn256_sub (tmp, tmp, tmp);
242               borrow = bn256_sub (tmp, tmp, tmp);
243               if (borrow)
244                 bn256_add (tmp, tmp, tmp);
245               else
246                 bn256_add (tmp, A, N);
247             }
248           else
249             {
250               bn256_sub (tmp, tmp, tmp);
251               borrow = bn256_sub (tmp, tmp, tmp);
252               if (borrow)
253                 bn256_add (tmp, tmp, tmp);
254               else
255                 bn256_add (tmp, tmp, N);
256             }
257           break;
258
259         case 2:
260           bn256_shift (u, u, -1);
261           if (bn256_is_even (A))
262             {
263               bn256_add (tmp, A, N);
264               carry = 0;
265             }
266           else
267             carry = bn256_add (A, A, N);
268
269           bn256_shift (A, A, -1);
270           A->word[7] |= carry * 0x80000000;
271
272           bn256_shift (tmp, tmp, -1);
273           if (bn256_is_even (tmp))
274             {
275               bn256_add (tmp, tmp, N);
276               carry = 0;
277             }
278           else
279             carry = bn256_add (tmp, tmp, N);
280
281           bn256_shift (tmp, tmp, -1);
282           tmp->word[7] |= carry * 0x80000000;
283
284           if (bn256_is_ge (tmp, tmp))
285             {
286               bn256_sub (tmp, tmp, tmp);
287               borrow = bn256_sub (tmp, tmp, tmp);
288               if (borrow)
289                 bn256_add (tmp, tmp, tmp);
290               else
291                 bn256_add (tmp, A, N);
292             }
293           else
294             {
295               bn256_sub (tmp, tmp, tmp);
296               borrow = bn256_sub (tmp, tmp, tmp);
297               if (borrow)
298                 bn256_add (tmp, tmp, tmp);
299               else
300                 bn256_add (tmp, tmp, N);
301             }
302           break;
303
304         case 0:
305           bn256_shift (tmp, tmp, -1);
306           if (bn256_is_even (tmp))
307             {
308               bn256_add (tmp, tmp, N);
309               carry = 0;
310             }
311           else
312             carry = bn256_add (tmp, tmp, N);
313
314           bn256_shift (tmp, tmp, -1);
315           tmp->word[7] |= carry * 0x80000000;
316
317           bn256_shift (tmp, tmp, -1);
318           if (bn256_is_even (tmp))
319             {
320               bn256_add (tmp, tmp, N);
321               carry = 0;
322             }
323           else
324             carry = bn256_add (tmp, tmp, N);
325
326           bn256_shift (tmp, tmp, -1);
327           tmp->word[7] |= carry * 0x80000000;
328
329           if (bn256_is_ge (u, v))
330             {
331               bn256_sub (u, u, v);
332               borrow = bn256_sub (A, A, C);
333               if (borrow)
334                 bn256_add (A, A, N);
335               else
336                 bn256_add (tmp, A, N);
337             }
338           else
339             {
340               bn256_sub (v, v, u);
341               borrow = bn256_sub (C, C, A);
342               if (borrow)
343                 bn256_add (C, C, N);
344               else
345                 bn256_add (tmp, C, N);
346             }
347           break;
348         }
349     }
350 #undef borrow
351 }