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