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