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