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 (14 * 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, size_t len) 119 { 120 struct bigint_hdr *hdr = (struct bigint_hdr *)bigInt; 121 122 static_assert(MBEDTLS_MPI_MAX_LIMBS + BIGINT_HDR_SIZE_IN_U32 >= 123 CFG_TA_BIGNUM_MAX_BITS / 32); 124 125 memset(bigInt, 0, len * sizeof(uint32_t)); 126 hdr->sign = 1; 127 128 /* "gpd.tee.arith.maxBigIntSize" is assigned CFG_TA_BIGNUM_MAX_BITS */ 129 if (len > CFG_TA_BIGNUM_MAX_BITS / 4) 130 API_PANIC("Too large bigint"); 131 hdr->alloc_size = len - BIGINT_HDR_SIZE_IN_U32; 132 } 133 134 void __GP11_TEE_BigIntInit(TEE_BigInt *bigInt, uint32_t len) 135 { 136 TEE_BigIntInit(bigInt, len); 137 } 138 139 TEE_Result TEE_BigIntConvertFromOctetString(TEE_BigInt *dest, 140 const uint8_t *buffer, 141 size_t bufferLen, int32_t sign) 142 { 143 TEE_Result res; 144 mbedtls_mpi mpi_dest; 145 146 get_mpi(&mpi_dest, NULL); 147 148 if (mbedtls_mpi_read_binary(&mpi_dest, buffer, bufferLen)) 149 res = TEE_ERROR_OVERFLOW; 150 else 151 res = TEE_SUCCESS; 152 153 if (sign < 0) 154 mpi_dest.s = -1; 155 156 if (!res) 157 res = copy_mpi_to_bigint(&mpi_dest, dest); 158 159 mbedtls_mpi_free(&mpi_dest); 160 161 return res; 162 } 163 164 TEE_Result __GP11_TEE_BigIntConvertFromOctetString(TEE_BigInt *dest, 165 const uint8_t *buffer, 166 uint32_t bufferLen, 167 int32_t sign) 168 { 169 return TEE_BigIntConvertFromOctetString(dest, buffer, bufferLen, sign); 170 } 171 172 TEE_Result TEE_BigIntConvertToOctetString(uint8_t *buffer, size_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_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 mbedtls_mpi_free(&mpi); 190 191 return res; 192 } 193 194 TEE_Result __GP11_TEE_BigIntConvertToOctetString(uint8_t *buffer, 195 uint32_t *bufferLen, 196 const TEE_BigInt *bigInt) 197 { 198 TEE_Result res = TEE_SUCCESS; 199 size_t l = *bufferLen; 200 201 res = TEE_BigIntConvertToOctetString(buffer, &l, bigInt); 202 *bufferLen = l; 203 return res; 204 } 205 206 void TEE_BigIntConvertFromS32(TEE_BigInt *dest, int32_t shortVal) 207 { 208 mbedtls_mpi mpi; 209 210 get_mpi(&mpi, dest); 211 212 MPI_CHECK(mbedtls_mpi_lset(&mpi, shortVal)); 213 214 MPI_CHECK(copy_mpi_to_bigint(&mpi, dest)); 215 mbedtls_mpi_free(&mpi); 216 } 217 218 TEE_Result TEE_BigIntConvertToS32(int32_t *dest, const TEE_BigInt *src) 219 { 220 TEE_Result res = TEE_SUCCESS; 221 mbedtls_mpi mpi; 222 uint32_t v; 223 224 get_mpi(&mpi, src); 225 226 if (mbedtls_mpi_write_binary(&mpi, (void *)&v, sizeof(v))) { 227 res = TEE_ERROR_OVERFLOW; 228 goto out; 229 } 230 231 if (mpi.s > 0) { 232 if (ADD_OVERFLOW(0, TEE_U32_FROM_BIG_ENDIAN(v), dest)) 233 res = TEE_ERROR_OVERFLOW; 234 } else { 235 if (SUB_OVERFLOW(0, TEE_U32_FROM_BIG_ENDIAN(v), dest)) 236 res = TEE_ERROR_OVERFLOW; 237 } 238 239 out: 240 mbedtls_mpi_free(&mpi); 241 242 return res; 243 } 244 245 int32_t TEE_BigIntCmp(const TEE_BigInt *op1, const TEE_BigInt *op2) 246 { 247 mbedtls_mpi mpi1; 248 mbedtls_mpi mpi2; 249 int32_t rc; 250 251 get_mpi(&mpi1, op1); 252 get_mpi(&mpi2, op2); 253 254 rc = mbedtls_mpi_cmp_mpi(&mpi1, &mpi2); 255 256 mbedtls_mpi_free(&mpi1); 257 mbedtls_mpi_free(&mpi2); 258 259 return rc; 260 } 261 262 int32_t TEE_BigIntCmpS32(const TEE_BigInt *op, int32_t shortVal) 263 { 264 mbedtls_mpi mpi; 265 int32_t rc; 266 267 get_mpi(&mpi, op); 268 269 rc = mbedtls_mpi_cmp_int(&mpi, shortVal); 270 271 mbedtls_mpi_free(&mpi); 272 273 return rc; 274 } 275 276 void TEE_BigIntShiftRight(TEE_BigInt *dest, const TEE_BigInt *op, size_t bits) 277 { 278 mbedtls_mpi mpi_dest; 279 mbedtls_mpi mpi_op; 280 281 get_mpi(&mpi_dest, dest); 282 283 if (dest == op) { 284 MPI_CHECK(mbedtls_mpi_shift_r(&mpi_dest, bits)); 285 goto out; 286 } 287 288 get_mpi(&mpi_op, op); 289 290 if (mbedtls_mpi_size(&mpi_dest) >= mbedtls_mpi_size(&mpi_op)) { 291 MPI_CHECK(mbedtls_mpi_copy(&mpi_dest, &mpi_op)); 292 MPI_CHECK(mbedtls_mpi_shift_r(&mpi_dest, bits)); 293 } else { 294 mbedtls_mpi mpi_t; 295 296 get_mpi(&mpi_t, NULL); 297 298 /* 299 * We're using a temporary buffer to avoid the corner case 300 * where destination is unexpectedly overflowed by up to 301 * @bits number of bits. 302 */ 303 MPI_CHECK(mbedtls_mpi_copy(&mpi_t, &mpi_op)); 304 MPI_CHECK(mbedtls_mpi_shift_r(&mpi_t, bits)); 305 MPI_CHECK(mbedtls_mpi_copy(&mpi_dest, &mpi_t)); 306 307 mbedtls_mpi_free(&mpi_t); 308 } 309 310 mbedtls_mpi_free(&mpi_op); 311 312 out: 313 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 314 mbedtls_mpi_free(&mpi_dest); 315 } 316 317 void __GP11_TEE_BigIntShiftRight(TEE_BigInt *dest, const TEE_BigInt *op, 318 uint32_t bits) 319 { 320 TEE_BigIntShiftRight(dest, op, bits); 321 } 322 323 bool TEE_BigIntGetBit(const TEE_BigInt *src, uint32_t bitIndex) 324 { 325 bool rc; 326 mbedtls_mpi mpi; 327 328 get_mpi(&mpi, src); 329 330 rc = mbedtls_mpi_get_bit(&mpi, bitIndex); 331 332 mbedtls_mpi_free(&mpi); 333 334 return rc; 335 } 336 337 uint32_t TEE_BigIntGetBitCount(const TEE_BigInt *src) 338 { 339 uint32_t rc; 340 mbedtls_mpi mpi; 341 342 get_mpi(&mpi, src); 343 344 rc = mbedtls_mpi_bitlen(&mpi); 345 346 mbedtls_mpi_free(&mpi); 347 348 return rc; 349 } 350 351 TEE_Result TEE_BigIntSetBit(TEE_BigInt *op, uint32_t bitIndex, bool value) 352 { 353 TEE_Result res = TEE_SUCCESS; 354 mbedtls_mpi mpi = { }; 355 int rc = 0; 356 357 get_mpi(&mpi, op); 358 359 rc = mbedtls_mpi_set_bit(&mpi, bitIndex, value); 360 if (rc) 361 res = TEE_ERROR_OVERFLOW; 362 else 363 res = copy_mpi_to_bigint(&mpi, op); 364 365 mbedtls_mpi_free(&mpi); 366 367 return res; 368 } 369 370 TEE_Result TEE_BigIntAssign(TEE_BigInt *dest, const TEE_BigInt *src) 371 { 372 const struct bigint_hdr *src_hdr = (struct bigint_hdr *)src; 373 struct bigint_hdr *dst_hdr = (struct bigint_hdr *)dest; 374 375 if (dst_hdr == src_hdr) 376 return TEE_SUCCESS; 377 378 if (dst_hdr->alloc_size < src_hdr->nblimbs) 379 return TEE_ERROR_OVERFLOW; 380 381 dst_hdr->nblimbs = src_hdr->nblimbs; 382 dst_hdr->sign = src_hdr->sign; 383 memcpy(dst_hdr + 1, src_hdr + 1, src_hdr->nblimbs * sizeof(uint32_t)); 384 385 return TEE_SUCCESS; 386 } 387 388 TEE_Result TEE_BigIntAbs(TEE_BigInt *dest, const TEE_BigInt *src) 389 { 390 TEE_Result res = TEE_BigIntAssign(dest, src); 391 392 if (!res) 393 ((struct bigint_hdr *)dest)->sign = 1; 394 395 return res; 396 } 397 398 static void bigint_binary(TEE_BigInt *dest, const TEE_BigInt *op1, 399 const TEE_BigInt *op2, 400 int (*func)(mbedtls_mpi *X, const mbedtls_mpi *A, 401 const mbedtls_mpi *B)) 402 { 403 mbedtls_mpi mpi_dest; 404 mbedtls_mpi mpi_op1; 405 mbedtls_mpi mpi_op2; 406 mbedtls_mpi *pop1 = &mpi_op1; 407 mbedtls_mpi *pop2 = &mpi_op2; 408 409 get_mpi(&mpi_dest, dest); 410 411 if (op1 == dest) 412 pop1 = &mpi_dest; 413 else 414 get_mpi(&mpi_op1, op1); 415 416 if (op2 == dest) 417 pop2 = &mpi_dest; 418 else if (op2 == op1) 419 pop2 = pop1; 420 else 421 get_mpi(&mpi_op2, op2); 422 423 MPI_CHECK(func(&mpi_dest, pop1, pop2)); 424 425 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 426 mbedtls_mpi_free(&mpi_dest); 427 if (pop1 == &mpi_op1) 428 mbedtls_mpi_free(&mpi_op1); 429 if (pop2 == &mpi_op2) 430 mbedtls_mpi_free(&mpi_op2); 431 } 432 433 static void bigint_binary_mod(TEE_BigInt *dest, const TEE_BigInt *op1, 434 const TEE_BigInt *op2, const TEE_BigInt *n, 435 int (*func)(mbedtls_mpi *X, const mbedtls_mpi *A, 436 const mbedtls_mpi *B)) 437 { 438 mbedtls_mpi mpi_dest; 439 mbedtls_mpi mpi_op1; 440 mbedtls_mpi mpi_op2; 441 mbedtls_mpi mpi_n; 442 mbedtls_mpi *pop1 = &mpi_op1; 443 mbedtls_mpi *pop2 = &mpi_op2; 444 mbedtls_mpi mpi_t; 445 446 if (TEE_BigIntCmpS32(n, 2) < 0) 447 API_PANIC("Modulus is too short"); 448 449 get_mpi(&mpi_dest, dest); 450 get_mpi(&mpi_n, n); 451 452 if (op1 == dest) 453 pop1 = &mpi_dest; 454 else 455 get_mpi(&mpi_op1, op1); 456 457 if (op2 == dest) 458 pop2 = &mpi_dest; 459 else if (op2 == op1) 460 pop2 = pop1; 461 else 462 get_mpi(&mpi_op2, op2); 463 464 get_mpi(&mpi_t, NULL); 465 466 MPI_CHECK(func(&mpi_t, pop1, pop2)); 467 MPI_CHECK(mbedtls_mpi_mod_mpi(&mpi_dest, &mpi_t, &mpi_n)); 468 469 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 470 mbedtls_mpi_free(&mpi_dest); 471 if (pop1 == &mpi_op1) 472 mbedtls_mpi_free(&mpi_op1); 473 if (pop2 == &mpi_op2) 474 mbedtls_mpi_free(&mpi_op2); 475 mbedtls_mpi_free(&mpi_t); 476 mbedtls_mpi_free(&mpi_n); 477 } 478 479 void TEE_BigIntAdd(TEE_BigInt *dest, const TEE_BigInt *op1, 480 const TEE_BigInt *op2) 481 { 482 bigint_binary(dest, op1, op2, mbedtls_mpi_add_mpi); 483 } 484 485 void TEE_BigIntSub(TEE_BigInt *dest, const TEE_BigInt *op1, 486 const TEE_BigInt *op2) 487 { 488 bigint_binary(dest, op1, op2, mbedtls_mpi_sub_mpi); 489 } 490 491 void TEE_BigIntNeg(TEE_BigInt *dest, const TEE_BigInt *src) 492 { 493 mbedtls_mpi mpi_dest; 494 495 get_mpi(&mpi_dest, dest); 496 497 if (dest != src) { 498 mbedtls_mpi mpi_src; 499 500 get_mpi(&mpi_src, src); 501 502 MPI_CHECK(mbedtls_mpi_copy(&mpi_dest, &mpi_src)); 503 504 mbedtls_mpi_free(&mpi_src); 505 } 506 507 mpi_dest.s *= -1; 508 509 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 510 mbedtls_mpi_free(&mpi_dest); 511 } 512 513 void TEE_BigIntMul(TEE_BigInt *dest, const TEE_BigInt *op1, 514 const TEE_BigInt *op2) 515 { 516 size_t bs1 = TEE_BigIntGetBitCount(op1); 517 size_t bs2 = TEE_BigIntGetBitCount(op2); 518 size_t s = TEE_BigIntSizeInU32(bs1) + TEE_BigIntSizeInU32(bs2); 519 TEE_BigInt zero[TEE_BigIntSizeInU32(1)] = { 0 }; 520 TEE_BigInt *tmp = NULL; 521 522 tmp = mempool_alloc(mbedtls_mpi_mempool, sizeof(uint32_t) * s); 523 if (!tmp) 524 TEE_Panic(TEE_ERROR_OUT_OF_MEMORY); 525 526 TEE_BigIntInit(tmp, s); 527 TEE_BigIntInit(zero, TEE_BigIntSizeInU32(1)); 528 529 bigint_binary(tmp, op1, op2, mbedtls_mpi_mul_mpi); 530 531 TEE_BigIntAdd(dest, tmp, zero); 532 533 mempool_free(mbedtls_mpi_mempool, tmp); 534 } 535 536 void TEE_BigIntSquare(TEE_BigInt *dest, const TEE_BigInt *op) 537 { 538 TEE_BigIntMul(dest, op, op); 539 } 540 541 void TEE_BigIntDiv(TEE_BigInt *dest_q, TEE_BigInt *dest_r, 542 const TEE_BigInt *op1, const TEE_BigInt *op2) 543 { 544 mbedtls_mpi mpi_dest_q; 545 mbedtls_mpi mpi_dest_r; 546 mbedtls_mpi mpi_op1; 547 mbedtls_mpi mpi_op2; 548 mbedtls_mpi *pop1 = &mpi_op1; 549 mbedtls_mpi *pop2 = &mpi_op2; 550 551 get_mpi(&mpi_dest_q, dest_q); 552 get_mpi(&mpi_dest_r, dest_r); 553 554 if (op1 == dest_q) 555 pop1 = &mpi_dest_q; 556 else if (op1 == dest_r) 557 pop1 = &mpi_dest_r; 558 else 559 get_mpi(&mpi_op1, op1); 560 561 if (op2 == dest_q) 562 pop2 = &mpi_dest_q; 563 else if (op2 == dest_r) 564 pop2 = &mpi_dest_r; 565 else if (op2 == op1) 566 pop2 = pop1; 567 else 568 get_mpi(&mpi_op2, op2); 569 570 MPI_CHECK(mbedtls_mpi_div_mpi(&mpi_dest_q, &mpi_dest_r, pop1, pop2)); 571 572 if (dest_q) 573 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest_q, dest_q)); 574 if (dest_r) 575 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest_r, dest_r)); 576 mbedtls_mpi_free(&mpi_dest_q); 577 mbedtls_mpi_free(&mpi_dest_r); 578 if (pop1 == &mpi_op1) 579 mbedtls_mpi_free(&mpi_op1); 580 if (pop2 == &mpi_op2) 581 mbedtls_mpi_free(&mpi_op2); 582 } 583 584 void TEE_BigIntMod(TEE_BigInt *dest, const TEE_BigInt *op, const TEE_BigInt *n) 585 { 586 if (TEE_BigIntCmpS32(n, 2) < 0) 587 API_PANIC("Modulus is too short"); 588 589 bigint_binary(dest, op, n, mbedtls_mpi_mod_mpi); 590 } 591 592 void TEE_BigIntAddMod(TEE_BigInt *dest, const TEE_BigInt *op1, 593 const TEE_BigInt *op2, const TEE_BigInt *n) 594 { 595 bigint_binary_mod(dest, op1, op2, n, mbedtls_mpi_add_mpi); 596 } 597 598 void TEE_BigIntSubMod(TEE_BigInt *dest, const TEE_BigInt *op1, 599 const TEE_BigInt *op2, const TEE_BigInt *n) 600 { 601 bigint_binary_mod(dest, op1, op2, n, mbedtls_mpi_sub_mpi); 602 } 603 604 void TEE_BigIntMulMod(TEE_BigInt *dest, const TEE_BigInt *op1, 605 const TEE_BigInt *op2, const TEE_BigInt *n) 606 { 607 bigint_binary_mod(dest, op1, op2, n, mbedtls_mpi_mul_mpi); 608 } 609 610 void TEE_BigIntSquareMod(TEE_BigInt *dest, const TEE_BigInt *op, 611 const TEE_BigInt *n) 612 { 613 TEE_BigIntMulMod(dest, op, op, n); 614 } 615 616 void TEE_BigIntInvMod(TEE_BigInt *dest, const TEE_BigInt *op, 617 const TEE_BigInt *n) 618 { 619 mbedtls_mpi mpi_dest; 620 mbedtls_mpi mpi_op; 621 mbedtls_mpi mpi_n; 622 mbedtls_mpi *pop = &mpi_op; 623 624 if (TEE_BigIntCmpS32(n, 2) < 0 || TEE_BigIntCmpS32(op, 0) == 0) 625 API_PANIC("too small modulus or trying to invert zero"); 626 627 get_mpi(&mpi_dest, dest); 628 get_mpi(&mpi_n, n); 629 630 if (op == dest) 631 pop = &mpi_dest; 632 else 633 get_mpi(&mpi_op, op); 634 635 MPI_CHECK(mbedtls_mpi_inv_mod(&mpi_dest, pop, &mpi_n)); 636 637 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 638 mbedtls_mpi_free(&mpi_dest); 639 mbedtls_mpi_free(&mpi_n); 640 if (pop == &mpi_op) 641 mbedtls_mpi_free(&mpi_op); 642 } 643 644 bool TEE_BigIntRelativePrime(const TEE_BigInt *op1, const TEE_BigInt *op2) 645 { 646 bool rc; 647 mbedtls_mpi mpi_op1; 648 mbedtls_mpi mpi_op2; 649 mbedtls_mpi *pop2 = &mpi_op2; 650 mbedtls_mpi gcd; 651 652 get_mpi(&mpi_op1, op1); 653 654 if (op2 == op1) 655 pop2 = &mpi_op1; 656 else 657 get_mpi(&mpi_op2, op2); 658 659 get_mpi(&gcd, NULL); 660 661 MPI_CHECK(mbedtls_mpi_gcd(&gcd, &mpi_op1, &mpi_op2)); 662 663 rc = !mbedtls_mpi_cmp_int(&gcd, 1); 664 665 mbedtls_mpi_free(&gcd); 666 mbedtls_mpi_free(&mpi_op1); 667 if (pop2 == &mpi_op2) 668 mbedtls_mpi_free(&mpi_op2); 669 670 return rc; 671 } 672 673 static bool mpi_is_odd(mbedtls_mpi *x) 674 { 675 return mbedtls_mpi_get_bit(x, 0); 676 } 677 678 static bool mpi_is_even(mbedtls_mpi *x) 679 { 680 return !mpi_is_odd(x); 681 } 682 683 TEE_Result TEE_BigIntExpMod(TEE_BigInt *dest, const TEE_BigInt *op1, 684 const TEE_BigInt *op2, const TEE_BigInt *n, 685 const TEE_BigIntFMMContext *context __unused) 686 { 687 TEE_Result res = TEE_SUCCESS; 688 mbedtls_mpi mpi_dest = { }; 689 mbedtls_mpi mpi_op1 = { }; 690 mbedtls_mpi mpi_op2 = { }; 691 mbedtls_mpi mpi_n = { }; 692 mbedtls_mpi *pop1 = &mpi_op1; 693 mbedtls_mpi *pop2 = &mpi_op2; 694 695 get_mpi(&mpi_dest, dest); 696 get_mpi(&mpi_n, n); 697 if (op1 == dest) 698 pop1 = &mpi_dest; 699 else 700 get_mpi(&mpi_op1, op1); 701 702 if (op2 == dest) 703 pop2 = &mpi_dest; 704 else if (op2 == op1) 705 pop2 = pop1; 706 else 707 get_mpi(&mpi_op2, op2); 708 709 if (mbedtls_mpi_cmp_int(&mpi_n, 2) <= 0) 710 API_PANIC("too small modulus"); 711 if (!mpi_is_odd(&mpi_n)) { 712 res = TEE_ERROR_NOT_SUPPORTED; 713 goto out; 714 } 715 716 MPI_CHECK(mbedtls_mpi_exp_mod(&mpi_dest, pop1, pop2, &mpi_n, NULL)); 717 MPI_CHECK(copy_mpi_to_bigint(&mpi_dest, dest)); 718 out: 719 mbedtls_mpi_free(&mpi_dest); 720 mbedtls_mpi_free(&mpi_n); 721 if (pop1 == &mpi_op1) 722 mbedtls_mpi_free(&mpi_op1); 723 if (pop2 == &mpi_op2) 724 mbedtls_mpi_free(&mpi_op2); 725 726 return res; 727 } 728 729 /* 730 * Based on libmpa implementation __mpa_egcd(), modified to work with MPI 731 * instead. 732 */ 733 static void mpi_egcd(mbedtls_mpi *gcd, mbedtls_mpi *a, mbedtls_mpi *b, 734 mbedtls_mpi *x_in, mbedtls_mpi *y_in) 735 { 736 mbedtls_mpi_uint k; 737 mbedtls_mpi A; 738 mbedtls_mpi B; 739 mbedtls_mpi C; 740 mbedtls_mpi D; 741 mbedtls_mpi x; 742 mbedtls_mpi y; 743 mbedtls_mpi u; 744 745 get_mpi(&A, NULL); 746 get_mpi(&B, NULL); 747 get_mpi(&C, NULL); 748 get_mpi(&D, NULL); 749 get_mpi(&x, NULL); 750 get_mpi(&y, NULL); 751 get_mpi(&u, NULL); 752 753 /* have y < x from assumption */ 754 if (!mbedtls_mpi_cmp_int(y_in, 0)) { 755 MPI_CHECK(mbedtls_mpi_lset(a, 1)); 756 MPI_CHECK(mbedtls_mpi_lset(b, 0)); 757 MPI_CHECK(mbedtls_mpi_copy(gcd, x_in)); 758 goto out; 759 } 760 761 MPI_CHECK(mbedtls_mpi_copy(&x, x_in)); 762 MPI_CHECK(mbedtls_mpi_copy(&y, y_in)); 763 764 k = 0; 765 while (mpi_is_even(&x) && mpi_is_even(&y)) { 766 k++; 767 MPI_CHECK(mbedtls_mpi_shift_r(&x, 1)); 768 MPI_CHECK(mbedtls_mpi_shift_r(&y, 1)); 769 } 770 771 MPI_CHECK(mbedtls_mpi_copy(&u, &x)); 772 MPI_CHECK(mbedtls_mpi_copy(gcd, &y)); 773 MPI_CHECK(mbedtls_mpi_lset(&A, 1)); 774 MPI_CHECK(mbedtls_mpi_lset(&B, 0)); 775 MPI_CHECK(mbedtls_mpi_lset(&C, 0)); 776 MPI_CHECK(mbedtls_mpi_lset(&D, 1)); 777 778 while (mbedtls_mpi_cmp_int(&u, 0)) { 779 while (mpi_is_even(&u)) { 780 MPI_CHECK(mbedtls_mpi_shift_r(&u, 1)); 781 if (mpi_is_odd(&A) || mpi_is_odd(&B)) { 782 MPI_CHECK(mbedtls_mpi_add_mpi(&A, &A, &y)); 783 MPI_CHECK(mbedtls_mpi_sub_mpi(&B, &B, &x)); 784 } 785 MPI_CHECK(mbedtls_mpi_shift_r(&A, 1)); 786 MPI_CHECK(mbedtls_mpi_shift_r(&B, 1)); 787 } 788 789 while (mpi_is_even(gcd)) { 790 MPI_CHECK(mbedtls_mpi_shift_r(gcd, 1)); 791 if (mpi_is_odd(&C) || mpi_is_odd(&D)) { 792 MPI_CHECK(mbedtls_mpi_add_mpi(&C, &C, &y)); 793 MPI_CHECK(mbedtls_mpi_sub_mpi(&D, &D, &x)); 794 } 795 MPI_CHECK(mbedtls_mpi_shift_r(&C, 1)); 796 MPI_CHECK(mbedtls_mpi_shift_r(&D, 1)); 797 798 } 799 800 if (mbedtls_mpi_cmp_mpi(&u, gcd) >= 0) { 801 MPI_CHECK(mbedtls_mpi_sub_mpi(&u, &u, gcd)); 802 MPI_CHECK(mbedtls_mpi_sub_mpi(&A, &A, &C)); 803 MPI_CHECK(mbedtls_mpi_sub_mpi(&B, &B, &D)); 804 } else { 805 MPI_CHECK(mbedtls_mpi_sub_mpi(gcd, gcd, &u)); 806 MPI_CHECK(mbedtls_mpi_sub_mpi(&C, &C, &A)); 807 MPI_CHECK(mbedtls_mpi_sub_mpi(&D, &D, &B)); 808 } 809 } 810 811 MPI_CHECK(mbedtls_mpi_copy(a, &C)); 812 MPI_CHECK(mbedtls_mpi_copy(b, &D)); 813 MPI_CHECK(mbedtls_mpi_shift_l(gcd, k)); 814 815 out: 816 mbedtls_mpi_free(&A); 817 mbedtls_mpi_free(&B); 818 mbedtls_mpi_free(&C); 819 mbedtls_mpi_free(&D); 820 mbedtls_mpi_free(&x); 821 mbedtls_mpi_free(&y); 822 mbedtls_mpi_free(&u); 823 } 824 825 void TEE_BigIntComputeExtendedGcd(TEE_BigInt *gcd, TEE_BigInt *u, 826 TEE_BigInt *v, const TEE_BigInt *op1, 827 const TEE_BigInt *op2) 828 { 829 mbedtls_mpi mpi_gcd_res; 830 mbedtls_mpi mpi_op1; 831 mbedtls_mpi mpi_op2; 832 mbedtls_mpi *pop2 = &mpi_op2; 833 834 get_mpi(&mpi_gcd_res, gcd); 835 get_mpi(&mpi_op1, op1); 836 837 if (op2 == op1) 838 pop2 = &mpi_op1; 839 else 840 get_mpi(&mpi_op2, op2); 841 842 if (!u && !v) { 843 MPI_CHECK(mbedtls_mpi_gcd(&mpi_gcd_res, &mpi_op1, pop2)); 844 } else { 845 mbedtls_mpi mpi_u; 846 mbedtls_mpi mpi_v; 847 int8_t s1 = mpi_op1.s; 848 int8_t s2 = pop2->s; 849 int cmp; 850 851 mpi_op1.s = 1; 852 pop2->s = 1; 853 854 get_mpi(&mpi_u, u); 855 get_mpi(&mpi_v, v); 856 857 cmp = mbedtls_mpi_cmp_abs(&mpi_op1, pop2); 858 if (cmp == 0) { 859 MPI_CHECK(mbedtls_mpi_copy(&mpi_gcd_res, &mpi_op1)); 860 MPI_CHECK(mbedtls_mpi_lset(&mpi_u, 1)); 861 MPI_CHECK(mbedtls_mpi_lset(&mpi_v, 0)); 862 } else if (cmp > 0) { 863 mpi_egcd(&mpi_gcd_res, &mpi_u, &mpi_v, &mpi_op1, pop2); 864 } else { 865 mpi_egcd(&mpi_gcd_res, &mpi_v, &mpi_u, pop2, &mpi_op1); 866 } 867 868 mpi_u.s *= s1; 869 mpi_v.s *= s2; 870 871 MPI_CHECK(copy_mpi_to_bigint(&mpi_u, u)); 872 MPI_CHECK(copy_mpi_to_bigint(&mpi_v, v)); 873 mbedtls_mpi_free(&mpi_u); 874 mbedtls_mpi_free(&mpi_v); 875 } 876 877 MPI_CHECK(copy_mpi_to_bigint(&mpi_gcd_res, gcd)); 878 mbedtls_mpi_free(&mpi_gcd_res); 879 mbedtls_mpi_free(&mpi_op1); 880 if (pop2 == &mpi_op2) 881 mbedtls_mpi_free(&mpi_op2); 882 } 883 884 static int rng_read(void *ignored __unused, unsigned char *buf, size_t blen) 885 { 886 if (_utee_cryp_random_number_generate(buf, blen)) 887 return MBEDTLS_ERR_MPI_FILE_IO_ERROR; 888 return 0; 889 } 890 891 int32_t TEE_BigIntIsProbablePrime(const TEE_BigInt *op, 892 uint32_t confidenceLevel) 893 { 894 int rc; 895 mbedtls_mpi mpi_op; 896 897 get_mpi(&mpi_op, op); 898 899 rc = mbedtls_mpi_is_prime_ext(&mpi_op, MAX(confidenceLevel, 80U), 900 rng_read, NULL); 901 902 mbedtls_mpi_free(&mpi_op); 903 904 if (rc) 905 return 0; 906 907 return 1; 908 } 909 910 /* 911 * Not so fast FMM implementation based on the normal big int functions. 912 * 913 * Note that these functions (along with all the other functions in this 914 * file) only are used directly by the TA doing bigint arithmetics on its 915 * own. Performance of RSA operations in TEE Internal API are not affected 916 * by this. 917 */ 918 void TEE_BigIntInitFMM(TEE_BigIntFMM *bigIntFMM, size_t len) 919 { 920 TEE_BigIntInit(bigIntFMM, len); 921 } 922 923 void __GP11_TEE_BigIntInitFMM(TEE_BigIntFMM *bigIntFMM, uint32_t len) 924 { 925 TEE_BigIntInitFMM(bigIntFMM, len); 926 } 927 928 void TEE_BigIntInitFMMContext(TEE_BigIntFMMContext *context __unused, 929 size_t len __unused, 930 const TEE_BigInt *modulus __unused) 931 { 932 } 933 934 void __GP11_TEE_BigIntInitFMMContext(TEE_BigIntFMMContext *context, 935 uint32_t len, const TEE_BigInt *modulus) 936 { 937 TEE_BigIntInitFMMContext(context, len, modulus); 938 } 939 940 TEE_Result TEE_BigIntInitFMMContext1(TEE_BigIntFMMContext *context __unused, 941 size_t len __unused, 942 const TEE_BigInt *modulus __unused) 943 { 944 return TEE_SUCCESS; 945 } 946 947 size_t TEE_BigIntFMMSizeInU32(size_t modulusSizeInBits) 948 { 949 return TEE_BigIntSizeInU32(modulusSizeInBits); 950 } 951 952 uint32_t __GP11_TEE_BigIntFMMSizeInU32(uint32_t modulusSizeInBits) 953 { 954 return TEE_BigIntFMMSizeInU32(modulusSizeInBits); 955 } 956 957 size_t TEE_BigIntFMMContextSizeInU32(size_t modulusSizeInBits __unused) 958 { 959 /* Return something larger than 0 to keep malloc() and friends happy */ 960 return 1; 961 } 962 963 uint32_t __GP11_TEE_BigIntFMMContextSizeInU32(uint32_t modulusSizeInBits) 964 { 965 return TEE_BigIntFMMContextSizeInU32(modulusSizeInBits); 966 } 967 968 void TEE_BigIntConvertToFMM(TEE_BigIntFMM *dest, const TEE_BigInt *src, 969 const TEE_BigInt *n, 970 const TEE_BigIntFMMContext *context __unused) 971 { 972 TEE_BigIntMod(dest, src, n); 973 } 974 975 void TEE_BigIntConvertFromFMM(TEE_BigInt *dest, const TEE_BigIntFMM *src, 976 const TEE_BigInt *n __unused, 977 const TEE_BigIntFMMContext *context __unused) 978 { 979 mbedtls_mpi mpi_dst; 980 mbedtls_mpi mpi_src; 981 982 get_mpi(&mpi_dst, dest); 983 get_mpi(&mpi_src, src); 984 985 MPI_CHECK(mbedtls_mpi_copy(&mpi_dst, &mpi_src)); 986 987 MPI_CHECK(copy_mpi_to_bigint(&mpi_dst, dest)); 988 mbedtls_mpi_free(&mpi_dst); 989 mbedtls_mpi_free(&mpi_src); 990 } 991 992 void TEE_BigIntComputeFMM(TEE_BigIntFMM *dest, const TEE_BigIntFMM *op1, 993 const TEE_BigIntFMM *op2, const TEE_BigInt *n, 994 const TEE_BigIntFMMContext *context __unused) 995 { 996 mbedtls_mpi mpi_dst; 997 mbedtls_mpi mpi_op1; 998 mbedtls_mpi mpi_op2; 999 mbedtls_mpi mpi_n; 1000 mbedtls_mpi mpi_t; 1001 1002 get_mpi(&mpi_dst, dest); 1003 get_mpi(&mpi_op1, op1); 1004 get_mpi(&mpi_op2, op2); 1005 get_mpi(&mpi_n, n); 1006 get_mpi(&mpi_t, NULL); 1007 1008 MPI_CHECK(mbedtls_mpi_mul_mpi(&mpi_t, &mpi_op1, &mpi_op2)); 1009 MPI_CHECK(mbedtls_mpi_mod_mpi(&mpi_dst, &mpi_t, &mpi_n)); 1010 1011 mbedtls_mpi_free(&mpi_t); 1012 mbedtls_mpi_free(&mpi_n); 1013 mbedtls_mpi_free(&mpi_op2); 1014 mbedtls_mpi_free(&mpi_op1); 1015 MPI_CHECK(copy_mpi_to_bigint(&mpi_dst, dest)); 1016 mbedtls_mpi_free(&mpi_dst); 1017 } 1018