minor fixes
[gnuk/gnuk.git] / src / modp256r1.c
1 /*
2  * modp256r1.c -- modulo arithmetic for p256r1
3  *
4  * Copyright (C) 2011, 2013, 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 /*
25  * p256 =  2^256 - 2^224 + 2^192 + 2^96 - 1
26  */
27 #include <stdint.h>
28 #include <string.h>
29
30 #include "bn.h"
31 #include "modp256r1.h"
32
33 /*
34 256      224      192      160      128       96       64       32        0
35 2^256
36   1 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
37 2^256 - 2^224
38   0 ffffffff 00000000 00000000 00000000 00000000 00000000 00000000 00000000
39 2^256 - 2^224 + 2^192
40   0 ffffffff 00000001 00000000 00000000 00000000 00000000 00000000 00000000
41 2^256 - 2^224 + 2^192 + 2^96
42   0 ffffffff 00000001 00000000 00000000 00000001 00000000 00000000 00000000
43 2^256 - 2^224 + 2^192 + 2^96 - 1
44   0 ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff
45 */
46 const bn256 p256r1 = { {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
47                         0x00000000, 0x00000000, 0x00000001, 0xffffffff} };
48
49 /**
50  * @brief  X = (A + B) mod p256r1
51  */
52 void
53 modp256r1_add (bn256 *X, const bn256 *A, const bn256 *B)
54 {
55   uint32_t carry;
56   bn256 tmp[1];
57
58   carry = bn256_add (X, A, B);
59   if (carry)
60     bn256_sub (X, X, P256R1);
61   else
62     bn256_sub (tmp, X, P256R1);
63 }
64
65 /**
66  * @brief  X = (A - B) mod p256r1
67  */
68 void
69 modp256r1_sub (bn256 *X, const bn256 *A, const bn256 *B)
70 {
71   uint32_t borrow;
72   bn256 tmp[1];
73
74   borrow = bn256_sub (X, A, B);
75   if (borrow)
76     bn256_add (X, X, P256R1);
77   else
78     bn256_add (tmp, X, P256R1);
79 }
80
81 /**
82  * @brief  X = A mod p256r1
83  */
84 void
85 modp256r1_reduce (bn256 *X, const bn512 *A)
86 {
87   bn256 tmp[1];
88   uint32_t borrow;
89
90 #define S1 X
91 #define S2 tmp
92 #define S3 tmp
93 #define S4 tmp
94 #define S5 tmp
95 #define S6 tmp
96 #define S7 tmp
97 #define S8 tmp
98 #define S9 tmp
99
100   S1->word[7] = A->word[7];
101   S1->word[6] = A->word[6];
102   S1->word[5] = A->word[5];
103   S1->word[4] = A->word[4];
104   S1->word[3] = A->word[3];
105   S1->word[2] = A->word[2];
106   S1->word[1] = A->word[1];
107   S1->word[0] = A->word[0];
108   /* X = S1 */
109
110   S2->word[7] = A->word[15];
111   S2->word[6] = A->word[14];
112   S2->word[5] = A->word[13];
113   S2->word[4] = A->word[12];
114   S2->word[3] = A->word[11];
115   S2->word[2] = S2->word[1] = S2->word[0] = 0;
116   /* X += 2 * S2 */
117   modp256r1_add (X, X, S2);
118   modp256r1_add (X, X, S2);
119
120   S3->word[7] = 0;
121   S3->word[6] = A->word[15];
122   S3->word[5] = A->word[14];
123   S3->word[4] = A->word[13];
124   S3->word[3] = A->word[12];
125   S3->word[2] = S3->word[1] = S3->word[0] = 0;
126   /* X += 2 * S3 */
127   modp256r1_add (X, X, S3);
128   modp256r1_add (X, X, S3);
129
130   S4->word[7] = A->word[15];
131   S4->word[6] = A->word[14];
132   S4->word[5] = S4->word[4] = S4->word[3] = 0;
133   S4->word[2] = A->word[10];
134   S4->word[1] = A->word[9];
135   S4->word[0] = A->word[8];
136   /* X += S4 */
137   modp256r1_add (X, X, S4);
138
139   S5->word[7] = A->word[8];
140   S5->word[6] = A->word[13];
141   S5->word[5] = A->word[15];
142   S5->word[4] = A->word[14];
143   S5->word[3] = A->word[13];
144   S5->word[2] = A->word[11];
145   S5->word[1] = A->word[10];
146   S5->word[0] = A->word[9];
147   /* X += S5 */
148   modp256r1_add (X, X, S5);
149
150   S6->word[7] = A->word[10];
151   S6->word[6] = A->word[8];
152   S6->word[5] = S6->word[4] = S6->word[3] = 0;
153   S6->word[2] = A->word[13];
154   S6->word[1] = A->word[12];
155   S6->word[0] = A->word[11];
156   /* X -= S6 */
157   modp256r1_sub (X, X, S6);
158
159   S7->word[7] = A->word[11];
160   S7->word[6] = A->word[9];
161   S7->word[5] = S7->word[4] = 0;
162   S7->word[3] = A->word[15];
163   S7->word[2] = A->word[14];
164   S7->word[1] = A->word[13];
165   S7->word[0] = A->word[12];
166   /* X -= S7 */
167   modp256r1_sub (X, X, S7);
168
169   S8->word[7] = A->word[12];
170   S8->word[6] = 0;
171   S8->word[5] = A->word[10];
172   S8->word[4] = A->word[9];
173   S8->word[3] = A->word[8];
174   S8->word[2] = A->word[15];
175   S8->word[1] = A->word[14];
176   S8->word[0] = A->word[13];
177   /* X -= S8 */
178   modp256r1_sub (X, X, S8);
179
180   S9->word[7] = A->word[13];
181   S9->word[6] = 0;
182   S9->word[5] = A->word[11];
183   S9->word[4] = A->word[10];
184   S9->word[3] = A->word[9];
185   S9->word[2] = 0;
186   S9->word[1] = A->word[15];
187   S9->word[0] = A->word[14];
188   /* X -= S9 */
189   modp256r1_sub (X, X, S9);
190
191   borrow = bn256_sub (tmp, X, P256R1);
192   if (borrow)
193     memcpy (tmp, X, sizeof (bn256));
194   else
195     memcpy (X, tmp, sizeof (bn256));
196
197 #undef S1
198 #undef S2
199 #undef S3
200 #undef S4
201 #undef S5
202 #undef S6
203 #undef S7
204 #undef S8
205 #undef S9
206 }
207
208 /**
209  * @brief  X = (A * B) mod p256r1
210  */
211 void
212 modp256r1_mul (bn256 *X, const bn256 *A, const bn256 *B)
213 {
214   bn512 AB[1];
215
216   bn256_mul (AB, A, B);
217   modp256r1_reduce (X, AB);
218 }
219
220 /**
221  * @brief  X = A * A mod p256r1
222  */
223 void
224 modp256r1_sqr (bn256 *X, const bn256 *A)
225 {
226   bn512 AA[1];
227
228   bn256_sqr (AA, A);
229   modp256r1_reduce (X, AA);
230 }
231
232 /**
233  * @brief  C = (1 / a)  mod p256r1
234  *
235  * Return -1 on error.
236  * Return 0 on success.
237  */
238 #define MAX_N_BITS 256
239
240 int
241 modp256r1_inv (bn256 *C, const bn256 *a)
242 {
243   bn256 u[1], v[1], tmp[1];
244   bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
245   uint32_t carry;
246   int n = MAX_N_BITS * 3;
247
248   if (bn256_is_zero (a))
249     return -1;
250
251   memset (C, 0, sizeof (bn256));
252   memcpy (u, a, sizeof (bn256));
253   memcpy (v, P256R1, sizeof (bn256));
254
255   while (n--)
256     {
257       int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
258
259       switch (c)
260         {
261         case 3:
262           bn256_shift (u, u, -1);
263           if (bn256_is_even (A))
264             {
265               bn256_add (tmp, A, P256R1);
266               carry = 0;
267             }
268           else
269             carry = bn256_add (A, A, P256R1);
270
271           bn256_shift (A, A, -1);
272           A->word[7] |= carry * 0x80000000;
273
274           bn256_shift (v, v, -1);
275           if (bn256_is_even (C))
276             {
277               bn256_add (tmp, C, P256R1);
278               carry = 0;
279             }
280           else
281             carry = bn256_add (C, C, P256R1);
282
283           bn256_shift (C, C, -1);
284           C->word[7] |= carry * 0x80000000;
285
286           if (bn256_is_ge (tmp, tmp))
287             {
288               bn256_sub (tmp, tmp, tmp);
289               modp256r1_sub (tmp, tmp, tmp);
290             }
291           else
292             {
293               bn256_sub (tmp, tmp, tmp);
294               modp256r1_sub (tmp, tmp, A);
295             }
296           break;
297
298         case 1:
299           bn256_shift (tmp, tmp, -1);
300           if (bn256_is_even (tmp))
301             {
302               bn256_add (tmp, tmp, P256R1);
303               carry = 0;
304             }
305           else
306             carry = bn256_add (tmp, tmp, P256R1);
307
308           bn256_shift (tmp, tmp, -1);
309           tmp->word[7] |= carry * 0x80000000;
310
311           bn256_shift (v, v, -1);
312           if (bn256_is_even (C))
313             {
314               bn256_add (tmp, C, P256R1);
315               carry = 0;
316             }
317           else
318             carry = bn256_add (C, C, P256R1);
319
320           bn256_shift (C, C, -1);
321           C->word[7] |= carry * 0x80000000;
322
323           if (bn256_is_ge (tmp, tmp))
324             {
325               bn256_sub (tmp, tmp, tmp);
326               modp256r1_sub (tmp, tmp, tmp);
327             }
328           else
329             {
330               bn256_sub (tmp, tmp, tmp);
331               modp256r1_sub (tmp, tmp, A);
332             }
333           break;
334
335         case 2:
336           bn256_shift (u, u, -1);
337           if (bn256_is_even (A))
338             {
339               bn256_add (tmp, A, P256R1);
340               carry = 0;
341             }
342           else
343             carry = bn256_add (A, A, P256R1);
344
345           bn256_shift (A, A, -1);
346           A->word[7] |= carry * 0x80000000;
347
348           bn256_shift (tmp, tmp, -1);
349           if (bn256_is_even (tmp))
350             {
351               bn256_add (tmp, tmp, P256R1);
352               carry = 0;
353             }
354           else
355             carry = bn256_add (tmp, tmp, P256R1);
356
357           bn256_shift (tmp, tmp, -1);
358           tmp->word[7] |= carry * 0x80000000;
359
360           if (bn256_is_ge (tmp, tmp))
361             {
362               bn256_sub (tmp, tmp, tmp);
363               modp256r1_sub (tmp, tmp, tmp);
364             }
365           else
366             {
367               bn256_sub (tmp, tmp, tmp);
368               modp256r1_sub (tmp, tmp, A);
369             }
370           break;
371
372         case 0:
373           bn256_shift (tmp, tmp, -1);
374           if (bn256_is_even (tmp))
375             {
376               bn256_add (tmp, tmp, P256R1);
377               carry = 0;
378             }
379           else
380             carry = bn256_add (tmp, tmp, P256R1);
381
382           bn256_shift (tmp, tmp, -1);
383           tmp->word[7] |= carry * 0x80000000;
384
385           bn256_shift (tmp, tmp, -1);
386           if (bn256_is_even (tmp))
387             {
388               bn256_add (tmp, tmp, P256R1);
389               carry = 0;
390             }
391           else
392             carry = bn256_add (tmp, tmp, P256R1);
393
394           bn256_shift (tmp, tmp, -1);
395           tmp->word[7] |= carry * 0x80000000;
396
397           if (bn256_is_ge (u, v))
398             {
399               bn256_sub (u, u, v);
400               modp256r1_sub (A, A, C);
401             }
402           else
403             {
404               bn256_sub (v, v, u);
405               modp256r1_sub (C, C, A);
406             }
407           break;
408         }
409     }
410
411   return 0;
412 }
413
414 /**
415  * @brief  X = (A << shift) mod p256r1
416  * @note   shift <= 32
417  */
418 void
419 modp256r1_shift (bn256 *X, const bn256 *A, int shift)
420 {
421   uint32_t carry;
422 #define borrow carry
423   bn256 tmp[1];
424
425   carry = bn256_shift (X, A, shift);
426   if (shift < 0)
427     return;
428
429   memset (tmp, 0, sizeof (bn256));
430   tmp->word[7] = carry;
431   tmp->word[0] = carry;
432   modp256r1_add (X, X, tmp);
433
434   tmp->word[7] = 0;
435   tmp->word[0] = 0;
436   tmp->word[6] = carry;
437   tmp->word[3] = carry;
438   modp256r1_sub (X, X, tmp);
439
440   borrow = bn256_sub (tmp, X, P256R1);
441   if (borrow)
442     memcpy (tmp, X, sizeof (bn256));
443   else
444     memcpy (X, tmp, sizeof (bn256));
445 #undef borrow
446 }