Home | History | Annotate | Download | only in src 
      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 Big number implementation.
     20  */
     21 #include "epid/common/math/bignum.h"
     22 #include "epid/common/math/src/bignum-internal.h"
     23 #include "epid/common/src/memory.h"
     24 #include "ext/ipp/include/ippcp.h"
     25 
     26 EpidStatus NewBigNum(size_t data_size_bytes, BigNum** bignum) {
     27   EpidStatus result = kEpidErr;
     28   IppsBigNumState* ipp_bn_ctx = NULL;
     29   BigNum* bn = NULL;
     30   do {
     31     IppStatus sts = ippStsNoErr;
     32     unsigned int ctxsize;
     33     unsigned int wordsize =
     34         (unsigned int)((data_size_bytes + sizeof(Ipp32u) - 1) / sizeof(Ipp32u));
     35 
     36     if (!bignum) {
     37       result = kEpidBadArgErr;
     38       break;
     39     }
     40     // Determine the memory requirement for bignum context
     41     sts = ippsBigNumGetSize(wordsize, (int*)&ctxsize);
     42     if (ippStsNoErr != sts) {
     43       if (ippStsLengthErr == sts) {
     44         result = kEpidBadArgErr;
     45       } else {
     46         result = kEpidMathErr;
     47       }
     48       break;
     49     }
     50     // Allocate space for ipp bignum context
     51     ipp_bn_ctx = (IppsBigNumState*)SAFE_ALLOC(ctxsize);
     52     if (!ipp_bn_ctx) {
     53       result = kEpidMemAllocErr;
     54       break;
     55     }
     56     // Initialize ipp bignum context
     57     sts = ippsBigNumInit(wordsize, ipp_bn_ctx);
     58     if (ippStsNoErr != sts) {
     59       if (ippStsLengthErr == sts) {
     60         result = kEpidBadArgErr;
     61       } else {
     62         result = kEpidMathErr;
     63       }
     64       break;
     65     }
     66 
     67     bn = (BigNum*)SAFE_ALLOC(sizeof(BigNum));
     68     if (!bn) {
     69       result = kEpidMemAllocErr;
     70       break;
     71     }
     72 
     73     bn->ipp_bn = ipp_bn_ctx;
     74 
     75     *bignum = bn;
     76     result = kEpidNoErr;
     77   } while (0);
     78 
     79   if (kEpidNoErr != result) {
     80     SAFE_FREE(ipp_bn_ctx);
     81     SAFE_FREE(bn);
     82   }
     83   return result;
     84 }
     85 
     86 void DeleteBigNum(BigNum** bignum) {
     87   if (bignum) {
     88     if (*bignum) {
     89       SAFE_FREE((*bignum)->ipp_bn);
     90     }
     91     SAFE_FREE(*bignum);
     92   }
     93 }
     94 
     95 EpidStatus ReadBigNum(ConstOctStr bn_str, size_t strlen, BigNum* bn) {
     96   IppStatus sts;
     97   size_t i;
     98   bool is_zero = true;
     99   Ipp8u const* byte_str = (Ipp8u const*)bn_str;
    100   int ipp_strlen = (int)strlen;
    101 
    102   if (!bn || !bn_str) return kEpidBadArgErr;
    103 
    104   if (!bn->ipp_bn) return kEpidBadArgErr;
    105 
    106   if (INT_MAX < strlen || strlen <= 0) return kEpidBadArgErr;
    107 
    108   /*
    109   Some versions of ippsSetOctString_BN have bug:
    110   When called for octet string with all bits set to zero the resulted BigNumber
    111   state initialize incorrectly which leads to unpredictable behaviour
    112   if used.
    113 
    114   Workaround:
    115   Test the input string before ippsSetOctStringSet_BN() call.
    116   If length of the string is zero or it does not contain any significant
    117   bits, then set BN to zero.  Keep in mind that ippsBigNumInit() set BN
    118   value to zero.
    119   */
    120   for (i = 0; i < strlen; ++i)
    121     if (0 != byte_str[i]) {
    122       is_zero = false;
    123       break;
    124     }
    125   if (is_zero) {
    126     Ipp32u zero32 = 0;
    127     sts = ippsSet_BN(IppsBigNumPOS, 1, &zero32, bn->ipp_bn);
    128   } else {
    129     sts = ippsSetOctString_BN(bn_str, ipp_strlen, bn->ipp_bn);
    130   }
    131   if (sts != ippStsNoErr) {
    132     if (ippStsContextMatchErr == sts || ippStsSizeErr == sts ||
    133         ippStsLengthErr == sts || ippStsOutOfRangeErr == sts)
    134       return kEpidBadArgErr;
    135     else
    136       return kEpidMathErr;
    137   }
    138 
    139   return kEpidNoErr;
    140 }
    141 
    142 EpidStatus WriteBigNum(BigNum const* bn, size_t strlen, OctStr bn_str) {
    143   IppStatus sts;
    144   int ipp_strlen = (int)strlen;
    145   if (!bn || !bn_str) return kEpidBadArgErr;
    146 
    147   if (!bn->ipp_bn) return kEpidBadArgErr;
    148 
    149   sts = ippsGetOctString_BN((OctStr)bn_str, ipp_strlen, bn->ipp_bn);
    150   if (ippStsNoErr != sts) {
    151     if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
    152         ippStsLengthErr == sts)
    153       return kEpidBadArgErr;
    154     else
    155       return kEpidMathErr;
    156   }
    157 
    158   return kEpidNoErr;
    159 }
    160 
    161 /// convert octet string into "big number unsigned" representation
    162 int OctStr2Bnu(BNU bnu_ptr, ConstOctStr octstr_ptr, int octstr_len) {
    163   int bnusize = 0;
    164   ConstIppOctStr byte_str = (ConstIppOctStr)octstr_ptr;
    165   IppBNU bnu = (IppBNU)bnu_ptr;
    166   if (!bnu_ptr || !octstr_ptr) {
    167     return -1;
    168   }
    169   if (octstr_len < 4 || octstr_len % 4 != 0) return -1;
    170 
    171   *bnu = 0;
    172   /* start from the end of string */
    173   for (; octstr_len >= 4; bnusize++, octstr_len -= 4) {
    174     /* pack 4 bytes into single Ipp32u value*/
    175     *bnu++ = (byte_str[octstr_len - 4] << (8 * 3)) +
    176              (byte_str[octstr_len - 3] << (8 * 2)) +
    177              (byte_str[octstr_len - 2] << (8 * 1)) + byte_str[octstr_len - 1];
    178   }
    179   return bnusize ? bnusize : -1;
    180 }
    181 
    182 /// Get octet string size in bits
    183 size_t OctStrBitSize(ConstOctStr octstr_ptr, size_t octstr_len) {
    184   uint8_t byte;
    185   size_t bitsize = 0;
    186   ConstIppOctStr octstr = (ConstIppOctStr)octstr_ptr;
    187 
    188   // find highest non zero byte
    189   size_t i = 0;
    190   while (i < octstr_len && !octstr[i]) i++;
    191   if (i == octstr_len) return 0;
    192   byte = octstr[i];
    193 
    194   // refine bit size
    195   if (0 == byte) return 0;
    196   bitsize = (octstr_len - i) << 3;
    197   if (0 == (byte & 0xF0)) {
    198     bitsize -= 4;
    199     byte <<= 4;
    200   }
    201   if (0 == (byte & 0xC0)) {
    202     bitsize -= 2;
    203     byte <<= 2;
    204   }
    205   if (0 == (byte & 0x80)) {
    206     bitsize--;
    207   }
    208 
    209   return bitsize;
    210 }
    211 
    212 EpidStatus BigNumAdd(BigNum const* a, BigNum const* b, BigNum* r) {
    213   IppStatus sts;
    214 
    215   if (!r || !a || !b) return kEpidBadArgErr;
    216 
    217   if (!r->ipp_bn || !a->ipp_bn || !b->ipp_bn) return kEpidBadArgErr;
    218 
    219   sts = ippsAdd_BN(a->ipp_bn, b->ipp_bn, r->ipp_bn);
    220   if (ippStsNoErr != sts) {
    221     if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
    222         ippStsLengthErr == sts) {
    223       return kEpidBadArgErr;
    224     } else {
    225       return kEpidMathErr;
    226     }
    227   }
    228 
    229   return kEpidNoErr;
    230 }
    231 
    232 EpidStatus BigNumSub(BigNum const* a, BigNum const* b, BigNum* r) {
    233   IppStatus sts;
    234   Ipp32u sign = IS_ZERO;
    235   if (!r || !a || !b) return kEpidBadArgErr;
    236 
    237   if (!r->ipp_bn || !a->ipp_bn || !b->ipp_bn) return kEpidBadArgErr;
    238 
    239   sts = ippsSub_BN(a->ipp_bn, b->ipp_bn, r->ipp_bn);
    240   if (ippStsNoErr != sts) {
    241     if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
    242         ippStsLengthErr == sts) {
    243       return kEpidBadArgErr;
    244     } else {
    245       return kEpidMathErr;
    246     }
    247   }
    248   sts = ippsCmpZero_BN(r->ipp_bn, &sign);
    249   if (ippStsNoErr != sts) {
    250     return kEpidMathErr;
    251   }
    252   if (sign == LESS_THAN_ZERO) {
    253     return kEpidUnderflowErr;
    254   }
    255   return kEpidNoErr;
    256 }
    257 
    258 EpidStatus BigNumMul(BigNum const* a, BigNum const* b, BigNum* r) {
    259   IppStatus sts;
    260 
    261   if (!r || !a || !b) return kEpidBadArgErr;
    262 
    263   if (!r->ipp_bn || !a->ipp_bn || !b->ipp_bn) return kEpidBadArgErr;
    264 
    265   sts = ippsMul_BN(a->ipp_bn, b->ipp_bn, r->ipp_bn);
    266   if (ippStsNoErr != sts) {
    267     if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
    268         ippStsLengthErr == sts || ippStsOutOfRangeErr == sts) {
    269       return kEpidBadArgErr;
    270     } else {
    271       return kEpidMathErr;
    272     }
    273   }
    274 
    275   return kEpidNoErr;
    276 }
    277 
    278 EpidStatus BigNumDiv(BigNum const* a, BigNum const* b, BigNum* q, BigNum* r) {
    279   IppStatus sts;
    280 
    281   if (!a || !b || !q || !r) return kEpidBadArgErr;
    282 
    283   if (!a->ipp_bn || !b->ipp_bn || !q->ipp_bn || !r->ipp_bn)
    284     return kEpidBadArgErr;
    285 
    286   sts = ippsDiv_BN(a->ipp_bn, b->ipp_bn, q->ipp_bn, r->ipp_bn);
    287   if (ippStsNoErr != sts) {
    288     if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
    289         ippStsLengthErr == sts || ippStsOutOfRangeErr == sts ||
    290         ippStsDivByZeroErr == sts) {
    291       return kEpidBadArgErr;
    292     } else {
    293       return kEpidMathErr;
    294     }
    295   }
    296 
    297   return kEpidNoErr;
    298 }
    299 
    300 EpidStatus BigNumMod(BigNum const* a, BigNum const* b, BigNum* r) {
    301   IppStatus sts;
    302 
    303   if (!r || !a || !b) return kEpidBadArgErr;
    304 
    305   if (!r->ipp_bn || !a->ipp_bn || !b->ipp_bn) return kEpidBadArgErr;
    306 
    307   sts = ippsMod_BN(a->ipp_bn, b->ipp_bn, r->ipp_bn);
    308   if (ippStsNoErr != sts) {
    309     if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
    310         ippStsLengthErr == sts || ippStsOutOfRangeErr == sts) {
    311       return kEpidBadArgErr;
    312     } else {
    313       return kEpidMathErr;
    314     }
    315   }
    316 
    317   return kEpidNoErr;
    318 }
    319 
    320 EpidStatus BigNumIsEven(BigNum const* a, bool* is_even) {
    321   IppStatus sts = ippStsNoErr;
    322   IppsBigNumSGN sgn;
    323   int bit_size;
    324   IppBNU data;
    325   // Check required parameters
    326   if (!a || !is_even) {
    327     return kEpidBadArgErr;
    328   }
    329   if (!a->ipp_bn) {
    330     return kEpidBadArgErr;
    331   }
    332   sts = ippsRef_BN(&sgn, &bit_size, &data, a->ipp_bn);
    333   if (ippStsNoErr != sts) {
    334     return kEpidMathErr;
    335   }
    336   *is_even = !(data[0] & 1);
    337   return kEpidNoErr;
    338 }
    339 
    340 EpidStatus BigNumIsZero(BigNum const* a, bool* is_zero) {
    341   IppStatus sts = ippStsNoErr;
    342   Ipp32u sign = 0;
    343   // Check required parameters
    344   if (!a || !is_zero) {
    345     return kEpidBadArgErr;
    346   }
    347   if (!a->ipp_bn) {
    348     return kEpidBadArgErr;
    349   }
    350   sts = ippsCmpZero_BN(a->ipp_bn, &sign);
    351   if (ippStsNoErr != sts) {
    352     return kEpidMathErr;
    353   }
    354   *is_zero = (IS_ZERO == sign);
    355   return kEpidNoErr;
    356 }
    357 
    358 EpidStatus BigNumPow2N(unsigned int n, BigNum* r) {
    359   EpidStatus result = kEpidErr;
    360   Ipp8u two_str = 2;
    361   Ipp8u one_str = 1;
    362   BigNum* two = NULL;
    363   do {
    364     if (n == 0) {
    365       result = ReadBigNum(&one_str, sizeof(one_str), r);
    366       if (kEpidNoErr != result) {
    367         break;
    368       }
    369     } else {
    370       result = NewBigNum(sizeof(BigNumStr), &two);
    371       if (kEpidNoErr != result) {
    372         break;
    373       }
    374       result = ReadBigNum(&two_str, sizeof(two_str), two);
    375       if (kEpidNoErr != result) {
    376         break;
    377       }
    378       result = ReadBigNum(&two_str, sizeof(two_str), r);
    379       if (kEpidNoErr != result) {
    380         break;
    381       }
    382 
    383       while (n > 1) {
    384         result = BigNumMul(r, two, r);
    385         if (kEpidNoErr != result) {
    386           break;
    387         }
    388         n -= 1;
    389       }
    390       if (kEpidNoErr != result) {
    391         break;
    392       }
    393     }
    394     result = kEpidNoErr;
    395   } while (0);
    396   DeleteBigNum(&two);
    397   return result;
    398 }
    399