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