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