Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(240)

Side by Side Diff: mozilla/security/nss/lib/freebl/ecl/ecp_256.c

Issue 12042100: Add an optimized 32-bit implementation of the NIST P-256 elliptic curve. (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/deps/third_party/nss/
Patch Set: Created 7 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
Property Changes:
Added: svn:eol-style
+ LF
OLDNEW
(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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698