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