1 // SPDX-License-Identifier: BSD-2-Clause 2 /* 3 * Copyright (c) 2018, Linaro limited 4 */ 5 #include <assert.h> 6 #include <mbedtls/bignum.h> 7 #include <mempool.h> 8 #include <stdio.h> 9 #include <string.h> 10 #include <tee_api.h> 11 #include <tee_arith_internal.h> 12 #include <utee_defines.h> 13 #include <utee_syscalls.h> 14 #include <util.h> 15 16 #define MPI_MEMPOOL_SIZE (12 * 1024) 17 18 static void __noreturn api_panic(const char *func, int line, const char *msg) 19 { 20 printf("Panic function %s, line %d: %s\n", func, line, msg); 21 TEE_Panic(0xB16127 /*BIGINT*/); 22 while (1) 23 ; /* Panic will crash the thread */ 24 } 25 26 #define API_PANIC(x) api_panic(__func__, __LINE__, x) 27 28 static void __noreturn mpi_panic(const char *func, int line, int rc) 29 { 30 printf("Panic function %s, line %d, code %d\n", func, line, rc); 31 TEE_Panic(0xB16127 /*BIGINT*/); 32 while (1) 33 ; /* Panic will crash the thread */ 34 } 35 36 #define MPI_CHECK(x) do { \ 37 int _rc = (x); \ 38 \ 39 if (_rc) \ 40 mpi_panic(__func__, __LINE__, _rc); \ 41 } while (0) 42 43 void _TEE_MathAPI_Init(void) 44 { 45 static uint8_t data[MPI_MEMPOOL_SIZE] __aligned(MEMPOOL_ALIGN); 46 47 mbedtls_mpi_mempool = mempool_alloc_pool(data, sizeof(data), NULL); 48 if (!mbedtls_mpi_mempool) 49 API_PANIC("Failed to initialize memory pool"); 50 } 51 52 struct bigint_hdr { 53 int32_t sign; 54 uint16_t alloc_size; 55 uint16_t nblimbs; 56 }; 57 58 #define BIGINT_HDR_SIZE_IN_U32 2 59 60 static TEE_Result copy_mpi_to_bigint(mbedtls_mpi *mpi, TEE_BigInt *bigInt) 61 { 62 struct bigint_hdr *hdr = (struct bigint_hdr *)bigInt; 63 size_t n = mpi->n; 64 65 /* Trim of eventual insignificant zeroes */ 66 while (n && !mpi->p[n - 1]) 67 n--; 68 69 if (hdr->alloc_size < n) 70 return TEE_ERROR_OVERFLOW; 71 72 hdr->nblimbs = n; 73 hdr->sign = mpi->s; 74 memcpy(hdr + 1, mpi->p, mpi->n * sizeof(mbedtls_mpi_uint)); 75 76 return TEE_SUCCESS; 77 } 78 79 /* 80 * Initializes a MPI. 81 * 82 * A temporary MPI is allocated and if a bigInt is supplied the MPI is 83 * initialized with the value of the bigInt. 84 */ 85 static void get_mpi(mbedtls_mpi *mpi, const TEE_BigInt *bigInt) 86 { 87 /* 88 * The way the GP spec is defining the bignums it's 89 * difficult/tricky to do it using 64-bit arithmetics given that 90 * we'd need 64-bit alignment of the data as well. 91 */ 92 COMPILE_TIME_ASSERT(sizeof(mbedtls_mpi_uint) == sizeof(uint32_t)); 93 94 /* 95 * The struct bigint_hdr is the overhead added to the bigint and 96 * is required to take exactly 2 uint32_t. 97 */ 98 COMPILE_TIME_ASSERT(sizeof(struct bigint_hdr) == 99 sizeof(uint32_t) * BIGINT_HDR_SIZE_IN_U32); 100 101 mbedtls_mpi_init_mempool(mpi); 102 103 if (bigInt) { 104 const struct bigint_hdr *hdr = (struct bigint_hdr *)bigInt; 105 const mbedtls_mpi_uint *p = (const mbedtls_mpi_uint *)(hdr + 1); 106 size_t n = hdr->nblimbs; 107 108 /* Trim of eventual insignificant zeroes */ 109 while (n && !p[n - 1]) 110 n--; 111 112 MPI_CHECK(mbedtls_mpi_grow(mpi, n)); 113 mpi->s = hdr->sign; 114 memcpy(mpi->p, p, n * sizeof(mbedtls_mpi_uint)); 115 } 116 } 117 118 void TEE_BigIntInit(TEE_BigInt *bigInt, uint32_t len) 119 { 120 struct bigint_hdr *hdr = (struct bigint_hdr *)bigInt; 121 122 memset(bigInt, 0, len * sizeof(uint32_t)); 123 hdr->sign = 1; 124 if ((len - BIGINT_HDR_SIZE_IN_U32) > MBEDTLS_MPI_MAX_LIMBS) 125 API_PANIC("Too large bigint"); 126 hdr->alloc_size = len - BIGINT_HDR_SIZE_IN_U32; 127 } 128 129 TEE_Result TEE_BigIntConvertFromOctetString(TEE_BigInt *dest, 130 const uint8_t *buffer, 131 uint32_t bufferLen, int32_t sign) 132 { 133 TEE_Result res; 134 mbedtls_mpi mpi_dest; 135 136 get_mpi(&mpi_dest, NULL); 137 138 if (mbedtls_mpi_read_binary(&mpi_dest, buffer, bufferLen)) 139 res = TEE_ERROR_OVERFLOW; 140 else 141 res = TEE_SUCCESS; 142 143 if (sign < 0) 144 mpi_dest.s = -1; 145 146 if (!res) 147 res = copy_mpi_to_bigint(&mpi_dest, dest); 148 149 mbedtls_mpi_free(&mpi_dest); 150 151 return res; 152 } 153 154 TEE_Result TEE_BigIntConvertToOctetString(uint8_t *buffer, uint32_t *bufferLen, 155 const TEE_BigInt *bigInt) 156 { 157 TEE_Result res = TEE_SUCCESS; 158 mbedtls_mpi mpi; 159 size_t sz; 160 161 get_mpi(&mpi, bigInt); 162 163 sz = mbedtls_mpi_size(&mpi); 164 if (sz <= *bufferLen) 165 MPI_CHECK(mbedtls_mpi_write_binary(&mpi, buffer, sz)); 166 else 167 res = TEE_ERROR_SHORT_BUFFER; 168 169 *bufferLen = sz; 170 171 mbedtls_mpi_free(&mpi); 172 173 return res; 174 } 175 176 void TEE_BigIntConvertFromS32(TEE_BigInt *dest, int32_t shortVal) 177 { 178 mbedtls_mpi mpi; 179 180 get_mpi(&mpi, dest); 181 182 MPI_CHECK(mbedtls_mpi_lset(&mpi, shortVal)); 183 184 MPI_CHECK(copy_mpi_to_bigint(&mpi, dest)); 185 mbedtls_mpi_free(&mpi); 186 } 187 188 TEE_Result TEE_BigIntConvertToS32(int32_t *dest, const TEE_BigInt *src) 189 { 190 TEE_Result res = TEE_SUCCESS; 191 mbedtls_mpi mpi; 192 uint32_t v; 193 194 get_mpi(&mpi, src); 195 196 if (mbedtls_mpi_write_binary(&mpi, (void *)&v, sizeof(v))) { 197 res = TEE_ERROR_OVERFLOW; 198 goto out; 199 } 200 201 if (mpi.s > 0) { 202 if (ADD_OVERFLOW(0, TEE_U32_FROM_BIG_ENDIAN(v), dest)) 203 res = TEE_ERROR_OVERFLOW; 204 } else { 205 if (SUB_OVERFLOW(0, TEE_U32_FROM_BIG_ENDIAN(v), dest)) 206 res = TEE_ERROR_OVERFLOW; 207 } 208 209 out: 210 mbedtls_mpi_free(&mpi); 211 212 return res; 213 } 214 215 int32_t TEE_BigIntCmp(const TEE_BigInt *op1, const TEE_BigInt *op2) 216 { 217 mbedtls_mpi mpi1; 218 mbedtls_mpi mpi2; 219 int32_t rc; 220 221 get_mpi(&mpi1, op1); 222 get_mpi(&mpi2, op2); 223 224 rc = mbedtls_mpi_cmp_mpi(&mpi1, &mpi2); 225 226 mbedtls_mpi_free(&mpi1); 227 mbedtls_mpi_free(&mpi2); 228 229 return rc; 230 } 231 232 int32_t TEE_BigIntCmpS32(const TEE_BigInt *op, int32_t shortVal) 233 { 234 mbedtls_mpi mpi; 235 int32_t rc; 236 237 get_mpi(&mpi, op); 238 239 rc = mbedtls_mpi_cmp_int(&mpi, shortVal); 240 241 mbedtls_mpi_free(&mpi); 242 243 return rc; 244 } 245 246 void TEE_BigIntShiftRight(TEE_BigInt *dest, const TEE_BigInt *op, size_t bits) 247 { 248 mbedtls_mpi mpi_dest; 249 mbedtls_mpi mpi_op; 250 251 get_mpi(&mpi_dest, dest); 252 253 if (dest == op) { 254 MPI_CHECK(mbedtls_mpi_shift_r(&mpi_dest, bits)); 255 goto out; 256 } 257 258 get_mpi(&mpi_op, op); 259 260 if (mbedtls_mpi_size(&mpi_dest) >= mbedtls_mpi_size(&mpi_op)) { 261 MPI_CHECK(mbedtls_mpi_copy(&mpi_dest, &mpi_op)); 262 MPI_CHECK(mbedtls_mpi_shift_r(&mpi_dest, bits)); 263 } else { 264 mbedtls_mpi mpi_t; 265 266 get_mpi(&mpi_t, NULL); 267 268 /* 269 * We're using a temporary buffer to avoid the corner case 270 * where destination is unexpectedly overflowed by up to 271 * @bits number of bits. 272 */ 273 MPI_CHECK(mbedtls_mpi_copy(&mpi_t, &mpi_op)); 274 MPI_CHECK(mbedtls_mpi_shift_r(&mpi_t, bits)); 275 MPI_CHECK(mbedtls_mpi_copy(&mpi_dest, &mpi_t)); 276 277 mbedtls_mpi_free(&mpi_t); 278 } 279 280 mbedtls_mpi_free(&mpi_op); 281 282 out: 283 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 284 mbedtls_mpi_free(&mpi_dest); 285 } 286 287 bool TEE_BigIntGetBit(const TEE_BigInt *src, uint32_t bitIndex) 288 { 289 bool rc; 290 mbedtls_mpi mpi; 291 292 get_mpi(&mpi, src); 293 294 rc = mbedtls_mpi_get_bit(&mpi, bitIndex); 295 296 mbedtls_mpi_free(&mpi); 297 298 return rc; 299 } 300 301 uint32_t TEE_BigIntGetBitCount(const TEE_BigInt *src) 302 { 303 uint32_t rc; 304 mbedtls_mpi mpi; 305 306 get_mpi(&mpi, src); 307 308 rc = mbedtls_mpi_bitlen(&mpi); 309 310 mbedtls_mpi_free(&mpi); 311 312 return rc; 313 } 314 315 static void bigint_binary(TEE_BigInt *dest, const TEE_BigInt *op1, 316 const TEE_BigInt *op2, 317 int (*func)(mbedtls_mpi *X, const mbedtls_mpi *A, 318 const mbedtls_mpi *B)) 319 { 320 mbedtls_mpi mpi_dest; 321 mbedtls_mpi mpi_op1; 322 mbedtls_mpi mpi_op2; 323 mbedtls_mpi *pop1 = &mpi_op1; 324 mbedtls_mpi *pop2 = &mpi_op2; 325 326 get_mpi(&mpi_dest, dest); 327 328 if (op1 == dest) 329 pop1 = &mpi_dest; 330 else 331 get_mpi(&mpi_op1, op1); 332 333 if (op2 == dest) 334 pop2 = &mpi_dest; 335 else if (op2 == op1) 336 pop2 = pop1; 337 else 338 get_mpi(&mpi_op2, op2); 339 340 MPI_CHECK(func(&mpi_dest, pop1, pop2)); 341 342 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 343 mbedtls_mpi_free(&mpi_dest); 344 if (pop1 == &mpi_op1) 345 mbedtls_mpi_free(&mpi_op1); 346 if (pop2 == &mpi_op2) 347 mbedtls_mpi_free(&mpi_op2); 348 } 349 350 static void bigint_binary_mod(TEE_BigInt *dest, const TEE_BigInt *op1, 351 const TEE_BigInt *op2, const TEE_BigInt *n, 352 int (*func)(mbedtls_mpi *X, const mbedtls_mpi *A, 353 const mbedtls_mpi *B)) 354 { 355 mbedtls_mpi mpi_dest; 356 mbedtls_mpi mpi_op1; 357 mbedtls_mpi mpi_op2; 358 mbedtls_mpi mpi_n; 359 mbedtls_mpi *pop1 = &mpi_op1; 360 mbedtls_mpi *pop2 = &mpi_op2; 361 mbedtls_mpi mpi_t; 362 363 if (TEE_BigIntCmpS32(n, 2) < 0) 364 API_PANIC("Modulus is too short"); 365 366 get_mpi(&mpi_dest, dest); 367 get_mpi(&mpi_n, n); 368 369 if (op1 == dest) 370 pop1 = &mpi_dest; 371 else 372 get_mpi(&mpi_op1, op1); 373 374 if (op2 == dest) 375 pop2 = &mpi_dest; 376 else if (op2 == op1) 377 pop2 = pop1; 378 else 379 get_mpi(&mpi_op2, op2); 380 381 get_mpi(&mpi_t, NULL); 382 383 MPI_CHECK(func(&mpi_t, pop1, pop2)); 384 MPI_CHECK(mbedtls_mpi_mod_mpi(&mpi_dest, &mpi_t, &mpi_n)); 385 386 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 387 mbedtls_mpi_free(&mpi_dest); 388 if (pop1 == &mpi_op1) 389 mbedtls_mpi_free(&mpi_op1); 390 if (pop2 == &mpi_op2) 391 mbedtls_mpi_free(&mpi_op2); 392 mbedtls_mpi_free(&mpi_t); 393 mbedtls_mpi_free(&mpi_n); 394 } 395 396 void TEE_BigIntAdd(TEE_BigInt *dest, const TEE_BigInt *op1, 397 const TEE_BigInt *op2) 398 { 399 bigint_binary(dest, op1, op2, mbedtls_mpi_add_mpi); 400 } 401 402 void TEE_BigIntSub(TEE_BigInt *dest, const TEE_BigInt *op1, 403 const TEE_BigInt *op2) 404 { 405 bigint_binary(dest, op1, op2, mbedtls_mpi_sub_mpi); 406 } 407 408 void TEE_BigIntNeg(TEE_BigInt *dest, const TEE_BigInt *src) 409 { 410 mbedtls_mpi mpi_dest; 411 412 get_mpi(&mpi_dest, dest); 413 414 if (dest != src) { 415 mbedtls_mpi mpi_src; 416 417 get_mpi(&mpi_src, src); 418 419 MPI_CHECK(mbedtls_mpi_copy(&mpi_dest, &mpi_src)); 420 421 mbedtls_mpi_free(&mpi_src); 422 } 423 424 mpi_dest.s *= -1; 425 426 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 427 mbedtls_mpi_free(&mpi_dest); 428 } 429 430 void TEE_BigIntMul(TEE_BigInt *dest, const TEE_BigInt *op1, 431 const TEE_BigInt *op2) 432 { 433 size_t bs1 = TEE_BigIntGetBitCount(op1); 434 size_t bs2 = TEE_BigIntGetBitCount(op2); 435 size_t s = TEE_BigIntSizeInU32(bs1) + TEE_BigIntSizeInU32(bs2); 436 TEE_BigInt zero[TEE_BigIntSizeInU32(1)] = { 0 }; 437 TEE_BigInt *tmp = NULL; 438 439 tmp = mempool_alloc(mbedtls_mpi_mempool, sizeof(uint32_t) * s); 440 if (!tmp) 441 TEE_Panic(TEE_ERROR_OUT_OF_MEMORY); 442 443 TEE_BigIntInit(tmp, s); 444 TEE_BigIntInit(zero, TEE_BigIntSizeInU32(1)); 445 446 bigint_binary(tmp, op1, op2, mbedtls_mpi_mul_mpi); 447 448 TEE_BigIntAdd(dest, tmp, zero); 449 450 mempool_free(mbedtls_mpi_mempool, tmp); 451 } 452 453 void TEE_BigIntSquare(TEE_BigInt *dest, const TEE_BigInt *op) 454 { 455 TEE_BigIntMul(dest, op, op); 456 } 457 458 void TEE_BigIntDiv(TEE_BigInt *dest_q, TEE_BigInt *dest_r, 459 const TEE_BigInt *op1, const TEE_BigInt *op2) 460 { 461 mbedtls_mpi mpi_dest_q; 462 mbedtls_mpi mpi_dest_r; 463 mbedtls_mpi mpi_op1; 464 mbedtls_mpi mpi_op2; 465 mbedtls_mpi *pop1 = &mpi_op1; 466 mbedtls_mpi *pop2 = &mpi_op2; 467 468 get_mpi(&mpi_dest_q, dest_q); 469 get_mpi(&mpi_dest_r, dest_r); 470 471 if (op1 == dest_q) 472 pop1 = &mpi_dest_q; 473 else if (op1 == dest_r) 474 pop1 = &mpi_dest_r; 475 else 476 get_mpi(&mpi_op1, op1); 477 478 if (op2 == dest_q) 479 pop2 = &mpi_dest_q; 480 else if (op2 == dest_r) 481 pop2 = &mpi_dest_r; 482 else if (op2 == op1) 483 pop2 = pop1; 484 else 485 get_mpi(&mpi_op2, op2); 486 487 MPI_CHECK(mbedtls_mpi_div_mpi(&mpi_dest_q, &mpi_dest_r, pop1, pop2)); 488 489 if (dest_q) 490 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest_q, dest_q)); 491 if (dest_r) 492 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest_r, dest_r)); 493 mbedtls_mpi_free(&mpi_dest_q); 494 mbedtls_mpi_free(&mpi_dest_r); 495 if (pop1 == &mpi_op1) 496 mbedtls_mpi_free(&mpi_op1); 497 if (pop2 == &mpi_op2) 498 mbedtls_mpi_free(&mpi_op2); 499 } 500 501 void TEE_BigIntMod(TEE_BigInt *dest, const TEE_BigInt *op, const TEE_BigInt *n) 502 { 503 if (TEE_BigIntCmpS32(n, 2) < 0) 504 API_PANIC("Modulus is too short"); 505 506 bigint_binary(dest, op, n, mbedtls_mpi_mod_mpi); 507 } 508 509 void TEE_BigIntAddMod(TEE_BigInt *dest, const TEE_BigInt *op1, 510 const TEE_BigInt *op2, const TEE_BigInt *n) 511 { 512 bigint_binary_mod(dest, op1, op2, n, mbedtls_mpi_add_mpi); 513 } 514 515 void TEE_BigIntSubMod(TEE_BigInt *dest, const TEE_BigInt *op1, 516 const TEE_BigInt *op2, const TEE_BigInt *n) 517 { 518 bigint_binary_mod(dest, op1, op2, n, mbedtls_mpi_sub_mpi); 519 } 520 521 void TEE_BigIntMulMod(TEE_BigInt *dest, const TEE_BigInt *op1, 522 const TEE_BigInt *op2, const TEE_BigInt *n) 523 { 524 bigint_binary_mod(dest, op1, op2, n, mbedtls_mpi_mul_mpi); 525 } 526 527 void TEE_BigIntSquareMod(TEE_BigInt *dest, const TEE_BigInt *op, 528 const TEE_BigInt *n) 529 { 530 TEE_BigIntMulMod(dest, op, op, n); 531 } 532 533 void TEE_BigIntInvMod(TEE_BigInt *dest, const TEE_BigInt *op, 534 const TEE_BigInt *n) 535 { 536 mbedtls_mpi mpi_dest; 537 mbedtls_mpi mpi_op; 538 mbedtls_mpi mpi_n; 539 mbedtls_mpi *pop = &mpi_op; 540 541 if (TEE_BigIntCmpS32(n, 2) < 0 || TEE_BigIntCmpS32(op, 0) == 0) 542 API_PANIC("too small modulus or trying to invert zero"); 543 544 get_mpi(&mpi_dest, dest); 545 get_mpi(&mpi_n, n); 546 547 if (op == dest) 548 pop = &mpi_dest; 549 else 550 get_mpi(&mpi_op, op); 551 552 MPI_CHECK(mbedtls_mpi_inv_mod(&mpi_dest, pop, &mpi_n)); 553 554 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 555 mbedtls_mpi_free(&mpi_dest); 556 mbedtls_mpi_free(&mpi_n); 557 if (pop == &mpi_op) 558 mbedtls_mpi_free(&mpi_op); 559 } 560 561 bool TEE_BigIntRelativePrime(const TEE_BigInt *op1, const TEE_BigInt *op2) 562 { 563 bool rc; 564 mbedtls_mpi mpi_op1; 565 mbedtls_mpi mpi_op2; 566 mbedtls_mpi *pop2 = &mpi_op2; 567 mbedtls_mpi gcd; 568 569 get_mpi(&mpi_op1, op1); 570 571 if (op2 == op1) 572 pop2 = &mpi_op1; 573 else 574 get_mpi(&mpi_op2, op2); 575 576 get_mpi(&gcd, NULL); 577 578 MPI_CHECK(mbedtls_mpi_gcd(&gcd, &mpi_op1, &mpi_op2)); 579 580 rc = !mbedtls_mpi_cmp_int(&gcd, 1); 581 582 mbedtls_mpi_free(&gcd); 583 mbedtls_mpi_free(&mpi_op1); 584 if (pop2 == &mpi_op2) 585 mbedtls_mpi_free(&mpi_op2); 586 587 return rc; 588 } 589 590 static bool mpi_is_odd(mbedtls_mpi *x) 591 { 592 return mbedtls_mpi_get_bit(x, 0); 593 } 594 595 static bool mpi_is_even(mbedtls_mpi *x) 596 { 597 return !mpi_is_odd(x); 598 } 599 600 /* 601 * Based on libmpa implementation __mpa_egcd(), modified to work with MPI 602 * instead. 603 */ 604 static void mpi_egcd(mbedtls_mpi *gcd, mbedtls_mpi *a, mbedtls_mpi *b, 605 mbedtls_mpi *x_in, mbedtls_mpi *y_in) 606 { 607 mbedtls_mpi_uint k; 608 mbedtls_mpi A; 609 mbedtls_mpi B; 610 mbedtls_mpi C; 611 mbedtls_mpi D; 612 mbedtls_mpi x; 613 mbedtls_mpi y; 614 mbedtls_mpi u; 615 616 get_mpi(&A, NULL); 617 get_mpi(&B, NULL); 618 get_mpi(&C, NULL); 619 get_mpi(&D, NULL); 620 get_mpi(&x, NULL); 621 get_mpi(&y, NULL); 622 get_mpi(&u, NULL); 623 624 /* have y < x from assumption */ 625 if (!mbedtls_mpi_cmp_int(y_in, 0)) { 626 MPI_CHECK(mbedtls_mpi_lset(a, 1)); 627 MPI_CHECK(mbedtls_mpi_lset(b, 0)); 628 MPI_CHECK(mbedtls_mpi_copy(gcd, x_in)); 629 goto out; 630 } 631 632 MPI_CHECK(mbedtls_mpi_copy(&x, x_in)); 633 MPI_CHECK(mbedtls_mpi_copy(&y, y_in)); 634 635 k = 0; 636 while (mpi_is_even(&x) && mpi_is_even(&y)) { 637 k++; 638 MPI_CHECK(mbedtls_mpi_shift_r(&x, 1)); 639 MPI_CHECK(mbedtls_mpi_shift_r(&y, 1)); 640 } 641 642 MPI_CHECK(mbedtls_mpi_copy(&u, &x)); 643 MPI_CHECK(mbedtls_mpi_copy(gcd, &y)); 644 MPI_CHECK(mbedtls_mpi_lset(&A, 1)); 645 MPI_CHECK(mbedtls_mpi_lset(&B, 0)); 646 MPI_CHECK(mbedtls_mpi_lset(&C, 0)); 647 MPI_CHECK(mbedtls_mpi_lset(&D, 1)); 648 649 while (mbedtls_mpi_cmp_int(&u, 0)) { 650 while (mpi_is_even(&u)) { 651 MPI_CHECK(mbedtls_mpi_shift_r(&u, 1)); 652 if (mpi_is_odd(&A) || mpi_is_odd(&B)) { 653 MPI_CHECK(mbedtls_mpi_add_mpi(&A, &A, &y)); 654 MPI_CHECK(mbedtls_mpi_sub_mpi(&B, &B, &x)); 655 } 656 MPI_CHECK(mbedtls_mpi_shift_r(&A, 1)); 657 MPI_CHECK(mbedtls_mpi_shift_r(&B, 1)); 658 } 659 660 while (mpi_is_even(gcd)) { 661 MPI_CHECK(mbedtls_mpi_shift_r(gcd, 1)); 662 if (mpi_is_odd(&C) || mpi_is_odd(&D)) { 663 MPI_CHECK(mbedtls_mpi_add_mpi(&C, &C, &y)); 664 MPI_CHECK(mbedtls_mpi_sub_mpi(&D, &D, &x)); 665 } 666 MPI_CHECK(mbedtls_mpi_shift_r(&C, 1)); 667 MPI_CHECK(mbedtls_mpi_shift_r(&D, 1)); 668 669 } 670 671 if (mbedtls_mpi_cmp_mpi(&u, gcd) >= 0) { 672 MPI_CHECK(mbedtls_mpi_sub_mpi(&u, &u, gcd)); 673 MPI_CHECK(mbedtls_mpi_sub_mpi(&A, &A, &C)); 674 MPI_CHECK(mbedtls_mpi_sub_mpi(&B, &B, &D)); 675 } else { 676 MPI_CHECK(mbedtls_mpi_sub_mpi(gcd, gcd, &u)); 677 MPI_CHECK(mbedtls_mpi_sub_mpi(&C, &C, &A)); 678 MPI_CHECK(mbedtls_mpi_sub_mpi(&D, &D, &B)); 679 } 680 } 681 682 MPI_CHECK(mbedtls_mpi_copy(a, &C)); 683 MPI_CHECK(mbedtls_mpi_copy(b, &D)); 684 MPI_CHECK(mbedtls_mpi_shift_l(gcd, k)); 685 686 out: 687 mbedtls_mpi_free(&A); 688 mbedtls_mpi_free(&B); 689 mbedtls_mpi_free(&C); 690 mbedtls_mpi_free(&D); 691 mbedtls_mpi_free(&x); 692 mbedtls_mpi_free(&y); 693 mbedtls_mpi_free(&u); 694 } 695 696 void TEE_BigIntComputeExtendedGcd(TEE_BigInt *gcd, TEE_BigInt *u, 697 TEE_BigInt *v, const TEE_BigInt *op1, 698 const TEE_BigInt *op2) 699 { 700 mbedtls_mpi mpi_gcd_res; 701 mbedtls_mpi mpi_op1; 702 mbedtls_mpi mpi_op2; 703 mbedtls_mpi *pop2 = &mpi_op2; 704 705 get_mpi(&mpi_gcd_res, gcd); 706 get_mpi(&mpi_op1, op1); 707 708 if (op2 == op1) 709 pop2 = &mpi_op1; 710 else 711 get_mpi(&mpi_op2, op2); 712 713 if (!u && !v) { 714 MPI_CHECK(mbedtls_mpi_gcd(&mpi_gcd_res, &mpi_op1, pop2)); 715 } else { 716 mbedtls_mpi mpi_u; 717 mbedtls_mpi mpi_v; 718 int8_t s1 = mpi_op1.s; 719 int8_t s2 = pop2->s; 720 int cmp; 721 722 mpi_op1.s = 1; 723 pop2->s = 1; 724 725 get_mpi(&mpi_u, u); 726 get_mpi(&mpi_v, v); 727 728 cmp = mbedtls_mpi_cmp_abs(&mpi_op1, pop2); 729 if (cmp == 0) { 730 MPI_CHECK(mbedtls_mpi_copy(&mpi_gcd_res, &mpi_op1)); 731 MPI_CHECK(mbedtls_mpi_lset(&mpi_u, 1)); 732 MPI_CHECK(mbedtls_mpi_lset(&mpi_v, 0)); 733 } else if (cmp > 0) { 734 mpi_egcd(&mpi_gcd_res, &mpi_u, &mpi_v, &mpi_op1, pop2); 735 } else { 736 mpi_egcd(&mpi_gcd_res, &mpi_v, &mpi_u, pop2, &mpi_op1); 737 } 738 739 mpi_u.s *= s1; 740 mpi_v.s *= s2; 741 742 MPI_CHECK(copy_mpi_to_bigint(&mpi_u, u)); 743 MPI_CHECK(copy_mpi_to_bigint(&mpi_v, v)); 744 mbedtls_mpi_free(&mpi_u); 745 mbedtls_mpi_free(&mpi_v); 746 } 747 748 MPI_CHECK(copy_mpi_to_bigint(&mpi_gcd_res, gcd)); 749 mbedtls_mpi_free(&mpi_gcd_res); 750 mbedtls_mpi_free(&mpi_op1); 751 if (pop2 == &mpi_op2) 752 mbedtls_mpi_free(&mpi_op2); 753 } 754 755 static int rng_read(void *ignored __unused, unsigned char *buf, size_t blen) 756 { 757 if (_utee_cryp_random_number_generate(buf, blen)) 758 return MBEDTLS_ERR_MPI_FILE_IO_ERROR; 759 return 0; 760 } 761 762 int32_t TEE_BigIntIsProbablePrime(const TEE_BigInt *op, 763 uint32_t confidenceLevel __unused) 764 { 765 int rc; 766 mbedtls_mpi mpi_op; 767 768 get_mpi(&mpi_op, op); 769 770 rc = mbedtls_mpi_is_prime(&mpi_op, rng_read, NULL); 771 772 mbedtls_mpi_free(&mpi_op); 773 774 if (rc) 775 return 0; 776 777 return 1; 778 } 779 780 /* 781 * Not so fast FMM implementation based on the normal big int functions. 782 * 783 * Note that these functions (along with all the other functions in this 784 * file) only are used directly by the TA doing bigint arithmetics on its 785 * own. Performance of RSA operations in TEE Internal API are not affected 786 * by this. 787 */ 788 void TEE_BigIntInitFMM(TEE_BigIntFMM *bigIntFMM, uint32_t len) 789 { 790 TEE_BigIntInit(bigIntFMM, len); 791 } 792 793 void TEE_BigIntInitFMMContext(TEE_BigIntFMMContext *context __unused, 794 uint32_t len __unused, 795 const TEE_BigInt *modulus __unused) 796 { 797 } 798 799 uint32_t TEE_BigIntFMMSizeInU32(uint32_t modulusSizeInBits) 800 { 801 return TEE_BigIntSizeInU32(modulusSizeInBits); 802 } 803 804 uint32_t TEE_BigIntFMMContextSizeInU32(uint32_t modulusSizeInBits __unused) 805 { 806 /* Return something larger than 0 to keep malloc() and friends happy */ 807 return 1; 808 } 809 810 void TEE_BigIntConvertToFMM(TEE_BigIntFMM *dest, const TEE_BigInt *src, 811 const TEE_BigInt *n, 812 const TEE_BigIntFMMContext *context __unused) 813 { 814 TEE_BigIntMod(dest, src, n); 815 } 816 817 void TEE_BigIntConvertFromFMM(TEE_BigInt *dest, const TEE_BigIntFMM *src, 818 const TEE_BigInt *n __unused, 819 const TEE_BigIntFMMContext *context __unused) 820 { 821 mbedtls_mpi mpi_dst; 822 mbedtls_mpi mpi_src; 823 824 get_mpi(&mpi_dst, dest); 825 get_mpi(&mpi_src, src); 826 827 MPI_CHECK(mbedtls_mpi_copy(&mpi_dst, &mpi_src)); 828 829 MPI_CHECK(copy_mpi_to_bigint(&mpi_dst, dest)); 830 mbedtls_mpi_free(&mpi_dst); 831 mbedtls_mpi_free(&mpi_src); 832 } 833 834 void TEE_BigIntComputeFMM(TEE_BigIntFMM *dest, const TEE_BigIntFMM *op1, 835 const TEE_BigIntFMM *op2, const TEE_BigInt *n, 836 const TEE_BigIntFMMContext *context __unused) 837 { 838 mbedtls_mpi mpi_dst; 839 mbedtls_mpi mpi_op1; 840 mbedtls_mpi mpi_op2; 841 mbedtls_mpi mpi_n; 842 mbedtls_mpi mpi_t; 843 844 get_mpi(&mpi_dst, dest); 845 get_mpi(&mpi_op1, op1); 846 get_mpi(&mpi_op2, op2); 847 get_mpi(&mpi_n, n); 848 get_mpi(&mpi_t, NULL); 849 850 MPI_CHECK(mbedtls_mpi_mul_mpi(&mpi_t, &mpi_op1, &mpi_op2)); 851 MPI_CHECK(mbedtls_mpi_mod_mpi(&mpi_dst, &mpi_t, &mpi_n)); 852 853 mbedtls_mpi_free(&mpi_t); 854 mbedtls_mpi_free(&mpi_n); 855 mbedtls_mpi_free(&mpi_op2); 856 mbedtls_mpi_free(&mpi_op1); 857 MPI_CHECK(copy_mpi_to_bigint(&mpi_dst, dest)); 858 mbedtls_mpi_free(&mpi_dst); 859 } 860