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