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