• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
Nlz32(uint32_t 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 
NewFiniteField(BigNumStr const * prime,FiniteField ** ff)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 
NewFiniteFieldViaBinomalExtension(FiniteField const * ground_field,FfElement const * ground_element,int degree,FiniteField ** ff)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 
NewFiniteFieldViaPolynomialExtension(FiniteField const * ground_field,BigNumStr const * irr_polynomial,int degree,FiniteField ** ff)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 
DeleteFiniteField(FiniteField ** ff)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 
NewFfElement(FiniteField const * ff,FfElement ** new_ff_elem)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 
DeleteFfElement(FfElement ** ff_elem)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 
IsValidFfElemOctString(ConstOctStr ff_elem_str,int strlen,FiniteField const * ff)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 
SetFfElementOctString(ConstOctStr ff_elem_str,int strlen,FfElement * ff_elem,FiniteField * ff)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 
ReadFfElement(FiniteField * ff,ConstOctStr ff_elem_str,size_t strlen,FfElement * ff_elem)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 */
GetFiniteFieldPrime(FiniteField * ff,BigNum ** bn)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 
InitFfElementFromBn(FiniteField * ff,BigNum * bn,FfElement * ff_elem)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 
WriteFfElement(FiniteField * ff,FfElement const * ff_elem,OctStr ff_elem_str,size_t strlen)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 
FfNeg(FiniteField * ff,FfElement const * a,FfElement * r)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 
FfInv(FiniteField * ff,FfElement const * a,FfElement * r)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 
FfAdd(FiniteField * ff,FfElement const * a,FfElement const * b,FfElement * r)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 
FfSub(FiniteField * ff,FfElement const * a,FfElement const * b,FfElement * r)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 
FfMul(FiniteField * ff,FfElement const * a,FfElement const * b,FfElement * r)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 
FfIsZero(FiniteField * ff,FfElement const * a,bool * is_zero)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 
FfExp(FiniteField * ff,FfElement const * a,BigNum const * b,FfElement * r)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 
FfMultiExp(FiniteField * ff,FfElement const ** p,BigNumStr const ** b,size_t m,FfElement * r)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 
FfMultiExpBn(FiniteField * ff,FfElement const ** p,BigNum const ** b,size_t m,FfElement * r)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 
FfSscmMultiExp(FiniteField * ff,FfElement const ** p,BigNumStr const ** b,size_t m,FfElement * r)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 
FfIsEqual(FiniteField * ff,FfElement const * a,FfElement const * b,bool * is_equal)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 
FfHash(FiniteField * ff,ConstOctStr msg,size_t msg_len,HashAlg hash_alg,FfElement * r)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)
FfGetRandom(FiniteField * ff,BigNumStr const * low_bound,BitSupplier rnd_func,void * rnd_param,FfElement * r)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 
FfSqrt(FiniteField * ff,FfElement const * a,FfElement * r)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, &gtp1d2);
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(&gtp1d2);
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