• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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)30 void multiprecision_init(uint32_t* c) {
31   for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) c[i] = 0;
32 }
33 
multiprecision_copy(uint32_t * c,uint32_t * a)34 void multiprecision_copy(uint32_t* c, uint32_t* a) {
35   for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) c[i] = a[i];
36 }
37 
multiprecision_compare(uint32_t * a,uint32_t * b)38 int multiprecision_compare(uint32_t* a, uint32_t* b) {
39   for (int i = KEY_LENGTH_DWORDS_P256 - 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)46 int multiprecision_iszero(uint32_t* a) {
47   for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; 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)61 uint32_t multiprecision_most_signdwords(uint32_t* a) {
62   int i;
63   for (i = KEY_LENGTH_DWORDS_P256 - 1; i >= 0; i--)
64     if (a[i]) break;
65   return (i + 1);
66 }
67 
multiprecision_most_signbits(uint32_t * a)68 uint32_t multiprecision_most_signbits(uint32_t* a) {
69   int aMostSignDWORDs;
70 
71   aMostSignDWORDs = multiprecision_most_signdwords(a);
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)78 uint32_t multiprecision_add(uint32_t* c, uint32_t* a, uint32_t* b) {
79   uint32_t carrier;
80   uint32_t temp;
81 
82   carrier = 0;
83   for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
84     temp = a[i] + carrier;
85     carrier = (temp < carrier);
86     temp += b[i];
87     carrier |= (temp < b[i]);
88     c[i] = temp;
89   }
90 
91   return carrier;
92 }
93 
94 // c=a-b
multiprecision_sub(uint32_t * c,uint32_t * a,uint32_t * b)95 uint32_t multiprecision_sub(uint32_t* c, uint32_t* a, uint32_t* b) {
96   uint32_t borrow;
97   uint32_t temp;
98 
99   borrow = 0;
100   for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
101     temp = a[i] - borrow;
102     borrow = (temp > a[i]);
103     c[i] = temp - b[i];
104     borrow |= (c[i] > temp);
105   }
106 
107   return borrow;
108 }
109 
110 // c = a << 1
multiprecision_lshift_mod(uint32_t * c,uint32_t * a)111 void multiprecision_lshift_mod(uint32_t* c, uint32_t* a) {
112   uint32_t carrier;
113   uint32_t* modp = curve_p256.p;
114 
115   carrier = multiprecision_lshift(c, a);
116   if (carrier) {
117     multiprecision_sub(c, c, modp);
118   } else if (multiprecision_compare(c, modp) >= 0) {
119     multiprecision_sub(c, c, modp);
120   }
121 }
122 
123 // c=a>>1
multiprecision_rshift(uint32_t * c,uint32_t * a)124 void multiprecision_rshift(uint32_t* c, uint32_t* a) {
125   int j;
126   uint32_t b = 1;
127 
128   j = DWORD_BITS - b;
129 
130   uint32_t carrier = 0;
131   uint32_t temp;
132   for (int i = KEY_LENGTH_DWORDS_P256 - 1; i >= 0; i--) {
133     temp = a[i];  // in case of c==a
134     c[i] = (temp >> b) | carrier;
135     carrier = temp << j;
136   }
137 }
138 
139 // Curve specific optimization when p is a pseudo-Mersenns prime,
140 // p=2^(KEY_LENGTH_BITS)-omega
multiprecision_mersenns_mult_mod(uint32_t * c,uint32_t * a,uint32_t * b)141 void multiprecision_mersenns_mult_mod(uint32_t* c, uint32_t* a, uint32_t* b) {
142   uint32_t cc[2 * KEY_LENGTH_DWORDS_P256];
143 
144   multiprecision_mult(cc, a, b);
145   multiprecision_fast_mod_P256(c, cc);
146 }
147 
148 // Curve specific optimization when p is a pseudo-Mersenns prime
multiprecision_mersenns_squa_mod(uint32_t * c,uint32_t * a)149 void multiprecision_mersenns_squa_mod(uint32_t* c, uint32_t* a) {
150   multiprecision_mersenns_mult_mod(c, a, a);
151 }
152 
153 // c=(a+b) mod p, b<p, a<p
multiprecision_add_mod(uint32_t * c,uint32_t * a,uint32_t * b)154 void multiprecision_add_mod(uint32_t* c, uint32_t* a, uint32_t* b) {
155   uint32_t carrier;
156   uint32_t* modp = curve_p256.p;
157 
158   carrier = multiprecision_add(c, a, b);
159   if (carrier) {
160     multiprecision_sub(c, c, modp);
161   } else if (multiprecision_compare(c, modp) >= 0) {
162     multiprecision_sub(c, c, modp);
163   }
164 }
165 
166 // c=(a-b) mod p, a<p, b<p
multiprecision_sub_mod(uint32_t * c,uint32_t * a,uint32_t * b)167 void multiprecision_sub_mod(uint32_t* c, uint32_t* a, uint32_t* b) {
168   uint32_t borrow;
169   uint32_t* modp = curve_p256.p;
170 
171   borrow = multiprecision_sub(c, a, b);
172   if (borrow) multiprecision_add(c, c, modp);
173 }
174 
175 // c=a<<b, b<DWORD_BITS, c has a buffer size of Numuint32_ts+1
multiprecision_lshift(uint32_t * c,uint32_t * a)176 uint32_t multiprecision_lshift(uint32_t* c, uint32_t* a) {
177   int j;
178   uint32_t b = 1;
179   j = DWORD_BITS - b;
180 
181   uint32_t carrier = 0;
182   uint32_t temp;
183 
184   for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
185     temp = a[i];  // in case c==a
186     c[i] = (temp << b) | carrier;
187     carrier = temp >> j;
188   }
189 
190   return carrier;
191 }
192 
193 // 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)194 void multiprecision_mult(uint32_t* c, uint32_t* a, uint32_t* b) {
195   uint32_t W;
196   uint32_t U;
197   uint32_t V;
198 
199   U = V = W = 0;
200   multiprecision_init(c);
201 
202   // assume little endian right now
203   for (uint32_t i = 0; i < KEY_LENGTH_DWORDS_P256; i++) {
204     U = 0;
205     for (uint32_t j = 0; j < KEY_LENGTH_DWORDS_P256; j++) {
206       uint64_t result;
207       result = ((uint64_t)a[i]) * ((uint64_t)b[j]);
208       W = result >> 32;
209       V = a[i] * b[j];
210       V = V + U;
211       U = (V < U);
212       U += W;
213       V = V + c[i + j];
214       U += (V < c[i + j]);
215       c[i + j] = V;
216     }
217     c[i + KEY_LENGTH_DWORDS_P256] = U;
218   }
219 }
220 
multiprecision_fast_mod_P256(uint32_t * c,uint32_t * a)221 void multiprecision_fast_mod_P256(uint32_t* c, uint32_t* a) {
222   uint32_t A;
223   uint32_t B;
224   uint32_t C;
225   uint32_t D;
226   uint32_t E;
227   uint32_t F;
228   uint32_t G;
229   uint8_t UA;
230   uint8_t UB;
231   uint8_t UC;
232   uint8_t UD;
233   uint8_t UE;
234   uint8_t UF;
235   uint8_t UG;
236   uint32_t U;
237   uint32_t* modp = curve_p256.p;
238 
239   // C = a[13] + a[14] + a[15];
240   C = a[13];
241   C += a[14];
242   UC = (C < a[14]);
243   C += a[15];
244   UC += (C < a[15]);
245 
246   // E = a[8] + a[9];
247   E = a[8];
248   E += a[9];
249   UE = (E < a[9]);
250 
251   // F = a[9] + a[10];
252   F = a[9];
253   F += a[10];
254   UF = (F < a[10]);
255 
256   // G = a[10] + a[11]
257   G = a[10];
258   G += a[11];
259   UG = (G < a[11]);
260 
261   // B = a[12] + a[13] + a[14] + a[15] == C + a[12]
262   B = C;
263   UB = UC;
264   B += a[12];
265   UB += (B < a[12]);
266 
267   // A = a[11] + a[12] + a[13] + a[14] == B + a[11] - a[15]
268   A = B;
269   UA = UB;
270   A += a[11];
271   UA += (A < a[11]);
272   UA -= (A < a[15]);
273   A -= a[15];
274 
275   // D = a[10] + a[11] + a[12] + a[13] == A + a[10] - a[14]
276   D = A;
277   UD = UA;
278   D += a[10];
279   UD += (D < a[10]);
280   UD -= (D < a[14]);
281   D -= a[14];
282 
283   c[0] = a[0];
284   c[0] += E;
285   U = (c[0] < E);
286   U += UE;
287   U -= (c[0] < A);
288   U -= UA;
289   c[0] -= A;
290 
291   if (U & 0x80000000) {
292     uint32_t UU;
293     UU = 0 - U;
294     U = (a[1] < UU);
295     c[1] = a[1] - UU;
296   } else {
297     c[1] = a[1] + U;
298     U = (c[1] < a[1]);
299   }
300 
301   c[1] += F;
302   U += (c[1] < F);
303   U += UF;
304   U -= (c[1] < B);
305   U -= UB;
306   c[1] -= B;
307 
308   if (U & 0x80000000) {
309     uint32_t UU;
310     UU = 0 - U;
311     U = (a[2] < UU);
312     c[2] = a[2] - UU;
313   } else {
314     c[2] = a[2] + U;
315     U = (c[2] < a[2]);
316   }
317 
318   c[2] += G;
319   U += (c[2] < G);
320   U += UG;
321   U -= (c[2] < C);
322   U -= UC;
323   c[2] -= C;
324 
325   if (U & 0x80000000) {
326     uint32_t UU;
327     UU = 0 - U;
328     U = (a[3] < UU);
329     c[3] = a[3] - UU;
330   } else {
331     c[3] = a[3] + U;
332     U = (c[3] < a[3]);
333   }
334 
335   c[3] += A;
336   U += (c[3] < A);
337   U += UA;
338   c[3] += a[11];
339   U += (c[3] < a[11]);
340   c[3] += a[12];
341   U += (c[3] < a[12]);
342   U -= (c[3] < a[14]);
343   c[3] -= a[14];
344   U -= (c[3] < a[15]);
345   c[3] -= a[15];
346   U -= (c[3] < E);
347   U -= UE;
348   c[3] -= E;
349 
350   if (U & 0x80000000) {
351     uint32_t UU;
352     UU = 0 - U;
353     U = (a[4] < UU);
354     c[4] = a[4] - UU;
355   } else {
356     c[4] = a[4] + U;
357     U = (c[4] < a[4]);
358   }
359 
360   c[4] += B;
361   U += (c[4] < B);
362   U += UB;
363   U -= (c[4] < a[15]);
364   c[4] -= a[15];
365   c[4] += a[12];
366   U += (c[4] < a[12]);
367   c[4] += a[13];
368   U += (c[4] < a[13]);
369   U -= (c[4] < F);
370   U -= UF;
371   c[4] -= F;
372 
373   if (U & 0x80000000) {
374     uint32_t UU;
375     UU = 0 - U;
376     U = (a[5] < UU);
377     c[5] = a[5] - UU;
378   } else {
379     c[5] = a[5] + U;
380     U = (c[5] < a[5]);
381   }
382 
383   c[5] += C;
384   U += (c[5] < C);
385   U += UC;
386   c[5] += a[13];
387   U += (c[5] < a[13]);
388   c[5] += a[14];
389   U += (c[5] < a[14]);
390   U -= (c[5] < G);
391   U -= UG;
392   c[5] -= G;
393 
394   if (U & 0x80000000) {
395     uint32_t UU;
396     UU = 0 - U;
397     U = (a[6] < UU);
398     c[6] = a[6] - UU;
399   } else {
400     c[6] = a[6] + U;
401     U = (c[6] < a[6]);
402   }
403 
404   c[6] += C;
405   U += (c[6] < C);
406   U += UC;
407   c[6] += a[14];
408   U += (c[6] < a[14]);
409   c[6] += a[14];
410   U += (c[6] < a[14]);
411   c[6] += a[15];
412   U += (c[6] < a[15]);
413   U -= (c[6] < E);
414   U -= UE;
415   c[6] -= E;
416 
417   if (U & 0x80000000) {
418     uint32_t UU;
419     UU = 0 - U;
420     U = (a[7] < UU);
421     c[7] = a[7] - UU;
422   } else {
423     c[7] = a[7] + U;
424     U = (c[7] < a[7]);
425   }
426 
427   c[7] += a[15];
428   U += (c[7] < a[15]);
429   c[7] += a[15];
430   U += (c[7] < a[15]);
431   c[7] += a[15];
432   U += (c[7] < a[15]);
433   c[7] += a[8];
434   U += (c[7] < a[8]);
435   U -= (c[7] < D);
436   U -= UD;
437   c[7] -= D;
438 
439   if (U & 0x80000000) {
440     while (U) {
441       multiprecision_add(c, c, modp);
442       U++;
443     }
444   } else if (U) {
445     while (U) {
446       multiprecision_sub(c, c, modp);
447       U--;
448     }
449   }
450 
451   if (multiprecision_compare(c, modp) >= 0) multiprecision_sub(c, c, modp);
452 }
453 
multiprecision_inv_mod(uint32_t * aminus,uint32_t * u)454 void multiprecision_inv_mod(uint32_t* aminus, uint32_t* u) {
455   uint32_t v[KEY_LENGTH_DWORDS_P256];
456   uint32_t A[KEY_LENGTH_DWORDS_P256 + 1];
457   uint32_t C[KEY_LENGTH_DWORDS_P256 + 1];
458   uint32_t* modp = curve_p256.p;
459 
460   multiprecision_copy(v, modp);
461   multiprecision_init(A);
462   multiprecision_init(C);
463   A[0] = 1;
464 
465   while (!multiprecision_iszero(u)) {
466     while (!(u[0] & 0x01))  // u is even
467     {
468       multiprecision_rshift(u, u);
469       if (!(A[0] & 0x01))  // A is even
470         multiprecision_rshift(A, A);
471       else {
472         A[KEY_LENGTH_DWORDS_P256] = multiprecision_add(A, A, modp);  // A =A+p
473         multiprecision_rshift(A, A);
474         A[KEY_LENGTH_DWORDS_P256 - 1] |= (A[KEY_LENGTH_DWORDS_P256] << 31);
475       }
476     }
477 
478     while (!(v[0] & 0x01))  // v is even
479     {
480       multiprecision_rshift(v, v);
481       if (!(C[0] & 0x01))  // C is even
482       {
483         multiprecision_rshift(C, C);
484       } else {
485         C[KEY_LENGTH_DWORDS_P256] = multiprecision_add(C, C, modp);  // C =C+p
486         multiprecision_rshift(C, C);
487         C[KEY_LENGTH_DWORDS_P256 - 1] |= (C[KEY_LENGTH_DWORDS_P256] << 31);
488       }
489     }
490 
491     if (multiprecision_compare(u, v) >= 0) {
492       multiprecision_sub(u, u, v);
493       multiprecision_sub_mod(A, A, C);
494     } else {
495       multiprecision_sub(v, v, u);
496       multiprecision_sub_mod(C, C, A);
497     }
498   }
499 
500   if (multiprecision_compare(C, modp) >= 0)
501     multiprecision_sub(aminus, C, modp);
502   else
503     multiprecision_copy(aminus, C);
504 }
505