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