Add ST_DONGLE and ST_NUCLEO_F103
[gnuk/gnuk.git] / src / modp256k1.c
1 /*
2  * modp256k1.c -- modulo arithmetic for p256k1
3  *
4  * Copyright (C) 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  * p256k1 =  2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
26  */
27 #include <stdint.h>
28 #include <string.h>
29
30 #include "bn.h"
31 #include "modp256k1.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^32
38   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 00000000
39 2^256 - 2^32 - 2^9
40   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffe00
41 2^256 - 2^32 - 2^9 - 2^8
42   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffd00
43 2^256 - 2^32 - 2^9 - 2^8 - 2^7
44   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc80
45 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6
46   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc40
47 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4
48   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc30
49 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
50   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
51 */
52 const bn256 p256k1 = { {0xfffffc2f, 0xfffffffe, 0xffffffff, 0xffffffff,
53                         0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } };
54
55 /*
56  * Implementation Note.
57  *
58  * It's not always modulo p256k1.  The representation is redundant
59  * during computation.  For example, when we add the prime - 1 and 1,
60  * it won't overflow to 2^256, and the result is represented within
61  * 256-bit.
62  *
63  * It is guaranteed that modp256k1_reduce reduces to modulo p256k1.
64  */
65
66 /**
67  * @brief  X = (A + B) mod p256k1
68  */
69 void
70 modp256k1_add (bn256 *X, const bn256 *A, const bn256 *B)
71 {
72   uint32_t carry;
73   bn256 tmp[1];
74
75   carry = bn256_add (X, A, B);
76   if (carry)
77     bn256_sub (X, X, P256K1);
78   else
79     bn256_sub (tmp, X, P256K1);
80 }
81
82 /**
83  * @brief  X = (A - B) mod p256
84  */
85 void
86 modp256k1_sub (bn256 *X, const bn256 *A, const bn256 *B)
87 {
88   uint32_t borrow;
89   bn256 tmp[1];
90
91   borrow = bn256_sub (X, A, B);
92   if (borrow)
93     bn256_add (X, X, P256K1);
94   else
95     bn256_add (tmp, X, P256K1);
96 }
97
98 /**
99  * @brief  X = A mod p256k1
100  */
101 void
102 modp256k1_reduce (bn256 *X, const bn512 *A)
103 {
104   bn256 tmp[1];
105   uint32_t carry;
106 #define borrow carry
107   uint32_t s0, s1;
108 #define s00 tmp->word[0]
109 #define s01 tmp->word[1]
110 #define s02 tmp->word[2]
111
112 #define W0 X
113 #define W1 tmp
114 #define W2 tmp
115 #define W3 tmp
116 #define W4 tmp
117 #define W5 tmp
118 #define W6 tmp
119 #define W7 tmp
120 #define S  tmp
121
122   /*
123    * Suppose: P256K1 = 2^256 - CONST
124    * Then, compute: W = A_low + A_high * CONST
125    *                256-bit W0 = W mod 2^256
126    *                64-bit (S1, S0) = W / 2^256
127    * where: CONST = 2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1
128    */
129
130   /* W0 = A_low   */
131   /* W7 = A_high  */
132   /* W0 += W7 */
133   carry = bn256_add (W0, (const bn256 *)&A->word[8], (const bn256 *)A);
134
135   /* W6 = W7 << 4 */
136   /* W0 += W6 */
137   bn256_shift (W6, (const bn256 *)&A->word[8], 4);
138   carry += bn256_add (W0, W0, W6);
139
140   /* W5 = W6 << 2 */
141   /* W0 += W5 */
142   bn256_shift (W5, W6, 2);
143   carry += bn256_add (W0, W0, W5);
144
145   /* W4 = W5 << 1 */
146   /* W0 += W4 */
147   bn256_shift (W4, W5, 1);
148   carry += bn256_add (W0, W0, W4);
149
150   /* W3 = W4 << 1 */
151   /* W0 += W3 */
152   bn256_shift (W3, W4, 1);
153   carry += bn256_add (W0, W0, W3);
154
155   /* W2 = W3 << 1 */
156   /* W0 += W2 */
157   bn256_shift (W2, W3, 1);
158   carry += bn256_add (W0, W0, W2);
159
160   /* W1 = A_high << 32 */
161   /* W0 += W1 */
162   W1->word[7] = A->word[14];
163   W1->word[6] = A->word[13];
164   W1->word[5] = A->word[12];
165   W1->word[4] = A->word[11];
166   W1->word[3] = A->word[10];
167   W1->word[2] = A->word[9];
168   W1->word[1] = A->word[8];
169   W1->word[0] = 0;
170   carry += bn256_add (W0, W0, W1);
171
172   /* (S1, S0) = W / 2^256 */
173   s0 = A->word[15];
174   carry += (s0 >> 28) + (s0 >> 26) + (s0 >> 25) + (s0 >> 24) + (s0 >> 23);
175   carry += s0;
176   s1 = (carry < s0) ? 1 : 0;
177   s0 = carry;
178
179   /*
180    * Compute: S:=(S02, S01, S00), S = (S1,S0)*CONST
181    */
182   S->word[7] = S->word[6] = S->word[5] = S->word[4] = S->word[3] = 0;
183
184   /* (S02, S01, S00) = (S1, S0) + (S1, S0)*2^32 */ 
185   s00 = s0;
186   s01 = s0 + s1;
187   s02 = s1 + ((s01 < s0)? 1 : 0);
188
189   /* (S02, S01, S00) += (S1, S0)*2^9 */ 
190   carry = (s0 >> 23) + s01;
191   s02 += (s1 >> 23) + ((carry < s01)? 1 : 0);
192   s01 = (s1 << 9) + carry;
193   s02 += ((s01 < carry)? 1 : 0);
194   s00 += (s0 << 9);
195   carry = ((s00 < (s0 << 9))? 1 : 0);
196   s01 += carry;
197   s02 += ((s01 < carry)? 1 : 0);
198
199   /* (S02, S01, S00) += (S1, S0)*2^8 */ 
200   carry = (s0 >> 24) + s01;
201   s02 += (s1 >> 24) + ((carry < s01)? 1 : 0);
202   s01 = (s1 << 8) + carry;
203   s02 += ((s01 < carry)? 1 : 0);
204   s00 += (s0 << 8);
205   carry = ((s00 < (s0 << 8))? 1 : 0);
206   s01 += carry;
207   s02 += ((s01 < carry)? 1 : 0);
208
209   /* (S02, S01, S00) += (S1, S0)*2^7 */ 
210   carry = (s0 >> 25) + s01;
211   s02 += (s1 >> 25) + ((carry < s01)? 1 : 0);
212   s01 = (s1 << 7) + carry;
213   s02 += ((s01 < carry)? 1 : 0);
214   s00 += (s0 << 7);
215   carry = ((s00 < (s0 << 7))? 1 : 0);
216   s01 += carry;
217   s02 += ((s01 < carry)? 1 : 0);
218
219   /* (S02, S01, S00) += (S1, S0)*2^6 */ 
220   carry = (s0 >> 26) + s01;
221   s02 += (s1 >> 26) + ((carry < s01)? 1 : 0);
222   s01 = (s1 << 6) + carry;
223   s02 += ((s01 < carry)? 1 : 0);
224   s00 += (s0 << 6);
225   carry = ((s00 < (s0 << 6))? 1 : 0);
226   s01 += carry;
227   s02 += ((s01 < carry)? 1 : 0);
228
229   /* (S02, S01, S00) += (S1, S0)*2^4 */ 
230   carry = (s0 >> 28) + s01;
231   s02 += (s1 >> 28) + ((carry < s01)? 1 : 0);
232   s01 = (s1 << 4) + carry;
233   s02 += ((s01 < carry)? 1 : 0);
234   s00 += (s0 << 4);
235   carry = ((s00 < (s0 << 4))? 1 : 0);
236   s01 += carry;
237   s02 += ((s01 < carry)? 1 : 0);
238
239   /* W0 += S */
240   modp256k1_add (W0, W0, S);
241
242   borrow = bn256_sub (tmp, W0, P256K1);
243   if (borrow)
244     memcpy (tmp, W0, sizeof (bn256));
245   else
246     memcpy (W0, tmp, sizeof (bn256));
247
248 #undef W0
249 #undef W1
250 #undef W2
251 #undef W3
252 #undef W4
253 #undef W5
254 #undef W6
255 #undef W7
256 #undef S
257 #undef s00
258 #undef s01
259 #undef s02
260 #undef borrow
261 }
262
263 /**
264  * @brief  X = (A * B) mod p256k1
265  */
266 void
267 modp256k1_mul (bn256 *X, const bn256 *A, const bn256 *B)
268 {
269   bn512 AB[1];
270
271   bn256_mul (AB, A, B);
272   modp256k1_reduce (X, AB);
273 }
274
275 /**
276  * @brief  X = A * A mod p256k1
277  */
278 void
279 modp256k1_sqr (bn256 *X, const bn256 *A)
280 {
281   bn512 AA[1];
282
283   bn256_sqr (AA, A);
284   modp256k1_reduce (X, AA);
285 }
286
287
288 /**
289  * @brief  X = (A << shift) mod p256k1
290  * @note   shift < 32
291  */
292 void
293 modp256k1_shift (bn256 *X, const bn256 *A, int shift)
294 {
295   uint32_t carry;
296   bn256 tmp[1];
297
298   carry = bn256_shift (X, A, shift);
299   if (shift < 0)
300     return;
301
302   memset (tmp, 0, sizeof (bn256));
303   tmp->word[0] = carry + (carry << 9);
304   tmp->word[1] = carry + (tmp->word[0] < (carry << 9)) + (carry >> 23);
305   tmp->word[0] = tmp->word[0] + (carry << 8);
306   tmp->word[1] = tmp->word[1] + (tmp->word[0] < (carry << 8)) + (carry >> 24);
307   tmp->word[0] = tmp->word[0] + (carry << 7);
308   tmp->word[1] = tmp->word[1] + (tmp->word[0] < (carry << 7)) + (carry >> 25);
309   tmp->word[0] = tmp->word[0] + (carry << 6);
310   tmp->word[1] = tmp->word[1] + (tmp->word[0] < (carry << 6)) + (carry >> 26);
311   tmp->word[0] = tmp->word[0] + (carry << 4);
312   tmp->word[1] = tmp->word[1] + (tmp->word[0] < (carry << 4)) + (carry >> 28);
313
314   modp256k1_add (X, X, tmp);
315 }