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