Fix the implementation for NIST P-256 and secp256k1
[gnuk/gnuk.git] / src / modp256r1.c
1 /*
2  * modp256r1.c -- modulo arithmetic for p256r1
3  *
4  * Copyright (C) 2011, 2013, 2014, 2016
5  *               Free Software Initiative of Japan
6  * Author: NIIBE Yutaka <gniibe@fsij.org>
7  *
8  * This file is a part of Gnuk, a GnuPG USB Token implementation.
9  *
10  * Gnuk is free software: you can redistribute it and/or modify it
11  * under the terms of the GNU General Public License as published by
12  * the Free Software Foundation, either version 3 of the License, or
13  * (at your option) any later version.
14  *
15  * Gnuk is distributed in the hope that it will be useful, but WITHOUT
16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
22  *
23  */
24
25 /*
26  * p256 =  2^256 - 2^224 + 2^192 + 2^96 - 1
27  */
28 #include <stdint.h>
29 #include <string.h>
30
31 #include "bn.h"
32 #include "modp256r1.h"
33
34 /*
35 256      224      192      160      128       96       64       32        0
36 2^256
37   1 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
38 2^256 - 2^224
39   0 ffffffff 00000000 00000000 00000000 00000000 00000000 00000000 00000000
40 2^256 - 2^224 + 2^192
41   0 ffffffff 00000001 00000000 00000000 00000000 00000000 00000000 00000000
42 2^256 - 2^224 + 2^192 + 2^96
43   0 ffffffff 00000001 00000000 00000000 00000001 00000000 00000000 00000000
44 2^256 - 2^224 + 2^192 + 2^96 - 1
45   0 ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff
46 */
47 const bn256 p256r1 = { {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
48                         0x00000000, 0x00000000, 0x00000001, 0xffffffff} };
49
50 /*
51  * Implementation Note.
52  *
53  * It's always modulo p256r1.
54  *
55  * Once, I tried redundant representation which caused wrong
56  * calculation.  Implementation could be correct with redundant
57  * representation, but it found that it's more expensive.
58  *
59  */
60
61 /**
62  * @brief  X = (A + B) mod p256r1
63  */
64 void
65 modp256r1_add (bn256 *X, const bn256 *A, const bn256 *B)
66 {
67   uint32_t cond;
68   bn256 tmp[1];
69
70   cond = (bn256_add (X, A, B) == 0);
71   cond &= bn256_sub (tmp, X, P256R1);
72   if (cond)
73     /* No-carry AND borrow */
74     memcpy (tmp, tmp, sizeof (bn256));
75   else
76     memcpy (X, tmp, sizeof (bn256));
77 }
78
79 /**
80  * @brief  X = (A - B) mod p256r1
81  */
82 void
83 modp256r1_sub (bn256 *X, const bn256 *A, const bn256 *B)
84 {
85   uint32_t borrow;
86   bn256 tmp[1];
87
88   borrow = bn256_sub (X, A, B);
89   bn256_add (tmp, X, P256R1);
90   if (borrow)
91     memcpy (X, tmp, sizeof (bn256));
92   else
93     memcpy (tmp, tmp, sizeof (bn256));
94 }
95
96 /**
97  * @brief  X = A mod p256r1
98  */
99 void
100 modp256r1_reduce (bn256 *X, const bn512 *A)
101 {
102   bn256 tmp[1], tmp0[1];
103   uint32_t borrow;
104
105 #define S1 X
106 #define S2 tmp
107 #define S3 tmp
108 #define S4 tmp
109 #define S5 tmp
110 #define S6 tmp
111 #define S7 tmp
112 #define S8 tmp
113 #define S9 tmp
114
115   S1->word[7] = A->word[7];
116   S1->word[6] = A->word[6];
117   S1->word[5] = A->word[5];
118   S1->word[4] = A->word[4];
119   S1->word[3] = A->word[3];
120   S1->word[2] = A->word[2];
121   S1->word[1] = A->word[1];
122   S1->word[0] = A->word[0];
123   borrow = bn256_sub (tmp0, S1, P256R1);
124   if (borrow)
125     memcpy (tmp0, tmp0, sizeof (bn256));
126   else
127     memcpy (S1, tmp0, sizeof (bn256));
128   /* X = S1 */
129
130   S2->word[7] = A->word[15];
131   S2->word[6] = A->word[14];
132   S2->word[5] = A->word[13];
133   S2->word[4] = A->word[12];
134   S2->word[3] = A->word[11];
135   S2->word[2] = S2->word[1] = S2->word[0] = 0;
136   /* X += 2 * S2 */
137   modp256r1_add (X, X, S2);
138   modp256r1_add (X, X, S2);
139
140   S3->word[7] = 0;
141   S3->word[6] = A->word[15];
142   S3->word[5] = A->word[14];
143   S3->word[4] = A->word[13];
144   S3->word[3] = A->word[12];
145   S3->word[2] = S3->word[1] = S3->word[0] = 0;
146   /* X += 2 * S3 */
147   modp256r1_add (X, X, S3);
148   modp256r1_add (X, X, S3);
149
150   S4->word[7] = A->word[15];
151   S4->word[6] = A->word[14];
152   S4->word[5] = S4->word[4] = S4->word[3] = 0;
153   S4->word[2] = A->word[10];
154   S4->word[1] = A->word[9];
155   S4->word[0] = A->word[8];
156   /* X += S4 */
157   modp256r1_add (X, X, S4);
158
159   S5->word[7] = A->word[8];
160   S5->word[6] = A->word[13];
161   S5->word[5] = A->word[15];
162   S5->word[4] = A->word[14];
163   S5->word[3] = A->word[13];
164   S5->word[2] = A->word[11];
165   S5->word[1] = A->word[10];
166   S5->word[0] = A->word[9];
167   borrow = bn256_sub (tmp0, S5, P256R1);
168   if (borrow)
169     memcpy (tmp0, tmp0, sizeof (bn256));
170   else
171     memcpy (S5, tmp0, sizeof (bn256));
172   /* X += S5 */
173   modp256r1_add (X, X, S5);
174
175   S6->word[7] = A->word[10];
176   S6->word[6] = A->word[8];
177   S6->word[5] = S6->word[4] = S6->word[3] = 0;
178   S6->word[2] = A->word[13];
179   S6->word[1] = A->word[12];
180   S6->word[0] = A->word[11];
181   borrow = bn256_sub (tmp0, S6, P256R1);
182   if (borrow)
183     memcpy (tmp0, tmp0, sizeof (bn256));
184   else
185     memcpy (S6, tmp0, sizeof (bn256));
186   /* X -= S6 */
187   modp256r1_sub (X, X, S6);
188
189   S7->word[7] = A->word[11];
190   S7->word[6] = A->word[9];
191   S7->word[5] = S7->word[4] = 0;
192   S7->word[3] = A->word[15];
193   S7->word[2] = A->word[14];
194   S7->word[1] = A->word[13];
195   S7->word[0] = A->word[12];
196   borrow = bn256_sub (tmp0, S7, P256R1);
197   if (borrow)
198     memcpy (tmp0, tmp0, sizeof (bn256));
199   else
200     memcpy (S7, tmp0, sizeof (bn256));
201   /* X -= S7 */
202   modp256r1_sub (X, X, S7);
203
204   S8->word[7] = A->word[12];
205   S8->word[6] = 0;
206   S8->word[5] = A->word[10];
207   S8->word[4] = A->word[9];
208   S8->word[3] = A->word[8];
209   S8->word[2] = A->word[15];
210   S8->word[1] = A->word[14];
211   S8->word[0] = A->word[13];
212   /* X -= S8 */
213   modp256r1_sub (X, X, S8);
214
215   S9->word[7] = A->word[13];
216   S9->word[6] = 0;
217   S9->word[5] = A->word[11];
218   S9->word[4] = A->word[10];
219   S9->word[3] = A->word[9];
220   S9->word[2] = 0;
221   S9->word[1] = A->word[15];
222   S9->word[0] = A->word[14];
223   /* X -= S9 */
224   modp256r1_sub (X, X, S9);
225
226   borrow = bn256_sub (tmp, X, P256R1);
227   if (borrow)
228     memcpy (tmp, X, sizeof (bn256));
229   else
230     memcpy (X, tmp, sizeof (bn256));
231
232 #undef S1
233 #undef S2
234 #undef S3
235 #undef S4
236 #undef S5
237 #undef S6
238 #undef S7
239 #undef S8
240 #undef S9
241 }
242
243 /**
244  * @brief  X = (A * B) mod p256r1
245  */
246 void
247 modp256r1_mul (bn256 *X, const bn256 *A, const bn256 *B)
248 {
249   bn512 AB[1];
250
251   bn256_mul (AB, A, B);
252   modp256r1_reduce (X, AB);
253 }
254
255 /**
256  * @brief  X = A * A mod p256r1
257  */
258 void
259 modp256r1_sqr (bn256 *X, const bn256 *A)
260 {
261   bn512 AA[1];
262
263   bn256_sqr (AA, A);
264   modp256r1_reduce (X, AA);
265 }
266
267
268 /**
269  * @brief  X = (A << shift) mod p256r1
270  * @note   shift < 32
271  */
272 void
273 modp256r1_shift (bn256 *X, const bn256 *A, int shift)
274 {
275   uint32_t carry;
276 #define borrow carry
277   bn256 tmp[1];
278
279   carry = bn256_shift (X, A, shift);
280   if (shift < 0)
281     return;
282
283   memset (tmp, 0, sizeof (bn256));
284   tmp->word[7] = carry;
285   tmp->word[0] = carry;
286   modp256r1_add (X, X, tmp);
287
288   tmp->word[7] = 0;
289   tmp->word[0] = 0;
290   tmp->word[6] = carry;
291   tmp->word[3] = carry;
292   modp256r1_sub (X, X, tmp);
293
294   borrow = bn256_sub (tmp, X, P256R1);
295   if (borrow)
296     memcpy (tmp, X, sizeof (bn256));
297   else
298     memcpy (X, tmp, sizeof (bn256));
299 #undef borrow
300 }