-
Notifications
You must be signed in to change notification settings - Fork 969
Expand file tree
/
Copy pathinteger.c
More file actions
5545 lines (4594 loc) · 122 KB
/
integer.c
File metadata and controls
5545 lines (4594 loc) · 122 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* integer.c
*
* Copyright (C) 2006-2026 wolfSSL Inc.
*
* This file is part of wolfSSL.
*
* wolfSSL is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* wolfSSL is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
*/
#include <wolfssl/wolfcrypt/libwolfssl_sources.h>
/*
* Based on public domain LibTomMath 0.38 by Tom St Denis, tomstdenis@iahu.ca,
* http://math.libtomcrypt.com
*/
#ifndef NO_BIG_INT
#if !defined(USE_FAST_MATH) && defined(USE_INTEGER_HEAP_MATH)
#ifndef WOLFSSL_SP_MATH
#ifdef NO_INLINE
#include <wolfssl/wolfcrypt/misc.h>
#else
#define WOLFSSL_MISC_INCLUDED
#include <wolfcrypt/src/misc.c>
#endif
#include <wolfssl/wolfcrypt/wolfmath.h>
#if defined(FREESCALE_LTC_TFM)
#include <wolfssl/wolfcrypt/port/nxp/ksdk_port.h>
#endif
#ifdef WOLFSSL_DEBUG_MATH
#include <stdio.h>
#endif
#ifdef SHOW_GEN
#ifndef NO_STDIO_FILESYSTEM
#include <stdio.h>
#endif
#endif
#if defined(WOLFSSL_HAVE_SP_RSA) || defined(WOLFSSL_HAVE_SP_DH)
#ifdef __cplusplus
extern "C" {
#endif
WOLFSSL_LOCAL int sp_ModExp_1024(mp_int* base, mp_int* exp, mp_int* mod,
mp_int* res);
WOLFSSL_LOCAL int sp_ModExp_1536(mp_int* base, mp_int* exp, mp_int* mod,
mp_int* res);
WOLFSSL_LOCAL int sp_ModExp_2048(mp_int* base, mp_int* exp, mp_int* mod,
mp_int* res);
WOLFSSL_LOCAL int sp_ModExp_3072(mp_int* base, mp_int* exp, mp_int* mod,
mp_int* res);
WOLFSSL_LOCAL int sp_ModExp_4096(mp_int* base, mp_int* exp, mp_int* mod,
mp_int* res);
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif
/* reverse an array, used for radix code */
static void
bn_reverse (unsigned char *s, int len)
{
int ix, iy;
unsigned char t;
ix = 0;
iy = len - 1;
while (ix < iy) {
t = s[ix];
s[ix] = s[iy];
s[iy] = t;
++ix;
--iy;
}
}
/* math settings check */
word32 CheckRunTimeSettings(void)
{
return CTC_SETTINGS;
}
/* handle up to 6 inits */
int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d, mp_int* e,
mp_int* f)
{
int res = MP_OKAY;
if (a) XMEMSET(a, 0, sizeof(mp_int));
if (b) XMEMSET(b, 0, sizeof(mp_int));
if (c) XMEMSET(c, 0, sizeof(mp_int));
if (d) XMEMSET(d, 0, sizeof(mp_int));
if (e) XMEMSET(e, 0, sizeof(mp_int));
if (f) XMEMSET(f, 0, sizeof(mp_int));
if (a && ((res = mp_init(a)) != MP_OKAY))
return res;
if (b && ((res = mp_init(b)) != MP_OKAY)) {
mp_clear(a);
return res;
}
if (c && ((res = mp_init(c)) != MP_OKAY)) {
mp_clear(a); mp_clear(b);
return res;
}
if (d && ((res = mp_init(d)) != MP_OKAY)) {
mp_clear(a); mp_clear(b); mp_clear(c);
return res;
}
if (e && ((res = mp_init(e)) != MP_OKAY)) {
mp_clear(a); mp_clear(b); mp_clear(c); mp_clear(d);
return res;
}
if (f && ((res = mp_init(f)) != MP_OKAY)) {
mp_clear(a); mp_clear(b); mp_clear(c); mp_clear(d); mp_clear(e);
return res;
}
return res;
}
/* init a new mp_int */
int mp_init (mp_int * a)
{
/* Safeguard against passing in a null pointer */
if (a == NULL)
return MP_VAL;
/* defer allocation until mp_grow */
a->dp = NULL;
/* set the used to zero, allocated digits to the default precision
* and sign to positive */
a->used = 0;
a->alloc = 0;
a->sign = MP_ZPOS;
#ifdef HAVE_WOLF_BIGINT
wc_bigint_init(&a->raw);
#endif
return MP_OKAY;
}
/* clear one (frees) */
void mp_clear (mp_int * a)
{
#ifdef HAVE_FIPS
mp_forcezero(a);
#else
int i;
if (a == NULL)
return;
/* only do anything if a hasn't been freed previously */
#ifndef HAVE_WOLF_BIGINT
/* When HAVE_WOLF_BIGINT then mp_free -> wc_bigint_free needs to be called
* because a->raw->buf may be allocated even when a->dp == NULL. This is the
* case for when a zero is loaded into the mp_int. */
if (a->dp != NULL)
#endif
{
/* first zero the digits */
for (i = 0; i < a->used; i++) {
a->dp[i] = 0;
}
/* free ram */
mp_free(a);
/* reset members to make debugging easier */
a->alloc = a->used = 0;
a->sign = MP_ZPOS;
}
#endif
}
void mp_free (mp_int * a)
{
/* only do anything if a hasn't been freed previously */
if (a->dp != NULL) {
/* free ram */
XFREE(a->dp, 0, DYNAMIC_TYPE_BIGINT);
a->dp = NULL;
}
#ifdef HAVE_WOLF_BIGINT
wc_bigint_free(&a->raw);
#endif
}
void mp_forcezero(mp_int * a)
{
if (a == NULL)
return;
/* only do anything if a hasn't been freed previously */
if (a->dp != NULL) {
/* force zero the used digits */
ForceZero(a->dp, a->used * sizeof(mp_digit));
#ifdef HAVE_WOLF_BIGINT
wc_bigint_zero(&a->raw);
#endif
/* free ram */
mp_free(a);
/* reset members to make debugging easier */
a->alloc = a->used = 0;
a->sign = MP_ZPOS;
}
a->sign = MP_ZPOS;
a->used = 0;
}
/* get the size for an unsigned equivalent */
int mp_unsigned_bin_size (const mp_int * a)
{
int size = mp_count_bits (a);
return (size / 8 + ((size & 7) != 0 ? 1 : 0));
}
/* returns the number of bits in an int */
int mp_count_bits (const mp_int * a)
{
int r;
mp_digit q;
/* shortcut */
if (a->used == 0) {
return 0;
}
/* get number of digits and add that */
r = (a->used - 1) * DIGIT_BIT;
/* take the last digit and count the bits in it */
q = a->dp[a->used - 1];
while (q > ((mp_digit) 0)) {
++r;
q >>= ((mp_digit) 1);
}
return r;
}
int mp_leading_bit (mp_int * a)
{
int c = mp_count_bits(a);
if (c == 0) return 0;
return (c % 8) == 0;
}
int mp_to_unsigned_bin_at_pos(int x, mp_int *t, unsigned char *b)
{
int res = 0;
while (mp_iszero(t) == MP_NO) {
#ifndef MP_8BIT
b[x++] = (unsigned char) (t->dp[0] & 255);
#else
b[x++] = (unsigned char) (t->dp[0] | ((t->dp[1] & 0x01) << 7));
#endif
if ((res = mp_div_2d (t, 8, t, NULL)) != MP_OKAY) {
return res;
}
res = x;
}
return res;
}
/* store in unsigned [big endian] format */
int mp_to_unsigned_bin (const mp_int * a, unsigned char *b)
{
int x, res;
mp_int t;
if ((res = mp_init_copy (&t, a)) != MP_OKAY) {
return res;
}
x = mp_to_unsigned_bin_at_pos(0, &t, b);
if (x < 0) {
mp_clear(&t);
return x;
}
bn_reverse (b, x);
mp_clear (&t);
return res;
}
int mp_to_unsigned_bin_len(mp_int * a, unsigned char *b, int c)
{
int i, len;
len = mp_unsigned_bin_size(a);
if (len > c) {
return MP_VAL;
}
/* pad front w/ zeros to match length */
for (i = 0; i < c - len; i++) {
b[i] = 0x00;
}
return mp_to_unsigned_bin(a, b + i);
}
/* creates "a" then copies b into it */
int mp_init_copy (mp_int * a, const mp_int * b)
{
int res;
if ((res = mp_init_size (a, b->used)) != MP_OKAY) {
return res;
}
if((res = mp_copy (b, a)) != MP_OKAY) {
mp_clear(a);
}
return res;
}
/* copy, b = a */
int mp_copy (const mp_int * a, mp_int * b)
{
int res, n;
/* Safeguard against passing in a null pointer */
if (a == NULL || b == NULL)
return MP_VAL;
/* if dst == src do nothing */
if (a == b) {
return MP_OKAY;
}
/* grow dest */
if (b->alloc < a->used || b->alloc == 0) {
if ((res = mp_grow (b, a->used)) != MP_OKAY) {
return res;
}
}
/* zero b and copy the parameters over */
{
mp_digit *tmpa, *tmpb;
/* pointer aliases */
/* source */
tmpa = a->dp;
/* destination */
tmpb = b->dp;
/* copy all the digits */
for (n = 0; n < a->used; n++) {
*tmpb++ = *tmpa++;
}
/* clear high digits */
for (; n < b->used && b->dp; n++) {
*tmpb++ = 0;
}
}
/* copy used count and sign */
b->used = a->used;
b->sign = a->sign;
return MP_OKAY;
}
/* grow as required */
int mp_grow (mp_int * a, int size)
{
mp_digit *tmp;
/* if the alloc size is smaller alloc more ram */
if ((a->alloc < size) || (size == 0) || (a->alloc == 0)) {
/* ensure there are always at least MP_PREC digits extra on top */
size += (MP_PREC * 2) - (size % MP_PREC);
/* reallocate the array a->dp
*
* We store the return in a temporary variable
* in case the operation failed we don't want
* to overwrite the dp member of a.
*/
tmp = (mp_digit *)XREALLOC (a->dp, sizeof (mp_digit) * size, NULL,
DYNAMIC_TYPE_BIGINT);
if (tmp == NULL) {
/* reallocation failed but "a" is still valid [can be freed] */
return MP_MEM;
}
/* reallocation succeeded so set a->dp */
a->dp = tmp;
/* zero excess digits */
XMEMSET(&a->dp[a->alloc], 0, sizeof (mp_digit) * (size - a->alloc));
a->alloc = size;
}
else if (a->dp == NULL) {
/* opportunistic sanity check for null a->dp with nonzero a->alloc */
return MP_VAL;
}
return MP_OKAY;
}
/* shift right by a certain bit count (store quotient in c, optional
remainder in d) */
int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d)
{
int D, res;
mp_int t;
/* if the shift count is <= 0 then we do no work */
if (b <= 0) {
res = mp_copy (a, c);
if (d != NULL) {
mp_zero (d);
}
return res;
}
if ((res = mp_init (&t)) != MP_OKAY) {
return res;
}
/* get the remainder */
if (d != NULL) {
if ((res = mp_mod_2d (a, b, &t)) != MP_OKAY) {
mp_clear (&t);
return res;
}
}
/* copy */
if ((res = mp_copy (a, c)) != MP_OKAY) {
mp_clear (&t);
return res;
}
/* shift by as many digits in the bit count */
if (b >= (int)DIGIT_BIT) {
mp_rshd (c, b / DIGIT_BIT);
}
/* shift any bit count < DIGIT_BIT */
D = (b % DIGIT_BIT);
if (D != 0) {
mp_rshb(c, D);
}
mp_clamp (c);
if (d != NULL) {
mp_exch (&t, d);
}
mp_clear (&t);
return MP_OKAY;
}
/* set to zero */
void mp_zero (mp_int * a)
{
int n;
mp_digit *tmp;
if (a == NULL)
return;
a->sign = MP_ZPOS;
a->used = 0;
tmp = a->dp;
for (n = 0; tmp != NULL && n < a->alloc; n++) {
*tmp++ = 0;
}
}
/* trim unused digits
*
* This is used to ensure that leading zero digits are
* trimmed and the leading "used" digit will be non-zero
* Typically very fast. Also fixes the sign if there
* are no more leading digits
*/
void mp_clamp (mp_int * a)
{
/* decrease used while the most significant digit is
* zero.
*/
while (a->used > 0 && a->dp[a->used - 1] == 0) {
--(a->used);
}
/* reset the sign flag if used == 0 */
if (a->used == 0) {
a->sign = MP_ZPOS;
}
}
/* swap the elements of two integers, for cases where you can't simply swap the
* mp_int pointers around
*/
int mp_exch (mp_int * a, mp_int * b)
{
mp_int t;
t = *a;
*a = *b;
*b = t;
return MP_OKAY;
}
/* Constant-time conditional swap: must not branch on m (leaks scalar bit).
* m must be 0 or 1. The t parameter is unused; XOR is performed in place
* with a single-digit stack scratch so callers don't need to clear t->dp. */
int mp_cond_swap_ct_ex (mp_int * a, mp_int * b, int c, int m, mp_int * t)
{
int i;
int err;
int imask;
int idiff;
mp_digit mask;
mp_digit d;
(void)t;
m &= 1;
imask = -m;
mask = (mp_digit)0 - (mp_digit)m;
if ((err = mp_grow(a, c)) != MP_OKAY)
return err;
if ((err = mp_grow(b, c)) != MP_OKAY)
return err;
idiff = (a->used ^ b->used) & imask;
a->used ^= idiff;
b->used ^= idiff;
idiff = (a->sign ^ b->sign) & imask;
a->sign ^= idiff;
b->sign ^= idiff;
for (i = 0; i < c; i++) {
d = (a->dp[i] ^ b->dp[i]) & mask;
a->dp[i] ^= d;
b->dp[i] ^= d;
}
return MP_OKAY;
}
int mp_cond_swap_ct (mp_int * a, mp_int * b, int c, int m)
{
return mp_cond_swap_ct_ex(a, b, c, m, NULL);
}
/* shift right a certain number of bits */
void mp_rshb (mp_int *c, int x)
{
mp_digit *tmpc, mask, shift;
mp_digit r, rr;
mp_digit D = x;
/* shifting by a negative number not supported, and shifting by
* zero changes nothing.
*/
if (x <= 0) return;
/* shift digits first if needed */
if (x >= DIGIT_BIT) {
mp_rshd(c, x / DIGIT_BIT);
/* recalculate number of bits to shift */
D = x % DIGIT_BIT;
/* check if any more shifting needed */
if (D == 0) return;
}
/* zero shifted is always zero */
if (mp_iszero(c)) return;
/* mask */
mask = (((mp_digit)1) << D) - 1;
/* shift for lsb */
shift = DIGIT_BIT - D;
/* alias */
tmpc = c->dp + (c->used - 1);
/* carry */
r = 0;
for (x = c->used - 1; x >= 0; x--) {
/* get the lower bits of this word in a temp */
rr = *tmpc & mask;
/* shift the current word and mix in the carry bits from previous word */
*tmpc = (*tmpc >> D) | (r << shift);
--tmpc;
/* set the carry to the carry bits of the current word found above */
r = rr;
}
mp_clamp(c);
}
/* shift right a certain amount of digits */
void mp_rshd (mp_int * a, int b)
{
int x;
/* if b <= 0 then ignore it */
if (b <= 0) {
return;
}
/* if b > used then simply zero it and return */
if (a->used <= b) {
mp_zero (a);
return;
}
{
mp_digit *bottom, *top;
/* shift the digits down */
/* bottom */
bottom = a->dp;
/* top [offset into digits] */
top = a->dp + b;
/* this is implemented as a sliding window where
* the window is b-digits long and digits from
* the top of the window are copied to the bottom
*
* e.g.
b-2 | b-1 | b0 | b1 | b2 | ... | bb | ---->
/\ | ---->
\-------------------/ ---->
*/
for (x = 0; x < (a->used - b); x++) {
*bottom++ = *top++;
}
/* zero the top digits */
for (; x < a->used; x++) {
*bottom++ = 0;
}
}
/* remove excess digits */
a->used -= b;
}
/* calc a value mod 2**b */
int mp_mod_2d (mp_int * a, int b, mp_int * c)
{
int x, res, bmax;
/* if b is <= 0 then zero the int */
if (b <= 0) {
mp_zero (c);
return MP_OKAY;
}
/* if the modulus is larger than the value than return */
if (a->sign == MP_ZPOS && b >= (int) (a->used * DIGIT_BIT)) {
res = mp_copy (a, c);
return res;
}
/* copy */
if ((res = mp_copy (a, c)) != MP_OKAY) {
return res;
}
/* calculate number of digits in mod value */
bmax = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1);
/* zero digits above the last digit of the modulus */
for (x = bmax; x < c->used; x++) {
c->dp[x] = 0;
}
if (c->sign == MP_NEG) {
mp_digit carry = 0;
/* grow result to size of modulus */
if ((res = mp_grow(c, bmax)) != MP_OKAY) {
return res;
}
/* negate value */
for (x = 0; x < c->used; x++) {
mp_digit next = c->dp[x] > 0;
c->dp[x] = ((mp_digit)0 - c->dp[x] - carry) & MP_MASK;
carry |= next;
}
for (; x < bmax; x++) {
c->dp[x] = ((mp_digit)0 - carry) & MP_MASK;
}
c->used = bmax;
c->sign = MP_ZPOS;
}
/* clear the digit that is not completely outside/inside the modulus */
x = DIGIT_BIT - (b % DIGIT_BIT);
if (x != DIGIT_BIT) {
c->dp[bmax - 1] &=
((mp_digit)~((mp_digit)0)) >> (x + ((sizeof(mp_digit)*8) - DIGIT_BIT));
}
mp_clamp (c);
return MP_OKAY;
}
/* reads a unsigned char array, assumes the msb is stored first [big endian] */
int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
{
int res;
int digits_needed;
while (c > 0 && b[0] == 0) {
c--;
b++;
}
digits_needed = ((c * CHAR_BIT) + DIGIT_BIT - 1) / DIGIT_BIT;
/* make sure there are enough digits available */
if (a->alloc < digits_needed) {
if ((res = mp_grow(a, digits_needed)) != MP_OKAY) {
return res;
}
}
/* zero the int */
mp_zero (a);
/* read the bytes in */
while (c-- > 0) {
if ((res = mp_mul_2d (a, 8, a)) != MP_OKAY) {
return res;
}
#ifndef MP_8BIT
a->dp[0] |= *b++;
if (a->used == 0)
a->used = 1;
#else
a->dp[0] = (*b & MP_MASK);
a->dp[1] |= ((*b++ >> 7U) & 1);
if (a->used == 0)
a->used = 2;
#endif
}
mp_clamp (a);
return MP_OKAY;
}
/* shift left by a certain bit count */
int mp_mul_2d (mp_int * a, int b, mp_int * c)
{
mp_digit d;
int res;
/* copy */
if (a != c) {
if ((res = mp_copy (a, c)) != MP_OKAY) {
return res;
}
}
if (c->alloc < (int)(c->used + b/DIGIT_BIT + 1)) {
if ((res = mp_grow (c, c->used + b / DIGIT_BIT + 1)) != MP_OKAY) {
return res;
}
}
/* shift by as many digits in the bit count */
if (b >= (int)DIGIT_BIT) {
if ((res = mp_lshd (c, b / DIGIT_BIT)) != MP_OKAY) {
return res;
}
}
/* shift any bit count < DIGIT_BIT */
d = (mp_digit) (b % DIGIT_BIT);
if (d != 0) {
mp_digit *tmpc, shift, mask, r, rr;
int x;
/* bitmask for carries */
mask = (((mp_digit)1) << d) - 1;
/* shift for msbs */
shift = DIGIT_BIT - d;
/* alias */
tmpc = c->dp;
/* carry */
r = 0;
for (x = 0; x < c->used; x++) {
/* get the higher bits of the current word */
rr = (*tmpc >> shift) & mask;
/* shift the current word and OR in the carry */
*tmpc = (mp_digit)(((*tmpc << d) | r) & MP_MASK);
++tmpc;
/* set the carry to the carry bits of the current word */
r = rr;
}
/* set final carry */
if (r != 0) {
c->dp[(c->used)++] = r;
}
}
mp_clamp (c);
return MP_OKAY;
}
/* shift left a certain amount of digits */
int mp_lshd (mp_int * a, int b)
{
int x, res;
/* if its less than zero return */
if (b <= 0) {
return MP_OKAY;
}
/* grow to fit the new digits */
if (a->alloc < a->used + b) {
if ((res = mp_grow (a, a->used + b)) != MP_OKAY) {
return res;
}
}
{
mp_digit *top, *bottom;
/* increment the used by the shift amount then copy upwards */
a->used += b;
/* top */
top = a->dp + a->used - 1;
/* base */
bottom = a->dp + a->used - 1 - b;
/* much like mp_rshd this is implemented using a sliding window
* except the window goes the other way around. Copying from
* the bottom to the top. see bn_mp_rshd.c for more info.
*/
for (x = a->used - 1; x >= b; x--) {
*top-- = *bottom--;
}
/* zero the lower digits */
top = a->dp;
for (x = 0; x < b; x++) {
*top++ = 0;
}
}
return MP_OKAY;
}
/* this is a shell function that calls either the normal or Montgomery
* exptmod functions. Originally the call to the montgomery code was
* embedded in the normal function but that wasted a lot of stack space
* for nothing (since 99% of the time the Montgomery code would be called)
*/
#if defined(FREESCALE_LTC_TFM)
int wolfcrypt_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
#else
int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y) /* //NOLINT(misc-no-recursion) */
#endif
{
int dr;
/* modulus P must be positive */
if (mp_iszero(P) || P->sign == MP_NEG) {
return MP_VAL;
}
if (mp_isone(P)) {
return mp_set(Y, 0);
}
if (mp_iszero(X)) {
return mp_set(Y, 1);
}
if (mp_iszero(G)) {
return mp_set(Y, 0);
}
/* if exponent X is negative we have to recurse */
if (X->sign == MP_NEG) {
#ifdef BN_MP_INVMOD_C
mp_int tmpG, tmpX;
int err;
/* first compute 1/G mod P */
if ((err = mp_init(&tmpG)) != MP_OKAY) {
return err;
}
if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
mp_clear(&tmpG);
return err;
}
/* now get |X| */
if ((err = mp_init(&tmpX)) != MP_OKAY) {
mp_clear(&tmpG);
return err;
}
if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
mp_clear(&tmpG);
mp_clear(&tmpX);
return err;
}
/* and now compute (1/G)**|X| instead of G**X [X < 0] */
err = mp_exptmod(&tmpG, &tmpX, P, Y);
mp_clear(&tmpG);
mp_clear(&tmpX);
return err;
#else
/* no invmod */
return MP_VAL;
#endif
}
#ifdef BN_MP_EXPTMOD_BASE_2
if (G->used == 1 && G->dp[0] == 2 && mp_isodd(P) == MP_YES) {
return mp_exptmod_base_2(X, P, Y);
}
#endif
/* modified diminished radix reduction */
#if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && \
defined(BN_S_MP_EXPTMOD_C)
if (mp_reduce_is_2k_l(P) == MP_YES) {
return s_mp_exptmod(G, X, P, Y, 1);
}
#endif
#ifdef BN_MP_DR_IS_MODULUS_C
/* is it a DR modulus? */
dr = mp_dr_is_modulus(P);
#else
/* default to no */
dr = 0;
#endif