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 interface. 20 */ 21 22 #ifndef EPID_COMMON_MATH_FINITEFIELD_H_ 23 #define EPID_COMMON_MATH_FINITEFIELD_H_ 24 25 #include "epid/common/bitsupplier.h" 26 #include "epid/common/errors.h" 27 #include "epid/common/math/bignum.h" 28 #include "epid/common/stdtypes.h" 29 #include "epid/common/types.h" 30 31 /// Finite field operations 32 /*! 33 \defgroup FiniteFieldPrimitives finitefield 34 provides APIs for working with finite fields. 35 Finite fields allow simple mathematical operations based on a finite set of 36 discrete values. The results of these operations are also contained in the 37 same set. 38 39 A simple example of a finite field is all integers from zero that are less than 40 a given value. 41 42 The elements (::FfElement) of a finite field can be used in a variety of 43 simple mathematical operations that result in elements of the same field. 44 45 \ingroup EpidMath 46 @{ 47 */ 48 49 /// A finite field. 50 typedef struct FiniteField FiniteField; 51 52 /// An element in a finite field. 53 typedef struct FfElement FfElement; 54 55 /// Creates new finite field. 56 /*! 57 Allocates memory and creates a new finite field GF(prime). 58 59 Use DeleteFiniteField() to free memory. 60 61 \param[in] prime 62 The order of the finite field. 63 \param[out] ff 64 The newly constructed finite field. 65 66 \returns ::EpidStatus 67 68 \see DeleteFiniteField 69 */ 70 EpidStatus NewFiniteField(BigNumStr const* prime, FiniteField** ff); 71 72 /// Creates a new finite field using binomial extension. 73 /*! 74 Allocates memory and creates a finite field using binomial extension. 75 76 Use DeleteFiniteField() to free memory. 77 78 \param[in] ground_field 79 The ground field. 80 \param[in] ground_element 81 The low-order term of the extension. 82 \param[in] degree 83 The degree of the extension. 84 \param[out] ff 85 The newly constructed finite field. 86 87 \returns ::EpidStatus 88 89 \attention It is the responsibility of the caller to ensure that ground_field 90 exists for the entire lifetime of the new FiniteField. 91 92 \see DeleteFiniteField 93 */ 94 EpidStatus NewFiniteFieldViaBinomalExtension(FiniteField const* ground_field, 95 FfElement const* ground_element, 96 int degree, FiniteField** ff); 97 98 /// Creates a new finite field using polynomial extension. 99 /*! 100 Allocates memory and creates a finite field using polynomial extension. 101 102 Use DeleteFiniteField() to free memory. 103 104 \note Only needed for Intel(R) EPID 1.1 verification. 105 106 \param[in] ground_field 107 The ground field. 108 \param[in] irr_polynomial 109 Array with coefficients of the irreducible polynomial. 110 Number of elements must be equal to the degree of the extension. 111 \param[in] degree 112 The degree of the extension. 113 \param[out] ff 114 The newly constructed finite field. 115 116 \returns ::EpidStatus 117 118 \attention It is the responsibility of the caller to ensure that ground_field 119 exists for the entire lifetime of the new FiniteField. 120 121 \see DeleteFiniteField 122 */ 123 EpidStatus NewFiniteFieldViaPolynomialExtension(FiniteField const* ground_field, 124 BigNumStr const* irr_polynomial, 125 int degree, FiniteField** ff); 126 127 /// Frees a previously allocated FiniteField. 128 /*! 129 Frees memory pointed to by finite field. Nulls the pointer. 130 131 \param[in] ff 132 The Finite field. Can be NULL. 133 134 \see NewFiniteField 135 */ 136 void DeleteFiniteField(FiniteField** ff); 137 138 /// Creates a new finite field element. 139 /*! 140 Allocates memory and creates a new finite field 141 element. 142 143 Use DeleteFfElement() to free memory. 144 145 \param[in] ff 146 The finite field. 147 \param[out] new_ff_elem 148 The Newly constructed finite field element. 149 150 \returns ::EpidStatus 151 152 \attention It is the responsibility of the caller to ensure that ff 153 exists for the entire lifetime of the new FfElement. 154 155 \see NewFiniteField 156 \see DeleteFfElement 157 */ 158 EpidStatus NewFfElement(FiniteField const* ff, FfElement** new_ff_elem); 159 160 /// Frees a previously allocated FfElement. 161 /*! 162 Frees memory pointed to by ff_elem. Nulls the pointer. 163 164 \param[in] ff_elem 165 The finite field element. Can be NULL. 166 167 \see NewFfElement 168 */ 169 void DeleteFfElement(FfElement** ff_elem); 170 171 /// Deserializes a FfElement from a string. 172 /*! 173 \param[in] ff 174 The finite field. 175 \param[in] ff_elem_str 176 The serialized value. 177 \param[in] strlen 178 The size of ff_elem_str in bytes. 179 \param[out] ff_elem 180 The target FfElement. 181 182 \returns ::EpidStatus 183 184 \see NewFfElement 185 \see WriteFfElement 186 */ 187 EpidStatus ReadFfElement(FiniteField* ff, ConstOctStr ff_elem_str, 188 size_t strlen, FfElement* ff_elem); 189 190 /// Initializes an existing FfElement from a BigNum. 191 /*! 192 \param[in] ff 193 The finite field. Must be a Prime Field. 194 \param[in] bn 195 The value to read. 196 \param[out] ff_elem 197 The target FfElement. 198 199 \returns ::EpidStatus 200 201 \see NewFfElement 202 \see WriteFfElement 203 */ 204 EpidStatus InitFfElementFromBn(FiniteField* ff, BigNum* bn, FfElement* ff_elem); 205 206 /// Serializes a finite field element to a string. 207 /*! 208 \param[in] ff 209 The finite field. 210 \param[in] ff_elem 211 The FfElement to be serialized. 212 \param[out] ff_elem_str 213 The target string. 214 \param[in] strlen 215 The size of ff_elem_str in bytes. 216 217 \returns ::EpidStatus 218 219 \see NewFfElement 220 \see FpElemStr 221 \see FqElemStr 222 \see GtElemStr 223 */ 224 EpidStatus WriteFfElement(FiniteField* ff, FfElement const* ff_elem, 225 OctStr ff_elem_str, size_t strlen); 226 227 /// Calculates the additive inverse of a finite field element. 228 /*! 229 \param[in] ff 230 The finite field. 231 \param[in] a 232 The element. 233 \param[out] r 234 The inverted element. 235 236 \returns ::EpidStatus 237 238 \see NewFiniteField 239 \see NewFfElement 240 */ 241 EpidStatus FfNeg(FiniteField* ff, FfElement const* a, FfElement* r); 242 243 /// Calculates the multiplicative inverse of a finite field element. 244 /*! 245 \param[in] ff 246 The finite field. 247 \param[in] a 248 The element. 249 \param[out] r 250 The inverted element. 251 252 \returns ::EpidStatus 253 254 \see NewFiniteField 255 \see NewFfElement 256 */ 257 EpidStatus FfInv(FiniteField* ff, FfElement const* a, FfElement* r); 258 259 /// Adds two finite field elements. 260 /*! 261 \param[in] ff 262 The finite field. 263 \param[out] a 264 The first operand to be added. 265 \param[out] b 266 The second operand to be added. 267 \param[out] r 268 The result of adding a and b. 269 270 \returns ::EpidStatus 271 */ 272 EpidStatus FfAdd(FiniteField* ff, FfElement const* a, FfElement const* b, 273 FfElement* r); 274 275 /// Subtracts two finite field elements. 276 /*! 277 278 \note Only needed for Intel(R) EPID 1.1 verification. 279 280 \param[in] ff 281 The finite field. 282 \param[out] a 283 The first operand to use in subtraction. 284 \param[out] b 285 The second operand to use in subtraction. 286 \param[out] r 287 The result of subtracting a and b. 288 289 \returns ::EpidStatus 290 */ 291 EpidStatus FfSub(FiniteField* ff, FfElement const* a, FfElement const* b, 292 FfElement* r); 293 294 /// Multiplies two finite field elements. 295 /*! 296 \param[in] ff 297 The finite field. 298 \param[out] a 299 The first operand to be multplied. 300 \param[out] b 301 The second operand to be multiplied. If ff is an extension field of a 302 field F then this parameter may be an element of either ff or F. 303 \param[out] r 304 The result of multiplying a and b. 305 306 \returns ::EpidStatus 307 308 \see NewFiniteField 309 \see NewFfElement 310 */ 311 EpidStatus FfMul(FiniteField* ff, FfElement const* a, FfElement const* b, 312 FfElement* r); 313 314 /// Checks if given finite field element is the additive identity (zero). 315 /*! 316 \param[in] ff 317 The finite field. 318 \param[out] a 319 The element. 320 \param[out] is_zero 321 The result of the check. 322 323 \returns ::EpidStatus 324 325 \see NewFiniteField 326 \see NewFfElement 327 */ 328 EpidStatus FfIsZero(FiniteField* ff, FfElement const* a, bool* is_zero); 329 330 /// Raises an element of a finite field to a power. 331 /*! 332 \param[in] ff 333 The finite field in which to perform the operation 334 \param[in] a 335 The base. 336 \param[in] b 337 The power. 338 \param[out] r 339 The result of raising a to the power b. 340 341 \returns ::EpidStatus 342 343 \see NewFiniteField 344 \see NewFfElement 345 */ 346 EpidStatus FfExp(FiniteField* ff, FfElement const* a, BigNum const* b, 347 FfElement* r); 348 349 /// Multi-exponentiates finite field elements. 350 /*! 351 Calculates FfExp(p[0],b[0]) * ... * FfExp(p[m-1],b[m-1]) for m > 1 352 353 \param[in] ff 354 The finite field in which to perform the operation 355 \param[in] a 356 The bases. 357 \param[in] b 358 The powers. 359 \param[in] m 360 Number of entries in a and b. 361 \param[out] r 362 The result of raising each a to the corresponding power b and multiplying 363 the results. 364 365 \returns ::EpidStatus 366 367 \see NewFiniteField 368 \see NewFfElement 369 */ 370 EpidStatus FfMultiExp(FiniteField* ff, FfElement const** a, BigNumStr const** b, 371 size_t m, FfElement* r); 372 373 /// Multi-exponentiates finite field elements. 374 /*! 375 Calculates FfExp(p[0],b[0]) * ... * FfExp(p[m-1],b[m-1]) for m > 1 376 377 \param[in] ff 378 The finite field in which to perform the operation 379 \param[in] a 380 The bases. 381 \param[in] b 382 The powers. 383 \param[in] m 384 Number of entries in a and b. 385 \param[out] r 386 The result of raising each a to the corresponding power b and multiplying 387 the results. 388 389 \returns ::EpidStatus 390 391 \see NewFiniteField 392 \see NewFfElement 393 */ 394 EpidStatus FfMultiExpBn(FiniteField* ff, FfElement const** a, BigNum const** b, 395 size_t m, FfElement* r); 396 397 /// Software side-channel mitigated implementation of FfMultiExp. 398 /*! 399 Calculates FfExp(p[0],b[0]) * ... * FfExp(p[m-1],b[m-1]) for m > 1 400 401 \attention 402 The reference implementation of FfSscmMultiExp calls FfMultiExp 403 directly because the implementation of FfMultiExp is already side channel 404 mitigated. Implementers providing their own versions of this function are 405 responsible for ensuring that FfSscmMultiExp is side channel mitigated per 406 section 8 of the Intel(R) EPID 2.0 spec. 407 408 \param[in] ff 409 The finite field in which to perform the operation. 410 \param[in] a 411 The bases. 412 \param[in] b 413 The powers. 414 \param[in] m 415 Number of entries in a and b. 416 \param[out] r 417 The result of raising each a to the corresponding power b and multiplying 418 the results. 419 420 \returns ::EpidStatus 421 422 \see NewFiniteField 423 \see NewFfElement 424 */ 425 426 EpidStatus FfSscmMultiExp(FiniteField* ff, FfElement const** a, 427 BigNumStr const** b, size_t m, FfElement* r); 428 429 /// Checks if two finite field elements are equal. 430 /*! 431 \param[in] ff 432 The finite field. 433 \param[in] a 434 An element to check. 435 \param[in] b 436 Another element to check. 437 \param[out] is_equal 438 The result of the check. 439 440 \returns ::EpidStatus 441 442 \see NewEcGroup 443 \see NewEcPoint 444 */ 445 EpidStatus FfIsEqual(FiniteField* ff, FfElement const* a, FfElement const* b, 446 bool* is_equal); 447 448 /// Hashes an arbitrary message to an element in a finite field. 449 /*! 450 \param[in] ff 451 The finite field. 452 \param[in] msg 453 The message. 454 \param[in] msg_len 455 The size of msg in bytes. 456 \param[in] hash_alg 457 The hash algorithm. 458 \param[out] r 459 The hashed value. 460 461 \returns ::EpidStatus 462 463 \see NewFiniteField 464 \see NewFfElement 465 */ 466 EpidStatus FfHash(FiniteField* ff, ConstOctStr msg, size_t msg_len, 467 HashAlg hash_alg, FfElement* r); 468 469 /// Generate random finite field element. 470 /*! 471 \param[in] ff 472 The finite field associated with the random finite field element. 473 \param[in] low_bound 474 Lower bound of the random finite field to be generated. 475 \param[in] rnd_func 476 Random number generator. 477 \param[in] rnd_param 478 Pass through context data for rnd_func. 479 \param[in,out] r 480 The random finite field element. 481 482 \returns ::EpidStatus 483 484 \retval ::kEpidRandMaxIterErr the function should be called again with 485 different random data. 486 487 \see NewFfElement 488 \see BitSupplier 489 */ 490 EpidStatus FfGetRandom(FiniteField* ff, BigNumStr const* low_bound, 491 BitSupplier rnd_func, void* rnd_param, FfElement* r); 492 493 /// Finds a square root of a finite field element. 494 /*! 495 This function calculates the square root by the method of false position. 496 497 \param[in] ff 498 The finite field in which to perform the operation 499 \param[in] a 500 The bases. 501 \param[out] r 502 The result of raising each a to the corresponding power b and multiplying 503 the results. 504 505 \retval kEpidMathQuadraticNonResidueError No square root could be found. 506 \returns ::EpidStatus 507 508 \see NewFiniteField 509 \see NewFfElement 510 */ 511 EpidStatus FfSqrt(FiniteField* ff, FfElement const* a, FfElement* r); 512 513 /*! 514 @} 515 */ 516 517 #endif // EPID_COMMON_MATH_FINITEFIELD_H_ 518