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
NewBigNum(size_t data_size_bytes,BigNum ** bignum)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
DeleteBigNum(BigNum ** bignum)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
ReadBigNum(ConstOctStr bn_str,size_t strlen,BigNum * bn)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
WriteBigNum(BigNum const * bn,size_t strlen,OctStr bn_str)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
OctStr2Bnu(BNU bnu_ptr,ConstOctStr octstr_ptr,int octstr_len)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
OctStrBitSize(ConstOctStr octstr_ptr,size_t octstr_len)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
BigNumAdd(BigNum const * a,BigNum const * b,BigNum * r)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
BigNumSub(BigNum const * a,BigNum const * b,BigNum * r)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
BigNumMul(BigNum const * a,BigNum const * b,BigNum * r)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
BigNumDiv(BigNum const * a,BigNum const * b,BigNum * q,BigNum * r)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
BigNumMod(BigNum const * a,BigNum const * b,BigNum * r)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
BigNumIsEven(BigNum const * a,bool * is_even)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
BigNumIsZero(BigNum const * a,bool * is_zero)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
BigNumPow2N(unsigned int n,BigNum * r)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