|
OLD | NEW |
---|---|
(Empty) | |
1 /* This Source Code Form is subject to the terms of the Mozilla Public | |
2 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
4 | |
5 #include "ecp.h" | |
6 #include "mpi.h" | |
7 #include "mplogic.h" | |
8 #include "mpi-priv.h" | |
9 #include "prcpucfg.h" | |
10 #include <stdlib.h> | |
Ryan Sleevi
2013/01/25 03:50:36
Why is this header necessary? libutil tries to hid
wtc
2013/01/27 00:11:17
This is likely to have been copied from another fi
| |
11 | |
12 /* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be r. | |
13 * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to | |
14 * Elliptic Curve Cryptography. */ | |
15 mp_err | |
16 ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth) | |
17 { | |
18 mp_err res = MP_OKAY; | |
19 mp_size a_used = MP_USED(a); | |
20 int a_bits = mpl_significant_bits(a); | |
21 mp_digit carry; | |
22 | |
23 #ifdef ECL_THIRTY_TWO_BIT | |
24 mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0; | |
25 mp_digit r0, r1, r2, r3, r4, r5, r6, r7; | |
26 int r8; /* must be a signed value ! */ | |
27 #else | |
28 mp_digit a4=0, a5=0, a6=0, a7=0; | |
29 mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l; | |
30 mp_digit r0, r1, r2, r3; | |
31 int r4; /* must be a signed value ! */ | |
32 #endif | |
33 /* for polynomials larger than twice the field size | |
34 * use regular reduction */ | |
35 if (a_bits < 256) { | |
36 if (a == r) return MP_OKAY; | |
37 return mp_copy(a,r); | |
38 } | |
39 if (a_bits > 512) { | |
40 MP_CHECKOK(mp_mod(a, &meth->irr, r)); | |
41 } else { | |
42 | |
43 #ifdef ECL_THIRTY_TWO_BIT | |
44 switch (a_used) { | |
45 case 16: | |
46 a15 = MP_DIGIT(a,15); | |
47 case 15: | |
48 a14 = MP_DIGIT(a,14); | |
49 case 14: | |
50 a13 = MP_DIGIT(a,13); | |
51 case 13: | |
52 a12 = MP_DIGIT(a,12); | |
53 case 12: | |
54 a11 = MP_DIGIT(a,11); | |
55 case 11: | |
56 a10 = MP_DIGIT(a,10); | |
57 case 10: | |
58 a9 = MP_DIGIT(a,9); | |
59 case 9: | |
60 a8 = MP_DIGIT(a,8); | |
61 } | |
62 | |
63 r0 = MP_DIGIT(a,0); | |
64 r1 = MP_DIGIT(a,1); | |
65 r2 = MP_DIGIT(a,2); | |
66 r3 = MP_DIGIT(a,3); | |
67 r4 = MP_DIGIT(a,4); | |
68 r5 = MP_DIGIT(a,5); | |
69 r6 = MP_DIGIT(a,6); | |
70 r7 = MP_DIGIT(a,7); | |
71 | |
72 /* sum 1 */ | |
73 MP_ADD_CARRY(r3, a11, r3, 0, carry); | |
74 MP_ADD_CARRY(r4, a12, r4, carry, carry); | |
75 MP_ADD_CARRY(r5, a13, r5, carry, carry); | |
76 MP_ADD_CARRY(r6, a14, r6, carry, carry); | |
77 MP_ADD_CARRY(r7, a15, r7, carry, carry); | |
78 r8 = carry; | |
79 MP_ADD_CARRY(r3, a11, r3, 0, carry); | |
80 MP_ADD_CARRY(r4, a12, r4, carry, carry); | |
81 MP_ADD_CARRY(r5, a13, r5, carry, carry); | |
82 MP_ADD_CARRY(r6, a14, r6, carry, carry); | |
83 MP_ADD_CARRY(r7, a15, r7, carry, carry); | |
84 r8 += carry; | |
85 /* sum 2 */ | |
86 MP_ADD_CARRY(r3, a12, r3, 0, carry); | |
87 MP_ADD_CARRY(r4, a13, r4, carry, carry); | |
88 MP_ADD_CARRY(r5, a14, r5, carry, carry); | |
89 MP_ADD_CARRY(r6, a15, r6, carry, carry); | |
90 MP_ADD_CARRY(r7, 0, r7, carry, carry); | |
91 r8 += carry; | |
92 /* combine last bottom of sum 3 with second sum 2 */ | |
93 MP_ADD_CARRY(r0, a8, r0, 0, carry); | |
94 MP_ADD_CARRY(r1, a9, r1, carry, carry); | |
95 MP_ADD_CARRY(r2, a10, r2, carry, carry); | |
96 MP_ADD_CARRY(r3, a12, r3, carry, carry); | |
97 MP_ADD_CARRY(r4, a13, r4, carry, carry); | |
98 MP_ADD_CARRY(r5, a14, r5, carry, carry); | |
99 MP_ADD_CARRY(r6, a15, r6, carry, carry); | |
100 MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */ | |
101 r8 += carry; | |
102 /* sum 3 (rest of it)*/ | |
103 MP_ADD_CARRY(r6, a14, r6, 0, carry); | |
104 MP_ADD_CARRY(r7, 0, r7, carry, carry); | |
105 r8 += carry; | |
106 /* sum 4 (rest of it)*/ | |
107 MP_ADD_CARRY(r0, a9, r0, 0, carry); | |
108 MP_ADD_CARRY(r1, a10, r1, carry, carry); | |
109 MP_ADD_CARRY(r2, a11, r2, carry, carry); | |
110 MP_ADD_CARRY(r3, a13, r3, carry, carry); | |
111 MP_ADD_CARRY(r4, a14, r4, carry, carry); | |
112 MP_ADD_CARRY(r5, a15, r5, carry, carry); | |
113 MP_ADD_CARRY(r6, a13, r6, carry, carry); | |
114 MP_ADD_CARRY(r7, a8, r7, carry, carry); | |
115 r8 += carry; | |
116 /* diff 5 */ | |
117 MP_SUB_BORROW(r0, a11, r0, 0, carry); | |
118 MP_SUB_BORROW(r1, a12, r1, carry, carry); | |
119 MP_SUB_BORROW(r2, a13, r2, carry, carry); | |
120 MP_SUB_BORROW(r3, 0, r3, carry, carry); | |
121 MP_SUB_BORROW(r4, 0, r4, carry, carry); | |
122 MP_SUB_BORROW(r5, 0, r5, carry, carry); | |
123 MP_SUB_BORROW(r6, a8, r6, carry, carry); | |
124 MP_SUB_BORROW(r7, a10, r7, carry, carry); | |
125 r8 -= carry; | |
126 /* diff 6 */ | |
127 MP_SUB_BORROW(r0, a12, r0, 0, carry); | |
128 MP_SUB_BORROW(r1, a13, r1, carry, carry); | |
129 MP_SUB_BORROW(r2, a14, r2, carry, carry); | |
130 MP_SUB_BORROW(r3, a15, r3, carry, carry); | |
131 MP_SUB_BORROW(r4, 0, r4, carry, carry); | |
132 MP_SUB_BORROW(r5, 0, r5, carry, carry); | |
133 MP_SUB_BORROW(r6, a9, r6, carry, carry); | |
134 MP_SUB_BORROW(r7, a11, r7, carry, carry); | |
135 r8 -= carry; | |
136 /* diff 7 */ | |
137 MP_SUB_BORROW(r0, a13, r0, 0, carry); | |
138 MP_SUB_BORROW(r1, a14, r1, carry, carry); | |
139 MP_SUB_BORROW(r2, a15, r2, carry, carry); | |
140 MP_SUB_BORROW(r3, a8, r3, carry, carry); | |
141 MP_SUB_BORROW(r4, a9, r4, carry, carry); | |
142 MP_SUB_BORROW(r5, a10, r5, carry, carry); | |
143 MP_SUB_BORROW(r6, 0, r6, carry, carry); | |
144 MP_SUB_BORROW(r7, a12, r7, carry, carry); | |
145 r8 -= carry; | |
146 /* diff 8 */ | |
147 MP_SUB_BORROW(r0, a14, r0, 0, carry); | |
148 MP_SUB_BORROW(r1, a15, r1, carry, carry); | |
149 MP_SUB_BORROW(r2, 0, r2, carry, carry); | |
150 MP_SUB_BORROW(r3, a9, r3, carry, carry); | |
151 MP_SUB_BORROW(r4, a10, r4, carry, carry); | |
152 MP_SUB_BORROW(r5, a11, r5, carry, carry); | |
153 MP_SUB_BORROW(r6, 0, r6, carry, carry); | |
154 MP_SUB_BORROW(r7, a13, r7, carry, carry); | |
155 r8 -= carry; | |
156 | |
157 /* reduce the overflows */ | |
158 while (r8 > 0) { | |
159 mp_digit r8_d = r8; | |
160 MP_ADD_CARRY(r0, r8_d, r0, 0, carry); | |
161 MP_ADD_CARRY(r1, 0, r1, carry, carry); | |
162 MP_ADD_CARRY(r2, 0, r2, carry, carry); | |
163 MP_ADD_CARRY(r3, -r8_d, r3, carry, carry); | |
164 MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry); | |
165 MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry); | |
166 MP_ADD_CARRY(r6, -(r8_d+1), r6, carry, carry); | |
167 MP_ADD_CARRY(r7, (r8_d-1), r7, carry, carry); | |
168 r8 = carry; | |
169 } | |
170 | |
171 /* reduce the underflows */ | |
172 while (r8 < 0) { | |
173 mp_digit r8_d = -r8; | |
174 MP_SUB_BORROW(r0, r8_d, r0, 0, carry); | |
175 MP_SUB_BORROW(r1, 0, r1, carry, carry); | |
176 MP_SUB_BORROW(r2, 0, r2, carry, carry); | |
177 MP_SUB_BORROW(r3, -r8_d, r3, carry, carry); | |
178 MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry); | |
179 MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry); | |
180 MP_SUB_BORROW(r6, -(r8_d+1), r6, carry, carry); | |
181 MP_SUB_BORROW(r7, (r8_d-1), r7, carry, carry); | |
182 r8 = -carry; | |
183 } | |
184 if (a != r) { | |
185 MP_CHECKOK(s_mp_pad(r,8)); | |
186 } | |
187 MP_SIGN(r) = MP_ZPOS; | |
188 MP_USED(r) = 8; | |
189 | |
190 MP_DIGIT(r,7) = r7; | |
191 MP_DIGIT(r,6) = r6; | |
192 MP_DIGIT(r,5) = r5; | |
193 MP_DIGIT(r,4) = r4; | |
194 MP_DIGIT(r,3) = r3; | |
195 MP_DIGIT(r,2) = r2; | |
196 MP_DIGIT(r,1) = r1; | |
197 MP_DIGIT(r,0) = r0; | |
198 | |
199 /* final reduction if necessary */ | |
200 if ((r7 == MP_DIGIT_MAX) && | |
201 ((r6 > 1) || ((r6 == 1) && | |
202 (r5 || r4 || r3 || | |
203 ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX) | |
204 && (r0 == MP_DIGIT_MAX)))))) { | |
205 MP_CHECKOK(mp_sub(r, &meth->irr, r)); | |
206 } | |
207 #ifdef notdef | |
Ryan Sleevi
2013/01/25 03:50:36
?
wtc
2013/01/27 00:11:17
Bob Relyea often uses this to comment out a block
| |
208 | |
209 | |
210 /* smooth the negatives */ | |
211 while (MP_SIGN(r) != MP_ZPOS) { | |
212 MP_CHECKOK(mp_add(r, &meth->irr, r)); | |
213 } | |
214 while (MP_USED(r) > 8) { | |
215 MP_CHECKOK(mp_sub(r, &meth->irr, r)); | |
216 } | |
217 | |
218 /* final reduction if necessary */ | |
219 if (MP_DIGIT(r,7) >= MP_DIGIT(&meth->irr,7)) { | |
220 if (mp_cmp(r,&meth->irr) != MP_LT) { | |
221 MP_CHECKOK(mp_sub(r, &meth->irr, r)); | |
222 } | |
223 } | |
224 #endif | |
225 s_mp_clamp(r); | |
226 #else | |
227 switch (a_used) { | |
228 case 8: | |
229 a7 = MP_DIGIT(a,7); | |
230 case 7: | |
231 a6 = MP_DIGIT(a,6); | |
232 case 6: | |
233 a5 = MP_DIGIT(a,5); | |
234 case 5: | |
235 a4 = MP_DIGIT(a,4); | |
236 } | |
237 a7l = a7 << 32; | |
238 a7h = a7 >> 32; | |
239 a6l = a6 << 32; | |
240 a6h = a6 >> 32; | |
241 a5l = a5 << 32; | |
242 a5h = a5 >> 32; | |
243 a4l = a4 << 32; | |
244 a4h = a4 >> 32; | |
245 r3 = MP_DIGIT(a,3); | |
246 r2 = MP_DIGIT(a,2); | |
247 r1 = MP_DIGIT(a,1); | |
248 r0 = MP_DIGIT(a,0); | |
249 | |
250 /* sum 1 */ | |
251 MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry); | |
252 MP_ADD_CARRY(r2, a6, r2, carry, carry); | |
253 MP_ADD_CARRY(r3, a7, r3, carry, carry); | |
254 r4 = carry; | |
255 MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry); | |
256 MP_ADD_CARRY(r2, a6, r2, carry, carry); | |
257 MP_ADD_CARRY(r3, a7, r3, carry, carry); | |
258 r4 += carry; | |
259 /* sum 2 */ | |
260 MP_ADD_CARRY(r1, a6l, r1, 0, carry); | |
261 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry); | |
262 MP_ADD_CARRY(r3, a7h, r3, carry, carry); | |
263 r4 += carry; | |
264 MP_ADD_CARRY(r1, a6l, r1, 0, carry); | |
265 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry); | |
266 MP_ADD_CARRY(r3, a7h, r3, carry, carry); | |
267 r4 += carry; | |
268 | |
269 /* sum 3 */ | |
270 MP_ADD_CARRY(r0, a4, r0, 0, carry); | |
271 MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry); | |
272 MP_ADD_CARRY(r2, 0, r2, carry, carry); | |
273 MP_ADD_CARRY(r3, a7, r3, carry, carry); | |
274 r4 += carry; | |
275 /* sum 4 */ | |
276 MP_ADD_CARRY(r0, a4h | a5l, r0, 0, carry); | |
277 MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry); | |
278 MP_ADD_CARRY(r2, a7, r2, carry, carry); | |
279 MP_ADD_CARRY(r3, a6h | a4l, r3, carry, carry); | |
280 r4 += carry; | |
281 /* diff 5 */ | |
282 MP_SUB_BORROW(r0, a5h | a6l, r0, 0, carry); | |
283 MP_SUB_BORROW(r1, a6h, r1, carry, carry); | |
284 MP_SUB_BORROW(r2, 0, r2, carry, carry); | |
285 MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry); | |
286 r4 -= carry; | |
287 /* diff 6 */ | |
288 MP_SUB_BORROW(r0, a6, r0, 0, carry); | |
289 MP_SUB_BORROW(r1, a7, r1, carry, carry); | |
290 MP_SUB_BORROW(r2, 0, r2, carry, carry); | |
291 MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry); | |
292 r4 -= carry; | |
293 /* diff 7 */ | |
294 MP_SUB_BORROW(r0, a6h|a7l, r0, 0, carry); | |
295 MP_SUB_BORROW(r1, a7h|a4l, r1, carry, carry); | |
296 MP_SUB_BORROW(r2, a4h|a5l, r2, carry, carry); | |
297 MP_SUB_BORROW(r3, a6l, r3, carry, carry); | |
298 r4 -= carry; | |
299 /* diff 8 */ | |
300 MP_SUB_BORROW(r0, a7, r0, 0, carry); | |
301 MP_SUB_BORROW(r1, a4h<<32, r1, carry, carry); | |
302 MP_SUB_BORROW(r2, a5, r2, carry, carry); | |
303 MP_SUB_BORROW(r3, a6h<<32, r3, carry, carry); | |
304 r4 -= carry; | |
305 | |
306 /* reduce the overflows */ | |
307 while (r4 > 0) { | |
308 mp_digit r4_long = r4; | |
309 mp_digit r4l = (r4_long << 32); | |
310 MP_ADD_CARRY(r0, r4_long, r0, 0, carry); | |
311 MP_ADD_CARRY(r1, -r4l, r1, carry, carry); | |
312 MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry); | |
313 MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry); | |
314 r4 = carry; | |
315 } | |
316 | |
317 /* reduce the underflows */ | |
318 while (r4 < 0) { | |
319 mp_digit r4_long = -r4; | |
320 mp_digit r4l = (r4_long << 32); | |
321 MP_SUB_BORROW(r0, r4_long, r0, 0, carry); | |
322 MP_SUB_BORROW(r1, -r4l, r1, carry, carry); | |
323 MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry); | |
324 MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry); | |
325 r4 = -carry; | |
326 } | |
327 | |
328 if (a != r) { | |
329 MP_CHECKOK(s_mp_pad(r,4)); | |
330 } | |
331 MP_SIGN(r) = MP_ZPOS; | |
332 MP_USED(r) = 4; | |
333 | |
334 MP_DIGIT(r,3) = r3; | |
335 MP_DIGIT(r,2) = r2; | |
336 MP_DIGIT(r,1) = r1; | |
337 MP_DIGIT(r,0) = r0; | |
338 | |
339 /* final reduction if necessary */ | |
340 if ((r3 > 0xFFFFFFFF00000001ULL) || | |
341 ((r3 == 0xFFFFFFFF00000001ULL) && | |
342 (r2 || (r1 >> 32)|| | |
343 (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) { | |
344 /* very rare, just use mp_sub */ | |
345 MP_CHECKOK(mp_sub(r, &meth->irr, r)); | |
346 } | |
347 | |
348 s_mp_clamp(r); | |
349 #endif | |
350 } | |
351 | |
352 CLEANUP: | |
353 return res; | |
354 } | |
355 | |
356 /* Compute the square of polynomial a, reduce modulo p256. Store the | |
357 * result in r. r could be a. Uses optimized modular reduction for p256. | |
358 */ | |
359 mp_err | |
360 ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) | |
361 { | |
362 mp_err res = MP_OKAY; | |
363 | |
364 MP_CHECKOK(mp_sqr(a, r)); | |
365 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); | |
366 CLEANUP: | |
367 return res; | |
368 } | |
369 | |
370 /* Compute the product of two polynomials a and b, reduce modulo p256. | |
371 * Store the result in r. r could be a or b; a could be b. Uses | |
372 * optimized modular reduction for p256. */ | |
373 mp_err | |
374 ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r, | |
375 const GFMethod *meth) | |
376 { | |
377 mp_err res = MP_OKAY; | |
378 | |
379 MP_CHECKOK(mp_mul(a, b, r)); | |
380 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); | |
381 CLEANUP: | |
382 return res; | |
383 } | |
384 | |
385 #ifdef IS_LITTLE_ENDIAN | |
wtc
2013/01/25 02:32:49
This is an existing NSS file. Our patch adds lines
| |
386 /* These are defined in ecp_256_32.c */ | |
387 extern mp_err ec_GFp_nistp256_base_point_mul( | |
388 const mp_int *n, | |
389 mp_int *out_x, mp_int *out_y, | |
390 const ECGroup *group); | |
391 | |
392 extern mp_err ec_GFp_nistp256_point_mul( | |
393 const mp_int *n, | |
394 const mp_int *in_x, const mp_int *in_y, | |
395 mp_int *out_x, mp_int *out_y, | |
396 const ECGroup *group); | |
397 | |
398 extern mp_err ec_GFp_nistp256_points_mul_vartime( | |
399 const mp_int *n1, const mp_int *n2, | |
400 const mp_int *in_x, const mp_int *in_y, | |
401 mp_int *out_x, mp_int *out_y, | |
402 const ECGroup *group); | |
403 #endif | |
404 | |
405 /* Wire in fast field arithmetic and precomputation of base point for | |
406 * named curves. */ | |
407 mp_err | |
408 ec_group_set_gfp256(ECGroup *group, ECCurveName name) | |
409 { | |
410 if (name == ECCurve_NIST_P256) { | |
411 group->meth->field_mod = &ec_GFp_nistp256_mod; | |
412 group->meth->field_mul = &ec_GFp_nistp256_mul; | |
413 group->meth->field_sqr = &ec_GFp_nistp256_sqr; | |
414 #ifdef IS_LITTLE_ENDIAN | |
415 group->base_point_mul = &ec_GFp_nistp256_base_point_mul; | |
416 group->point_mul = &ec_GFp_nistp256_point_mul; | |
417 group->points_mul = &ec_GFp_nistp256_points_mul_vartime; | |
418 #endif | |
419 } | |
420 return MP_OKAY; | |
421 } | |
OLD | NEW |