• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*############################################################################
2 # Copyright 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 /// Implementation of Fq math
17 /*! \file */
18 
19 #include "epid/member/tiny/math/fq.h"
20 
21 #include <limits.h>  // for CHAR_BIT
22 #include "epid/member/tiny/math/mathtypes.h"
23 #include "epid/member/tiny/math/serialize.h"
24 #include "epid/member/tiny/math/vli.h"
25 #include "epid/member/tiny/stdlib/tiny_stdlib.h"
26 
27 /// A security parameter. In this version of Intel(R) EPID SDK, slen = 128
28 #define EPID_SLEN 128
29 /// buffer size of random integer t in INT32
30 #define RAND_NUM_WORDS \
31   ((sizeof(FpElem) + EPID_SLEN / CHAR_BIT) / sizeof(uint32_t))
32 
33 static VeryLargeInt const epid20_q = {{0xAED33013, 0xD3292DDB, 0x12980A82,
34                                        0x0CDC65FB, 0xEE71A49F, 0x46E5F25E,
35                                        0xFFFCF0CD, 0xFFFFFFFF}};
36 
FqInField(FqElem const * in)37 int FqInField(FqElem const* in) { return (VliCmp(&in->limbs, &epid20_q) < 0); }
38 
FqAdd(FqElem * result,FqElem const * left,FqElem const * right)39 void FqAdd(FqElem* result, FqElem const* left, FqElem const* right) {
40   VliModAdd(&result->limbs, &left->limbs, &right->limbs, &epid20_q);
41 }
42 
FqSub(FqElem * result,FqElem const * left,FqElem const * right)43 void FqSub(FqElem* result, FqElem const* left, FqElem const* right) {
44   VliModSub(&result->limbs, &left->limbs, &right->limbs, &epid20_q);
45 }
46 
FqMul(FqElem * result,FqElem const * left,FqElem const * right)47 void FqMul(FqElem* result, FqElem const* left, FqElem const* right) {
48   VliModMul(&result->limbs, &left->limbs, &right->limbs, &epid20_q);
49 }
50 
FqExp(FqElem * result,FqElem const * base,VeryLargeInt const * exp)51 void FqExp(FqElem* result, FqElem const* base, VeryLargeInt const* exp) {
52   VliModExp(&result->limbs, &base->limbs, exp, &epid20_q);
53 }
54 
FqCp(FqElem * result,FqElem const * in)55 void FqCp(FqElem* result, FqElem const* in) {
56   VliSet(&result->limbs, &in->limbs);
57 }
58 
FqIsZero(FqElem const * value)59 int FqIsZero(FqElem const* value) { return VliIsZero(&value->limbs); }
60 
FqInv(FqElem * result,FqElem const * in)61 void FqInv(FqElem* result, FqElem const* in) {
62   VliModInv(&result->limbs, &in->limbs, &epid20_q);
63 }
64 
FqNeg(FqElem * result,FqElem const * in)65 void FqNeg(FqElem* result, FqElem const* in) {
66   VliCondSet(&result->limbs, &epid20_q, &in->limbs, VliIsZero(&in->limbs));
67   VliSub(&result->limbs, &epid20_q, &result->limbs);
68 }
69 
FqSquare(FqElem * result,FqElem const * in)70 void FqSquare(FqElem* result, FqElem const* in) {
71   VliModSquare(&result->limbs, &in->limbs, &epid20_q);
72 }
73 
FqClear(FqElem * result)74 void FqClear(FqElem* result) { VliClear(&result->limbs); }
75 
FqSet(FqElem * result,uint32_t in)76 void FqSet(FqElem* result, uint32_t in) {
77   FqClear(result);
78   *(uint32_t*)(result->limbs.word) = in;
79 }
80 
FqEq(FqElem const * left,FqElem const * right)81 int FqEq(FqElem const* left, FqElem const* right) {
82   return (VliCmp(&left->limbs, &right->limbs) == 0);
83 }
84 
FqCondSet(FqElem * result,FqElem const * true_val,FqElem const * false_val,int truth_val)85 void FqCondSet(FqElem* result, FqElem const* true_val, FqElem const* false_val,
86                int truth_val) {
87   VliCondSet(&result->limbs, &true_val->limbs, &false_val->limbs, truth_val);
88 }
89 
FqSqrt(FqElem * result,FqElem const * in)90 int FqSqrt(FqElem* result, FqElem const* in) {
91   VeryLargeInt tmp;
92   // Intel(R) EPID 2.0 parameter q meets q = 3 mod 4.
93   // Square root can be computed as in^((q+1)/4) mod q.
94   VliRShift(&tmp, &epid20_q, 2);  // tmp = (q-3)/4
95   (tmp.word[0])++;                // tmp = (q+1)/4
96   FqExp(result, in, &tmp);        // result = in^((q+1)/4) mod q
97   // validate sqrt exists
98   VliModSquare(&tmp, &result->limbs, &epid20_q);
99   return 0 == VliCmp(&tmp, &in->limbs);
100 }
101 
FqRand(FqElem * result,BitSupplier rnd_func,void * rnd_param)102 int FqRand(FqElem* result, BitSupplier rnd_func, void* rnd_param) {
103   VeryLargeIntProduct deserialized_t = {{0}};
104   uint32_t t[RAND_NUM_WORDS] = {0};
105   OctStr32 const* src = (OctStr32 const*)t;
106   int i;
107 
108   if (rnd_func(t, sizeof(FpElem) * CHAR_BIT + EPID_SLEN, rnd_param)) {
109     return 0;
110   }
111   for (i = RAND_NUM_WORDS - 1; i >= 0; i--) {
112     src = Uint32Deserialize(deserialized_t.word + i, src);
113   }
114   VliModBarrett(&result->limbs, &deserialized_t, &epid20_q);
115   return 1;
116 }
117 
FqFromHash(FqElem * result,unsigned char const * hash,size_t len)118 void FqFromHash(FqElem* result, unsigned char const* hash, size_t len) {
119   size_t i;
120   VeryLargeIntProduct vli;
121   memset(&vli, 0, sizeof(vli));
122   for (i = 0; i < len; i++) {
123     ((uint8_t*)vli.word)[len - i - 1] = hash[i];
124   }
125   VliModBarrett(&result->limbs, &vli, &epid20_q);
126 }
127