1 /******************************************************************************
2 *
3 * Copyright 2006-2015 Broadcom Corporation
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at:
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 ******************************************************************************/
18
19 /*******************************************************************************
20 *
21 * This file contains simple pairing algorithms
22 *
23 ******************************************************************************/
24
25 #include "p_256_multprecision.h"
26
27 #include "p_256_ecc_pp.h"
28
multiprecision_init(uint32_t * c)29 void multiprecision_init(uint32_t* c) {
30 for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
31 c[i] = 0;
32 }
33 }
34
multiprecision_copy(uint32_t * c,uint32_t * a)35 void multiprecision_copy(uint32_t* c, uint32_t* a) {
36 for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
37 c[i] = a[i];
38 }
39 }
40
multiprecision_compare(uint32_t * a,uint32_t * b)41 int multiprecision_compare(uint32_t* a, uint32_t* b) {
42 for (int i = KEY_LENGTH_DWORDS_P256 - 1; i >= 0; i--) {
43 if (a[i] > b[i]) {
44 return 1;
45 }
46 if (a[i] < b[i]) {
47 return -1;
48 }
49 }
50 return 0;
51 }
52
multiprecision_iszero(uint32_t * a)53 int multiprecision_iszero(uint32_t* a) {
54 for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
55 if (a[i]) {
56 return 0;
57 }
58 }
59
60 return 1;
61 }
62
multiprecision_dword_bits(uint32_t a)63 uint32_t multiprecision_dword_bits(uint32_t a) {
64 uint32_t i;
65 for (i = 0; i < DWORD_BITS; i++, a >>= 1) {
66 if (a == 0) {
67 break;
68 }
69 }
70
71 return i;
72 }
73
multiprecision_most_signdwords(uint32_t * a)74 uint32_t multiprecision_most_signdwords(uint32_t* a) {
75 int i;
76 for (i = KEY_LENGTH_DWORDS_P256 - 1; i >= 0; i--) {
77 if (a[i]) {
78 break;
79 }
80 }
81 return i + 1;
82 }
83
multiprecision_most_signbits(uint32_t * a)84 uint32_t multiprecision_most_signbits(uint32_t* a) {
85 int aMostSignDWORDs;
86
87 aMostSignDWORDs = multiprecision_most_signdwords(a);
88 if (aMostSignDWORDs == 0) {
89 return 0;
90 }
91
92 return ((aMostSignDWORDs - 1) << DWORD_BITS_SHIFT) +
93 multiprecision_dword_bits(a[aMostSignDWORDs - 1]);
94 }
95
multiprecision_add(uint32_t * c,uint32_t * a,uint32_t * b)96 uint32_t multiprecision_add(uint32_t* c, uint32_t* a, uint32_t* b) {
97 uint32_t carrier;
98 uint32_t temp;
99
100 carrier = 0;
101 for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
102 temp = a[i] + carrier;
103 carrier = (temp < carrier);
104 temp += b[i];
105 carrier |= (temp < b[i]);
106 c[i] = temp;
107 }
108
109 return carrier;
110 }
111
112 // c=a-b
multiprecision_sub(uint32_t * c,uint32_t * a,uint32_t * b)113 uint32_t multiprecision_sub(uint32_t* c, uint32_t* a, uint32_t* b) {
114 uint32_t borrow;
115 uint32_t temp;
116
117 borrow = 0;
118 for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
119 temp = a[i] - borrow;
120 borrow = (temp > a[i]);
121 c[i] = temp - b[i];
122 borrow |= (c[i] > temp);
123 }
124
125 return borrow;
126 }
127
128 // c = a << 1
multiprecision_lshift_mod(uint32_t * c,uint32_t * a)129 void multiprecision_lshift_mod(uint32_t* c, uint32_t* a) {
130 uint32_t carrier;
131 uint32_t* modp = curve_p256.p;
132
133 carrier = multiprecision_lshift(c, a);
134 if (carrier) {
135 multiprecision_sub(c, c, modp);
136 } else if (multiprecision_compare(c, modp) >= 0) {
137 multiprecision_sub(c, c, modp);
138 }
139 }
140
141 // c=a>>1
multiprecision_rshift(uint32_t * c,uint32_t * a)142 void multiprecision_rshift(uint32_t* c, uint32_t* a) {
143 int j;
144 uint32_t b = 1;
145
146 j = DWORD_BITS - b;
147
148 uint32_t carrier = 0;
149 uint32_t temp;
150 for (int i = KEY_LENGTH_DWORDS_P256 - 1; i >= 0; i--) {
151 temp = a[i]; // in case of c==a
152 c[i] = (temp >> b) | carrier;
153 carrier = temp << j;
154 }
155 }
156
157 // Curve specific optimization when p is a pseudo-Mersenns prime,
158 // p=2^(KEY_LENGTH_BITS)-omega
multiprecision_mersenns_mult_mod(uint32_t * c,uint32_t * a,uint32_t * b)159 void multiprecision_mersenns_mult_mod(uint32_t* c, uint32_t* a, uint32_t* b) {
160 uint32_t cc[2 * KEY_LENGTH_DWORDS_P256];
161
162 multiprecision_mult(cc, a, b);
163 multiprecision_fast_mod_P256(c, cc);
164 }
165
166 // Curve specific optimization when p is a pseudo-Mersenns prime
multiprecision_mersenns_squa_mod(uint32_t * c,uint32_t * a)167 void multiprecision_mersenns_squa_mod(uint32_t* c, uint32_t* a) {
168 multiprecision_mersenns_mult_mod(c, a, a);
169 }
170
171 // c=(a+b) mod p, b<p, a<p
multiprecision_add_mod(uint32_t * c,uint32_t * a,uint32_t * b)172 void multiprecision_add_mod(uint32_t* c, uint32_t* a, uint32_t* b) {
173 uint32_t carrier;
174 uint32_t* modp = curve_p256.p;
175
176 carrier = multiprecision_add(c, a, b);
177 if (carrier) {
178 multiprecision_sub(c, c, modp);
179 } else if (multiprecision_compare(c, modp) >= 0) {
180 multiprecision_sub(c, c, modp);
181 }
182 }
183
184 // c=(a-b) mod p, a<p, b<p
multiprecision_sub_mod(uint32_t * c,uint32_t * a,uint32_t * b)185 void multiprecision_sub_mod(uint32_t* c, uint32_t* a, uint32_t* b) {
186 uint32_t borrow;
187 uint32_t* modp = curve_p256.p;
188
189 borrow = multiprecision_sub(c, a, b);
190 if (borrow) {
191 multiprecision_add(c, c, modp);
192 }
193 }
194
195 // c=a<<b, b<DWORD_BITS, c has a buffer size of Numuint32_ts+1
multiprecision_lshift(uint32_t * c,uint32_t * a)196 uint32_t multiprecision_lshift(uint32_t* c, uint32_t* a) {
197 int j;
198 uint32_t b = 1;
199 j = DWORD_BITS - b;
200
201 uint32_t carrier = 0;
202 uint32_t temp;
203
204 for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
205 temp = a[i]; // in case c==a
206 c[i] = (temp << b) | carrier;
207 carrier = temp >> j;
208 }
209
210 return carrier;
211 }
212
213 // c=a*b; c must have a buffer of 2*Key_LENGTH_uint32_tS, c != a != b
multiprecision_mult(uint32_t * c,uint32_t * a,uint32_t * b)214 void multiprecision_mult(uint32_t* c, uint32_t* a, uint32_t* b) {
215 uint32_t W;
216 uint32_t U;
217 uint32_t V;
218
219 U = V = W = 0;
220 multiprecision_init(c);
221
222 // assume little endian right now
223 for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
224 U = 0;
225 for (uint32_t j = 0; j < KEY_LENGTH_DWORDS_P256; j++) {
226 uint64_t result;
227 result = ((uint64_t)a[i]) * ((uint64_t)b[j]);
228 W = result >> 32;
229 V = a[i] * b[j];
230 V = V + U;
231 U = (V < U);
232 U += W;
233 V = V + c[i + j];
234 U += (V < c[i + j]);
235 c[i + j] = V;
236 }
237 c[i + KEY_LENGTH_DWORDS_P256] = U;
238 }
239 }
240
multiprecision_fast_mod_P256(uint32_t * c,uint32_t * a)241 void multiprecision_fast_mod_P256(uint32_t* c, uint32_t* a) {
242 uint32_t A;
243 uint32_t B;
244 uint32_t C;
245 uint32_t D;
246 uint32_t E;
247 uint32_t F;
248 uint32_t G;
249 uint8_t UA;
250 uint8_t UB;
251 uint8_t UC;
252 uint8_t UD;
253 uint8_t UE;
254 uint8_t UF;
255 uint8_t UG;
256 uint32_t U;
257 uint32_t* modp = curve_p256.p;
258
259 // C = a[13] + a[14] + a[15];
260 C = a[13];
261 C += a[14];
262 UC = (C < a[14]);
263 C += a[15];
264 UC += (C < a[15]);
265
266 // E = a[8] + a[9];
267 E = a[8];
268 E += a[9];
269 UE = (E < a[9]);
270
271 // F = a[9] + a[10];
272 F = a[9];
273 F += a[10];
274 UF = (F < a[10]);
275
276 // G = a[10] + a[11]
277 G = a[10];
278 G += a[11];
279 UG = (G < a[11]);
280
281 // B = a[12] + a[13] + a[14] + a[15] == C + a[12]
282 B = C;
283 UB = UC;
284 B += a[12];
285 UB += (B < a[12]);
286
287 // A = a[11] + a[12] + a[13] + a[14] == B + a[11] - a[15]
288 A = B;
289 UA = UB;
290 A += a[11];
291 UA += (A < a[11]);
292 UA -= (A < a[15]);
293 A -= a[15];
294
295 // D = a[10] + a[11] + a[12] + a[13] == A + a[10] - a[14]
296 D = A;
297 UD = UA;
298 D += a[10];
299 UD += (D < a[10]);
300 UD -= (D < a[14]);
301 D -= a[14];
302
303 c[0] = a[0];
304 c[0] += E;
305 U = (c[0] < E);
306 U += UE;
307 U -= (c[0] < A);
308 U -= UA;
309 c[0] -= A;
310
311 if (U & 0x80000000) {
312 uint32_t UU;
313 UU = 0 - U;
314 U = (a[1] < UU);
315 c[1] = a[1] - UU;
316 } else {
317 c[1] = a[1] + U;
318 U = (c[1] < a[1]);
319 }
320
321 c[1] += F;
322 U += (c[1] < F);
323 U += UF;
324 U -= (c[1] < B);
325 U -= UB;
326 c[1] -= B;
327
328 if (U & 0x80000000) {
329 uint32_t UU;
330 UU = 0 - U;
331 U = (a[2] < UU);
332 c[2] = a[2] - UU;
333 } else {
334 c[2] = a[2] + U;
335 U = (c[2] < a[2]);
336 }
337
338 c[2] += G;
339 U += (c[2] < G);
340 U += UG;
341 U -= (c[2] < C);
342 U -= UC;
343 c[2] -= C;
344
345 if (U & 0x80000000) {
346 uint32_t UU;
347 UU = 0 - U;
348 U = (a[3] < UU);
349 c[3] = a[3] - UU;
350 } else {
351 c[3] = a[3] + U;
352 U = (c[3] < a[3]);
353 }
354
355 c[3] += A;
356 U += (c[3] < A);
357 U += UA;
358 c[3] += a[11];
359 U += (c[3] < a[11]);
360 c[3] += a[12];
361 U += (c[3] < a[12]);
362 U -= (c[3] < a[14]);
363 c[3] -= a[14];
364 U -= (c[3] < a[15]);
365 c[3] -= a[15];
366 U -= (c[3] < E);
367 U -= UE;
368 c[3] -= E;
369
370 if (U & 0x80000000) {
371 uint32_t UU;
372 UU = 0 - U;
373 U = (a[4] < UU);
374 c[4] = a[4] - UU;
375 } else {
376 c[4] = a[4] + U;
377 U = (c[4] < a[4]);
378 }
379
380 c[4] += B;
381 U += (c[4] < B);
382 U += UB;
383 U -= (c[4] < a[15]);
384 c[4] -= a[15];
385 c[4] += a[12];
386 U += (c[4] < a[12]);
387 c[4] += a[13];
388 U += (c[4] < a[13]);
389 U -= (c[4] < F);
390 U -= UF;
391 c[4] -= F;
392
393 if (U & 0x80000000) {
394 uint32_t UU;
395 UU = 0 - U;
396 U = (a[5] < UU);
397 c[5] = a[5] - UU;
398 } else {
399 c[5] = a[5] + U;
400 U = (c[5] < a[5]);
401 }
402
403 c[5] += C;
404 U += (c[5] < C);
405 U += UC;
406 c[5] += a[13];
407 U += (c[5] < a[13]);
408 c[5] += a[14];
409 U += (c[5] < a[14]);
410 U -= (c[5] < G);
411 U -= UG;
412 c[5] -= G;
413
414 if (U & 0x80000000) {
415 uint32_t UU;
416 UU = 0 - U;
417 U = (a[6] < UU);
418 c[6] = a[6] - UU;
419 } else {
420 c[6] = a[6] + U;
421 U = (c[6] < a[6]);
422 }
423
424 c[6] += C;
425 U += (c[6] < C);
426 U += UC;
427 c[6] += a[14];
428 U += (c[6] < a[14]);
429 c[6] += a[14];
430 U += (c[6] < a[14]);
431 c[6] += a[15];
432 U += (c[6] < a[15]);
433 U -= (c[6] < E);
434 U -= UE;
435 c[6] -= E;
436
437 if (U & 0x80000000) {
438 uint32_t UU;
439 UU = 0 - U;
440 U = (a[7] < UU);
441 c[7] = a[7] - UU;
442 } else {
443 c[7] = a[7] + U;
444 U = (c[7] < a[7]);
445 }
446
447 c[7] += a[15];
448 U += (c[7] < a[15]);
449 c[7] += a[15];
450 U += (c[7] < a[15]);
451 c[7] += a[15];
452 U += (c[7] < a[15]);
453 c[7] += a[8];
454 U += (c[7] < a[8]);
455 U -= (c[7] < D);
456 U -= UD;
457 c[7] -= D;
458
459 if (U & 0x80000000) {
460 while (U) {
461 multiprecision_add(c, c, modp);
462 U++;
463 }
464 } else if (U) {
465 while (U) {
466 multiprecision_sub(c, c, modp);
467 U--;
468 }
469 }
470
471 if (multiprecision_compare(c, modp) >= 0) {
472 multiprecision_sub(c, c, modp);
473 }
474 }
475
multiprecision_inv_mod(uint32_t * aminus,uint32_t * u)476 void multiprecision_inv_mod(uint32_t* aminus, uint32_t* u) {
477 uint32_t v[KEY_LENGTH_DWORDS_P256];
478 uint32_t A[KEY_LENGTH_DWORDS_P256 + 1];
479 uint32_t C[KEY_LENGTH_DWORDS_P256 + 1];
480 uint32_t* modp = curve_p256.p;
481
482 multiprecision_copy(v, modp);
483 multiprecision_init(A);
484 multiprecision_init(C);
485 A[0] = 1;
486
487 while (!multiprecision_iszero(u)) {
488 while (!(u[0] & 0x01)) // u is even
489 {
490 multiprecision_rshift(u, u);
491 if (!(A[0] & 0x01)) { // A is even
492 multiprecision_rshift(A, A);
493 } else {
494 A[KEY_LENGTH_DWORDS_P256] = multiprecision_add(A, A, modp); // A =A+p
495 multiprecision_rshift(A, A);
496 A[KEY_LENGTH_DWORDS_P256 - 1] |= (A[KEY_LENGTH_DWORDS_P256] << 31);
497 }
498 }
499
500 while (!(v[0] & 0x01)) // v is even
501 {
502 multiprecision_rshift(v, v);
503 if (!(C[0] & 0x01)) // C is even
504 {
505 multiprecision_rshift(C, C);
506 } else {
507 C[KEY_LENGTH_DWORDS_P256] = multiprecision_add(C, C, modp); // C =C+p
508 multiprecision_rshift(C, C);
509 C[KEY_LENGTH_DWORDS_P256 - 1] |= (C[KEY_LENGTH_DWORDS_P256] << 31);
510 }
511 }
512
513 if (multiprecision_compare(u, v) >= 0) {
514 multiprecision_sub(u, u, v);
515 multiprecision_sub_mod(A, A, C);
516 } else {
517 multiprecision_sub(v, v, u);
518 multiprecision_sub_mod(C, C, A);
519 }
520 }
521
522 if (multiprecision_compare(C, modp) >= 0) {
523 multiprecision_sub(aminus, C, modp);
524 } else {
525 multiprecision_copy(aminus, C);
526 }
527 }
528