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