Implement writable key algorithm attributes
[gnuk/gnuk.git] / src / ecc.c
1 /*                                                    -*- coding: utf-8 -*-
2  * ecc.c - Elliptic curve over GF(prime)
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  * References:
26  *
27  * [1] Suite B Implementer's Guide to FIPS 186-3 (ECDSA), February 3, 2010.
28  *
29  * [2] Michael Brown, Darrel Hankerson, Julio López, and Alfred Menezes,
30  *     Software Implementation of the NIST Elliptic Curves Over Prime Fields,
31  *     Proceedings of the 2001 Conference on Topics in Cryptology: The
32  *     Cryptographer's Track at RSA
33  *     Pages 250-265, Springer-Verlag London, UK, 2001
34  *     ISBN:3-540-41898-9
35  *
36  * [3] Mustapha Hedabou, Pierre Pinel, Lucien Bénéteau, 
37  *     A comb method to render ECC resistant against Side Channel Attacks,
38  *     2004
39  */
40
41 #include "field-group-select.h"
42
43 /*
44  * Coefficients
45  */
46 /*
47  * static const bn256 *coefficient_a;
48  * static const bn256 *coefficient_b;
49  */
50 /*
51  * N: order of G
52  */
53 /*
54  * static const bn256 N[1];
55  */
56 /*
57  * MU = 2^512 / N
58  * MU = ( (1 << 256) | MU_lower )
59  */
60 /*
61  * static const bn256 MU_lower[1];
62  */
63
64 /*
65  * w = 4
66  * m = 256
67  * d = 64
68  * e = 32
69  */
70
71 /*
72  * static const ac precomputed_KG[15];
73  * static const ac precomputed_2E_KG[15];
74  */
75
76 #if TEST
77 /*
78  * Generator of Elliptic curve over GF(p256)
79  */
80 const ac *G = &precomputed_KG[0];
81 #endif
82
83
84 static int
85 get_vk (const bn256 *K, int i)
86 {
87   uint32_t w0, w1, w2, w3;
88
89   if (i < 32)
90     {
91       w3 = K->word[6]; w2 = K->word[4]; w1 = K->word[2]; w0 = K->word[0];
92     }
93   else
94     {
95       w3 = K->word[7]; w2 = K->word[5]; w1 = K->word[3]; w0 = K->word[1];
96       i -= 32;
97     }
98
99   w3 >>= i;  w2 >>= i;  w1 >>= i;  w0 >>= i;
100   return ((w3 & 1) << 3) | ((w2 & 1) << 2) | ((w1 & 1) << 1) | (w0 & 1);
101 }
102
103
104 /**
105  * @brief       X  = k * G
106  *
107  * @param K     scalar k
108  *
109  * Return -1 on error.
110  * Return 0 on success.
111  */
112 int
113 FUNC(compute_kG) (ac *X, const bn256 *K)
114 {
115   uint8_t index[64]; /* Lower 4-bit for index absolute value, msb is
116                         for sign (encoded as: 0 means 1, 1 means -1).  */
117   bn256 K_dash[1];
118   jpc Q[1], tmp[1], *dst;
119   int i;
120   int vk;
121   uint32_t k_is_even = bn256_is_even (K);
122
123   bn256_sub_uint (K_dash, K, k_is_even);
124   /* It keeps the condition: 1 <= K' <= N - 2, and K' is odd.  */
125
126   /* Fill index.  */
127   vk = get_vk (K_dash, 0);
128   for (i = 1; i < 64; i++)
129     {
130       int vk_next, is_zero;
131
132       vk_next = get_vk (K_dash, i);
133       is_zero = (vk_next == 0);
134       index[i-1] = (vk - 1) | (is_zero << 7);
135       vk = (is_zero ? vk : vk_next);
136     }
137   index[63] = vk - 1;
138
139   memset (Q->z, 0, sizeof (bn256)); /* infinity */
140   for (i = 31; i >= 0; i--)
141     {
142       FUNC(jpc_double) (Q, Q);
143       FUNC(jpc_add_ac_signed) (Q, Q, &precomputed_2E_KG[index[i+32]&0x0f],
144                                index[i+32] >> 7);
145       FUNC(jpc_add_ac_signed) (Q, Q, &precomputed_KG[index[i]&0x0f],
146                                index[i] >> 7);
147     }
148
149   dst = k_is_even ? Q : tmp;
150   FUNC(jpc_add_ac) (dst, Q, &precomputed_KG[0]);
151
152   return FUNC(jpc_to_ac) (X, Q);
153 }
154
155
156
157 /**
158  * check if P is on the curve.
159  *
160  * Return -1 on error.
161  * Return 0 on success.
162  */
163 static int
164 point_is_on_the_curve (const ac *P)
165 {
166   bn256 s[1], t[1];
167
168   /* Elliptic curve: y^2 = x^3 + a*x + b */
169   MFNC(sqr) (s, P->x);
170   MFNC(mul) (s, s, P->x);
171
172 #ifdef COEFFICIENT_A_IS_ZERO
173   MFNC(mul) (t, coefficient_a, P->x);
174   MFNC(add) (s, s, t);
175 #endif
176   MFNC(add) (s, s, coefficient_b);
177
178   MFNC(sqr) (t, P->y);
179   if (bn256_cmp (s, t) == 0)
180     return 0;
181   else
182     return -1;
183 }
184
185
186 static int
187 get_vk_kP (const bn256 *K, int i)
188 {
189   uint32_t w;
190   uint8_t blk = i/32;
191   uint8_t pos = i%32;
192   uint8_t col = 3*(pos % 11) + (pos >= 11) + (pos >= 22);
193   uint8_t word_index = (blk * 3) + (pos / 11);
194
195   w = ((K->word[word_index] >> col) & 7);
196   if (word_index < 7 && (pos == 10 || pos == 21))
197     {
198       uint8_t mask;
199       uint8_t shift;
200
201       word_index++;
202       if (pos == 10)
203         {
204           shift = 2;
205           mask = 4;
206         }
207       else
208         {
209           shift = 1;
210           mask = 6;
211         }
212
213       w |= ((K->word[word_index] << shift) & mask);
214     }
215
216   return w;
217 }
218
219 /**
220  * @brief       X  = k * P
221  *
222  * @param K     scalar k
223  * @param P     P in affine coordiate
224  *
225  * Return -1 on error.
226  * Return 0 on success.
227  *
228  * For the curve (cofactor is 1 and n is prime), possible error cases are:
229  *
230  *     P is not on the curve.
231  *     P = G, k = n
232  *     Something wrong in the code.
233  *
234  * Mathmatically, k=1 and P=O is another possible case, but O cannot be
235  * represented by affine coordinate.
236  */
237 int
238 FUNC(compute_kP) (ac *X, const bn256 *K, const ac *P)
239 {
240   uint8_t index[86]; /* Lower 2-bit for index absolute value, msb is
241                         for sign (encoded as: 0 means 1, 1 means -1).  */
242   bn256 K_dash[1];
243   uint32_t k_is_even = bn256_is_even (K);
244   jpc Q[1], tmp[1], *dst;
245   int i;
246   int vk;
247   ac P3[1], P5[1], P7[1];
248   const ac *p_Pi[4];
249
250   if (point_is_on_the_curve (P) < 0)
251     return -1;
252
253   if (bn256_sub (K_dash, K, N) == 0)    /* >= N, it's too big.  */
254     return -1;
255
256   bn256_sub_uint (K_dash, K, k_is_even);
257   /* It keeps the condition: 1 <= K' <= N - 2, and K' is odd.  */
258
259   p_Pi[0] = P;
260   p_Pi[1] = P3;
261   p_Pi[2] = P5;
262   p_Pi[3] = P7;
263
264   {
265     jpc Q1[1];
266
267     memcpy (Q->x, P->x, sizeof (bn256));
268     memcpy (Q->y, P->y, sizeof (bn256));
269     memset (Q->z, 0, sizeof (bn256));
270     Q->z->word[0] = 1;
271
272     FUNC(jpc_double) (Q, Q);
273     FUNC(jpc_add_ac) (Q1, Q, P);
274     if (FUNC(jpc_to_ac) (P3, Q1) < 0) /* Never occurs, except coding errors.  */
275       return -1;
276     FUNC(jpc_double) (Q, Q);
277     FUNC(jpc_add_ac) (Q1, Q, P);
278     if (FUNC(jpc_to_ac) (P5, Q1) < 0) /* Never occurs, except coding errors.  */
279       return -1;
280
281     memcpy (Q->x, P3->x, sizeof (bn256));
282     memcpy (Q->y, P3->y, sizeof (bn256));
283     memset (Q->z, 0, sizeof (bn256));
284     Q->z->word[0] = 1;
285     FUNC(jpc_double) (Q, Q);
286     FUNC(jpc_add_ac) (Q1, Q, P);
287     if (FUNC(jpc_to_ac) (P7, Q1) < 0) /* Never occurs, except coding errors.  */
288       return -1;
289   }
290
291   /* Fill index.  */
292   vk = get_vk_kP (K_dash, 0);
293   for (i = 1; i < 86; i++)
294     {
295       int vk_next, is_even;
296
297       vk_next = get_vk_kP (K_dash, i);
298       is_even = ((vk_next & 1) == 0);
299       index[i-1] = (is_even << 7) | ((is_even?7-vk:vk-1) >> 1);
300       vk = vk_next + is_even;
301     }
302   index[85] = ((vk - 1) >> 1);
303
304   memset (Q->z, 0, sizeof (bn256)); /* infinity */
305   for (i = 85; i >= 0; i--)
306     {
307       FUNC(jpc_double) (Q, Q);
308       FUNC(jpc_double) (Q, Q);
309       FUNC(jpc_double) (Q, Q);
310       FUNC(jpc_add_ac_signed) (Q, Q, p_Pi[index[i]&0x03], index[i] >> 7);
311     }
312
313   dst = k_is_even ? Q : tmp;
314   FUNC(jpc_add_ac) (dst, Q, &precomputed_KG[0]);
315
316   return FUNC(jpc_to_ac) (X, Q);
317 }
318
319
320 /**
321  * @brief Compute signature (r,s) of hash string z with secret key d
322  */
323 void
324 FUNC(ecdsa) (bn256 *r, bn256 *s, const bn256 *z, const bn256 *d)
325 {
326   bn256 k[1];
327   ac KG[1];
328   bn512 tmp[1];
329   bn256 k_inv[1];
330   uint32_t carry;
331 #define borrow carry
332 #define tmp_k k_inv
333
334   do
335     {
336       do
337         {
338           bn256_random (k);
339           if (bn256_add_uint (k, k, 1))
340             continue;
341           if (bn256_sub (tmp_k, k, N) == 0)     /* >= N, it's too big.  */
342             continue;
343           /* 1 <= k <= N - 1 */
344           FUNC(compute_kG) (KG, k);
345           borrow = bn256_sub (r, KG->x, N);
346           if (borrow)
347             memcpy (r, KG->x, sizeof (bn256));
348           else
349             memcpy (KG->x, r, sizeof (bn256));
350         }
351       while (bn256_is_zero (r));
352
353       mod_inv (k_inv, k, N);
354       bn256_mul (tmp, r, d);
355       mod_reduce (s, tmp, N, MU_lower);
356       carry = bn256_add (s, s, z);
357       if (carry)
358         bn256_sub (s, s, N);
359       else
360         bn256_sub ((bn256 *)tmp, s, N);
361       bn256_mul (tmp, s, k_inv);
362       mod_reduce (s, tmp, N, MU_lower);
363     }
364   while (bn256_is_zero (s));
365
366 #undef tmp_k
367 #undef borrow
368 }