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 "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