docker: source checking container
[gnuk/gnuk.git] / src / mod25638.c
1 /*
2  * mod25638.c -- modulo arithmetic of 2^256-38 for 2^255-19 field
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  * The field is \Z/(2^255-19)
26  *
27  * We use radix-32.  During computation, it's not reduced to 2^255-19,
28  * but it is represented in 256-bit (it is redundant representation),
29  * that is, something like 2^256-38.
30  *
31  * The idea is, keeping within 256-bit until it will be converted to
32  * affine coordinates.
33  */
34
35 #include <stdint.h>
36 #include <string.h>
37
38 #include "bn.h"
39 #include "mod25638.h"
40
41 #ifndef BN256_C_IMPLEMENTATION
42 #define ASM_IMPLEMENTATION 1
43 #endif
44
45 #if ASM_IMPLEMENTATION
46 #include "muladd_256.h"
47 #define ADDWORD_256(d_,s_,w_,c_)                        \
48  asm ( "ldmia  %[s]!, { r4, r5, r6, r7 } \n\t"          \
49        "adds   r4, r4, %[w]             \n\t"           \
50        "adcs   r5, r5, #0               \n\t"           \
51        "adcs   r6, r6, #0               \n\t"           \
52        "adcs   r7, r7, #0               \n\t"           \
53        "stmia  %[d]!, { r4, r5, r6, r7 }\n\t"           \
54        "ldmia  %[s]!, { r4, r5, r6, r7 } \n\t"          \
55        "adcs   r4, r4, #0               \n\t"           \
56        "adcs   r5, r5, #0               \n\t"           \
57        "adcs   r6, r6, #0               \n\t"           \
58        "adcs   r7, r7, #0               \n\t"           \
59        "stmia  %[d]!, { r4, r5, r6, r7 }\n\t"           \
60        "mov    %[c], #0                 \n\t"           \
61        "adc    %[c], %[c], #0"                          \
62        : [s] "=&r" (s_), [d] "=&r" (d_), [c] "=&r" (c_) \
63        : "[s]" (s_), "[d]" (d_), [w] "r" (w_)           \
64        : "r4", "r5", "r6", "r7", "memory", "cc" )
65 #endif
66
67 /*
68 256      224      192      160      128       96       64       32        0
69 2^256
70   1 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
71 2^256 - 16
72   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffff0
73 2^256 - 16 - 2
74   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffee
75 2^256 - 16 - 2 - 1
76   0 ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffed
77 */
78 const bn256 p25519[1] = {
79   {{ 0xffffffed, 0xffffffff, 0xffffffff, 0xffffffff,
80      0xffffffff, 0xffffffff, 0xffffffff, 0x7fffffff }} };
81
82
83 /*
84  * Implementation Note.
85  *
86  * It's not always modulo n25638.  The representation is redundant
87  * during computation.  For example, when we add the number - 1 and 1,
88  * it won't overflow to 2^256, and the result is represented within
89  * 256-bit.
90  */
91
92
93 /**
94  * @brief  X = (A + B) mod 2^256-38
95  */
96 void
97 mod25638_add (bn256 *X, const bn256 *A, const bn256 *B)
98 {
99   uint32_t carry;
100
101   carry = bn256_add (X, A, B);
102   carry = bn256_add_uint (X, X, carry*38);
103   X->word[0] += carry * 38;
104 }
105
106 /**
107  * @brief  X = (A - B) mod 2^256-38
108  */
109 void
110 mod25638_sub (bn256 *X, const bn256 *A, const bn256 *B)
111 {
112   uint32_t borrow;
113
114   borrow = bn256_sub (X, A, B);
115   borrow = bn256_sub_uint (X, X, borrow*38);
116   X->word[0] -= borrow * 38;
117 }
118
119
120 /**
121  * @brief  X = A mod 2^256-38
122  *
123  * Note that the second argument is not "const bn512 *".
124  * A is modified during the computation of modulo.
125  *
126  * It's not precisely modulo 2^256-38 for all cases,
127  * but result may be redundant.
128  */
129 static void
130 mod25638_reduce (bn256 *X, bn512 *A)
131 {
132   const uint32_t *s;
133   uint32_t *d;
134   uint32_t w;
135
136 #if ASM_IMPLEMENTATION
137   uint32_t c, c0;
138
139   s = &A->word[8]; d = &A->word[0]; w = 38; MULADD_256 (s, d, w, c);
140   c0 = A->word[8] * 38;
141   d = &X->word[0];
142   s = &A->word[0];
143   ADDWORD_256 (d, s, c0, c);
144   X->word[0] += c * 38;
145 #else
146   s = &A->word[8]; d = &A->word[0]; w = 38;
147   {
148     int i;
149     uint64_t r;
150     uint32_t carry;
151
152     r = 0;
153     for (i = 0; i < BN256_WORDS; i++)
154       {
155         uint64_t uv;
156
157         r += d[i];
158         carry = (r < d[i]);
159
160         uv = ((uint64_t)s[i])*w;
161         r += uv;
162         carry += (r < uv);
163
164         d[i] = (uint32_t)r;
165         r = ((r >> 32) | ((uint64_t)carry << 32));
166       }
167
168     carry = bn256_add_uint (X, (bn256 *)A, r * 38);
169     X->word[0] += carry * 38;
170   }
171 #endif
172 }
173
174 /**
175  * @brief  X = (A * B) mod 2^256-38
176  */
177 void
178 mod25638_mul (bn256 *X, const bn256 *A, const bn256 *B)
179 {
180   bn512 tmp[1];
181
182   bn256_mul (tmp, A, B);
183   mod25638_reduce (X, tmp);
184 }
185
186 /**
187  * @brief  X = A * A mod 2^256-38
188  */
189 void
190 mod25638_sqr (bn256 *X, const bn256 *A)
191 {
192   bn512 tmp[1];
193
194   bn256_sqr (tmp, A);
195   mod25638_reduce (X, tmp);
196 }
197
198
199 /**
200  * @brief  X = (A << shift) mod 2^256-38
201  * @note   shift < 32
202  */
203 void
204 mod25638_shift (bn256 *X, const bn256 *A, int shift)
205 {
206   uint32_t carry;
207   bn256 tmp[1];
208
209   carry = bn256_shift (X, A, shift);
210   if (shift < 0)
211     return;
212
213   memset (tmp, 0, sizeof (bn256));
214   tmp->word[0] = (carry << 1);
215   /* tmp->word[1] = (carry >> 31);  always zero.  */
216   tmp->word[0] = tmp->word[0] + (carry << 2);
217   tmp->word[1] = (tmp->word[0] < (carry << 2)) + (carry >> 30);
218   tmp->word[0] = tmp->word[0] + (carry << 5);
219   tmp->word[1] = tmp->word[1] + (tmp->word[0] < (carry << 5)) + (carry >> 27);
220
221   mod25638_add (X, X, tmp);
222 }
223
224
225 /*
226  * @brief  X = A mod 2^255-19
227  *
228  * It's precisely modulo 2^255-19 (unlike mod25638_reduce).
229  */
230 void
231 mod25519_reduce (bn256 *X)
232 {
233   uint32_t q;
234   bn256 r0[1], r1[1];
235   int flag;
236
237   memcpy (r0, X, sizeof (bn256));
238   q = (r0->word[7] >> 31);
239   r0->word[7] &= 0x7fffffff;
240   if (q)
241     {
242       bn256_add_uint (r0, r0, 19);
243       q = (r0->word[7] >> 31);
244       r0->word[7] &= 0x7fffffff;
245       if (q)
246         {
247           bn256_add_uint (r1, r0, 19);
248           q = (r1->word[7] >> 31);
249           r1->word[7] &= 0x7fffffff;
250           flag = 0;
251         }
252       else
253         flag = 1;
254     }
255   else
256     {
257       bn256_add_uint (r1, r0, 19);
258       q = (r1->word[7] >> 31);   /* dummy */
259       r1->word[7] &= 0x7fffffff; /* dummy */
260       if (q)
261         flag = 2;
262       else
263         flag = 3;
264     }
265
266   if (flag)
267     {
268       bn256_add_uint (r1, r0, 19);
269       q = (r1->word[7] >> 31);
270       r1->word[7] &= 0x7fffffff;
271       if (q)
272         memcpy (X, r1, sizeof (bn256));
273       else
274         memcpy (X, r0, sizeof (bn256));
275     }
276   else
277     {
278       if (q)
279         {
280           asm volatile ("" : : "r" (q) : "memory");
281           memcpy (X, r1, sizeof (bn256));
282           asm volatile ("" : : "r" (q) : "memory");
283         }
284       else
285         memcpy (X, r1, sizeof (bn256));
286     }
287 }