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