1 /*############################################################################ 2 # Copyright 2016-2017 Intel Corporation 3 # 4 # Licensed under the Apache License, Version 2.0 (the "License"); 5 # you may not use this file except in compliance with the License. 6 # You may obtain a copy of the License at 7 # 8 # http://www.apache.org/licenses/LICENSE-2.0 9 # 10 # Unless required by applicable law or agreed to in writing, software 11 # distributed under the License is distributed on an "AS IS" BASIS, 12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 # See the License for the specific language governing permissions and 14 # limitations under the License. 15 ############################################################################*/ 16 17 /*! 18 * \file 19 * \brief Finite field implementation. 20 */ 21 22 #include "epid/common/math/finitefield.h" 23 #include <limits.h> 24 #include <stdint.h> 25 #include <string.h> 26 #include "epid/common/math/src/finitefield-internal.h" 27 #include "epid/common/src/memory.h" 28 29 #ifndef MIN 30 /// Evaluate to minimum of two values 31 #define MIN(a, b) ((a) < (b) ? (a) : (b)) 32 #endif // MIN 33 34 /// Number of leading zero bits in 32 bit integer x. 35 static size_t Nlz32(uint32_t x) { 36 size_t nlz = sizeof(x) * 8; 37 if (x) { 38 nlz = 0; 39 if (0 == (x & 0xFFFF0000)) { 40 nlz += 16; 41 x <<= 16; 42 } 43 if (0 == (x & 0xFF000000)) { 44 nlz += 8; 45 x <<= 8; 46 } 47 if (0 == (x & 0xF0000000)) { 48 nlz += 4; 49 x <<= 4; 50 } 51 if (0 == (x & 0xC0000000)) { 52 nlz += 2; 53 x <<= 2; 54 } 55 if (0 == (x & 0x80000000)) { 56 nlz++; 57 } 58 } 59 return nlz; 60 } 61 62 /// Bit size of bit number representated as array of Ipp32u. 63 #define BNU_BITSIZE(bnu, len) \ 64 ((len) * sizeof(Ipp32u) * 8 - Nlz32((bnu)[(len)-1])) 65 66 /// Convert bit size to byte size 67 #define BIT2BYTE_SIZE(bits) (((bits) + 7) >> 3) 68 69 EpidStatus NewFiniteField(BigNumStr const* prime, FiniteField** ff) { 70 EpidStatus result = kEpidErr; 71 IppsGFpState* ipp_finitefield_ctx = NULL; 72 FiniteField* finitefield_ptr = NULL; 73 BigNum* prime_bn = NULL; 74 do { 75 EpidStatus status = kEpidErr; 76 IppStatus sts = ippStsNoErr; 77 Ipp32u bnu[sizeof(BigNumStr) / sizeof(Ipp32u)]; 78 int bnu_size; 79 int bit_size = CHAR_BIT * sizeof(BigNumStr); 80 int state_size_in_bytes = 0; 81 82 if (!prime || !ff) { 83 result = kEpidBadArgErr; 84 break; 85 } 86 87 bit_size = (int)OctStrBitSize(prime->data.data, sizeof(prime->data.data)); 88 89 bnu_size = OctStr2Bnu(bnu, prime, sizeof(*prime)); 90 if (bnu_size < 0) { 91 result = kEpidMathErr; 92 break; 93 } 94 95 // skip high order zeros from BNU 96 while (bnu_size > 1 && 0 == bnu[bnu_size - 1]) { 97 bnu_size--; 98 } 99 100 // Determine the memory requirement for finite field context 101 sts = ippsGFpGetSize(bit_size, &state_size_in_bytes); 102 if (ippStsNoErr != sts) { 103 if (ippStsSizeErr == sts) { 104 result = kEpidBadArgErr; 105 } else { 106 result = kEpidMathErr; 107 } 108 break; 109 } 110 // Allocate space for ipp bignum context 111 ipp_finitefield_ctx = (IppsGFpState*)SAFE_ALLOC(state_size_in_bytes); 112 if (!ipp_finitefield_ctx) { 113 result = kEpidMemAllocErr; 114 break; 115 } 116 117 status = NewBigNum(sizeof(BigNumStr), &prime_bn); 118 if (kEpidNoErr != status) { 119 result = kEpidMathErr; 120 break; 121 } 122 123 status = ReadBigNum(prime, sizeof(BigNumStr), prime_bn); 124 if (kEpidNoErr != status) { 125 result = kEpidMathErr; 126 break; 127 } 128 // Initialize ipp finite field context 129 sts = ippsGFpInit(prime_bn->ipp_bn, bit_size, ippsGFpMethod_pArb(), 130 ipp_finitefield_ctx); 131 if (ippStsNoErr != sts) { 132 if (ippStsSizeErr == sts) { 133 result = kEpidBadArgErr; 134 } else { 135 result = kEpidMathErr; 136 } 137 break; 138 } 139 finitefield_ptr = (FiniteField*)SAFE_ALLOC(sizeof(FiniteField)); 140 if (!finitefield_ptr) { 141 result = kEpidMemAllocErr; 142 break; 143 } 144 finitefield_ptr->element_strlen_required = 145 BIT2BYTE_SIZE(BNU_BITSIZE(bnu, bnu_size)); 146 finitefield_ptr->modulus_0 = prime_bn; 147 finitefield_ptr->basic_degree = 1; 148 finitefield_ptr->ground_degree = 1; 149 finitefield_ptr->element_len = bnu_size; 150 finitefield_ptr->ground_ff = NULL; 151 finitefield_ptr->ipp_ff = ipp_finitefield_ctx; 152 *ff = finitefield_ptr; 153 result = kEpidNoErr; 154 } while (0); 155 156 if (kEpidNoErr != result) { 157 SAFE_FREE(finitefield_ptr); 158 SAFE_FREE(prime_bn); 159 SAFE_FREE(ipp_finitefield_ctx); 160 } 161 return result; 162 } 163 164 EpidStatus NewFiniteFieldViaBinomalExtension(FiniteField const* ground_field, 165 FfElement const* ground_element, 166 int degree, FiniteField** ff) { 167 EpidStatus result = kEpidErr; 168 IppsGFpState* ipp_finitefield_ctx = NULL; 169 IppOctStr ff_elem_str = NULL; 170 FiniteField* finitefield_ptr = NULL; 171 BigNum* modulus_0 = NULL; 172 do { 173 EpidStatus status = kEpidErr; 174 IppStatus sts = ippStsNoErr; 175 int state_size_in_bytes = 0; 176 if (!ground_field || !ground_element || !ff) { 177 result = kEpidBadArgErr; 178 break; 179 } else if (degree < 2 || !ground_field->ipp_ff || 180 !ground_element->ipp_ff_elem) { 181 result = kEpidBadArgErr; 182 break; 183 } 184 185 // Determine the memory requirement for finite field context 186 sts = ippsGFpxGetSize(ground_field->ipp_ff, degree, &state_size_in_bytes); 187 if (ippStsNoErr != sts) { 188 if (ippStsSizeErr == sts) { 189 result = kEpidBadArgErr; 190 } else { 191 result = kEpidMathErr; 192 } 193 break; 194 } 195 196 // Allocate space for ipp finite field context 197 ipp_finitefield_ctx = (IppsGFpState*)SAFE_ALLOC(state_size_in_bytes); 198 if (!ipp_finitefield_ctx) { 199 result = kEpidMemAllocErr; 200 break; 201 } 202 203 // Initialize ipp binomial extension finite field context 204 sts = ippsGFpxInitBinomial( 205 ground_field->ipp_ff, degree, ground_element->ipp_ff_elem, 206 2 == degree 207 ? (3 == ground_field->basic_degree ? ippsGFpxMethod_binom2() 208 : ippsGFpxMethod_binom2_epid2()) 209 : ippsGFpxMethod_binom3_epid2(), 210 ipp_finitefield_ctx); 211 if (ippStsNoErr != sts) { 212 if (ippStsSizeErr == sts) { 213 result = kEpidBadArgErr; 214 } else { 215 result = kEpidMathErr; 216 } 217 break; 218 } 219 finitefield_ptr = (FiniteField*)SAFE_ALLOC(sizeof(FiniteField)); 220 if (!finitefield_ptr) { 221 result = kEpidMemAllocErr; 222 break; 223 } 224 finitefield_ptr->element_strlen_required = 225 ground_field->element_strlen_required * degree; 226 ff_elem_str = 227 (IppOctStr)SAFE_ALLOC(ground_field->element_len * sizeof(Ipp32u)); 228 if (!ff_elem_str) { 229 result = kEpidMemAllocErr; 230 break; 231 } 232 status = NewBigNum(ground_field->element_len * sizeof(Ipp32u), &modulus_0); 233 if (kEpidNoErr != status) { 234 break; 235 } 236 if (kEpidNoErr != status) { 237 result = kEpidMathErr; 238 break; 239 } 240 result = 241 WriteFfElement((FiniteField*)ground_field, ground_element, ff_elem_str, 242 ground_field->element_len * sizeof(Ipp32u)); 243 if (kEpidNoErr != result) break; 244 status = ReadBigNum(ff_elem_str, ground_field->element_len * sizeof(Ipp32u), 245 modulus_0); 246 if (kEpidNoErr != status) { 247 result = kEpidMathErr; 248 break; 249 } 250 251 finitefield_ptr->basic_degree = ground_field->basic_degree * degree; 252 finitefield_ptr->ground_degree = degree; 253 finitefield_ptr->element_len = ground_field->element_len * degree; 254 finitefield_ptr->modulus_0 = modulus_0; 255 // Warning: once assigned ground field must never be modified. this was not 256 // made const 257 // to allow the FiniteField structure to be used in context when we want to 258 // modify the parameters. 259 finitefield_ptr->ground_ff = (FiniteField*)ground_field; 260 finitefield_ptr->ipp_ff = ipp_finitefield_ctx; 261 *ff = finitefield_ptr; 262 result = kEpidNoErr; 263 } while (0); 264 265 SAFE_FREE(ff_elem_str); 266 267 if (kEpidNoErr != result) { 268 SAFE_FREE(finitefield_ptr); 269 SAFE_FREE(modulus_0); 270 SAFE_FREE(ipp_finitefield_ctx); 271 } 272 return result; 273 } 274 275 EpidStatus NewFiniteFieldViaPolynomialExtension(FiniteField const* ground_field, 276 BigNumStr const* irr_polynomial, 277 int degree, FiniteField** ff) { 278 EpidStatus result = kEpidErr; 279 IppsGFpState* ipp_finitefield_ctx = NULL; 280 FiniteField* finitefield_ptr = NULL; 281 FfElement** ff_elems = NULL; 282 IppsGFpElement** ff_elems_state = NULL; 283 BigNum* modulus_0 = NULL; 284 int i; 285 do { 286 EpidStatus status = kEpidErr; 287 IppStatus sts = ippStsNoErr; 288 int state_size_in_bytes = 0; 289 if (!ground_field || !irr_polynomial || !ff) { 290 result = kEpidBadArgErr; 291 break; 292 } 293 if (degree < 1 || degree > (int)(INT_MAX / sizeof(BigNumStr)) || 294 !ground_field->ipp_ff) { 295 result = kEpidBadArgErr; 296 break; 297 } 298 299 // Determine the memory requirement for finite field context 300 sts = ippsGFpxGetSize(ground_field->ipp_ff, degree, &state_size_in_bytes); 301 if (ippStsNoErr != sts) { 302 if (ippStsSizeErr == sts) { 303 result = kEpidBadArgErr; 304 } else { 305 result = kEpidMathErr; 306 } 307 break; 308 } 309 310 // Allocate space for ipp finite field context 311 ipp_finitefield_ctx = (IppsGFpState*)SAFE_ALLOC(state_size_in_bytes); 312 if (!ipp_finitefield_ctx) { 313 result = kEpidMemAllocErr; 314 break; 315 } 316 ff_elems = (FfElement**)SAFE_ALLOC(sizeof(FfElement*) * degree); 317 if (!ff_elems) { 318 result = kEpidMemAllocErr; 319 break; 320 } 321 ff_elems_state = 322 (IppsGFpElement**)SAFE_ALLOC(sizeof(IppsGFpElement*) * degree); 323 if (!ff_elems_state) { 324 result = kEpidMemAllocErr; 325 break; 326 } 327 for (i = 0; i < degree; ++i) { 328 status = NewFfElement(ground_field, &ff_elems[i]); 329 if (kEpidNoErr != status) { 330 result = kEpidMathErr; 331 break; 332 } 333 334 status = ReadFfElement((FiniteField*)ground_field, &irr_polynomial[i], 335 sizeof(BigNumStr), ff_elems[i]); 336 if (kEpidNoErr != status) { 337 result = kEpidMathErr; 338 break; 339 } 340 ff_elems_state[i] = ff_elems[i]->ipp_ff_elem; 341 } 342 // Initialize ipp binomial extension finite field context 343 sts = ippsGFpxInit(ground_field->ipp_ff, degree, 344 (const IppsGFpElement* const*)ff_elems_state, degree, 345 ippsGFpxMethod_com(), ipp_finitefield_ctx); 346 if (ippStsNoErr != sts) { 347 if (ippStsSizeErr == sts) { 348 result = kEpidBadArgErr; 349 } else { 350 result = kEpidMathErr; 351 } 352 break; 353 } 354 status = NewBigNum(sizeof(irr_polynomial[0]), &modulus_0); 355 if (kEpidNoErr != status) { 356 break; 357 } 358 status = 359 ReadBigNum(&irr_polynomial[0], sizeof(irr_polynomial[0]), modulus_0); 360 if (kEpidNoErr != status) { 361 break; 362 } 363 finitefield_ptr = (FiniteField*)SAFE_ALLOC(sizeof(FiniteField)); 364 if (!finitefield_ptr) { 365 result = kEpidMemAllocErr; 366 break; 367 } 368 finitefield_ptr->element_strlen_required = 369 ground_field->element_len * sizeof(Ipp32u) * degree; 370 finitefield_ptr->modulus_0 = modulus_0; 371 finitefield_ptr->basic_degree = ground_field->basic_degree * degree; 372 finitefield_ptr->ground_degree = degree; 373 finitefield_ptr->element_len = ground_field->element_len * degree; 374 // Warning: once assigned ground field must never be modified. this was not 375 // made const 376 // to allow the FiniteField structure to be used in context when we want to 377 // modify the parameters. 378 finitefield_ptr->ground_ff = (FiniteField*)ground_field; 379 finitefield_ptr->ipp_ff = ipp_finitefield_ctx; 380 *ff = finitefield_ptr; 381 result = kEpidNoErr; 382 } while (0); 383 384 if (ff_elems != NULL) { 385 for (i = 0; i < degree; i++) { 386 DeleteFfElement(&ff_elems[i]); 387 } 388 } 389 SAFE_FREE(ff_elems); 390 SAFE_FREE(ff_elems_state); 391 392 if (kEpidNoErr != result) { 393 SAFE_FREE(finitefield_ptr); 394 SAFE_FREE(modulus_0) 395 SAFE_FREE(ipp_finitefield_ctx); 396 } 397 return result; 398 } 399 400 void DeleteFiniteField(FiniteField** ff) { 401 if (ff) { 402 if (*ff) { 403 SAFE_FREE((*ff)->ipp_ff); 404 DeleteBigNum(&(*ff)->modulus_0); 405 } 406 SAFE_FREE((*ff)); 407 } 408 } 409 410 EpidStatus NewFfElement(FiniteField const* ff, FfElement** new_ff_elem) { 411 EpidStatus result = kEpidErr; 412 IppsGFpElement* ipp_ff_elem = NULL; 413 FfElement* ff_elem = NULL; 414 do { 415 IppStatus sts = ippStsNoErr; 416 unsigned int ctxsize = 0; 417 Ipp32u zero = 0; 418 // check parameters 419 if (!ff || !new_ff_elem) { 420 result = kEpidBadArgErr; 421 break; 422 } else if (!ff->ipp_ff) { 423 result = kEpidBadArgErr; 424 break; 425 } 426 // Determine the memory requirement for finite field element context 427 sts = ippsGFpElementGetSize(ff->ipp_ff, (int*)&ctxsize); 428 if (ippStsNoErr != sts) { 429 result = kEpidMathErr; 430 break; 431 } 432 // Allocate space for ipp bignum context 433 ipp_ff_elem = (IppsGFpElement*)SAFE_ALLOC(ctxsize); 434 if (!ipp_ff_elem) { 435 result = kEpidMemAllocErr; 436 break; 437 } 438 // Initialize ipp bignum context 439 // initialize state 440 sts = ippsGFpElementInit(&zero, 1, ipp_ff_elem, ff->ipp_ff); 441 if (ippStsNoErr != sts) { 442 result = kEpidMathErr; 443 break; 444 } 445 446 ff_elem = (FfElement*)SAFE_ALLOC(sizeof(FfElement)); 447 if (!ff_elem) { 448 result = kEpidMemAllocErr; 449 break; 450 } 451 452 ff_elem->ipp_ff_elem = ipp_ff_elem; 453 ff_elem->element_len = ff->element_len; 454 ff_elem->degree = ff->ground_degree; 455 456 *new_ff_elem = ff_elem; 457 result = kEpidNoErr; 458 } while (0); 459 460 if (kEpidNoErr != result) { 461 SAFE_FREE(ipp_ff_elem); 462 SAFE_FREE(ff_elem); 463 } 464 return result; 465 } 466 467 void DeleteFfElement(FfElement** ff_elem) { 468 if (ff_elem) { 469 if (*ff_elem) { 470 SAFE_FREE((*ff_elem)->ipp_ff_elem); 471 } 472 SAFE_FREE(*ff_elem); 473 } 474 } 475 476 EpidStatus IsValidFfElemOctString(ConstOctStr ff_elem_str, int strlen, 477 FiniteField const* ff) { 478 int i; 479 EpidStatus result = kEpidNoErr; 480 IppStatus sts = ippStsNoErr; 481 FiniteField const* basic_ff; 482 BigNum* pData = NULL; 483 int prime_length; 484 IppOctStr ff_elem_str_p; 485 Ipp32u cmp_res; 486 int tmp_strlen = strlen; 487 if (!ff || !ff_elem_str) { 488 return kEpidBadArgErr; 489 } 490 basic_ff = ff; 491 while (basic_ff->ground_ff != NULL) { 492 basic_ff = basic_ff->ground_ff; 493 } 494 prime_length = basic_ff->element_len * sizeof(Ipp32u); 495 ff_elem_str_p = (IppOctStr)ff_elem_str; 496 for (i = 0; (i < ff->basic_degree) && (tmp_strlen > 0); i++) { 497 int length; 498 length = MIN(prime_length, tmp_strlen); 499 result = NewBigNum(length, &pData); 500 if (kEpidNoErr != result) { 501 break; 502 } 503 result = ReadBigNum(ff_elem_str_p, length, pData); 504 if (kEpidNoErr != result) { 505 break; 506 } 507 sts = ippsCmp_BN(basic_ff->modulus_0->ipp_bn, pData->ipp_bn, &cmp_res); 508 // check return codes 509 if (ippStsNoErr != sts) { 510 if (ippStsContextMatchErr == sts) 511 result = kEpidBadArgErr; 512 else 513 result = kEpidMathErr; 514 break; 515 } 516 if (cmp_res != IPP_IS_GT) { 517 result = kEpidBadArgErr; 518 break; 519 } 520 DeleteBigNum(&pData); 521 tmp_strlen -= length; 522 ff_elem_str_p += length; 523 } 524 DeleteBigNum(&pData); 525 return result; 526 } 527 528 EpidStatus SetFfElementOctString(ConstOctStr ff_elem_str, int strlen, 529 FfElement* ff_elem, FiniteField* ff) { 530 EpidStatus result = kEpidErr; 531 IppOctStr extended_ff_elem_str = NULL; 532 if (!ff || !ff_elem || !ff_elem_str) { 533 return kEpidBadArgErr; 534 } 535 do { 536 IppStatus sts; 537 // Ipp2017u2 contians a bug in ippsGFpSetElementOctString, does not check 538 // whether ff_elem_str < modulus 539 result = IsValidFfElemOctString(ff_elem_str, strlen, ff); 540 if (kEpidNoErr != result) { 541 break; 542 } 543 // workaround because of bug in ipp2017u2 544 if (strlen < (int)(ff->element_len * sizeof(Ipp32u))) { 545 int length = ff->element_len * sizeof(Ipp32u); 546 extended_ff_elem_str = (IppOctStr)SAFE_ALLOC(length); 547 if (!extended_ff_elem_str) { 548 result = kEpidMemAllocErr; 549 break; 550 } 551 memset(extended_ff_elem_str, 0, length); 552 memcpy_S(extended_ff_elem_str, length, ff_elem_str, strlen); 553 strlen = length; 554 sts = ippsGFpSetElementOctString(extended_ff_elem_str, strlen, 555 ff_elem->ipp_ff_elem, ff->ipp_ff); 556 } else { 557 sts = ippsGFpSetElementOctString(ff_elem_str, strlen, 558 ff_elem->ipp_ff_elem, ff->ipp_ff); 559 } 560 if (ippStsNoErr != sts) { 561 if (ippStsContextMatchErr == sts || ippStsOutOfRangeErr == sts) { 562 result = kEpidBadArgErr; 563 } else { 564 result = kEpidMathErr; 565 } 566 break; 567 } 568 } while (0); 569 SAFE_FREE(extended_ff_elem_str); 570 return result; 571 } 572 573 EpidStatus ReadFfElement(FiniteField* ff, ConstOctStr ff_elem_str, 574 size_t strlen, FfElement* ff_elem) { 575 size_t strlen_required = 0; 576 int ipp_str_size = 0; 577 EpidStatus result = kEpidNoErr; 578 ConstIppOctStr str = (ConstIppOctStr)ff_elem_str; 579 580 if (!ff || !ff_elem_str || !ff_elem) { 581 return kEpidBadArgErr; 582 } 583 if (!ff_elem->ipp_ff_elem || !ff->ipp_ff) { 584 return kEpidBadArgErr; 585 } 586 587 if (ff->element_len != ff_elem->element_len) { 588 return kEpidBadArgErr; 589 } 590 591 strlen_required = ff->element_strlen_required; 592 593 // Remove leading zeros when de-serializing finite field of degree 1. 594 // This takes care of serialization chunk size adjustments when importing 595 // a big numbers. 596 if (1 == ff->basic_degree) { 597 while (strlen_required < strlen && 0 == *str) { 598 str++; 599 strlen--; 600 } 601 } 602 603 // Check if serialized value does not exceed ippsGFpSetElementOctString 604 // expected size. 605 if (strlen_required < strlen) { 606 return kEpidBadArgErr; 607 } 608 609 ipp_str_size = (int)strlen; 610 if (ipp_str_size <= 0) { 611 return kEpidBadArgErr; 612 } 613 614 result = SetFfElementOctString(str, ipp_str_size, ff_elem, ff); 615 616 return result; 617 } 618 619 /// Gets the prime value of a finite field 620 /*! 621 This function returns a reference to the bignum containing the field's prime 622 value. 623 624 This function only works with non-composite fields. 625 626 \param[in] ff 627 The field. 628 \param[out] bn 629 The target BigNum. 630 631 \returns ::EpidStatus 632 */ 633 EpidStatus GetFiniteFieldPrime(FiniteField* ff, BigNum** bn) { 634 if (!ff || !bn) { 635 return kEpidBadArgErr; 636 } 637 if (!ff->ipp_ff) { 638 return kEpidBadArgErr; 639 } 640 if (ff->basic_degree != 1 || ff->ground_degree != 1) { 641 return kEpidBadArgErr; 642 } 643 *bn = ff->modulus_0; 644 return kEpidNoErr; 645 } 646 647 EpidStatus InitFfElementFromBn(FiniteField* ff, BigNum* bn, 648 FfElement* ff_elem) { 649 EpidStatus result = kEpidErr; 650 BigNum* prime_bn = NULL; // non-owning reference 651 BigNum* mod_bn = NULL; 652 BNU mod_str = NULL; 653 654 if (!ff || !bn || !ff_elem) { 655 return kEpidBadArgErr; 656 } 657 if (!ff_elem->ipp_ff_elem || !ff->ipp_ff) { 658 return kEpidBadArgErr; 659 } 660 if (ff->basic_degree != 1 || ff->ground_degree != 1) { 661 return kEpidBadArgErr; 662 } 663 if (ff->element_len != ff_elem->element_len) { 664 return kEpidBadArgErr; 665 } 666 do { 667 size_t elem_size = ff->element_len * sizeof(Ipp32u); 668 result = NewBigNum(elem_size, &mod_bn); 669 if (kEpidNoErr != result) { 670 break; 671 } 672 result = GetFiniteFieldPrime(ff, &prime_bn); 673 if (kEpidNoErr != result) { 674 break; 675 } 676 677 result = BigNumMod(bn, prime_bn, mod_bn); 678 if (kEpidNoErr != result) { 679 break; 680 } 681 mod_str = (BNU)SAFE_ALLOC(elem_size); 682 if (NULL == mod_str) { 683 result = kEpidMemAllocErr; 684 break; 685 } 686 result = WriteBigNum(mod_bn, elem_size, mod_str); 687 if (kEpidNoErr != result) { 688 break; 689 } 690 result = ReadFfElement(ff, mod_str, elem_size, ff_elem); 691 if (kEpidNoErr != result) { 692 break; 693 } 694 result = kEpidNoErr; 695 } while (0); 696 SAFE_FREE(mod_str); 697 prime_bn = NULL; 698 DeleteBigNum(&mod_bn); 699 return result; 700 } 701 702 EpidStatus WriteFfElement(FiniteField* ff, FfElement const* ff_elem, 703 OctStr ff_elem_str, size_t strlen) { 704 IppStatus sts; 705 size_t strlen_required = 0; 706 size_t pad = 0; 707 IppOctStr str = (IppOctStr)ff_elem_str; 708 709 if (!ff || !ff_elem_str || !ff_elem) { 710 return kEpidBadArgErr; 711 } 712 if (!ff_elem->ipp_ff_elem || !ff->ipp_ff) { 713 return kEpidBadArgErr; 714 } 715 if (INT_MAX < strlen) { 716 return kEpidBadArgErr; 717 } 718 if (ff->element_len != ff_elem->element_len) { 719 return kEpidBadArgErr; 720 } 721 722 strlen_required = ff->element_strlen_required; 723 724 // add zero padding for extension of a degree 1 (a prime field) 725 // so it can be deserialized into big number correctly. 726 if (1 == ff->basic_degree && strlen_required < strlen) { 727 pad = strlen - strlen_required; 728 memset(str, 0, pad); 729 strlen -= pad; 730 str += pad; 731 } 732 733 // Check if output buffer meets ippsGFpGetElementOctString expectations. 734 if (strlen_required != strlen) return kEpidBadArgErr; 735 736 // get the data 737 sts = ippsGFpGetElementOctString(ff_elem->ipp_ff_elem, str, (int)strlen, 738 ff->ipp_ff); 739 if (ippStsNoErr != sts) { 740 if (ippStsContextMatchErr == sts) { 741 return kEpidBadArgErr; 742 } else { 743 return kEpidMathErr; 744 } 745 } 746 747 return kEpidNoErr; 748 } 749 750 EpidStatus FfNeg(FiniteField* ff, FfElement const* a, FfElement* r) { 751 IppStatus sts = ippStsNoErr; 752 if (!ff || !a || !r) { 753 return kEpidBadArgErr; 754 } else if (!ff->ipp_ff || !a->ipp_ff_elem || !r->ipp_ff_elem) { 755 return kEpidBadArgErr; 756 } 757 if (ff->element_len != a->element_len || ff->element_len != r->element_len) { 758 return kEpidBadArgErr; 759 } 760 sts = ippsGFpNeg(a->ipp_ff_elem, r->ipp_ff_elem, ff->ipp_ff); 761 if (ippStsNoErr != sts) { 762 if (ippStsContextMatchErr == sts) { 763 return kEpidBadArgErr; 764 } else { 765 return kEpidMathErr; 766 } 767 } 768 return kEpidNoErr; 769 } 770 771 EpidStatus FfInv(FiniteField* ff, FfElement const* a, FfElement* r) { 772 IppStatus sts = ippStsNoErr; 773 // Check required parametersWriteFfElement 774 if (!ff || !a || !r) { 775 return kEpidBadArgErr; 776 } else if (!ff->ipp_ff || !a->ipp_ff_elem || !r->ipp_ff_elem) { 777 return kEpidBadArgErr; 778 } 779 if (ff->element_len != a->element_len || ff->element_len != r->element_len) { 780 return kEpidBadArgErr; 781 } 782 // Invert the element 783 sts = ippsGFpInv(a->ipp_ff_elem, r->ipp_ff_elem, ff->ipp_ff); 784 // Check return codes 785 if (ippStsNoErr != sts) { 786 if (ippStsContextMatchErr == sts) 787 return kEpidBadArgErr; 788 else if (ippStsDivByZeroErr == sts) 789 return kEpidDivByZeroErr; 790 else 791 return kEpidMathErr; 792 } 793 return kEpidNoErr; 794 } 795 796 EpidStatus FfAdd(FiniteField* ff, FfElement const* a, FfElement const* b, 797 FfElement* r) { 798 IppStatus sts = ippStsNoErr; 799 if (!ff || !a || !b || !r) { 800 return kEpidBadArgErr; 801 } else if (!ff->ipp_ff || !a->ipp_ff_elem || !b->ipp_ff_elem || 802 !r->ipp_ff_elem) { 803 return kEpidBadArgErr; 804 } 805 if (ff->element_len != a->element_len || ff->element_len != b->element_len || 806 ff->element_len != r->element_len) { 807 return kEpidBadArgErr; 808 } 809 810 sts = ippsGFpAdd(a->ipp_ff_elem, b->ipp_ff_elem, r->ipp_ff_elem, ff->ipp_ff); 811 if (ippStsContextMatchErr == sts) { 812 return kEpidBadArgErr; 813 } else if (ippStsNoErr != sts) { 814 return kEpidMathErr; 815 } 816 return kEpidNoErr; 817 } 818 819 EpidStatus FfSub(FiniteField* ff, FfElement const* a, FfElement const* b, 820 FfElement* r) { 821 IppStatus sts = ippStsNoErr; 822 if (!ff || !a || !b || !r) { 823 return kEpidBadArgErr; 824 } else if (!ff->ipp_ff || !a->ipp_ff_elem || !b->ipp_ff_elem || 825 !r->ipp_ff_elem) { 826 return kEpidBadArgErr; 827 } 828 829 if (ff->element_len != a->element_len || ff->element_len != b->element_len || 830 ff->element_len != r->element_len) { 831 return kEpidBadArgErr; 832 } 833 834 sts = ippsGFpSub(a->ipp_ff_elem, b->ipp_ff_elem, r->ipp_ff_elem, ff->ipp_ff); 835 if (ippStsContextMatchErr == sts) { 836 return kEpidBadArgErr; 837 } else if (ippStsNoErr != sts) { 838 return kEpidMathErr; 839 } 840 return kEpidNoErr; 841 } 842 843 EpidStatus FfMul(FiniteField* ff, FfElement const* a, FfElement const* b, 844 FfElement* r) { 845 IppStatus sts = ippStsNoErr; 846 // Check required parametersWriteFfElement 847 if (!ff || !a || !b || !r) { 848 return kEpidBadArgErr; 849 } else if (!ff->ipp_ff || !a->ipp_ff_elem || !b->ipp_ff_elem || 850 !r->ipp_ff_elem) { 851 return kEpidBadArgErr; 852 } 853 // Multiplies elements 854 if (a->element_len != b->element_len && 855 a->element_len == a->degree * b->element_len) { 856 sts = ippsGFpMul_PE(a->ipp_ff_elem, b->ipp_ff_elem, r->ipp_ff_elem, 857 ff->ipp_ff); 858 } else { 859 if (ff->element_len != a->element_len || 860 ff->element_len != b->element_len || 861 ff->element_len != r->element_len) { 862 return kEpidBadArgErr; 863 } 864 sts = 865 ippsGFpMul(a->ipp_ff_elem, b->ipp_ff_elem, r->ipp_ff_elem, ff->ipp_ff); 866 } 867 // Check return codes 868 if (ippStsNoErr != sts) { 869 if (ippStsContextMatchErr == sts) 870 return kEpidBadArgErr; 871 else 872 return kEpidMathErr; 873 } 874 return kEpidNoErr; 875 } 876 877 EpidStatus FfIsZero(FiniteField* ff, FfElement const* a, bool* is_zero) { 878 IppStatus sts = ippStsNoErr; 879 int ipp_result = IPP_IS_NE; 880 // Check required parameters 881 if (!ff || !a || !is_zero) { 882 return kEpidBadArgErr; 883 } else if (!ff->ipp_ff || !a->ipp_ff_elem) { 884 return kEpidBadArgErr; 885 } 886 if (ff->element_len != a->element_len) { 887 return kEpidBadArgErr; 888 } 889 // Check if the element is zero 890 sts = ippsGFpIsZeroElement(a->ipp_ff_elem, &ipp_result, ff->ipp_ff); 891 // Check return codes 892 if (ippStsNoErr != sts) { 893 if (ippStsContextMatchErr == sts) 894 return kEpidBadArgErr; 895 else 896 return kEpidMathErr; 897 } 898 if (IPP_IS_EQ == ipp_result) { 899 *is_zero = true; 900 } else { 901 *is_zero = false; 902 } 903 return kEpidNoErr; 904 } 905 906 EpidStatus FfExp(FiniteField* ff, FfElement const* a, BigNum const* b, 907 FfElement* r) { 908 EpidStatus result = kEpidErr; 909 OctStr scratch_buffer = NULL; 910 int exp_bit_size = 0; 911 int element_size = 0; 912 913 do { 914 IppStatus sts = ippStsNoErr; 915 // Check required parameters 916 if (!ff || !a || !b || !r) { 917 result = kEpidBadArgErr; 918 break; 919 } else if (!ff->ipp_ff || !a->ipp_ff_elem || !r->ipp_ff_elem) { 920 result = kEpidBadArgErr; 921 break; 922 } 923 if (ff->element_len != a->element_len || 924 ff->element_len != r->element_len) { 925 return kEpidBadArgErr; 926 } 927 928 sts = ippsRef_BN(0, &exp_bit_size, 0, b->ipp_bn); 929 if (ippStsNoErr != sts) { 930 result = kEpidMathErr; 931 break; 932 } 933 934 sts = ippsGFpScratchBufferSize(1, exp_bit_size, ff->ipp_ff, &element_size); 935 if (ippStsNoErr != sts) { 936 result = kEpidMathErr; 937 break; 938 } 939 940 scratch_buffer = (OctStr)SAFE_ALLOC(element_size); 941 if (!scratch_buffer) { 942 result = kEpidMemAllocErr; 943 break; 944 } 945 946 sts = ippsGFpExp(a->ipp_ff_elem, b->ipp_bn, r->ipp_ff_elem, ff->ipp_ff, 947 scratch_buffer); 948 // Check return codes 949 if (ippStsNoErr != sts) { 950 if (ippStsContextMatchErr == sts || ippStsRangeErr == sts) 951 result = kEpidBadArgErr; 952 else 953 result = kEpidMathErr; 954 break; 955 } 956 result = kEpidNoErr; 957 } while (0); 958 SAFE_FREE(scratch_buffer); 959 return result; 960 } 961 962 EpidStatus FfMultiExp(FiniteField* ff, FfElement const** p, BigNumStr const** b, 963 size_t m, FfElement* r) { 964 EpidStatus result = kEpidErr; 965 IppsGFpElement** ipp_p = NULL; 966 IppsBigNumState** ipp_b = NULL; 967 BigNum** bignums = NULL; 968 OctStr scratch_buffer = NULL; 969 int i = 0; 970 int ipp_m = 0; 971 972 // Check required parameters 973 if (!ff || !p || !b || !r) { 974 return kEpidBadArgErr; 975 } else if (!ff->ipp_ff || !r->ipp_ff_elem || m <= 0) { 976 return kEpidBadArgErr; 977 } 978 // because we use ipp function with number of items parameter 979 // defined as "int" we need to verify that input length 980 // do not exceed INT_MAX to avoid overflow 981 if (m > INT_MAX) { 982 return kEpidBadArgErr; 983 } 984 ipp_m = (int)m; 985 986 for (i = 0; i < ipp_m; i++) { 987 if (!p[i]) { 988 return kEpidBadArgErr; 989 } 990 if (!p[i]->ipp_ff_elem) { 991 return kEpidBadArgErr; 992 } 993 if (ff->element_len != p[i]->element_len) { 994 return kEpidBadArgErr; 995 } 996 } 997 if (ff->element_len != r->element_len) { 998 return kEpidBadArgErr; 999 } 1000 1001 do { 1002 IppStatus sts = ippStsNoErr; 1003 int scratch_buffer_size = 0; 1004 const int exp_bit_size = CHAR_BIT * sizeof(BigNumStr); 1005 1006 // Allocate memory for finite field elements for ipp call 1007 ipp_p = (IppsGFpElement**)SAFE_ALLOC(ipp_m * sizeof(IppsGFpElement*)); 1008 if (!ipp_p) { 1009 result = kEpidMemAllocErr; 1010 break; 1011 } 1012 for (i = 0; i < ipp_m; i++) { 1013 ipp_p[i] = p[i]->ipp_ff_elem; 1014 } 1015 1016 // Create big number elements for ipp call 1017 // Allocate memory for finite field elements for ipp call 1018 bignums = (BigNum**)SAFE_ALLOC(ipp_m * sizeof(BigNum*)); 1019 if (!bignums) { 1020 result = kEpidMemAllocErr; 1021 break; 1022 } 1023 ipp_b = (IppsBigNumState**)SAFE_ALLOC(ipp_m * sizeof(IppsBigNumState*)); 1024 if (!ipp_b) { 1025 result = kEpidMemAllocErr; 1026 break; 1027 } 1028 // Initialize BigNum and fill ipp array for ipp call 1029 for (i = 0; i < ipp_m; i++) { 1030 result = NewBigNum(sizeof(BigNumStr), &bignums[i]); 1031 if (kEpidNoErr != result) break; 1032 result = ReadBigNum(b[i], sizeof(BigNumStr), bignums[i]); 1033 if (kEpidNoErr != result) break; 1034 ipp_b[i] = bignums[i]->ipp_bn; 1035 } 1036 if (kEpidNoErr != result) break; 1037 1038 // calculate scratch buffer size 1039 sts = ippsGFpScratchBufferSize(ipp_m, exp_bit_size, ff->ipp_ff, 1040 &scratch_buffer_size); 1041 if (sts != ippStsNoErr) { 1042 result = kEpidMathErr; 1043 break; 1044 } 1045 // allocate memory for scratch buffer 1046 scratch_buffer = (OctStr)SAFE_ALLOC(scratch_buffer_size); 1047 if (!scratch_buffer) { 1048 result = kEpidMemAllocErr; 1049 break; 1050 } 1051 1052 sts = ippsGFpMultiExp((const IppsGFpElement* const*)ipp_p, 1053 (const IppsBigNumState* const*)ipp_b, ipp_m, 1054 r->ipp_ff_elem, ff->ipp_ff, scratch_buffer); 1055 if (ippStsNoErr != sts) { 1056 if (ippStsContextMatchErr == sts || ippStsRangeErr == sts) 1057 result = kEpidBadArgErr; 1058 else 1059 result = kEpidMathErr; 1060 break; 1061 } 1062 result = kEpidNoErr; 1063 } while (0); 1064 if (NULL != bignums) { // delete big nums only if it was really allocated 1065 for (i = 0; i < ipp_m; i++) { 1066 DeleteBigNum(&bignums[i]); 1067 } 1068 } 1069 SAFE_FREE(bignums); 1070 SAFE_FREE(ipp_p); 1071 SAFE_FREE(ipp_b); 1072 SAFE_FREE(scratch_buffer); 1073 return result; 1074 } 1075 1076 EpidStatus FfMultiExpBn(FiniteField* ff, FfElement const** p, BigNum const** b, 1077 size_t m, FfElement* r) { 1078 IppStatus sts = ippStsNoErr; 1079 EpidStatus result = kEpidErr; 1080 IppsGFpElement** ipp_p = NULL; 1081 IppsBigNumState** ipp_b = NULL; 1082 OctStr scratch_buffer = NULL; 1083 1084 int exp_bit_size = 0; 1085 size_t i = 0; 1086 int ipp_m = 0; 1087 1088 // Check required parameters 1089 if (!ff || !p || !b || !r) { 1090 return kEpidBadArgErr; 1091 } else if (!ff->ipp_ff || !r->ipp_ff_elem || m <= 0) { 1092 return kEpidBadArgErr; 1093 } else if (ff->element_len != r->element_len) { 1094 return kEpidBadArgErr; 1095 } 1096 // because we use ipp function with number of items parameter 1097 // defined as "int" we need to verify that input length 1098 // do not exceed INT_MAX to avoid overflow 1099 if (m > INT_MAX) { 1100 return kEpidBadArgErr; 1101 } 1102 ipp_m = (int)m; 1103 for (i = 0; i < m; i++) { 1104 int b_size = 0; 1105 if (!p[i] || !p[i]->ipp_ff_elem || !b[i] || !b[i]->ipp_bn) { 1106 return kEpidBadArgErr; 1107 } 1108 if (ff->element_len != p[i]->element_len) { 1109 return kEpidBadArgErr; 1110 } 1111 sts = ippsGetSize_BN(b[i]->ipp_bn, &b_size); 1112 if (ippStsNoErr != sts) { 1113 return kEpidBadArgErr; 1114 } 1115 b_size *= (sizeof(Ipp32u) * CHAR_BIT); 1116 if (b_size > exp_bit_size) { 1117 exp_bit_size = b_size; 1118 } 1119 } 1120 1121 do { 1122 int scratch_buffer_size = 0; 1123 1124 // Allocate memory for finite field elements for ipp call 1125 ipp_p = (IppsGFpElement**)SAFE_ALLOC(m * sizeof(IppsGFpElement*)); 1126 if (!ipp_p) { 1127 result = kEpidMemAllocErr; 1128 break; 1129 } 1130 for (i = 0; i < m; i++) { 1131 ipp_p[i] = p[i]->ipp_ff_elem; 1132 } 1133 1134 ipp_b = (IppsBigNumState**)SAFE_ALLOC(m * sizeof(IppsBigNumState*)); 1135 if (!ipp_b) { 1136 result = kEpidMemAllocErr; 1137 break; 1138 } 1139 // fill ipp array for ipp call 1140 for (i = 0; i < m; i++) { 1141 ipp_b[i] = b[i]->ipp_bn; 1142 } 1143 1144 // calculate scratch buffer size 1145 sts = ippsGFpScratchBufferSize(ipp_m, exp_bit_size, ff->ipp_ff, 1146 &scratch_buffer_size); 1147 if (sts != ippStsNoErr) { 1148 result = kEpidMathErr; 1149 break; 1150 } 1151 // allocate memory for scratch buffer 1152 scratch_buffer = (OctStr)SAFE_ALLOC(scratch_buffer_size); 1153 if (!scratch_buffer) { 1154 result = kEpidMemAllocErr; 1155 break; 1156 } 1157 1158 sts = ippsGFpMultiExp((const IppsGFpElement* const*)ipp_p, 1159 (const IppsBigNumState* const*)ipp_b, ipp_m, 1160 r->ipp_ff_elem, ff->ipp_ff, scratch_buffer); 1161 if (ippStsNoErr != sts) { 1162 if (ippStsContextMatchErr == sts || ippStsRangeErr == sts) 1163 result = kEpidBadArgErr; 1164 else 1165 result = kEpidMathErr; 1166 break; 1167 } 1168 1169 result = kEpidNoErr; 1170 } while (0); 1171 1172 SAFE_FREE(scratch_buffer); 1173 SAFE_FREE(ipp_b); 1174 SAFE_FREE(ipp_p); 1175 return result; 1176 } 1177 1178 EpidStatus FfSscmMultiExp(FiniteField* ff, FfElement const** p, 1179 BigNumStr const** b, size_t m, FfElement* r) { 1180 // call EcMultiExp directly because its implementation is side channel 1181 // mitigated already 1182 return FfMultiExp(ff, p, b, m, r); 1183 } 1184 1185 EpidStatus FfIsEqual(FiniteField* ff, FfElement const* a, FfElement const* b, 1186 bool* is_equal) { 1187 IppStatus sts; 1188 int result; 1189 1190 if (!ff || !a || !b || !is_equal) { 1191 return kEpidBadArgErr; 1192 } 1193 if (!ff->ipp_ff || !a->ipp_ff_elem || !b->ipp_ff_elem) { 1194 return kEpidBadArgErr; 1195 } 1196 if (ff->element_len != a->element_len || ff->element_len != b->element_len) { 1197 return kEpidBadArgErr; 1198 } 1199 1200 sts = ippsGFpCmpElement(a->ipp_ff_elem, b->ipp_ff_elem, &result, ff->ipp_ff); 1201 if (ippStsNoErr != sts) { 1202 if (ippStsContextMatchErr == sts) { 1203 return kEpidBadArgErr; 1204 } else { 1205 return kEpidMathErr; 1206 } 1207 } 1208 *is_equal = IPP_IS_EQ == result; 1209 1210 return kEpidNoErr; 1211 } 1212 1213 EpidStatus FfHash(FiniteField* ff, ConstOctStr msg, size_t msg_len, 1214 HashAlg hash_alg, FfElement* r) { 1215 EpidStatus result = kEpidErr; 1216 do { 1217 IppStatus sts = ippStsNoErr; 1218 IppHashAlgId hash_id; 1219 int ipp_msg_len = 0; 1220 if (!ff || !msg || !r) { 1221 result = kEpidBadArgErr; 1222 break; 1223 } else if (!ff->ipp_ff || !r->ipp_ff_elem || msg_len <= 0) { 1224 result = kEpidBadArgErr; 1225 break; 1226 } 1227 // because we use ipp function with message length parameter 1228 // defined as "int" we need to verify that input length 1229 // do not exceed INT_MAX to avoid overflow 1230 if (msg_len > INT_MAX) { 1231 result = kEpidBadArgErr; 1232 break; 1233 } 1234 ipp_msg_len = (int)msg_len; 1235 1236 if (kSha256 == hash_alg) { 1237 hash_id = ippHashAlg_SHA256; 1238 } else if (kSha384 == hash_alg) { 1239 hash_id = ippHashAlg_SHA384; 1240 } else if (kSha512 == hash_alg) { 1241 hash_id = ippHashAlg_SHA512; 1242 } else if (kSha512_256 == hash_alg) { 1243 hash_id = ippHashAlg_SHA512_256; 1244 } else { 1245 result = kEpidHashAlgorithmNotSupported; 1246 break; 1247 } 1248 if (ff->element_len != r->element_len) { 1249 return kEpidBadArgErr; 1250 } 1251 sts = ippsGFpSetElementHash(msg, ipp_msg_len, r->ipp_ff_elem, ff->ipp_ff, 1252 hash_id); 1253 if (ippStsNoErr != sts) { 1254 if (ippStsContextMatchErr == sts || ippStsBadArgErr == sts || 1255 ippStsLengthErr == sts) { 1256 return kEpidBadArgErr; 1257 } else { 1258 return kEpidMathErr; 1259 } 1260 } 1261 result = kEpidNoErr; 1262 } while (0); 1263 return result; 1264 } 1265 1266 /// Number of tries for RNG 1267 #define RNG_WATCHDOG (10) 1268 EpidStatus FfGetRandom(FiniteField* ff, BigNumStr const* low_bound, 1269 BitSupplier rnd_func, void* rnd_param, FfElement* r) { 1270 EpidStatus result = kEpidErr; 1271 FfElement* low = NULL; 1272 do { 1273 IppStatus sts = ippStsNoErr; 1274 unsigned int rngloopCount = RNG_WATCHDOG; 1275 if (!ff || !low_bound || !rnd_func || !r) { 1276 result = kEpidBadArgErr; 1277 break; 1278 } 1279 if (!ff->ipp_ff || !r->ipp_ff_elem) { 1280 result = kEpidBadArgErr; 1281 break; 1282 } 1283 if (ff->element_len != r->element_len) { 1284 return kEpidBadArgErr; 1285 } 1286 // create a new FfElement to hold low_bound 1287 result = NewFfElement(ff, &low); 1288 if (kEpidNoErr != result) { 1289 break; 1290 } 1291 result = ReadFfElement(ff, low_bound, sizeof(*low_bound), low); 1292 if (kEpidNoErr != result) { 1293 break; 1294 } 1295 do { 1296 int cmpResult = IPP_IS_NE; 1297 sts = ippsGFpSetElementRandom(r->ipp_ff_elem, ff->ipp_ff, 1298 (IppBitSupplier)rnd_func, rnd_param); 1299 if (ippStsNoErr != sts) { 1300 result = kEpidMathErr; 1301 break; 1302 } 1303 sts = ippsGFpCmpElement(r->ipp_ff_elem, low->ipp_ff_elem, &cmpResult, 1304 ff->ipp_ff); 1305 if (ippStsNoErr != sts) { 1306 result = kEpidMathErr; 1307 break; 1308 } 1309 if (IPP_IS_LT != cmpResult) { 1310 // we have a valid value, proceed 1311 result = kEpidNoErr; 1312 break; 1313 } else { 1314 result = kEpidRandMaxIterErr; 1315 continue; 1316 } 1317 } while (--rngloopCount); 1318 } while (0); 1319 DeleteFfElement(&low); 1320 return result; 1321 } 1322 1323 EpidStatus FfSqrt(FiniteField* ff, FfElement const* a, FfElement* r) { 1324 EpidStatus result = kEpidErr; 1325 BigNum* qm1 = NULL; 1326 BigNum* one = NULL; 1327 FfElement* qm1_ffe = NULL; 1328 BigNum* two = NULL; 1329 BigNum* qm1d2 = NULL; 1330 BigNum* remainder = NULL; 1331 FfElement* g = NULL; 1332 FfElement* gg = NULL; 1333 BigNum* t = NULL; 1334 BigNum* e = NULL; 1335 BigNum* j = NULL; 1336 BigNum* qm1dj = NULL; 1337 FfElement* ge = NULL; 1338 FfElement* h = NULL; 1339 FfElement* temp = NULL; 1340 FfElement* one_ffe = NULL; 1341 BigNum* ed2 = NULL; 1342 FfElement* ged2 = NULL; 1343 BigNum* tp1d2 = NULL; 1344 FfElement* gtp1d2 = NULL; 1345 FfElement* dd = NULL; 1346 1347 if (!ff || !a || !r) { 1348 return kEpidBadArgErr; 1349 } 1350 do { 1351 BigNum* prime = NULL; // non-owning reference 1352 bool is_equal = false; 1353 unsigned int s; 1354 bool is_even = false; 1355 unsigned int i; 1356 Ipp8u one_str = 1; 1357 BigNumStr qm1_str; 1358 const BigNumStr zero_str = {0}; 1359 1360 result = GetFiniteFieldPrime(ff, &prime); 1361 if (kEpidNoErr != result) { 1362 break; 1363 } 1364 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &qm1); 1365 if (kEpidNoErr != result) { 1366 break; 1367 } 1368 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &one); 1369 if (kEpidNoErr != result) { 1370 break; 1371 } 1372 result = NewFfElement(ff, &qm1_ffe); 1373 if (kEpidNoErr != result) { 1374 break; 1375 } 1376 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &two); 1377 if (kEpidNoErr != result) { 1378 break; 1379 } 1380 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &qm1d2); 1381 if (kEpidNoErr != result) { 1382 break; 1383 } 1384 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &remainder); 1385 if (kEpidNoErr != result) { 1386 break; 1387 } 1388 result = NewFfElement(ff, &g); 1389 if (kEpidNoErr != result) { 1390 break; 1391 } 1392 result = NewFfElement(ff, &gg); 1393 if (kEpidNoErr != result) { 1394 break; 1395 } 1396 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &t); 1397 if (kEpidNoErr != result) { 1398 break; 1399 } 1400 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &e); 1401 if (kEpidNoErr != result) { 1402 break; 1403 } 1404 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &j); 1405 if (kEpidNoErr != result) { 1406 break; 1407 } 1408 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &qm1dj); 1409 if (kEpidNoErr != result) { 1410 break; 1411 } 1412 result = NewFfElement(ff, &ge); 1413 if (kEpidNoErr != result) { 1414 break; 1415 } 1416 result = NewFfElement(ff, &h); 1417 if (kEpidNoErr != result) { 1418 break; 1419 } 1420 result = NewFfElement(ff, &temp); 1421 if (kEpidNoErr != result) { 1422 break; 1423 } 1424 result = NewFfElement(ff, &one_ffe); 1425 if (kEpidNoErr != result) { 1426 break; 1427 } 1428 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &ed2); 1429 if (kEpidNoErr != result) { 1430 break; 1431 } 1432 result = NewFfElement(ff, &ged2); 1433 if (kEpidNoErr != result) { 1434 break; 1435 } 1436 result = NewBigNum(sizeof(BigNumStr) * CHAR_BIT, &tp1d2); 1437 if (kEpidNoErr != result) { 1438 break; 1439 } 1440 result = NewFfElement(ff, >p1d2); 1441 if (kEpidNoErr != result) { 1442 break; 1443 } 1444 result = NewFfElement(ff, &dd); 1445 if (kEpidNoErr != result) { 1446 break; 1447 } 1448 result = ReadBigNum(&one_str, sizeof(one_str), one); 1449 if (kEpidNoErr != result) { 1450 break; 1451 } 1452 result = BigNumSub(prime, one, qm1); 1453 if (kEpidNoErr != result) { 1454 break; 1455 } 1456 result = BigNumAdd(one, one, two); 1457 if (kEpidNoErr != result) { 1458 break; 1459 } 1460 result = InitFfElementFromBn(ff, one, one_ffe); 1461 if (kEpidNoErr != result) { 1462 break; 1463 } 1464 result = WriteBigNum(qm1, sizeof(qm1_str), &qm1_str); 1465 if (kEpidNoErr != result) { 1466 break; 1467 } 1468 result = InitFfElementFromBn(ff, qm1, qm1_ffe); 1469 if (kEpidNoErr != result) { 1470 break; 1471 } 1472 result = BigNumDiv(qm1, two, qm1d2, remainder); 1473 if (kEpidNoErr != result) { 1474 break; 1475 } 1476 1477 // 1. Choose an element g in Fq. 1478 result = ReadFfElement(ff, &one_str, sizeof(one_str), g); 1479 if (kEpidNoErr != result) { 1480 break; 1481 } 1482 // try small values for g starting from 2 until 1483 // it meets the requirements from the step 2 1484 do { 1485 result = FfAdd(ff, g, one_ffe, g); 1486 if (kEpidNoErr != result) { 1487 break; 1488 } 1489 1490 // 2. Check whether g^((q-1)/2) mod q = q-1. If not, go to step 1. 1491 result = FfExp(ff, g, qm1d2, gg); 1492 if (kEpidNoErr != result) { 1493 break; 1494 } 1495 1496 result = FfIsEqual(ff, gg, qm1_ffe, &is_equal); 1497 if (kEpidNoErr != result) { 1498 break; 1499 } 1500 } while (!is_equal); 1501 if (kEpidNoErr != result) { 1502 break; 1503 } 1504 1505 // 3. Set t = q-1, s = 0. 1506 result = ReadBigNum(&qm1_str, sizeof(qm1_str), t); 1507 if (kEpidNoErr != result) { 1508 break; 1509 } 1510 s = 0; 1511 // 4. While (t is even number) 1512 // t = t/2, s = s+1. 1513 result = BigNumIsEven(t, &is_even); 1514 if (kEpidNoErr != result) { 1515 break; 1516 } 1517 1518 while (is_even) { 1519 result = BigNumDiv(t, two, t, remainder); 1520 if (kEpidNoErr != result) { 1521 break; 1522 } 1523 s = s + 1; 1524 result = BigNumIsEven(t, &is_even); 1525 if (kEpidNoErr != result) { 1526 break; 1527 } 1528 } 1529 // 5. Note that g, s, t can be pre-computed and used for all 1530 // future computations. 1531 // Also note that q-1 = (2^s)*t where t is an odd integer. 1532 1533 // 6. e = 0. 1534 result = ReadBigNum(&zero_str, sizeof(zero_str), e); 1535 if (kEpidNoErr != result) { 1536 break; 1537 } 1538 1539 // 7. For i = 2, ..., s 1540 // j = 2^i, 1541 // if (a ? g^(-e))^((q-1)/j) mod q != 1, then set e = e + j/2. 1542 for (i = 2; i <= s; i++) { 1543 result = BigNumPow2N(i, j); 1544 if (kEpidNoErr != result) { 1545 break; 1546 } 1547 result = BigNumDiv(qm1, j, qm1dj, remainder); 1548 if (kEpidNoErr != result) { 1549 break; 1550 } 1551 result = FfExp(ff, g, e, ge); 1552 if (kEpidNoErr != result) { 1553 break; 1554 } 1555 // 8. Compute h = (a * g^(-e)) mod q. 1556 result = FfInv(ff, ge, ge); 1557 if (kEpidNoErr != result) { 1558 break; 1559 } 1560 result = FfMul(ff, a, ge, h); 1561 if (kEpidNoErr != result) { 1562 break; 1563 } 1564 result = FfExp(ff, h, qm1dj, temp); 1565 if (kEpidNoErr != result) { 1566 break; 1567 } 1568 result = FfIsEqual(ff, temp, one_ffe, &is_equal); 1569 if (!is_equal) { 1570 result = BigNumDiv(j, two, j, remainder); 1571 if (kEpidNoErr != result) { 1572 break; 1573 } 1574 result = BigNumAdd(e, j, e); 1575 if (kEpidNoErr != result) { 1576 break; 1577 } 1578 } 1579 } 1580 1581 // 8. Compute h = (a * g^(-e)) mod q. 1582 result = FfExp(ff, g, e, ge); 1583 if (kEpidNoErr != result) { 1584 break; 1585 } 1586 result = FfInv(ff, ge, ge); 1587 if (kEpidNoErr != result) { 1588 break; 1589 } 1590 result = FfMul(ff, a, ge, h); 1591 if (kEpidNoErr != result) { 1592 break; 1593 } 1594 1595 // 9. Compute r = d = (g^(e/2) * h^((t+1)/2)) mod q. 1596 result = BigNumDiv(e, two, ed2, remainder); 1597 if (kEpidNoErr != result) { 1598 break; 1599 } 1600 result = FfExp(ff, g, ed2, ged2); 1601 if (kEpidNoErr != result) { 1602 break; 1603 } 1604 result = BigNumAdd(t, one, tp1d2); 1605 if (kEpidNoErr != result) { 1606 break; 1607 } 1608 result = BigNumDiv(tp1d2, two, tp1d2, remainder); 1609 if (kEpidNoErr != result) { 1610 break; 1611 } 1612 result = FfExp(ff, h, tp1d2, gtp1d2); 1613 if (kEpidNoErr != result) { 1614 break; 1615 } 1616 result = FfMul(ff, ged2, gtp1d2, r); 1617 if (kEpidNoErr != result) { 1618 break; 1619 } 1620 // 10. Verify whether a = d^2 mod q. If so, return r, otherwise, return 1621 // fail. 1622 result = FfMul(ff, r, r, dd); 1623 if (kEpidNoErr != result) { 1624 break; 1625 } 1626 result = FfIsEqual(ff, dd, a, &is_equal); 1627 if (kEpidNoErr != result) { 1628 break; 1629 } 1630 if (!is_equal) { 1631 result = kEpidMathQuadraticNonResidueError; 1632 break; 1633 } 1634 result = kEpidNoErr; 1635 prime = NULL; 1636 } while (0); 1637 DeleteFfElement(&dd); 1638 DeleteFfElement(>p1d2); 1639 DeleteBigNum(&tp1d2); 1640 DeleteFfElement(&ged2); 1641 DeleteBigNum(&ed2); 1642 DeleteFfElement(&one_ffe); 1643 DeleteFfElement(&temp); 1644 DeleteFfElement(&h); 1645 DeleteFfElement(&ge); 1646 DeleteBigNum(&qm1dj); 1647 DeleteBigNum(&j); 1648 DeleteBigNum(&e); 1649 DeleteBigNum(&t); 1650 DeleteFfElement(&gg); 1651 DeleteFfElement(&g); 1652 DeleteBigNum(&remainder); 1653 DeleteBigNum(&qm1d2); 1654 DeleteBigNum(&two); 1655 DeleteFfElement(&qm1_ffe); 1656 DeleteBigNum(&one); 1657 DeleteBigNum(&qm1); 1658 return result; 1659 } 1660
