1 /******************************************************************************
3 * Copyright (C) 2006-2015 Broadcom Corporation
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:
9 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 ******************************************************************************/
19 /******************************************************************************
21 * This file contains simple pairing algorithms
23 ******************************************************************************/
26 #include "bt_target.h"
27 #include "p_256_ecc_pp.h"
28 #include "p_256_multprecision.h"
30 void multiprecision_init(DWORD *c, uint32_t keyLength)
32 for (uint32_t i = 0; i < keyLength; i++)
36 void multiprecision_copy(DWORD *c, DWORD *a, uint32_t keyLength)
38 for (uint32_t i = 0; i < keyLength; i++)
42 int multiprecision_compare(DWORD *a, DWORD *b, uint32_t keyLength)
44 for (int i = keyLength - 1; i >= 0; i--)
54 int multiprecision_iszero(DWORD *a, uint32_t keyLength)
56 for (uint32_t i = 0; i < keyLength; i++)
63 UINT32 multiprecision_dword_bits(DWORD a)
66 for (i = 0; i < DWORD_BITS; i++, a >>= 1)
73 UINT32 multiprecision_most_signdwords(DWORD *a, uint32_t keyLength)
76 for (i = keyLength - 1; i >= 0; i--)
82 UINT32 multiprecision_most_signbits(DWORD *a, uint32_t keyLength)
86 aMostSignDWORDs = multiprecision_most_signdwords(a, keyLength);
87 if (aMostSignDWORDs == 0)
90 return (((aMostSignDWORDs-1) << DWORD_BITS_SHIFT) +
91 multiprecision_dword_bits(a[aMostSignDWORDs-1]) );
94 DWORD multiprecision_add(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength)
100 for (uint32_t i = 0; i < keyLength; i++)
102 temp = a[i] + carrier;
103 carrier = (temp < carrier);
105 carrier |= (temp < b[i]);
113 DWORD multiprecision_sub(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength)
119 for (uint32_t i=0; i < keyLength; i++)
121 temp = a[i] - borrow;
122 borrow = (temp > a[i]);
124 borrow |= (c[i] > temp);
131 void multiprecision_lshift_mod(DWORD * c, DWORD * a, uint32_t keyLength)
136 if (keyLength == KEY_LENGTH_DWORDS_P192)
140 else if (keyLength == KEY_LENGTH_DWORDS_P256)
147 carrier = multiprecision_lshift(c, a, keyLength);
150 multiprecision_sub(c, c, modp, keyLength);
152 else if (multiprecision_compare(c, modp, keyLength)>=0)
154 multiprecision_sub(c, c, modp, keyLength);
159 void multiprecision_rshift(DWORD * c, DWORD * a, uint32_t keyLength)
168 for (int i = keyLength-1; i >= 0; i--)
170 temp = a[i]; // in case of c==a
171 c[i] = (temp >> b) | carrier;
176 // Curve specific optimization when p is a pseudo-Mersenns prime, p=2^(KEY_LENGTH_BITS)-omega
177 void multiprecision_mersenns_mult_mod(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength)
179 DWORD cc[2*KEY_LENGTH_DWORDS_P256];
181 multiprecision_mult(cc, a, b, keyLength);
184 multiprecision_fast_mod(c, cc);
186 else if (keyLength == 8)
188 multiprecision_fast_mod_P256(c, cc);
192 // Curve specific optimization when p is a pseudo-Mersenns prime
193 void multiprecision_mersenns_squa_mod(DWORD *c, DWORD *a, uint32_t keyLength)
195 multiprecision_mersenns_mult_mod(c, a, a, keyLength);
198 // c=(a+b) mod p, b<p, a<p
199 void multiprecision_add_mod(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength)
204 if (keyLength == KEY_LENGTH_DWORDS_P192)
208 else if (keyLength == KEY_LENGTH_DWORDS_P256)
215 carrier = multiprecision_add(c, a, b, keyLength);
218 multiprecision_sub(c, c, modp, keyLength);
220 else if (multiprecision_compare(c, modp, keyLength) >= 0)
222 multiprecision_sub(c, c, modp, keyLength);
226 // c=(a-b) mod p, a<p, b<p
227 void multiprecision_sub_mod(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength)
232 if (keyLength == KEY_LENGTH_DWORDS_P192)
236 else if(keyLength == KEY_LENGTH_DWORDS_P256)
243 borrow = multiprecision_sub(c, a, b, keyLength);
245 multiprecision_add(c, c, modp, keyLength);
248 // c=a<<b, b<DWORD_BITS, c has a buffer size of NumDWORDs+1
249 DWORD multiprecision_lshift(DWORD * c, DWORD * a, uint32_t keyLength)
258 for (uint32_t i = 0; i < keyLength; i++)
260 temp = a[i]; // in case c==a
261 c[i] = (temp << b) | carrier;
268 // c=a*b; c must have a buffer of 2*Key_LENGTH_DWORDS, c != a != b
269 void multiprecision_mult(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength)
276 multiprecision_init(c, keyLength);
278 //assume little endian right now
279 for (uint32_t i = 0; i < keyLength; i++)
282 for (uint32_t j = 0; j < keyLength; j++)
285 result = ((UINT64)a[i]) * ((uint64_t) b[j]);
299 void multiprecision_fast_mod(DWORD *c, DWORD *a)
303 DWORD *modp = curve.p;
366 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P192);
368 else if(multiprecision_compare(c, modp, KEY_LENGTH_DWORDS_P192) >= 0)
370 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P192);
374 void multiprecision_fast_mod_P256(DWORD *c, DWORD *a)
391 DWORD *modp = curve_p256.p;
393 // C = a[13] + a[14] + a[15];
415 // B = a[12] + a[13] + a[14] + a[15] == C + a[12]
421 // A = a[11] + a[12] + a[13] + a[14] == B + a[11] - a[15]
429 // D = a[10] + a[11] + a[12] + a[13] == A + a[10] - a[14]
618 multiprecision_add(c, c, modp, KEY_LENGTH_DWORDS_P256);
626 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P256);
631 if (multiprecision_compare(c, modp, KEY_LENGTH_DWORDS_P256)>=0)
632 multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P256);
636 void multiprecision_inv_mod(DWORD *aminus, DWORD *u, uint32_t keyLength)
638 DWORD v[KEY_LENGTH_DWORDS_P256];
639 DWORD A[KEY_LENGTH_DWORDS_P256+1];
640 DWORD C[KEY_LENGTH_DWORDS_P256+1];
643 if(keyLength == KEY_LENGTH_DWORDS_P256)
652 multiprecision_copy(v, modp, keyLength);
653 multiprecision_init(A, keyLength);
654 multiprecision_init(C, keyLength);
657 while (!multiprecision_iszero(u, keyLength))
659 while (!(u[0] & 0x01)) // u is even
661 multiprecision_rshift(u, u, keyLength);
662 if(!(A[0] & 0x01)) // A is even
663 multiprecision_rshift(A, A, keyLength);
666 A[keyLength]=multiprecision_add(A, A, modp, keyLength); // A =A+p
667 multiprecision_rshift(A, A, keyLength);
668 A[keyLength-1] |= (A[keyLength]<<31);
672 while (!(v[0] & 0x01)) // v is even
674 multiprecision_rshift(v, v, keyLength);
675 if (!(C[0] & 0x01)) // C is even
677 multiprecision_rshift(C, C, keyLength);
681 C[keyLength] = multiprecision_add(C, C, modp, keyLength); // C =C+p
682 multiprecision_rshift(C, C, keyLength);
683 C[keyLength-1] |= (C[keyLength] << 31);
687 if (multiprecision_compare(u, v, keyLength) >= 0)
689 multiprecision_sub(u, u, v, keyLength);
690 multiprecision_sub_mod(A, A, C, keyLength);
694 multiprecision_sub(v, v, u, keyLength);
695 multiprecision_sub_mod(C, C, A, keyLength);
699 if (multiprecision_compare(C, modp, keyLength) >= 0)
700 multiprecision_sub(aminus, C, modp, keyLength);
702 multiprecision_copy(aminus, C, keyLength);