Implement writable key algorithm attributes
[gnuk/gnuk.git] / src / modp256r1.c
1 /*
2  * modp256r1.c -- modulo arithmetic for p256r1
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  * p256 =  2^256 - 2^224 + 2^192 + 2^96 - 1
26  */
27 #include <stdint.h>
28 #include <string.h>
29
30 #include "bn.h"
31 #include "modp256r1.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^224
38   0 ffffffff 00000000 00000000 00000000 00000000 00000000 00000000 00000000
39 2^256 - 2^224 + 2^192
40   0 ffffffff 00000001 00000000 00000000 00000000 00000000 00000000 00000000
41 2^256 - 2^224 + 2^192 + 2^96
42   0 ffffffff 00000001 00000000 00000000 00000001 00000000 00000000 00000000
43 2^256 - 2^224 + 2^192 + 2^96 - 1
44   0 ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff
45 */
46 const bn256 p256r1 = { {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
47                         0x00000000, 0x00000000, 0x00000001, 0xffffffff} };
48
49 /*
50  * Implementation Note.
51  *
52  * It's not always modulo p256r1.  The representation is redundant
53  * during computation.  For example, when we add the prime - 1 and 1,
54  * it won't overflow to 2^256, and the result is represented within
55  * 256-bit.
56  *
57  * It is guaranteed that modp256r1_reduce reduces to modulo p256r1.
58  */
59
60 /**
61  * @brief  X = (A + B) mod p256r1
62  */
63 void
64 modp256r1_add (bn256 *X, const bn256 *A, const bn256 *B)
65 {
66   uint32_t carry;
67   bn256 tmp[1];
68
69   carry = bn256_add (X, A, B);
70   if (carry)
71     bn256_sub (X, X, P256R1);
72   else
73     bn256_sub (tmp, X, P256R1);
74 }
75
76 /**
77  * @brief  X = (A - B) mod p256r1
78  */
79 void
80 modp256r1_sub (bn256 *X, const bn256 *A, const bn256 *B)
81 {
82   uint32_t borrow;
83   bn256 tmp[1];
84
85   borrow = bn256_sub (X, A, B);
86   if (borrow)
87     bn256_add (X, X, P256R1);
88   else
89     bn256_add (tmp, X, P256R1);
90 }
91
92 /**
93  * @brief  X = A mod p256r1
94  */
95 void
96 modp256r1_reduce (bn256 *X, const bn512 *A)
97 {
98   bn256 tmp[1];
99   uint32_t borrow;
100
101 #define S1 X
102 #define S2 tmp
103 #define S3 tmp
104 #define S4 tmp
105 #define S5 tmp
106 #define S6 tmp
107 #define S7 tmp
108 #define S8 tmp
109 #define S9 tmp
110
111   S1->word[7] = A->word[7];
112   S1->word[6] = A->word[6];
113   S1->word[5] = A->word[5];
114   S1->word[4] = A->word[4];
115   S1->word[3] = A->word[3];
116   S1->word[2] = A->word[2];
117   S1->word[1] = A->word[1];
118   S1->word[0] = A->word[0];
119   /* X = S1 */
120
121   S2->word[7] = A->word[15];
122   S2->word[6] = A->word[14];
123   S2->word[5] = A->word[13];
124   S2->word[4] = A->word[12];
125   S2->word[3] = A->word[11];
126   S2->word[2] = S2->word[1] = S2->word[0] = 0;
127   /* X += 2 * S2 */
128   modp256r1_add (X, X, S2);
129   modp256r1_add (X, X, S2);
130
131   S3->word[7] = 0;
132   S3->word[6] = A->word[15];
133   S3->word[5] = A->word[14];
134   S3->word[4] = A->word[13];
135   S3->word[3] = A->word[12];
136   S3->word[2] = S3->word[1] = S3->word[0] = 0;
137   /* X += 2 * S3 */
138   modp256r1_add (X, X, S3);
139   modp256r1_add (X, X, S3);
140
141   S4->word[7] = A->word[15];
142   S4->word[6] = A->word[14];
143   S4->word[5] = S4->word[4] = S4->word[3] = 0;
144   S4->word[2] = A->word[10];
145   S4->word[1] = A->word[9];
146   S4->word[0] = A->word[8];
147   /* X += S4 */
148   modp256r1_add (X, X, S4);
149
150   S5->word[7] = A->word[8];
151   S5->word[6] = A->word[13];
152   S5->word[5] = A->word[15];
153   S5->word[4] = A->word[14];
154   S5->word[3] = A->word[13];
155   S5->word[2] = A->word[11];
156   S5->word[1] = A->word[10];
157   S5->word[0] = A->word[9];
158   /* X += S5 */
159   modp256r1_add (X, X, S5);
160
161   S6->word[7] = A->word[10];
162   S6->word[6] = A->word[8];
163   S6->word[5] = S6->word[4] = S6->word[3] = 0;
164   S6->word[2] = A->word[13];
165   S6->word[1] = A->word[12];
166   S6->word[0] = A->word[11];
167   /* X -= S6 */
168   modp256r1_sub (X, X, S6);
169
170   S7->word[7] = A->word[11];
171   S7->word[6] = A->word[9];
172   S7->word[5] = S7->word[4] = 0;
173   S7->word[3] = A->word[15];
174   S7->word[2] = A->word[14];
175   S7->word[1] = A->word[13];
176   S7->word[0] = A->word[12];
177   /* X -= S7 */
178   modp256r1_sub (X, X, S7);
179
180   S8->word[7] = A->word[12];
181   S8->word[6] = 0;
182   S8->word[5] = A->word[10];
183   S8->word[4] = A->word[9];
184   S8->word[3] = A->word[8];
185   S8->word[2] = A->word[15];
186   S8->word[1] = A->word[14];
187   S8->word[0] = A->word[13];
188   /* X -= S8 */
189   modp256r1_sub (X, X, S8);
190
191   S9->word[7] = A->word[13];
192   S9->word[6] = 0;
193   S9->word[5] = A->word[11];
194   S9->word[4] = A->word[10];
195   S9->word[3] = A->word[9];
196   S9->word[2] = 0;
197   S9->word[1] = A->word[15];
198   S9->word[0] = A->word[14];
199   /* X -= S9 */
200   modp256r1_sub (X, X, S9);
201
202   borrow = bn256_sub (tmp, X, P256R1);
203   if (borrow)
204     memcpy (tmp, X, sizeof (bn256));
205   else
206     memcpy (X, tmp, sizeof (bn256));
207
208 #undef S1
209 #undef S2
210 #undef S3
211 #undef S4
212 #undef S5
213 #undef S6
214 #undef S7
215 #undef S8
216 #undef S9
217 }
218
219 /**
220  * @brief  X = (A * B) mod p256r1
221  */
222 void
223 modp256r1_mul (bn256 *X, const bn256 *A, const bn256 *B)
224 {
225   bn512 AB[1];
226
227   bn256_mul (AB, A, B);
228   modp256r1_reduce (X, AB);
229 }
230
231 /**
232  * @brief  X = A * A mod p256r1
233  */
234 void
235 modp256r1_sqr (bn256 *X, const bn256 *A)
236 {
237   bn512 AA[1];
238
239   bn256_sqr (AA, A);
240   modp256r1_reduce (X, AA);
241 }
242
243
244 /**
245  * @brief  X = (A << shift) mod p256r1
246  * @note   shift < 32
247  */
248 void
249 modp256r1_shift (bn256 *X, const bn256 *A, int shift)
250 {
251   uint32_t carry;
252 #define borrow carry
253   bn256 tmp[1];
254
255   carry = bn256_shift (X, A, shift);
256   if (shift < 0)
257     return;
258
259   memset (tmp, 0, sizeof (bn256));
260   tmp->word[7] = carry;
261   tmp->word[0] = carry;
262   modp256r1_add (X, X, tmp);
263
264   tmp->word[7] = 0;
265   tmp->word[0] = 0;
266   tmp->word[6] = carry;
267   tmp->word[3] = carry;
268   modp256r1_sub (X, X, tmp);
269
270   borrow = bn256_sub (tmp, X, P256R1);
271   if (borrow)
272     memcpy (tmp, X, sizeof (bn256));
273   else
274     memcpy (X, tmp, sizeof (bn256));
275 #undef borrow
276 }