Home | History | Annotate | Download | only in src 
      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 
     37 int FqInField(FqElem const* in) { return (VliCmp(&in->limbs, &epid20_q) < 0); }
     38 
     39 void FqAdd(FqElem* result, FqElem const* left, FqElem const* right) {
     40   VliModAdd(&result->limbs, &left->limbs, &right->limbs, &epid20_q);
     41 }
     42 
     43 void FqSub(FqElem* result, FqElem const* left, FqElem const* right) {
     44   VliModSub(&result->limbs, &left->limbs, &right->limbs, &epid20_q);
     45 }
     46 
     47 void FqMul(FqElem* result, FqElem const* left, FqElem const* right) {
     48   VliModMul(&result->limbs, &left->limbs, &right->limbs, &epid20_q);
     49 }
     50 
     51 void FqExp(FqElem* result, FqElem const* base, VeryLargeInt const* exp) {
     52   VliModExp(&result->limbs, &base->limbs, exp, &epid20_q);
     53 }
     54 
     55 void FqCp(FqElem* result, FqElem const* in) {
     56   VliSet(&result->limbs, &in->limbs);
     57 }
     58 
     59 int FqIsZero(FqElem const* value) { return VliIsZero(&value->limbs); }
     60 
     61 void FqInv(FqElem* result, FqElem const* in) {
     62   VliModInv(&result->limbs, &in->limbs, &epid20_q);
     63 }
     64 
     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 
     70 void FqSquare(FqElem* result, FqElem const* in) {
     71   VliModSquare(&result->limbs, &in->limbs, &epid20_q);
     72 }
     73 
     74 void FqClear(FqElem* result) { VliClear(&result->limbs); }
     75 
     76 void FqSet(FqElem* result, uint32_t in) {
     77   FqClear(result);
     78   *(uint32_t*)(result->limbs.word) = in;
     79 }
     80 
     81 int FqEq(FqElem const* left, FqElem const* right) {
     82   return (VliCmp(&left->limbs, &right->limbs) == 0);
     83 }
     84 
     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 
     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 
    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 
    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