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 using Elliptic Curve
22 * Cryptography for private public key
23 *
24 ******************************************************************************/
25 #include "security/ecc/p_256_ecc_pp.h"
26
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "security/ecc/multprecision.h"
31
32 namespace bluetooth {
33 namespace security {
34 namespace ecc {
35
36 const uint32_t* modp = curve_p256.p;
37
p_256_init_point(Point * q)38 static void p_256_init_point(Point* q) {
39 memset(q, 0, sizeof(Point));
40 }
41
p_256_copy_point(Point * q,const Point * p)42 static void p_256_copy_point(Point* q, const Point* p) {
43 memcpy(q, p, sizeof(Point));
44 }
45
46 // q=2q
ECC_Double(Point * q,const Point * p)47 static void ECC_Double(Point* q, const Point* p) {
48 uint32_t t1[KEY_LENGTH_DWORDS_P256];
49 uint32_t t2[KEY_LENGTH_DWORDS_P256];
50 uint32_t t3[KEY_LENGTH_DWORDS_P256];
51 const uint32_t* x1;
52 uint32_t* x3;
53 const uint32_t* y1;
54 uint32_t* y3;
55 const uint32_t* z1;
56 uint32_t* z3;
57
58 if (multiprecision_iszero(p->z)) {
59 multiprecision_init(q->z);
60 return; // return infinity
61 }
62
63 x1 = p->x;
64 y1 = p->y;
65 z1 = p->z;
66 x3 = q->x;
67 y3 = q->y;
68 z3 = q->z;
69
70 multiprecision_mersenns_squa_mod(t1, z1, modp); // t1=z1^2
71 multiprecision_sub_mod(t2, x1, t1, modp); // t2=x1-t1
72 multiprecision_add_mod(t1, x1, t1, modp); // t1=x1+t1
73 multiprecision_mersenns_mult_mod(t2, t1, t2, modp); // t2=t2*t1
74 multiprecision_lshift_mod(t3, t2, modp);
75 multiprecision_add_mod(t2, t3, t2, modp); // t2=3t2
76
77 multiprecision_mersenns_mult_mod(z3, y1, z1, modp); // z3=y1*z1
78 multiprecision_lshift_mod(z3, z3, modp);
79
80 multiprecision_mersenns_squa_mod(y3, y1, modp); // y3=y1^2
81 multiprecision_lshift_mod(y3, y3, modp);
82 multiprecision_mersenns_mult_mod(t3, y3, x1, modp); // t3=y3*x1=x1*y1^2
83 multiprecision_lshift_mod(t3, t3, modp);
84 multiprecision_mersenns_squa_mod(y3, y3, modp); // y3=y3^2=y1^4
85 multiprecision_lshift_mod(y3, y3, modp);
86
87 multiprecision_mersenns_squa_mod(x3, t2, modp); // x3=t2^2
88 multiprecision_lshift_mod(t1, t3, modp); // t1=2t3
89 multiprecision_sub_mod(x3, x3, t1, modp); // x3=x3-t1
90 multiprecision_sub_mod(t1, t3, x3, modp); // t1=t3-x3
91 multiprecision_mersenns_mult_mod(t1, t1, t2, modp); // t1=t1*t2
92 multiprecision_sub_mod(y3, t1, y3, modp); // y3=t1-y3
93 }
94
95 // q=q+p, zp must be 1
ECC_Add(Point * r,Point * p,const Point * q)96 static void ECC_Add(Point* r, Point* p, const Point* q) {
97 uint32_t t1[KEY_LENGTH_DWORDS_P256];
98 uint32_t t2[KEY_LENGTH_DWORDS_P256];
99 uint32_t* x1;
100 const uint32_t* x2;
101 uint32_t* x3;
102 uint32_t* y1;
103 const uint32_t* y2;
104 uint32_t* y3;
105 uint32_t* z1;
106 const uint32_t* z2;
107 uint32_t* z3;
108
109 x1 = p->x;
110 y1 = p->y;
111 z1 = p->z;
112 x2 = q->x;
113 y2 = q->y;
114 z2 = q->z;
115 x3 = r->x;
116 y3 = r->y;
117 z3 = r->z;
118
119 // if Q=infinity, return p
120 if (multiprecision_iszero(z2)) {
121 p_256_copy_point(r, p);
122 return;
123 }
124
125 // if P=infinity, return q
126 if (multiprecision_iszero(z1)) {
127 p_256_copy_point(r, q);
128 return;
129 }
130
131 multiprecision_mersenns_squa_mod(t1, z1, modp); // t1=z1^2
132 multiprecision_mersenns_mult_mod(t2, z1, t1, modp); // t2=t1*z1
133 multiprecision_mersenns_mult_mod(t1, x2, t1, modp); // t1=t1*x2
134 multiprecision_mersenns_mult_mod(t2, y2, t2, modp); // t2=t2*y2
135
136 multiprecision_sub_mod(t1, t1, x1, modp); // t1=t1-x1
137 multiprecision_sub_mod(t2, t2, y1, modp); // t2=t2-y1
138
139 if (multiprecision_iszero(t1)) {
140 if (multiprecision_iszero(t2)) {
141 ECC_Double(r, q);
142 return;
143 } else {
144 multiprecision_init(z3);
145 return; // return infinity
146 }
147 }
148
149 multiprecision_mersenns_mult_mod(z3, z1, t1, modp); // z3=z1*t1
150 multiprecision_mersenns_squa_mod(y3, t1, modp); // t3=t1^2
151 multiprecision_mersenns_mult_mod(z1, y3, t1, modp); // t4=t3*t1
152 multiprecision_mersenns_mult_mod(y3, y3, x1, modp); // t3=t3*x1
153 multiprecision_lshift_mod(t1, y3, modp); // t1=2*t3
154 multiprecision_mersenns_squa_mod(x3, t2, modp); // x3=t2^2
155 multiprecision_sub_mod(x3, x3, t1, modp); // x3=x3-t1
156 multiprecision_sub_mod(x3, x3, z1, modp); // x3=x3-t4
157 multiprecision_sub_mod(y3, y3, x3, modp); // t3=t3-x3
158 multiprecision_mersenns_mult_mod(y3, y3, t2, modp); // t3=t3*t2
159 multiprecision_mersenns_mult_mod(z1, z1, y1, modp); // t4=t4*t1
160 multiprecision_sub_mod(y3, y3, z1, modp);
161 }
162
163 // Computing the Non-Adjacent Form of a positive integer
ECC_NAF(uint8_t * naf,uint32_t * NumNAF,uint32_t * k)164 static void ECC_NAF(uint8_t* naf, uint32_t* NumNAF, uint32_t* k) {
165 uint32_t sign;
166 int i = 0;
167 int j;
168 uint32_t var;
169
170 while ((var = multiprecision_most_signbits(k)) >= 1) {
171 if (k[0] & 0x01) // k is odd
172 {
173 sign = (k[0] & 0x03); // 1 or 3
174
175 // k = k-naf[i]
176 if (sign == 1)
177 k[0] = k[0] & 0xFFFFFFFE;
178 else {
179 k[0] = k[0] + 1;
180 if (k[0] == 0) // overflow
181 {
182 j = 1;
183 do {
184 k[j]++;
185 } while (k[j++] == 0); // overflow
186 }
187 }
188 } else
189 sign = 0;
190
191 multiprecision_rshift(k, k);
192 naf[i / 4] |= (sign) << ((i % 4) * 2);
193 i++;
194 }
195
196 *NumNAF = i;
197 }
198
199 // Binary Non-Adjacent Form for point multiplication
ECC_PointMult_Bin_NAF(Point * q,const Point * p,uint32_t * n)200 void ECC_PointMult_Bin_NAF(Point* q, const Point* p, uint32_t* n) {
201 uint32_t sign;
202 uint8_t naf[256 / 4 + 1];
203 uint32_t NumNaf;
204 Point minus_p;
205 Point r;
206
207 p_256_init_point(&r);
208
209 // initialization
210 p_256_init_point(q);
211
212 // -p
213 multiprecision_copy(minus_p.x, p->x);
214 multiprecision_sub(minus_p.y, modp, p->y);
215
216 multiprecision_init(minus_p.z);
217 minus_p.z[0] = 1;
218
219 // NAF
220 memset(naf, 0, sizeof(naf));
221 ECC_NAF(naf, &NumNaf, n);
222
223 for (int i = NumNaf - 1; i >= 0; i--) {
224 p_256_copy_point(&r, q);
225 ECC_Double(q, &r);
226 sign = (naf[i / 4] >> ((i % 4) * 2)) & 0x03;
227
228 if (sign == 1) {
229 p_256_copy_point(&r, q);
230 ECC_Add(q, &r, p);
231 } else if (sign == 3) {
232 p_256_copy_point(&r, q);
233 ECC_Add(q, &r, &minus_p);
234 }
235 }
236
237 multiprecision_inv_mod(minus_p.x, q->z, modp);
238 multiprecision_mersenns_squa_mod(q->z, minus_p.x, modp);
239 multiprecision_mersenns_mult_mod(q->x, q->x, q->z, modp);
240 multiprecision_mersenns_mult_mod(q->z, q->z, minus_p.x, modp);
241 multiprecision_mersenns_mult_mod(q->y, q->y, q->z, modp);
242 }
243
ECC_ValidatePoint(const Point & pt)244 bool ECC_ValidatePoint(const Point& pt) {
245 // Ensure y^2 = x^3 + a*x + b (mod p); a = -3
246
247 // y^2 mod p
248 uint32_t y2_mod[KEY_LENGTH_DWORDS_P256] = {0};
249 multiprecision_mersenns_squa_mod(y2_mod, (uint32_t*)pt.y, modp);
250
251 // Right hand side calculation
252 uint32_t rhs[KEY_LENGTH_DWORDS_P256] = {0};
253 multiprecision_mersenns_squa_mod(rhs, (uint32_t*)pt.x, modp);
254 uint32_t three[KEY_LENGTH_DWORDS_P256] = {0};
255 three[0] = 3;
256 multiprecision_sub_mod(rhs, rhs, three, modp);
257 multiprecision_mersenns_mult_mod(rhs, rhs, (uint32_t*)pt.x, modp);
258 multiprecision_add_mod(rhs, rhs, curve_p256.b, modp);
259
260 return multiprecision_compare(rhs, y2_mod) == 0;
261 }
262
263 } // namespace ecc
264 } // namespace security
265 } // namespace bluetooth
266