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 #include <string.h>
27 #include "bt_target.h"
28 #include "p_256_ecc_pp.h"
29
multiprecision_init(uint32_t * c,uint32_t keyLength)30 void multiprecision_init(uint32_t* c, uint32_t keyLength) {
31 for (uint32_t i = 0; i < keyLength; i++) c[i] = 0;
32 }
33
multiprecision_copy(uint32_t * c,uint32_t * a,uint32_t keyLength)34 void multiprecision_copy(uint32_t* c, uint32_t* a, uint32_t keyLength) {
35 for (uint32_t i = 0; i < keyLength; i++) c[i] = a[i];
36 }
37
multiprecision_compare(uint32_t * a,uint32_t * b,uint32_t keyLength)38 int multiprecision_compare(uint32_t* a, uint32_t* b, uint32_t keyLength) {
39 for (int i = keyLength - 1; i >= 0; i--) {
40 if (a[i] > b[i]) return 1;
41 if (a[i] < b[i]) return -1;
42 }
43 return 0;
44 }
45
multiprecision_iszero(uint32_t * a,uint32_t keyLength)46 int multiprecision_iszero(uint32_t* a, uint32_t keyLength) {
47 for (uint32_t i = 0; i < keyLength; i++)
48 if (a[i]) return 0;
49
50 return 1;
51 }
52
multiprecision_dword_bits(uint32_t a)53 uint32_t multiprecision_dword_bits(uint32_t a) {
54 uint32_t i;
55 for (i = 0; i < DWORD_BITS; i++, a >>= 1)
56 if (a == 0) break;
57
58 return i;
59 }
60
multiprecision_most_signdwords(uint32_t * a,uint32_t keyLength)61 uint32_t multiprecision_most_signdwords(uint32_t* a, uint32_t keyLength) {
62 int i;
63 for (i = keyLength - 1; i >= 0; i--)
64 if (a[i]) break;
65 return (i + 1);
66 }
67
multiprecision_most_signbits(uint32_t * a,uint32_t keyLength)68 uint32_t multiprecision_most_signbits(uint32_t* a, uint32_t keyLength) {
69 int aMostSignDWORDs;
70
71 aMostSignDWORDs = multiprecision_most_signdwords(a, keyLength);
72 if (aMostSignDWORDs == 0) return 0;
73
74 return (((aMostSignDWORDs - 1) << DWORD_BITS_SHIFT) +
75 multiprecision_dword_bits(a[aMostSignDWORDs - 1]));
76 }
77
multiprecision_add(uint32_t * c,uint32_t * a,uint32_t * b,uint32_t keyLength)78 uint32_t multiprecision_add(uint32_t* c, uint32_t* a, uint32_t* b,
79 uint32_t keyLength) {
80 uint32_t carrier;
81 uint32_t temp;
82
83 carrier = 0;
84 for (uint32_t i = 0; i < keyLength; i++) {
85 temp = a[i] + carrier;
86 carrier = (temp < carrier);
87 temp += b[i];
88 carrier |= (temp < b[i]);
89 c[i] = temp;
90 }
91
92 return carrier;
93 }
94
95 // c=a-b
multiprecision_sub(uint32_t * c,uint32_t * a,uint32_t * b,uint32_t keyLength)96 uint32_t multiprecision_sub(uint32_t* c, uint32_t* a, uint32_t* b,
97 uint32_t keyLength) {
98 uint32_t borrow;
99 uint32_t temp;
100
101 borrow = 0;
102 for (uint32_t i = 0; i < keyLength; i++) {
103 temp = a[i] - borrow;
104 borrow = (temp > a[i]);
105 c[i] = temp - b[i];
106 borrow |= (c[i] > temp);
107 }
108
109 return borrow;
110 }
111
112 // c = a << 1
multiprecision_lshift_mod(uint32_t * c,uint32_t * a,uint32_t keyLength)113 void multiprecision_lshift_mod(uint32_t* c, uint32_t* a, uint32_t keyLength) {
114 uint32_t carrier;
115 uint32_t* modp;
116
117 if (keyLength == KEY_LENGTH_DWORDS_P192) {
118 modp = curve.p;
119 } else if (keyLength == KEY_LENGTH_DWORDS_P256) {
120 modp = curve_p256.p;
121 } else
122 return;
123
124 carrier = multiprecision_lshift(c, a, keyLength);
125 if (carrier) {
126 multiprecision_sub(c, c, modp, keyLength);
127 } else if (multiprecision_compare(c, modp, keyLength) >= 0) {
128 multiprecision_sub(c, c, modp, keyLength);
129 }
130 }
131
132 // c=a>>1
multiprecision_rshift(uint32_t * c,uint32_t * a,uint32_t keyLength)133 void multiprecision_rshift(uint32_t* c, uint32_t* a, uint32_t keyLength) {
134 int j;
135 uint32_t b = 1;
136
137 j = DWORD_BITS - b;
138
139 uint32_t carrier = 0;
140 uint32_t temp;
141 for (int i = keyLength - 1; i >= 0; i--) {
142 temp = a[i]; // in case of c==a
143 c[i] = (temp >> b) | carrier;
144 carrier = temp << j;
145 }
146 }
147
148 // Curve specific optimization when p is a pseudo-Mersenns prime,
149 // p=2^(KEY_LENGTH_BITS)-omega
multiprecision_mersenns_mult_mod(uint32_t * c,uint32_t * a,uint32_t * b,uint32_t keyLength)150 void multiprecision_mersenns_mult_mod(uint32_t* c, uint32_t* a, uint32_t* b,
151 uint32_t keyLength) {
152 uint32_t cc[2 * KEY_LENGTH_DWORDS_P256];
153
154 multiprecision_mult(cc, a, b, keyLength);
155 if (keyLength == 6) {
156 multiprecision_fast_mod(c, cc);
157 } else if (keyLength == 8) {
158 multiprecision_fast_mod_P256(c, cc);
159 }
160 }
161
162 // Curve specific optimization when p is a pseudo-Mersenns prime
multiprecision_mersenns_squa_mod(uint32_t * c,uint32_t * a,uint32_t keyLength)163 void multiprecision_mersenns_squa_mod(uint32_t* c, uint32_t* a,
164 uint32_t keyLength) {
165 multiprecision_mersenns_mult_mod(c, a, a, keyLength);
166 }
167
168 // c=(a+b) mod p, b<p, a<p
multiprecision_add_mod(uint32_t * c,uint32_t * a,uint32_t * b,uint32_t keyLength)169 void multiprecision_add_mod(uint32_t* c, uint32_t* a, uint32_t* b,
170 uint32_t keyLength) {
171 uint32_t carrier;
172 uint32_t* modp;
173
174 if (keyLength == KEY_LENGTH_DWORDS_P192) {
175 modp = curve.p;
176 } else if (keyLength == KEY_LENGTH_DWORDS_P256) {
177 modp = curve_p256.p;
178 } else
179 return;
180
181 carrier = multiprecision_add(c, a, b, keyLength);
182 if (carrier) {
183 multiprecision_sub(c, c, modp, keyLength);
184 } else if (multiprecision_compare(c, modp, keyLength) >= 0) {
185 multiprecision_sub(c, c, modp, keyLength);
186 }
187 }
188
189 // c=(a-b) mod p, a<p, b<p
multiprecision_sub_mod(uint32_t * c,uint32_t * a,uint32_t * b,uint32_t keyLength)190 void multiprecision_sub_mod(uint32_t* c, uint32_t* a, uint32_t* b,
191 uint32_t keyLength) {
192 uint32_t borrow;
193 uint32_t* modp;
194
195 if (keyLength == KEY_LENGTH_DWORDS_P192) {
196 modp = curve.p;
197 } else if (keyLength == KEY_LENGTH_DWORDS_P256) {
198 modp = curve_p256.p;
199 } else
200 return;
201
202 borrow = multiprecision_sub(c, a, b, keyLength);
203 if (borrow) multiprecision_add(c, c, modp, keyLength);
204 }
205
206 // c=a<<b, b<DWORD_BITS, c has a buffer size of Numuint32_ts+1
multiprecision_lshift(uint32_t * c,uint32_t * a,uint32_t keyLength)207 uint32_t multiprecision_lshift(uint32_t* c, uint32_t* a, uint32_t keyLength) {
208 int j;
209 uint32_t b = 1;
210 j = DWORD_BITS - b;
211
212 uint32_t carrier = 0;
213 uint32_t temp;
214
215 for (uint32_t i = 0; i < keyLength; i++) {
216 temp = a[i]; // in case c==a
217 c[i] = (temp << b) | carrier;
218 carrier = temp >> j;
219 }
220
221 return carrier;
222 }
223
224 // 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,uint32_t keyLength)225 void multiprecision_mult(uint32_t* c, uint32_t* a, uint32_t* b,
226 uint32_t keyLength) {
227 uint32_t W;
228 uint32_t U;
229 uint32_t V;
230
231 U = V = W = 0;
232 multiprecision_init(c, keyLength);
233
234 // assume little endian right now
235 for (uint32_t i = 0; i < keyLength; i++) {
236 U = 0;
237 for (uint32_t j = 0; j < keyLength; j++) {
238 uint64_t result;
239 result = ((uint64_t)a[i]) * ((uint64_t)b[j]);
240 W = result >> 32;
241 V = a[i] * b[j];
242 V = V + U;
243 U = (V < U);
244 U += W;
245 V = V + c[i + j];
246 U += (V < c[i + j]);
247 c[i + j] = V;
248 }
249 c[i + keyLength] = U;
250 }
251 }
252
multiprecision_fast_mod(uint32_t * c,uint32_t * a)253 void multiprecision_fast_mod(uint32_t* c, uint32_t* a) {
254 uint32_t U;
255 uint32_t V;
256 uint32_t* modp = curve.p;
257
258 c[0] = a[0] + a[6];
259 U = c[0] < a[0];
260 c[0] += a[10];
261 U += c[0] < a[10];
262
263 c[1] = a[1] + U;
264 U = c[1] < a[1];
265 c[1] += a[7];
266 U += c[1] < a[7];
267 c[1] += a[11];
268 U += c[1] < a[11];
269
270 c[2] = a[2] + U;
271 U = c[2] < a[2];
272 c[2] += a[6];
273 U += c[2] < a[6];
274 c[2] += a[8];
275 U += c[2] < a[8];
276 c[2] += a[10];
277 U += c[2] < a[10];
278
279 c[3] = a[3] + U;
280 U = c[3] < a[3];
281 c[3] += a[7];
282 U += c[3] < a[7];
283 c[3] += a[9];
284 U += c[3] < a[9];
285 c[3] += a[11];
286 U += c[3] < a[11];
287
288 c[4] = a[4] + U;
289 U = c[4] < a[4];
290 c[4] += a[8];
291 U += c[4] < a[8];
292 c[4] += a[10];
293 U += c[4] < a[10];
294
295 c[5] = a[5] + U;
296 U = c[5] < a[5];
297 c[5] += a[9];
298 U += c[5] < a[9];
299 c[5] += a[11];
300 U += c[5] < a[11];
301
302 c[0] += U;
303 V = c[0] < U;
304 c[1] += V;
305 V = c[1] < V;
306 c[2] += V;
307 V = c[2] < V;
308 c[2] += U;
309 V = c[2] < U;
310 c[3] += V;
311 V = c[3] < V;
312 c[4] += V;
313 V = c[4] < V;
314 c[5] += V;
315 V = c[5] < V;
316
317 if (V) {
318 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P192);
319 } else if (multiprecision_compare(c, modp, KEY_LENGTH_DWORDS_P192) >= 0) {
320 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P192);
321 }
322 }
323
multiprecision_fast_mod_P256(uint32_t * c,uint32_t * a)324 void multiprecision_fast_mod_P256(uint32_t* c, uint32_t* a) {
325 uint32_t A;
326 uint32_t B;
327 uint32_t C;
328 uint32_t D;
329 uint32_t E;
330 uint32_t F;
331 uint32_t G;
332 uint8_t UA;
333 uint8_t UB;
334 uint8_t UC;
335 uint8_t UD;
336 uint8_t UE;
337 uint8_t UF;
338 uint8_t UG;
339 uint32_t U;
340 uint32_t* modp = curve_p256.p;
341
342 // C = a[13] + a[14] + a[15];
343 C = a[13];
344 C += a[14];
345 UC = (C < a[14]);
346 C += a[15];
347 UC += (C < a[15]);
348
349 // E = a[8] + a[9];
350 E = a[8];
351 E += a[9];
352 UE = (E < a[9]);
353
354 // F = a[9] + a[10];
355 F = a[9];
356 F += a[10];
357 UF = (F < a[10]);
358
359 // G = a[10] + a[11]
360 G = a[10];
361 G += a[11];
362 UG = (G < a[11]);
363
364 // B = a[12] + a[13] + a[14] + a[15] == C + a[12]
365 B = C;
366 UB = UC;
367 B += a[12];
368 UB += (B < a[12]);
369
370 // A = a[11] + a[12] + a[13] + a[14] == B + a[11] - a[15]
371 A = B;
372 UA = UB;
373 A += a[11];
374 UA += (A < a[11]);
375 UA -= (A < a[15]);
376 A -= a[15];
377
378 // D = a[10] + a[11] + a[12] + a[13] == A + a[10] - a[14]
379 D = A;
380 UD = UA;
381 D += a[10];
382 UD += (D < a[10]);
383 UD -= (D < a[14]);
384 D -= a[14];
385
386 c[0] = a[0];
387 c[0] += E;
388 U = (c[0] < E);
389 U += UE;
390 U -= (c[0] < A);
391 U -= UA;
392 c[0] -= A;
393
394 if (U & 0x80000000) {
395 uint32_t UU;
396 UU = 0 - U;
397 U = (a[1] < UU);
398 c[1] = a[1] - UU;
399 } else {
400 c[1] = a[1] + U;
401 U = (c[1] < a[1]);
402 }
403
404 c[1] += F;
405 U += (c[1] < F);
406 U += UF;
407 U -= (c[1] < B);
408 U -= UB;
409 c[1] -= B;
410
411 if (U & 0x80000000) {
412 uint32_t UU;
413 UU = 0 - U;
414 U = (a[2] < UU);
415 c[2] = a[2] - UU;
416 } else {
417 c[2] = a[2] + U;
418 U = (c[2] < a[2]);
419 }
420
421 c[2] += G;
422 U += (c[2] < G);
423 U += UG;
424 U -= (c[2] < C);
425 U -= UC;
426 c[2] -= C;
427
428 if (U & 0x80000000) {
429 uint32_t UU;
430 UU = 0 - U;
431 U = (a[3] < UU);
432 c[3] = a[3] - UU;
433 } else {
434 c[3] = a[3] + U;
435 U = (c[3] < a[3]);
436 }
437
438 c[3] += A;
439 U += (c[3] < A);
440 U += UA;
441 c[3] += a[11];
442 U += (c[3] < a[11]);
443 c[3] += a[12];
444 U += (c[3] < a[12]);
445 U -= (c[3] < a[14]);
446 c[3] -= a[14];
447 U -= (c[3] < a[15]);
448 c[3] -= a[15];
449 U -= (c[3] < E);
450 U -= UE;
451 c[3] -= E;
452
453 if (U & 0x80000000) {
454 uint32_t UU;
455 UU = 0 - U;
456 U = (a[4] < UU);
457 c[4] = a[4] - UU;
458 } else {
459 c[4] = a[4] + U;
460 U = (c[4] < a[4]);
461 }
462
463 c[4] += B;
464 U += (c[4] < B);
465 U += UB;
466 U -= (c[4] < a[15]);
467 c[4] -= a[15];
468 c[4] += a[12];
469 U += (c[4] < a[12]);
470 c[4] += a[13];
471 U += (c[4] < a[13]);
472 U -= (c[4] < F);
473 U -= UF;
474 c[4] -= F;
475
476 if (U & 0x80000000) {
477 uint32_t UU;
478 UU = 0 - U;
479 U = (a[5] < UU);
480 c[5] = a[5] - UU;
481 } else {
482 c[5] = a[5] + U;
483 U = (c[5] < a[5]);
484 }
485
486 c[5] += C;
487 U += (c[5] < C);
488 U += UC;
489 c[5] += a[13];
490 U += (c[5] < a[13]);
491 c[5] += a[14];
492 U += (c[5] < a[14]);
493 U -= (c[5] < G);
494 U -= UG;
495 c[5] -= G;
496
497 if (U & 0x80000000) {
498 uint32_t UU;
499 UU = 0 - U;
500 U = (a[6] < UU);
501 c[6] = a[6] - UU;
502 } else {
503 c[6] = a[6] + U;
504 U = (c[6] < a[6]);
505 }
506
507 c[6] += C;
508 U += (c[6] < C);
509 U += UC;
510 c[6] += a[14];
511 U += (c[6] < a[14]);
512 c[6] += a[14];
513 U += (c[6] < a[14]);
514 c[6] += a[15];
515 U += (c[6] < a[15]);
516 U -= (c[6] < E);
517 U -= UE;
518 c[6] -= E;
519
520 if (U & 0x80000000) {
521 uint32_t UU;
522 UU = 0 - U;
523 U = (a[7] < UU);
524 c[7] = a[7] - UU;
525 } else {
526 c[7] = a[7] + U;
527 U = (c[7] < a[7]);
528 }
529
530 c[7] += a[15];
531 U += (c[7] < a[15]);
532 c[7] += a[15];
533 U += (c[7] < a[15]);
534 c[7] += a[15];
535 U += (c[7] < a[15]);
536 c[7] += a[8];
537 U += (c[7] < a[8]);
538 U -= (c[7] < D);
539 U -= UD;
540 c[7] -= D;
541
542 if (U & 0x80000000) {
543 while (U) {
544 multiprecision_add(c, c, modp, KEY_LENGTH_DWORDS_P256);
545 U++;
546 }
547 } else if (U) {
548 while (U) {
549 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P256);
550 U--;
551 }
552 }
553
554 if (multiprecision_compare(c, modp, KEY_LENGTH_DWORDS_P256) >= 0)
555 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P256);
556 }
557
multiprecision_inv_mod(uint32_t * aminus,uint32_t * u,uint32_t keyLength)558 void multiprecision_inv_mod(uint32_t* aminus, uint32_t* u, uint32_t keyLength) {
559 uint32_t v[KEY_LENGTH_DWORDS_P256];
560 uint32_t A[KEY_LENGTH_DWORDS_P256 + 1];
561 uint32_t C[KEY_LENGTH_DWORDS_P256 + 1];
562 uint32_t* modp;
563
564 if (keyLength == KEY_LENGTH_DWORDS_P256) {
565 modp = curve_p256.p;
566 } else {
567 modp = curve.p;
568 }
569
570 multiprecision_copy(v, modp, keyLength);
571 multiprecision_init(A, keyLength);
572 multiprecision_init(C, keyLength);
573 A[0] = 1;
574
575 while (!multiprecision_iszero(u, keyLength)) {
576 while (!(u[0] & 0x01)) // u is even
577 {
578 multiprecision_rshift(u, u, keyLength);
579 if (!(A[0] & 0x01)) // A is even
580 multiprecision_rshift(A, A, keyLength);
581 else {
582 A[keyLength] = multiprecision_add(A, A, modp, keyLength); // A =A+p
583 multiprecision_rshift(A, A, keyLength);
584 A[keyLength - 1] |= (A[keyLength] << 31);
585 }
586 }
587
588 while (!(v[0] & 0x01)) // v is even
589 {
590 multiprecision_rshift(v, v, keyLength);
591 if (!(C[0] & 0x01)) // C is even
592 {
593 multiprecision_rshift(C, C, keyLength);
594 } else {
595 C[keyLength] = multiprecision_add(C, C, modp, keyLength); // C =C+p
596 multiprecision_rshift(C, C, keyLength);
597 C[keyLength - 1] |= (C[keyLength] << 31);
598 }
599 }
600
601 if (multiprecision_compare(u, v, keyLength) >= 0) {
602 multiprecision_sub(u, u, v, keyLength);
603 multiprecision_sub_mod(A, A, C, keyLength);
604 } else {
605 multiprecision_sub(v, v, u, keyLength);
606 multiprecision_sub_mod(C, C, A, keyLength);
607 }
608 }
609
610 if (multiprecision_compare(C, modp, keyLength) >= 0)
611 multiprecision_sub(aminus, C, modp, keyLength);
612 else
613 multiprecision_copy(aminus, C, keyLength);
614 }
615