Arduino Cryptography Library
BigNumberUtil.cpp
1 /*
2  * Copyright (C) 2015 Southern Storm Software, Pty Ltd.
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included
12  * in all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20  * DEALINGS IN THE SOFTWARE.
21  */
22 
23 #include "BigNumberUtil.h"
24 #include "utility/EndianUtil.h"
25 #include "utility/LimbUtil.h"
26 #include <string.h>
27 
55 void BigNumberUtil::unpackLE(limb_t *limbs, size_t count,
56  const uint8_t *bytes, size_t len)
57 {
58 #if BIGNUMBER_LIMB_8BIT
59  if (len < count) {
60  memcpy(limbs, bytes, len);
61  memset(limbs + len, 0, count - len);
62  } else {
63  memcpy(limbs, bytes, count);
64  }
65 #elif CRYPTO_LITTLE_ENDIAN
66  count *= sizeof(limb_t);
67  if (len < count) {
68  memcpy(limbs, bytes, len);
69  memset(((uint8_t *)limbs) + len, 0, count - len);
70  } else {
71  memcpy(limbs, bytes, count);
72  }
73 #elif BIGNUMBER_LIMB_16BIT
74  while (count > 0 && len >= 2) {
75  *limbs++ = ((limb_t)(bytes[0])) |
76  (((limb_t)(bytes[1])) << 8);
77  bytes += 2;
78  --count;
79  len -= 2;
80  }
81  if (count > 0 && len == 1) {
82  *limbs++ = ((limb_t)(bytes[0]));
83  --count;
84  }
85  while (count > 0) {
86  *limbs++ = 0;
87  --count;
88  }
89 #elif BIGNUMBER_LIMB_32BIT
90  while (count > 0 && len >= 4) {
91  *limbs++ = ((limb_t)(bytes[0])) |
92  (((limb_t)(bytes[1])) << 8) |
93  (((limb_t)(bytes[2])) << 16) |
94  (((limb_t)(bytes[3])) << 24);
95  bytes += 4;
96  --count;
97  len -= 4;
98  }
99  if (count > 0 && len > 0) {
100  if (len == 3) {
101  *limbs++ = ((limb_t)(bytes[0])) |
102  (((limb_t)(bytes[1])) << 8) |
103  (((limb_t)(bytes[2])) << 16);
104  } else if (len == 2) {
105  *limbs++ = ((limb_t)(bytes[0])) |
106  (((limb_t)(bytes[1])) << 8);
107  } else {
108  *limbs++ = ((limb_t)(bytes[0]));
109  }
110  --count;
111  }
112  while (count > 0) {
113  *limbs++ = 0;
114  --count;
115  }
116 #elif BIGNUMBER_LIMB_64BIT
117  while (count > 0 && len >= 8) {
118  *limbs++ = ((limb_t)(bytes[0])) |
119  (((limb_t)(bytes[1])) << 8) |
120  (((limb_t)(bytes[2])) << 16) |
121  (((limb_t)(bytes[3])) << 24) |
122  (((limb_t)(bytes[4])) << 32) |
123  (((limb_t)(bytes[5])) << 40) |
124  (((limb_t)(bytes[6])) << 48) |
125  (((limb_t)(bytes[7])) << 56);
126  bytes += 8;
127  --count;
128  len -= 8;
129  }
130  if (count > 0 && len > 0) {
131  limb_t word = 0;
132  uint8_t shift = 0;
133  while (len > 0 && shift < 64) {
134  word |= (((limb_t)(*bytes++)) << shift);
135  shift += 8;
136  --len;
137  }
138  *limbs++ = word;
139  --count;
140  }
141  while (count > 0) {
142  *limbs++ = 0;
143  --count;
144  }
145 #endif
146 }
147 
163 void BigNumberUtil::unpackBE(limb_t *limbs, size_t count,
164  const uint8_t *bytes, size_t len)
165 {
166 #if BIGNUMBER_LIMB_8BIT
167  while (count > 0 && len > 0) {
168  --count;
169  --len;
170  *limbs++ = bytes[len];
171  }
172  memset(limbs, 0, count);
173 #elif BIGNUMBER_LIMB_16BIT
174  bytes += len;
175  while (count > 0 && len >= 2) {
176  --count;
177  bytes -= 2;
178  len -= 2;
179  *limbs++ = ((limb_t)(bytes[1])) |
180  (((limb_t)(bytes[0])) << 8);
181  }
182  if (count > 0 && len == 1) {
183  --count;
184  --bytes;
185  *limbs++ = (limb_t)(bytes[0]);
186  }
187  memset(limbs, 0, count * sizeof(limb_t));
188 #elif BIGNUMBER_LIMB_32BIT
189  bytes += len;
190  while (count > 0 && len >= 4) {
191  --count;
192  bytes -= 4;
193  len -= 4;
194  *limbs++ = ((limb_t)(bytes[3])) |
195  (((limb_t)(bytes[2])) << 8) |
196  (((limb_t)(bytes[1])) << 16) |
197  (((limb_t)(bytes[0])) << 24);
198  }
199  if (count > 0) {
200  if (len == 3) {
201  --count;
202  bytes -= 3;
203  *limbs++ = ((limb_t)(bytes[2])) |
204  (((limb_t)(bytes[1])) << 8) |
205  (((limb_t)(bytes[0])) << 16);
206  } else if (len == 2) {
207  --count;
208  bytes -= 2;
209  *limbs++ = ((limb_t)(bytes[1])) |
210  (((limb_t)(bytes[0])) << 8);
211  } else if (len == 1) {
212  --count;
213  --bytes;
214  *limbs++ = (limb_t)(bytes[0]);
215  }
216  }
217  memset(limbs, 0, count * sizeof(limb_t));
218 #elif BIGNUMBER_LIMB_64BIT
219  bytes += len;
220  while (count > 0 && len >= 8) {
221  --count;
222  bytes -= 8;
223  len -= 8;
224  *limbs++ = ((limb_t)(bytes[7])) |
225  (((limb_t)(bytes[6])) << 8) |
226  (((limb_t)(bytes[5])) << 16) |
227  (((limb_t)(bytes[4])) << 24) |
228  (((limb_t)(bytes[3])) << 32) |
229  (((limb_t)(bytes[2])) << 40) |
230  (((limb_t)(bytes[1])) << 48) |
231  (((limb_t)(bytes[0])) << 56);
232  }
233  if (count > 0 && len > 0) {
234  limb_t word = 0;
235  uint8_t shift = 0;
236  while (len > 0 && shift < 64) {
237  word |= (((limb_t)(*(--bytes))) << shift);
238  shift += 8;
239  --len;
240  }
241  *limbs++ = word;
242  --count;
243  }
244  memset(limbs, 0, count * sizeof(limb_t));
245 #endif
246 }
247 
264 void BigNumberUtil::packLE(uint8_t *bytes, size_t len,
265  const limb_t *limbs, size_t count)
266 {
267 #if BIGNUMBER_LIMB_8BIT
268  if (len <= count) {
269  memcpy(bytes, limbs, len);
270  } else {
271  memcpy(bytes, limbs, count);
272  memset(bytes + count, 0, len - count);
273  }
274 #elif CRYPTO_LITTLE_ENDIAN
275  count *= sizeof(limb_t);
276  if (len <= count) {
277  memcpy(bytes, limbs, len);
278  } else {
279  memcpy(bytes, limbs, count);
280  memset(bytes + count, 0, len - count);
281  }
282 #elif BIGNUMBER_LIMB_16BIT
283  limb_t word;
284  while (count > 0 && len >= 2) {
285  word = *limbs++;
286  bytes[0] = (uint8_t)word;
287  bytes[1] = (uint8_t)(word >> 8);
288  --count;
289  len -= 2;
290  bytes += 2;
291  }
292  if (count > 0 && len == 1) {
293  bytes[0] = (uint8_t)(*limbs);
294  --len;
295  ++bytes;
296  }
297  memset(bytes, 0, len);
298 #elif BIGNUMBER_LIMB_32BIT
299  limb_t word;
300  while (count > 0 && len >= 4) {
301  word = *limbs++;
302  bytes[0] = (uint8_t)word;
303  bytes[1] = (uint8_t)(word >> 8);
304  bytes[2] = (uint8_t)(word >> 16);
305  bytes[3] = (uint8_t)(word >> 24);
306  --count;
307  len -= 4;
308  bytes += 4;
309  }
310  if (count > 0) {
311  if (len == 3) {
312  word = *limbs;
313  bytes[0] = (uint8_t)word;
314  bytes[1] = (uint8_t)(word >> 8);
315  bytes[2] = (uint8_t)(word >> 16);
316  len -= 3;
317  bytes += 3;
318  } else if (len == 2) {
319  word = *limbs;
320  bytes[0] = (uint8_t)word;
321  bytes[1] = (uint8_t)(word >> 8);
322  len -= 2;
323  bytes += 2;
324  } else if (len == 1) {
325  bytes[0] = (uint8_t)(*limbs);
326  --len;
327  ++bytes;
328  }
329  }
330  memset(bytes, 0, len);
331 #elif BIGNUMBER_LIMB_64BIT
332  limb_t word;
333  while (count > 0 && len >= 8) {
334  word = *limbs++;
335  bytes[0] = (uint8_t)word;
336  bytes[1] = (uint8_t)(word >> 8);
337  bytes[2] = (uint8_t)(word >> 16);
338  bytes[3] = (uint8_t)(word >> 24);
339  bytes[4] = (uint8_t)(word >> 32);
340  bytes[5] = (uint8_t)(word >> 40);
341  bytes[6] = (uint8_t)(word >> 48);
342  bytes[7] = (uint8_t)(word >> 56);
343  --count;
344  len -= 8;
345  bytes += 8;
346  }
347  if (count > 0) {
348  word = *limbs;
349  while (len > 0) {
350  *bytes++ = (uint8_t)word;
351  word >>= 8;
352  --len;
353  }
354  }
355  memset(bytes, 0, len);
356 #endif
357 }
358 
375 void BigNumberUtil::packBE(uint8_t *bytes, size_t len,
376  const limb_t *limbs, size_t count)
377 {
378 #if BIGNUMBER_LIMB_8BIT
379  if (len > count) {
380  size_t size = len - count;
381  memset(bytes, 0, size);
382  len -= size;
383  bytes += size;
384  } else if (len < count) {
385  count = len;
386  }
387  limbs += count;
388  while (count > 0) {
389  --count;
390  *bytes++ = *(--limbs);
391  }
392 #elif BIGNUMBER_LIMB_16BIT
393  size_t countBytes = count * sizeof(limb_t);
394  limb_t word;
395  if (len >= countBytes) {
396  size_t size = len - countBytes;
397  memset(bytes, 0, size);
398  len -= size;
399  bytes += size;
400  limbs += count;
401  } else {
402  count = len / sizeof(limb_t);
403  limbs += count;
404  if ((len & 1) != 0)
405  *bytes++ = (uint8_t)(*limbs);
406  }
407  while (count > 0) {
408  --count;
409  word = *(--limbs);
410  *bytes++ = (uint8_t)(word >> 8);
411  *bytes++ = (uint8_t)word;
412  }
413 #elif BIGNUMBER_LIMB_32BIT
414  size_t countBytes = count * sizeof(limb_t);
415  limb_t word;
416  if (len >= countBytes) {
417  size_t size = len - countBytes;
418  memset(bytes, 0, size);
419  len -= size;
420  bytes += size;
421  limbs += count;
422  } else {
423  count = len / sizeof(limb_t);
424  limbs += count;
425  if ((len & 3) == 3) {
426  word = *limbs;
427  *bytes++ = (uint8_t)(word >> 16);
428  *bytes++ = (uint8_t)(word >> 8);
429  *bytes++ = (uint8_t)word;
430  } else if ((len & 3) == 2) {
431  word = *limbs;
432  *bytes++ = (uint8_t)(word >> 8);
433  *bytes++ = (uint8_t)word;
434  } else if ((len & 3) == 1) {
435  *bytes++ = (uint8_t)(*limbs);
436  }
437  }
438  while (count > 0) {
439  --count;
440  word = *(--limbs);
441  *bytes++ = (uint8_t)(word >> 24);
442  *bytes++ = (uint8_t)(word >> 16);
443  *bytes++ = (uint8_t)(word >> 8);
444  *bytes++ = (uint8_t)word;
445  }
446 #elif BIGNUMBER_LIMB_64BIT
447  size_t countBytes = count * sizeof(limb_t);
448  limb_t word;
449  if (len >= countBytes) {
450  size_t size = len - countBytes;
451  memset(bytes, 0, size);
452  len -= size;
453  bytes += size;
454  limbs += count;
455  } else {
456  count = len / sizeof(limb_t);
457  limbs += count;
458  uint8_t size = len & 7;
459  uint8_t shift = size * 8;
460  word = *limbs;
461  while (size > 0) {
462  shift -= 8;
463  *bytes++ = (uint8_t)(word >> shift);
464  --size;
465  }
466  }
467  while (count > 0) {
468  --count;
469  word = *(--limbs);
470  *bytes++ = (uint8_t)(word >> 56);
471  *bytes++ = (uint8_t)(word >> 48);
472  *bytes++ = (uint8_t)(word >> 40);
473  *bytes++ = (uint8_t)(word >> 32);
474  *bytes++ = (uint8_t)(word >> 24);
475  *bytes++ = (uint8_t)(word >> 16);
476  *bytes++ = (uint8_t)(word >> 8);
477  *bytes++ = (uint8_t)word;
478  }
479 #endif
480 }
481 
495 limb_t BigNumberUtil::add(limb_t *result, const limb_t *x,
496  const limb_t *y, size_t size)
497 {
498  dlimb_t carry = 0;
499  while (size > 0) {
500  carry += *x++;
501  carry += *y++;
502  *result++ = (limb_t)carry;
503  carry >>= LIMB_BITS;
504  --size;
505  }
506  return (limb_t)carry;
507 }
508 
522 limb_t BigNumberUtil::sub(limb_t *result, const limb_t *x,
523  const limb_t *y, size_t size)
524 {
525  dlimb_t borrow = 0;
526  while (size > 0) {
527  borrow = ((dlimb_t)(*x++)) - (*y++) - ((borrow >> LIMB_BITS) & 0x01);
528  *result++ = (limb_t)borrow;
529  --size;
530  }
531  return ((limb_t)(borrow >> LIMB_BITS)) & 0x01;
532 }
533 
546 void BigNumberUtil::mul(limb_t *result, const limb_t *x, size_t xcount,
547  const limb_t *y, size_t ycount)
548 {
549  size_t i, j;
550  dlimb_t carry;
551  limb_t word;
552  const limb_t *xx;
553  limb_t *rr;
554 
555  // Multiply the lowest limb of y by x.
556  carry = 0;
557  word = y[0];
558  xx = x;
559  rr = result;
560  for (i = 0; i < xcount; ++i) {
561  carry += ((dlimb_t)(*xx++)) * word;
562  *rr++ = (limb_t)carry;
563  carry >>= LIMB_BITS;
564  }
565  *rr = (limb_t)carry;
566 
567  // Multiply and add the remaining limbs of y by x.
568  for (i = 1; i < ycount; ++i) {
569  word = y[i];
570  carry = 0;
571  xx = x;
572  rr = result + i;
573  for (j = 0; j < xcount; ++j) {
574  carry += ((dlimb_t)(*xx++)) * word;
575  carry += *rr;
576  *rr++ = (limb_t)carry;
577  carry >>= LIMB_BITS;
578  }
579  *rr = (limb_t)carry;
580  }
581 }
582 
598 void BigNumberUtil::reduceQuick(limb_t *result, const limb_t *x,
599  const limb_t *y, size_t size)
600 {
601  // Subtract "y" from "x" and turn the borrow into an AND mask.
602  limb_t mask = sub(result, x, y, size);
603  mask = (~mask) + 1;
604 
605  // Add "y" back to the result if the mask is non-zero.
606  dlimb_t carry = 0;
607  while (size > 0) {
608  carry += *result;
609  carry += (*y++ & mask);
610  *result++ = (limb_t)carry;
611  carry >>= LIMB_BITS;
612  --size;
613  }
614 }
615 
628 limb_t BigNumberUtil::add_P(limb_t *result, const limb_t *x,
629  const limb_t *y, size_t size)
630 {
631  dlimb_t carry = 0;
632  while (size > 0) {
633  carry += *x++;
634  carry += pgm_read_limb(y++);
635  *result++ = (limb_t)carry;
636  carry >>= LIMB_BITS;
637  --size;
638  }
639  return (limb_t)carry;
640 }
641 
655 limb_t BigNumberUtil::sub_P(limb_t *result, const limb_t *x,
656  const limb_t *y, size_t size)
657 {
658  dlimb_t borrow = 0;
659  while (size > 0) {
660  borrow = ((dlimb_t)(*x++)) - pgm_read_limb(y++) - ((borrow >> LIMB_BITS) & 0x01);
661  *result++ = (limb_t)borrow;
662  --size;
663  }
664  return ((limb_t)(borrow >> LIMB_BITS)) & 0x01;
665 }
666 
680 void BigNumberUtil::mul_P(limb_t *result, const limb_t *x, size_t xcount,
681  const limb_t *y, size_t ycount)
682 {
683  size_t i, j;
684  dlimb_t carry;
685  limb_t word;
686  const limb_t *xx;
687  limb_t *rr;
688 
689  // Multiply the lowest limb of y by x.
690  carry = 0;
691  word = pgm_read_limb(&(y[0]));
692  xx = x;
693  rr = result;
694  for (i = 0; i < xcount; ++i) {
695  carry += ((dlimb_t)(*xx++)) * word;
696  *rr++ = (limb_t)carry;
697  carry >>= LIMB_BITS;
698  }
699  *rr = (limb_t)carry;
700 
701  // Multiply and add the remaining limb of y by x.
702  for (i = 1; i < ycount; ++i) {
703  word = pgm_read_limb(&(y[i]));
704  carry = 0;
705  xx = x;
706  rr = result + i;
707  for (j = 0; j < xcount; ++j) {
708  carry += ((dlimb_t)(*xx++)) * word;
709  carry += *rr;
710  *rr++ = (limb_t)carry;
711  carry >>= LIMB_BITS;
712  }
713  *rr = (limb_t)carry;
714  }
715 }
716 
734 void BigNumberUtil::reduceQuick_P(limb_t *result, const limb_t *x,
735  const limb_t *y, size_t size)
736 {
737  // Subtract "y" from "x" and turn the borrow into an AND mask.
738  limb_t mask = sub_P(result, x, y, size);
739  mask = (~mask) + 1;
740 
741  // Add "y" back to the result if the mask is non-zero.
742  dlimb_t carry = 0;
743  while (size > 0) {
744  carry += *result;
745  carry += (pgm_read_limb(y++) & mask);
746  *result++ = (limb_t)carry;
747  carry >>= LIMB_BITS;
748  --size;
749  }
750 }
751 
761 limb_t BigNumberUtil::isZero(const limb_t *x, size_t size)
762 {
763  limb_t word = 0;
764  while (size > 0) {
765  word |= *x++;
766  --size;
767  }
768  return (limb_t)(((((dlimb_t)1) << LIMB_BITS) - word) >> LIMB_BITS);
769 }
BigNumberUtil::reduceQuick_P
static void reduceQuick_P(limb_t *result, const limb_t *x, const limb_t *y, size_t size)
Reduces x modulo y using subtraction where y is in program memory.
Definition: BigNumberUtil.cpp:734
BigNumberUtil::mul
static void mul(limb_t *result, const limb_t *x, size_t xcount, const limb_t *y, size_t ycount)
Multiplies two big numbers.
Definition: BigNumberUtil.cpp:546
BigNumberUtil::unpackLE
static void unpackLE(limb_t *limbs, size_t count, const uint8_t *bytes, size_t len)
Unpacks the little-endian byte representation of a big number into a limb array.
Definition: BigNumberUtil.cpp:55
BigNumberUtil::reduceQuick
static void reduceQuick(limb_t *result, const limb_t *x, const limb_t *y, size_t size)
Reduces x modulo y using subtraction.
Definition: BigNumberUtil.cpp:598
BigNumberUtil::unpackBE
static void unpackBE(limb_t *limbs, size_t count, const uint8_t *bytes, size_t len)
Unpacks the big-endian byte representation of a big number into a limb array.
Definition: BigNumberUtil.cpp:163
BigNumberUtil::sub
static limb_t sub(limb_t *result, const limb_t *x, const limb_t *y, size_t size)
Subtracts one big number from another.
Definition: BigNumberUtil.cpp:522
BigNumberUtil::packLE
static void packLE(uint8_t *bytes, size_t len, const limb_t *limbs, size_t count)
Packs the little-endian byte representation of a big number into a byte array.
Definition: BigNumberUtil.cpp:264
BigNumberUtil::add
static limb_t add(limb_t *result, const limb_t *x, const limb_t *y, size_t size)
Adds two big numbers.
Definition: BigNumberUtil.cpp:495
BigNumberUtil::mul_P
static void mul_P(limb_t *result, const limb_t *x, size_t xcount, const limb_t *y, size_t ycount)
Multiplies two big numbers where one is in program memory.
Definition: BigNumberUtil.cpp:680
BigNumberUtil::add_P
static limb_t add_P(limb_t *result, const limb_t *x, const limb_t *y, size_t size)
Adds two big numbers where one of them is in program memory.
Definition: BigNumberUtil.cpp:628
BigNumberUtil::isZero
static limb_t isZero(const limb_t *x, size_t size)
Determine if a big number is zero.
Definition: BigNumberUtil.cpp:761
BigNumberUtil::sub_P
static limb_t sub_P(limb_t *result, const limb_t *x, const limb_t *y, size_t size)
Subtracts one big number from another where one is in program memory.
Definition: BigNumberUtil.cpp:655
BigNumberUtil::packBE
static void packBE(uint8_t *bytes, size_t len, const limb_t *limbs, size_t count)
Packs the big-endian byte representation of a big number into a byte array.
Definition: BigNumberUtil.cpp:375
Generated on Sat Apr 1 2023 09:42:58 for Arduino Cryptography Library by doxygen 1.9.1