Implement writable key algorithm attributes
[gnuk/gnuk.git] / src / bn.c
1 /*
2  * bn.c -- 256-bit (and 512-bit) bignum calculation
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 #include <stdint.h>
25 #include <string.h>
26 #ifndef BN256_NO_RANDOM
27 #include "random.h"
28 #endif
29 #include "bn.h"
30
31 uint32_t
32 bn256_add (bn256 *X, const bn256 *A, const bn256 *B)
33 {
34   int i;
35   uint32_t v;
36   uint32_t carry = 0;
37   uint32_t *px;
38   const uint32_t *pa, *pb;
39
40   px = X->word;
41   pa = A->word;
42   pb = B->word;
43
44   for (i = 0; i < BN256_WORDS; i++)
45     {
46       v = *pb;
47       *px = *pa + carry;
48       carry = (*px < carry);
49       *px += v;
50       carry += (*px < v);
51       px++;
52       pa++;
53       pb++;
54     }
55
56   return carry;
57 }
58
59 uint32_t
60 bn256_sub (bn256 *X, const bn256 *A, const bn256 *B)
61 {
62   int i;
63   uint32_t v;
64   uint32_t borrow = 0;
65   uint32_t *px;
66   const uint32_t *pa, *pb;
67
68   px = X->word;
69   pa = A->word;
70   pb = B->word;
71
72   for (i = 0; i < BN256_WORDS; i++)
73     {
74       uint32_t borrow0 = (*pa < borrow);
75
76       v = *pb;
77       *px = *pa - borrow;
78       borrow = (*px < v) + borrow0;
79       *px -= v;
80       px++;
81       pa++;
82       pb++;
83     }
84
85   return borrow;
86 }
87
88 uint32_t
89 bn256_add_uint (bn256 *X, const bn256 *A, uint32_t w)
90 {
91   int i;
92   uint32_t carry = w;
93   uint32_t *px;
94   const uint32_t *pa;
95
96   px = X->word;
97   pa = A->word;
98
99   for (i = 0; i < BN256_WORDS; i++)
100     {
101       *px = *pa + carry;
102       carry = (*px < carry);
103       px++;
104       pa++;
105     }
106
107   return carry;
108 }
109
110 uint32_t
111 bn256_sub_uint (bn256 *X, const bn256 *A, uint32_t w)
112 {
113   int i;
114   uint32_t borrow = w;
115   uint32_t *px;
116   const uint32_t *pa;
117
118   px = X->word;
119   pa = A->word;
120
121   for (i = 0; i < BN256_WORDS; i++)
122     {
123       uint32_t borrow0 = (*pa < borrow);
124
125       *px = *pa - borrow;
126       borrow = borrow0;
127       px++;
128       pa++;
129     }
130
131   return borrow;
132 }
133
134 #ifndef BN256_C_IMPLEMENTATION
135 #define ASM_IMPLEMENTATION 1
136 #endif
137 void
138 bn256_mul (bn512 *X, const bn256 *A, const bn256 *B)
139 {
140 #if ASM_IMPLEMENTATION
141 #include "muladd_256.h"
142   const uint32_t *s;
143   uint32_t *d;
144   uint32_t w;
145   uint32_t c;
146
147   memset (X->word, 0, sizeof (uint32_t)*BN256_WORDS*2);
148
149   s = A->word;  d = &X->word[0];  w = B->word[0];  MULADD_256 (s, d, w, c);
150   s = A->word;  d = &X->word[1];  w = B->word[1];  MULADD_256 (s, d, w, c);
151   s = A->word;  d = &X->word[2];  w = B->word[2];  MULADD_256 (s, d, w, c);
152   s = A->word;  d = &X->word[3];  w = B->word[3];  MULADD_256 (s, d, w, c);
153   s = A->word;  d = &X->word[4];  w = B->word[4];  MULADD_256 (s, d, w, c);
154   s = A->word;  d = &X->word[5];  w = B->word[5];  MULADD_256 (s, d, w, c);
155   s = A->word;  d = &X->word[6];  w = B->word[6];  MULADD_256 (s, d, w, c);
156   s = A->word;  d = &X->word[7];  w = B->word[7];  MULADD_256 (s, d, w, c);
157 #else
158   int i, j, k;
159   int i_beg, i_end;
160   uint32_t r0, r1, r2;
161
162   r0 = r1 = r2 = 0;
163   for (k = 0; k <= (BN256_WORDS - 1)*2; k++)
164     {
165       if (k < BN256_WORDS)
166         {
167           i_beg = 0;
168           i_end = k;
169         }
170       else
171         {
172           i_beg = k - BN256_WORDS + 1;
173           i_end = BN256_WORDS - 1;
174         }
175
176       for (i = i_beg; i <= i_end; i++)
177         {
178           uint64_t uv;
179           uint32_t u, v;
180           uint32_t carry;
181
182           j = k - i;
183
184           uv = ((uint64_t )A->word[i])*((uint64_t )B->word[j]);
185           v = uv;
186           u = (uv >> 32);
187           r0 += v;
188           carry = (r0 < v);
189           r1 += carry;
190           carry = (r1 < carry);
191           r1 += u;
192           carry += (r1 < u);
193           r2 += carry;
194         }
195
196       X->word[k] = r0;
197       r0 = r1;
198       r1 = r2;
199       r2 = 0;
200     }
201
202   X->word[k] = r0;
203 #endif
204 }
205
206 void
207 bn256_sqr (bn512 *X, const bn256 *A)
208 {
209 #if ASM_IMPLEMENTATION
210   int i;
211
212   memset (X->word, 0, sizeof (bn512));
213   for (i = 0; i < BN256_WORDS; i++)
214     {
215       uint32_t *wij = &X->word[i*2];
216       const uint32_t *xj = &A->word[i];
217       uint32_t x_i = *xj++;
218       uint32_t c;
219
220       asm (/* (C,R4,R5) := w_i_i + x_i*x_i; w_i_i := R5; */
221            "mov    %[c], #0\n\t"
222            "ldr    r5, [%[wij]]\n\t"          /* R5 := w_i_i; */
223            "mov    r4, %[c]\n\t"
224            "umlal  r5, r4, %[x_i], %[x_i]\n\t"
225            "str    r5, [%[wij]], #4\n\t"
226            "cmp    %[xj], %[x_max1]\n\t"
227            "bhi    0f\n\t"
228            "mov    r9, %[c]\n\t"  /* R9 := 0, the constant ZERO from here.  */
229            "beq    1f\n"
230    "2:\n\t"
231            "ldmia  %[xj]!, { r7, r8 }\n\t"
232            "ldmia  %[wij], { r5, r6 }\n\t"
233            /* (C,R4,R5) := (C,R4) + w_i_j + 2*x_i*x_j; */
234            "umull  r7, r12, %[x_i], r7\n\t"
235            "adds   r5, r5, r4\n\t"
236            "adc    r4, %[c], r9\n\t"
237            "adds   r5, r5, r7\n\t"
238            "adcs   r4, r4, r12\n\t"
239            "adc    %[c], r9, r9\n\t"
240            "adds   r5, r5, r7\n\t"
241            "adcs   r4, r4, r12\n\t"
242            "adc    %[c], %[c], r9\n\t"
243            /* (C,R4,R6) := (C,R4) + w_i_j + 2*x_i*x_j; */
244            "adds   r6, r6, r4\n\t"
245            "adc    r4, %[c], r9\n\t"
246            "umull  r7, r12, %[x_i], r8\n\t"
247            "adds   r6, r6, r7\n\t"
248            "adcs   r4, r4, r12\n\t"
249            "adc    %[c], r9, r9\n\t"
250            "adds   r6, r6, r7\n\t"
251            "adcs   r4, r4, r12\n\t"
252            "adc    %[c], %[c], r9\n\t"
253            /**/
254            "stmia  %[wij]!, { r5, r6 }\n\t"
255            "cmp    %[xj], %[x_max1]\n\t"
256            "bcc    2b\n\t"
257            "bne    0f\n"
258    "1:\n\t"
259            /* (C,R4,R5) := (C,R4) + w_i_j + 2*x_i*x_j; */
260            "ldr    r5, [%[wij]]\n\t"
261            "ldr    r6, [%[xj]], #4\n\t"
262            "adds   r5, r5, r4\n\t"
263            "adc    r4, %[c], r9\n\t"
264            "umull  r7, r12, %[x_i], r6\n\t"
265            "adds   r5, r5, r7\n\t"
266            "adcs   r4, r4, r12\n\t"
267            "adc    %[c], r9, r9\n\t"
268            "adds   r5, r5, r7\n\t"
269            "adcs   r4, r4, r12\n\t"
270            "adc    %[c], %[c], r9\n\t"
271            "str    r5, [%[wij]], #4\n"
272    "0:\n\t"
273            "ldr    r5, [%[wij]]\n\t"
274            "adds   r4, r4, r5\n\t"
275            "adc    %[c], %[c], #0\n\t"
276            "str    r4, [%[wij]], #4"
277            : [c] "=&r" (c), [wij] "=r" (wij), [xj] "=r" (xj)
278            : [x_i] "r" (x_i), [x_max1] "r" (&A->word[BN256_WORDS-1]),
279              "[wij]" (wij), "[xj]" (xj)
280            : "r4", "r5", "r6", "r7", "r8", "r9", "r12", "memory", "cc");
281
282       if (i < BN256_WORDS - 1)
283         *wij = c;
284     }
285 #else
286   int i, j, k;
287   int i_beg, i_end;
288   uint32_t r0, r1, r2;
289
290   r0 = r1 = r2 = 0;
291   for (k = 0; k <= (BN256_WORDS - 1)*2; k++)
292     {
293       if (k < BN256_WORDS)
294         {
295           i_beg = 0;
296           i_end = k/2;
297         }
298       else
299         {
300           i_beg = k - BN256_WORDS + 1;
301           i_end = k/2;
302         }
303
304       for (i = i_beg; i <= i_end; i++)
305         {
306           uint64_t uv;
307           uint32_t u, v;
308           uint32_t carry;
309
310           j = k - i;
311
312           uv = ((uint64_t )A->word[i])*((uint64_t )A->word[j]);
313           if (i < j)
314             {
315               r2 += ((uv >> 63) != 0);
316               uv <<= 1;
317             }
318           v = uv;
319           u = (uv >> 32);
320           r0 += v;
321           carry = (r0 < v);
322           r1 += carry;
323           carry = (r1 < carry);
324           r1 += u;
325           carry += (r1 < u);
326           r2 += carry;
327         }
328
329       X->word[k] = r0;
330       r0 = r1;
331       r1 = r2;
332       r2 = 0;
333     }
334
335   X->word[k] = r0;
336 #endif
337 }
338
339 uint32_t
340 bn256_shift (bn256 *X, const bn256 *A, int shift)
341 {
342   int i;
343   uint32_t carry = 0, next_carry;
344
345   if (shift > 0)
346     {
347       for (i = 0; i < BN256_WORDS; i++)
348         {
349           next_carry = A->word[i] >> (32 - shift);
350           X->word[i] = (A->word[i] << shift) | carry;
351           carry = next_carry;
352         }
353     }
354   else
355     {
356       shift = -shift;
357
358       for (i = BN256_WORDS - 1; i >= 0; i--)
359         {
360           next_carry = A->word[i] & ((1 << shift) - 1);
361           X->word[i] = (A->word[i] >> shift) | (carry << (32 - shift));
362           carry = next_carry;
363         }
364     }
365
366   return carry;
367 }
368
369 int
370 bn256_is_zero (const bn256 *X)
371 {
372   int i;
373   int r = 1;
374
375   for (i = 0; i < BN256_WORDS; i++)
376     r &=  (X->word[i] == 0);
377
378   return r;
379 }
380
381 int
382 bn256_is_even (const bn256 *X)
383 {
384   return !(X->word[0] & 1);
385 }
386
387 int
388 bn256_is_ge (const bn256 *A, const bn256 *B)
389 {
390   uint32_t borrow;
391   bn256 tmp[1];
392
393   borrow = bn256_sub (tmp, A, B);
394   return borrow == 0;
395 }
396
397
398 int
399 bn256_cmp (const bn256 *A, const bn256 *B)
400 {
401   uint32_t borrow;
402   int is_zero;
403   bn256 tmp[1];
404
405   borrow = bn256_sub (tmp, A, B);
406   is_zero = bn256_is_zero (tmp);
407   return is_zero ? 0 : (borrow ? -1 : 1);
408 }
409
410
411 #ifndef BN256_NO_RANDOM
412 void
413 bn256_random (bn256 *X)
414 {
415   const uint8_t *rand = random_bytes_get ();
416
417   X->word[7] = ((uint32_t *)rand)[7];
418   X->word[6] = ((uint32_t *)rand)[6];
419   X->word[5] = ((uint32_t *)rand)[5];
420   X->word[4] = ((uint32_t *)rand)[4];
421   X->word[3] = ((uint32_t *)rand)[3];
422   X->word[2] = ((uint32_t *)rand)[2];
423   X->word[1] = ((uint32_t *)rand)[1];
424   X->word[0] = ((uint32_t *)rand)[0];
425
426   random_bytes_free (rand);
427 }
428 #endif