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