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