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