security/nss/lib/freebl/ecl/ecp_256.c@6474c204b198
security/nss/lib/freebl/ecl/ecp_256.c
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
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/. */
5 #include "ecp.h"
6 #include "mpi.h"
7 #include "mplogic.h"
8 #include "mpi-priv.h"
10 /* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be r.
11 * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to
12 * Elliptic Curve Cryptography. */
13 static mp_err
14 ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
15 {
16 mp_err res = MP_OKAY;
17 mp_size a_used = MP_USED(a);
18 int a_bits = mpl_significant_bits(a);
19 mp_digit carry;
21 #ifdef ECL_THIRTY_TWO_BIT
22 mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0;
23 mp_digit r0, r1, r2, r3, r4, r5, r6, r7;
24 int r8; /* must be a signed value ! */
25 #else
26 mp_digit a4=0, a5=0, a6=0, a7=0;
27 mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l;
28 mp_digit r0, r1, r2, r3;
29 int r4; /* must be a signed value ! */
30 #endif
31 /* for polynomials larger than twice the field size
32 * use regular reduction */
33 if (a_bits < 256) {
34 if (a == r) return MP_OKAY;
35 return mp_copy(a,r);
36 }
37 if (a_bits > 512) {
38 MP_CHECKOK(mp_mod(a, &meth->irr, r));
39 } else {
41 #ifdef ECL_THIRTY_TWO_BIT
42 switch (a_used) {
43 case 16:
44 a15 = MP_DIGIT(a,15);
45 case 15:
46 a14 = MP_DIGIT(a,14);
47 case 14:
48 a13 = MP_DIGIT(a,13);
49 case 13:
50 a12 = MP_DIGIT(a,12);
51 case 12:
52 a11 = MP_DIGIT(a,11);
53 case 11:
54 a10 = MP_DIGIT(a,10);
55 case 10:
56 a9 = MP_DIGIT(a,9);
57 case 9:
58 a8 = MP_DIGIT(a,8);
59 }
61 r0 = MP_DIGIT(a,0);
62 r1 = MP_DIGIT(a,1);
63 r2 = MP_DIGIT(a,2);
64 r3 = MP_DIGIT(a,3);
65 r4 = MP_DIGIT(a,4);
66 r5 = MP_DIGIT(a,5);
67 r6 = MP_DIGIT(a,6);
68 r7 = MP_DIGIT(a,7);
70 /* sum 1 */
71 MP_ADD_CARRY(r3, a11, r3, 0, carry);
72 MP_ADD_CARRY(r4, a12, r4, carry, carry);
73 MP_ADD_CARRY(r5, a13, r5, carry, carry);
74 MP_ADD_CARRY(r6, a14, r6, carry, carry);
75 MP_ADD_CARRY(r7, a15, r7, carry, carry);
76 r8 = carry;
77 MP_ADD_CARRY(r3, a11, r3, 0, carry);
78 MP_ADD_CARRY(r4, a12, r4, carry, carry);
79 MP_ADD_CARRY(r5, a13, r5, carry, carry);
80 MP_ADD_CARRY(r6, a14, r6, carry, carry);
81 MP_ADD_CARRY(r7, a15, r7, carry, carry);
82 r8 += carry;
83 /* sum 2 */
84 MP_ADD_CARRY(r3, a12, r3, 0, carry);
85 MP_ADD_CARRY(r4, a13, r4, carry, carry);
86 MP_ADD_CARRY(r5, a14, r5, carry, carry);
87 MP_ADD_CARRY(r6, a15, r6, carry, carry);
88 MP_ADD_CARRY(r7, 0, r7, carry, carry);
89 r8 += carry;
90 /* combine last bottom of sum 3 with second sum 2 */
91 MP_ADD_CARRY(r0, a8, r0, 0, carry);
92 MP_ADD_CARRY(r1, a9, r1, carry, carry);
93 MP_ADD_CARRY(r2, a10, r2, carry, carry);
94 MP_ADD_CARRY(r3, a12, r3, carry, carry);
95 MP_ADD_CARRY(r4, a13, r4, carry, carry);
96 MP_ADD_CARRY(r5, a14, r5, carry, carry);
97 MP_ADD_CARRY(r6, a15, r6, carry, carry);
98 MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */
99 r8 += carry;
100 /* sum 3 (rest of it)*/
101 MP_ADD_CARRY(r6, a14, r6, 0, carry);
102 MP_ADD_CARRY(r7, 0, r7, carry, carry);
103 r8 += carry;
104 /* sum 4 (rest of it)*/
105 MP_ADD_CARRY(r0, a9, r0, 0, carry);
106 MP_ADD_CARRY(r1, a10, r1, carry, carry);
107 MP_ADD_CARRY(r2, a11, r2, carry, carry);
108 MP_ADD_CARRY(r3, a13, r3, carry, carry);
109 MP_ADD_CARRY(r4, a14, r4, carry, carry);
110 MP_ADD_CARRY(r5, a15, r5, carry, carry);
111 MP_ADD_CARRY(r6, a13, r6, carry, carry);
112 MP_ADD_CARRY(r7, a8, r7, carry, carry);
113 r8 += carry;
114 /* diff 5 */
115 MP_SUB_BORROW(r0, a11, r0, 0, carry);
116 MP_SUB_BORROW(r1, a12, r1, carry, carry);
117 MP_SUB_BORROW(r2, a13, r2, carry, carry);
118 MP_SUB_BORROW(r3, 0, r3, carry, carry);
119 MP_SUB_BORROW(r4, 0, r4, carry, carry);
120 MP_SUB_BORROW(r5, 0, r5, carry, carry);
121 MP_SUB_BORROW(r6, a8, r6, carry, carry);
122 MP_SUB_BORROW(r7, a10, r7, carry, carry);
123 r8 -= carry;
124 /* diff 6 */
125 MP_SUB_BORROW(r0, a12, r0, 0, carry);
126 MP_SUB_BORROW(r1, a13, r1, carry, carry);
127 MP_SUB_BORROW(r2, a14, r2, carry, carry);
128 MP_SUB_BORROW(r3, a15, r3, carry, carry);
129 MP_SUB_BORROW(r4, 0, r4, carry, carry);
130 MP_SUB_BORROW(r5, 0, r5, carry, carry);
131 MP_SUB_BORROW(r6, a9, r6, carry, carry);
132 MP_SUB_BORROW(r7, a11, r7, carry, carry);
133 r8 -= carry;
134 /* diff 7 */
135 MP_SUB_BORROW(r0, a13, r0, 0, carry);
136 MP_SUB_BORROW(r1, a14, r1, carry, carry);
137 MP_SUB_BORROW(r2, a15, r2, carry, carry);
138 MP_SUB_BORROW(r3, a8, r3, carry, carry);
139 MP_SUB_BORROW(r4, a9, r4, carry, carry);
140 MP_SUB_BORROW(r5, a10, r5, carry, carry);
141 MP_SUB_BORROW(r6, 0, r6, carry, carry);
142 MP_SUB_BORROW(r7, a12, r7, carry, carry);
143 r8 -= carry;
144 /* diff 8 */
145 MP_SUB_BORROW(r0, a14, r0, 0, carry);
146 MP_SUB_BORROW(r1, a15, r1, carry, carry);
147 MP_SUB_BORROW(r2, 0, r2, carry, carry);
148 MP_SUB_BORROW(r3, a9, r3, carry, carry);
149 MP_SUB_BORROW(r4, a10, r4, carry, carry);
150 MP_SUB_BORROW(r5, a11, r5, carry, carry);
151 MP_SUB_BORROW(r6, 0, r6, carry, carry);
152 MP_SUB_BORROW(r7, a13, r7, carry, carry);
153 r8 -= carry;
155 /* reduce the overflows */
156 while (r8 > 0) {
157 mp_digit r8_d = r8;
158 MP_ADD_CARRY(r0, r8_d, r0, 0, carry);
159 MP_ADD_CARRY(r1, 0, r1, carry, carry);
160 MP_ADD_CARRY(r2, 0, r2, carry, carry);
161 MP_ADD_CARRY(r3, 0-r8_d, r3, carry, carry);
162 MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry);
163 MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry);
164 MP_ADD_CARRY(r6, 0-(r8_d+1), r6, carry, carry);
165 MP_ADD_CARRY(r7, (r8_d-1), r7, carry, carry);
166 r8 = carry;
167 }
169 /* reduce the underflows */
170 while (r8 < 0) {
171 mp_digit r8_d = -r8;
172 MP_SUB_BORROW(r0, r8_d, r0, 0, carry);
173 MP_SUB_BORROW(r1, 0, r1, carry, carry);
174 MP_SUB_BORROW(r2, 0, r2, carry, carry);
175 MP_SUB_BORROW(r3, 0-r8_d, r3, carry, carry);
176 MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry);
177 MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry);
178 MP_SUB_BORROW(r6, 0-(r8_d+1), r6, carry, carry);
179 MP_SUB_BORROW(r7, (r8_d-1), r7, carry, carry);
180 r8 = 0-carry;
181 }
182 if (a != r) {
183 MP_CHECKOK(s_mp_pad(r,8));
184 }
185 MP_SIGN(r) = MP_ZPOS;
186 MP_USED(r) = 8;
188 MP_DIGIT(r,7) = r7;
189 MP_DIGIT(r,6) = r6;
190 MP_DIGIT(r,5) = r5;
191 MP_DIGIT(r,4) = r4;
192 MP_DIGIT(r,3) = r3;
193 MP_DIGIT(r,2) = r2;
194 MP_DIGIT(r,1) = r1;
195 MP_DIGIT(r,0) = r0;
197 /* final reduction if necessary */
198 if ((r7 == MP_DIGIT_MAX) &&
199 ((r6 > 1) || ((r6 == 1) &&
200 (r5 || r4 || r3 ||
201 ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX)
202 && (r0 == MP_DIGIT_MAX)))))) {
203 MP_CHECKOK(mp_sub(r, &meth->irr, r));
204 }
206 s_mp_clamp(r);
207 #else
208 switch (a_used) {
209 case 8:
210 a7 = MP_DIGIT(a,7);
211 case 7:
212 a6 = MP_DIGIT(a,6);
213 case 6:
214 a5 = MP_DIGIT(a,5);
215 case 5:
216 a4 = MP_DIGIT(a,4);
217 }
218 a7l = a7 << 32;
219 a7h = a7 >> 32;
220 a6l = a6 << 32;
221 a6h = a6 >> 32;
222 a5l = a5 << 32;
223 a5h = a5 >> 32;
224 a4l = a4 << 32;
225 a4h = a4 >> 32;
226 r3 = MP_DIGIT(a,3);
227 r2 = MP_DIGIT(a,2);
228 r1 = MP_DIGIT(a,1);
229 r0 = MP_DIGIT(a,0);
231 /* sum 1 */
232 MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry);
233 MP_ADD_CARRY(r2, a6, r2, carry, carry);
234 MP_ADD_CARRY(r3, a7, r3, carry, carry);
235 r4 = carry;
236 MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry);
237 MP_ADD_CARRY(r2, a6, r2, carry, carry);
238 MP_ADD_CARRY(r3, a7, r3, carry, carry);
239 r4 += carry;
240 /* sum 2 */
241 MP_ADD_CARRY(r1, a6l, r1, 0, carry);
242 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
243 MP_ADD_CARRY(r3, a7h, r3, carry, carry);
244 r4 += carry;
245 MP_ADD_CARRY(r1, a6l, r1, 0, carry);
246 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
247 MP_ADD_CARRY(r3, a7h, r3, carry, carry);
248 r4 += carry;
250 /* sum 3 */
251 MP_ADD_CARRY(r0, a4, r0, 0, carry);
252 MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry);
253 MP_ADD_CARRY(r2, 0, r2, carry, carry);
254 MP_ADD_CARRY(r3, a7, r3, carry, carry);
255 r4 += carry;
256 /* sum 4 */
257 MP_ADD_CARRY(r0, a4h | a5l, r0, 0, carry);
258 MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry);
259 MP_ADD_CARRY(r2, a7, r2, carry, carry);
260 MP_ADD_CARRY(r3, a6h | a4l, r3, carry, carry);
261 r4 += carry;
262 /* diff 5 */
263 MP_SUB_BORROW(r0, a5h | a6l, r0, 0, carry);
264 MP_SUB_BORROW(r1, a6h, r1, carry, carry);
265 MP_SUB_BORROW(r2, 0, r2, carry, carry);
266 MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry);
267 r4 -= carry;
268 /* diff 6 */
269 MP_SUB_BORROW(r0, a6, r0, 0, carry);
270 MP_SUB_BORROW(r1, a7, r1, carry, carry);
271 MP_SUB_BORROW(r2, 0, r2, carry, carry);
272 MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry);
273 r4 -= carry;
274 /* diff 7 */
275 MP_SUB_BORROW(r0, a6h|a7l, r0, 0, carry);
276 MP_SUB_BORROW(r1, a7h|a4l, r1, carry, carry);
277 MP_SUB_BORROW(r2, a4h|a5l, r2, carry, carry);
278 MP_SUB_BORROW(r3, a6l, r3, carry, carry);
279 r4 -= carry;
280 /* diff 8 */
281 MP_SUB_BORROW(r0, a7, r0, 0, carry);
282 MP_SUB_BORROW(r1, a4h<<32, r1, carry, carry);
283 MP_SUB_BORROW(r2, a5, r2, carry, carry);
284 MP_SUB_BORROW(r3, a6h<<32, r3, carry, carry);
285 r4 -= carry;
287 /* reduce the overflows */
288 while (r4 > 0) {
289 mp_digit r4_long = r4;
290 mp_digit r4l = (r4_long << 32);
291 MP_ADD_CARRY(r0, r4_long, r0, 0, carry);
292 MP_ADD_CARRY(r1, 0-r4l, r1, carry, carry);
293 MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry);
294 MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry);
295 r4 = carry;
296 }
298 /* reduce the underflows */
299 while (r4 < 0) {
300 mp_digit r4_long = -r4;
301 mp_digit r4l = (r4_long << 32);
302 MP_SUB_BORROW(r0, r4_long, r0, 0, carry);
303 MP_SUB_BORROW(r1, 0-r4l, r1, carry, carry);
304 MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry);
305 MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry);
306 r4 = 0-carry;
307 }
309 if (a != r) {
310 MP_CHECKOK(s_mp_pad(r,4));
311 }
312 MP_SIGN(r) = MP_ZPOS;
313 MP_USED(r) = 4;
315 MP_DIGIT(r,3) = r3;
316 MP_DIGIT(r,2) = r2;
317 MP_DIGIT(r,1) = r1;
318 MP_DIGIT(r,0) = r0;
320 /* final reduction if necessary */
321 if ((r3 > 0xFFFFFFFF00000001ULL) ||
322 ((r3 == 0xFFFFFFFF00000001ULL) &&
323 (r2 || (r1 >> 32)||
324 (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) {
325 /* very rare, just use mp_sub */
326 MP_CHECKOK(mp_sub(r, &meth->irr, r));
327 }
329 s_mp_clamp(r);
330 #endif
331 }
333 CLEANUP:
334 return res;
335 }
337 /* Compute the square of polynomial a, reduce modulo p256. Store the
338 * result in r. r could be a. Uses optimized modular reduction for p256.
339 */
340 static mp_err
341 ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
342 {
343 mp_err res = MP_OKAY;
345 MP_CHECKOK(mp_sqr(a, r));
346 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
347 CLEANUP:
348 return res;
349 }
351 /* Compute the product of two polynomials a and b, reduce modulo p256.
352 * Store the result in r. r could be a or b; a could be b. Uses
353 * optimized modular reduction for p256. */
354 static mp_err
355 ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r,
356 const GFMethod *meth)
357 {
358 mp_err res = MP_OKAY;
360 MP_CHECKOK(mp_mul(a, b, r));
361 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
362 CLEANUP:
363 return res;
364 }
366 /* Wire in fast field arithmetic and precomputation of base point for
367 * named curves. */
368 mp_err
369 ec_group_set_gfp256(ECGroup *group, ECCurveName name)
370 {
371 if (name == ECCurve_NIST_P256) {
372 group->meth->field_mod = &ec_GFp_nistp256_mod;
373 group->meth->field_mul = &ec_GFp_nistp256_mul;
374 group->meth->field_sqr = &ec_GFp_nistp256_sqr;
375 }
376 return MP_OKAY;
377 }
