1
2
3
4
5
6#include "tls.h"
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#ifndef DISABLE_PSTM
49
50static int32 pstm_mul_2d(pstm_int *a, int b, pstm_int *c);
51
52
53
54
55
56int32 pstm_init_size(psPool_t *pool, pstm_int * a, uint32 size)
57{
58
59
60
61
62
63
64 a->dp = xzalloc(sizeof (pstm_digit) * size);
65
66 a->used = 0;
67 a->alloc = size;
68 a->sign = PSTM_ZPOS;
69
70
71
72
73
74
75
76 return PSTM_OKAY;
77}
78
79
80
81
82
83int32 pstm_init(psPool_t *pool, pstm_int * a)
84{
85
86
87
88
89
90 a->dp = xzalloc(sizeof (pstm_digit) * PSTM_DEFAULT_INIT);
91
92
93
94
95
96
97
98
99
100
101
102
103 a->used = 0;
104 a->alloc = PSTM_DEFAULT_INIT;
105 a->sign = PSTM_ZPOS;
106
107 return PSTM_OKAY;
108}
109
110
111
112
113
114int32 pstm_grow(pstm_int * a, int size)
115{
116 int i;
117 pstm_digit *tmp;
118
119
120
121
122 if (a->alloc < size) {
123
124
125
126
127
128
129 tmp = xrealloc(a->dp, sizeof (pstm_digit) * size);
130
131
132
133 a->dp = tmp;
134
135
136
137 i = a->alloc;
138 a->alloc = size;
139 for (; i < a->alloc; i++) {
140 a->dp[i] = 0;
141 }
142 }
143 return PSTM_OKAY;
144}
145
146
147
148
149
150int32 pstm_copy(pstm_int * a, pstm_int * b)
151{
152 int32 res, n;
153
154
155
156
157 if (a == b) {
158 return PSTM_OKAY;
159 }
160
161
162
163 if (b->alloc < a->used) {
164 if ((res = pstm_grow (b, a->used)) != PSTM_OKAY) {
165 return res;
166 }
167 }
168
169
170
171 {
172 register pstm_digit *tmpa, *tmpb;
173
174
175
176 tmpa = a->dp;
177
178
179 tmpb = b->dp;
180
181
182 for (n = 0; n < a->used; n++) {
183 *tmpb++ = *tmpa++;
184 }
185
186
187 for (; n < b->used; n++) {
188 *tmpb++ = 0;
189 }
190 }
191
192
193
194 b->used = a->used;
195 b->sign = a->sign;
196 return PSTM_OKAY;
197}
198
199
200
201
202
203
204
205
206
207void pstm_clamp(pstm_int * a)
208{
209
210 while (a->used > 0 && a->dp[a->used - 1] == 0) {
211 --(a->used);
212 }
213
214 if (a->used == 0) {
215 a->sign = PSTM_ZPOS;
216 }
217}
218
219
220
221
222
223void pstm_clear(pstm_int * a)
224{
225 int32 i;
226
227
228
229 if (a != NULL && a->dp != NULL) {
230
231
232
233 for (i = 0; i < a->used; i++) {
234 a->dp[i] = 0;
235 }
236
237 psFree (a->dp, a->pool);
238
239
240
241 a->dp = NULL;
242 a->alloc = a->used = 0;
243 a->sign = PSTM_ZPOS;
244 }
245}
246
247
248
249
250
251void pstm_clear_multi(pstm_int *mp0, pstm_int *mp1, pstm_int *mp2,
252 pstm_int *mp3, pstm_int *mp4, pstm_int *mp5,
253 pstm_int *mp6, pstm_int *mp7)
254{
255 int32 n;
256
257 pstm_int *tempArray[9];
258
259 tempArray[0] = mp0;
260 tempArray[1] = mp1;
261 tempArray[2] = mp2;
262 tempArray[3] = mp3;
263 tempArray[4] = mp4;
264 tempArray[5] = mp5;
265 tempArray[6] = mp6;
266 tempArray[7] = mp7;
267 tempArray[8] = NULL;
268
269 for (n = 0; tempArray[n] != NULL; n++) {
270 if ((tempArray[n] != NULL) && (tempArray[n]->dp != NULL)) {
271 pstm_clear(tempArray[n]);
272 }
273 }
274}
275
276
277
278
279
280void pstm_zero(pstm_int * a)
281{
282 int32 n;
283 pstm_digit *tmp;
284
285 a->sign = PSTM_ZPOS;
286 a->used = 0;
287
288 tmp = a->dp;
289 for (n = 0; n < a->alloc; n++) {
290 *tmp++ = 0;
291 }
292}
293
294
295
296
297
298
299int32 pstm_cmp_mag(pstm_int * a, pstm_int * b)
300{
301 int n;
302 pstm_digit *tmpa, *tmpb;
303
304
305
306
307 if (a->used > b->used) {
308 return PSTM_GT;
309 }
310
311 if (a->used < b->used) {
312 return PSTM_LT;
313 }
314
315
316 tmpa = a->dp + (a->used - 1);
317
318
319 tmpb = b->dp + (a->used - 1);
320
321
322
323
324 for (n = 0; n < a->used; ++n, --tmpa, --tmpb) {
325 if (*tmpa > *tmpb) {
326 return PSTM_GT;
327 }
328 if (*tmpa < *tmpb) {
329 return PSTM_LT;
330 }
331 }
332 return PSTM_EQ;
333}
334
335
336
337
338
339int32 pstm_cmp(pstm_int * a, pstm_int * b)
340{
341
342
343
344 if (a->sign != b->sign) {
345 if (a->sign == PSTM_NEG) {
346 return PSTM_LT;
347 } else {
348 return PSTM_GT;
349 }
350 }
351
352
353
354 if (a->sign == PSTM_NEG) {
355
356 return pstm_cmp_mag(b, a);
357 } else {
358 return pstm_cmp_mag(a, b);
359 }
360}
361
362
363
364
365
366
367int32 pstm_init_for_read_unsigned_bin(psPool_t *pool, pstm_int *a, uint32 len)
368{
369 int32 size;
370
371
372
373
374
375
376 size = (((len / sizeof(pstm_digit)) * (sizeof(pstm_digit) * CHAR_BIT))
377 / DIGIT_BIT) + 2;
378 return pstm_init_size(pool, a, size);
379}
380
381
382
383
384
385
386
387
388int32 pstm_read_unsigned_bin(pstm_int *a, unsigned char *b, int32 c)
389{
390
391 pstm_zero (a);
392
393
394
395
396
397#if (defined(ENDIAN_LITTLE) || defined(ENDIAN_BIG)) && !defined(PSTM_64BIT)
398
399#if defined(ENDIAN_LITTLE) && defined(ENDIAN_BIG)
400#error Both ENDIAN_LITTLE and ENDIAN_BIG defined.
401#endif
402 {
403 unsigned char *pd;
404 if ((unsigned)c > (PSTM_MAX_SIZE * sizeof(pstm_digit))) {
405 uint32 excess = c - (PSTM_MAX_SIZE * sizeof(pstm_digit));
406 c -= excess;
407 b += excess;
408 }
409 a->used = ((c + sizeof(pstm_digit) - 1)/sizeof(pstm_digit));
410 if (a->alloc < a->used) {
411 if (pstm_grow(a, a->used) != PSTM_OKAY) {
412 return PSTM_MEM;
413 }
414 }
415 pd = (unsigned char *)a->dp;
416
417#ifdef ENDIAN_BIG
418 {
419
420 int32 idx = (c - 1) & ~3;
421 switch (c % 4) {
422 case 0: do { pd[idx+0] = *b++;
423 case 3: pd[idx+1] = *b++;
424 case 2: pd[idx+2] = *b++;
425 case 1: pd[idx+3] = *b++;
426 idx -= 4;
427 } while ((c -= 4) > 0);
428 }
429 }
430#else
431 for (c -= 1; c >= 0; c -= 1) {
432 pd[c] = *b++;
433 }
434#endif
435 }
436#else
437
438 a->used = (((c / sizeof(pstm_digit)) * (sizeof(pstm_digit) * CHAR_BIT))
439 / DIGIT_BIT) + 2;
440
441 if (a->alloc < a->used) {
442 if (pstm_grow(a, a->used) != PSTM_OKAY) {
443 return PSTM_MEM;
444 }
445 }
446
447 for (; c > 0; c--) {
448 if (pstm_mul_2d (a, 8, a) != PSTM_OKAY) {
449 return PS_MEM_FAIL;
450 }
451 a->dp[0] |= *b++;
452 a->used += 1;
453 }
454#endif
455
456 pstm_clamp (a);
457 return PS_SUCCESS;
458}
459
460
461
462
463int pstm_count_bits (pstm_int * a)
464{
465 int r;
466 pstm_digit q;
467
468 if (a->used == 0) {
469 return 0;
470 }
471
472
473 r = (a->used - 1) * DIGIT_BIT;
474
475
476 q = a->dp[a->used - 1];
477 while (q > ((pstm_digit) 0)) {
478 ++r;
479 q >>= ((pstm_digit) 1);
480 }
481 return r;
482}
483
484
485int32 pstm_unsigned_bin_size(pstm_int *a)
486{
487 int32 size = pstm_count_bits (a);
488 return (size / 8 + ((size & 7) != 0 ? 1 : 0));
489}
490
491
492void pstm_set(pstm_int *a, pstm_digit b)
493{
494 pstm_zero(a);
495 a->dp[0] = b;
496 a->used = a->dp[0] ? 1 : 0;
497}
498
499
500
501
502
503void pstm_rshd(pstm_int *a, int x)
504{
505 int y;
506
507
508 if (x >= a->used) {
509 pstm_zero(a);
510 return;
511 }
512
513
514 for (y = 0; y < a->used - x; y++) {
515 a->dp[y] = a->dp[y+x];
516 }
517
518
519 for (; y < a->used; y++) {
520 a->dp[y] = 0;
521 }
522
523
524 a->used -= x;
525 pstm_clamp(a);
526}
527
528
529
530
531
532int32 pstm_lshd(pstm_int * a, int b)
533{
534 int x;
535 int32 res;
536
537
538
539
540 if (b <= 0) {
541 return PSTM_OKAY;
542 }
543
544
545
546 if (a->alloc < a->used + b) {
547 if ((res = pstm_grow (a, a->used + b)) != PSTM_OKAY) {
548 return res;
549 }
550 }
551
552 {
553 register pstm_digit *top, *bottom;
554
555
556
557 a->used += b;
558
559
560 top = a->dp + a->used - 1;
561
562
563 bottom = a->dp + a->used - 1 - b;
564
565
566
567
568 for (x = a->used - 1; x >= b; x--) {
569 *top-- = *bottom--;
570 }
571
572
573 top = a->dp;
574 for (x = 0; x < b; x++) {
575 *top++ = 0;
576 }
577 }
578 return PSTM_OKAY;
579}
580
581
582
583
584
585int32 pstm_2expt(pstm_int *a, int b)
586{
587 int z;
588
589
590 pstm_zero (a);
591
592 if (b < 0) {
593 return PSTM_OKAY;
594 }
595
596 z = b / DIGIT_BIT;
597 if (z >= PSTM_MAX_SIZE) {
598 return PS_LIMIT_FAIL;
599 }
600
601
602 a->used = z + 1;
603
604 if (a->used > a->alloc) {
605 if (pstm_grow(a, a->used) != PSTM_OKAY) {
606 return PS_MEM_FAIL;
607 }
608 }
609
610
611 a->dp[z] = ((pstm_digit)1) << (b % DIGIT_BIT);
612 return PSTM_OKAY;
613}
614
615
616
617
618
619int32 pstm_mul_2(pstm_int * a, pstm_int * b)
620{
621 int32 res;
622 int x, oldused;
623
624
625
626
627 if (b->alloc < a->used + 1) {
628 if ((res = pstm_grow (b, a->used + 1)) != PSTM_OKAY) {
629 return res;
630 }
631 }
632 oldused = b->used;
633 b->used = a->used;
634
635 {
636 register pstm_digit r, rr, *tmpa, *tmpb;
637
638
639 tmpa = a->dp;
640
641
642 tmpb = b->dp;
643
644
645 r = 0;
646 for (x = 0; x < a->used; x++) {
647
648
649
650
651 rr = *tmpa >> ((pstm_digit)(DIGIT_BIT - 1));
652
653
654
655 *tmpb++ = ((*tmpa++ << ((pstm_digit)1)) | r);
656
657
658
659
660 r = rr;
661 }
662
663
664 if (r != 0 && b->used != (PSTM_MAX_SIZE-1)) {
665
666 *tmpb = 1;
667 ++(b->used);
668 }
669
670
671
672 tmpb = b->dp + b->used;
673 for (x = b->used; x < oldused; x++) {
674 *tmpb++ = 0;
675 }
676 }
677 b->sign = a->sign;
678 return PSTM_OKAY;
679}
680
681
682
683
684
685int32 s_pstm_sub(pstm_int *a, pstm_int *b, pstm_int *c)
686{
687 int oldbused, oldused;
688 int32 x;
689 pstm_word t;
690
691 if (b->used > a->used) {
692 return PS_LIMIT_FAIL;
693 }
694 if (c->alloc < a->used) {
695 if ((x = pstm_grow (c, a->used)) != PSTM_OKAY) {
696 return x;
697 }
698 }
699 oldused = c->used;
700 oldbused = b->used;
701 c->used = a->used;
702 t = 0;
703
704 for (x = 0; x < oldbused; x++) {
705 t = ((pstm_word)a->dp[x]) - (((pstm_word)b->dp[x]) + t);
706 c->dp[x] = (pstm_digit)t;
707 t = (t >> DIGIT_BIT)&1;
708 }
709 for (; x < a->used; x++) {
710 t = ((pstm_word)a->dp[x]) - t;
711 c->dp[x] = (pstm_digit)t;
712 t = (t >> DIGIT_BIT);
713 }
714 for (; x < oldused; x++) {
715 c->dp[x] = 0;
716 }
717 pstm_clamp(c);
718 return PSTM_OKAY;
719}
720
721
722
723
724
725static int32 s_pstm_add(pstm_int *a, pstm_int *b, pstm_int *c)
726{
727 int x, y, oldused;
728 register pstm_word t, adp, bdp;
729
730 y = a->used;
731 if (b->used > y) {
732 y = b->used;
733 }
734 oldused = c->used;
735 c->used = y;
736
737 if (c->used > c->alloc) {
738 if (pstm_grow(c, c->used) != PSTM_OKAY) {
739 return PS_MEM_FAIL;
740 }
741 }
742
743 t = 0;
744 for (x = 0; x < y; x++) {
745 if (a->used < x) {
746 adp = 0;
747 } else {
748 adp = (pstm_word)a->dp[x];
749 }
750 if (b->used < x) {
751 bdp = 0;
752 } else {
753 bdp = (pstm_word)b->dp[x];
754 }
755 t += (adp) + (bdp);
756 c->dp[x] = (pstm_digit)t;
757 t >>= DIGIT_BIT;
758 }
759 if (t != 0 && x < PSTM_MAX_SIZE) {
760 if (c->used == c->alloc) {
761 if (pstm_grow(c, c->alloc + 1) != PSTM_OKAY) {
762 return PS_MEM_FAIL;
763 }
764 }
765 c->dp[c->used++] = (pstm_digit)t;
766 ++x;
767 }
768
769 c->used = x;
770 for (; x < oldused; x++) {
771 c->dp[x] = 0;
772 }
773 pstm_clamp(c);
774 return PSTM_OKAY;
775}
776
777
778
779
780
781
782int32 pstm_sub(pstm_int *a, pstm_int *b, pstm_int *c)
783{
784 int32 res;
785 int sa, sb;
786
787 sa = a->sign;
788 sb = b->sign;
789
790 if (sa != sb) {
791
792
793
794
795 c->sign = sa;
796 if ((res = s_pstm_add (a, b, c)) != PSTM_OKAY) {
797 return res;
798 }
799 } else {
800
801
802
803
804 if (pstm_cmp_mag (a, b) != PSTM_LT) {
805
806 c->sign = sa;
807
808 if ((res = s_pstm_sub (a, b, c)) != PSTM_OKAY) {
809 return res;
810 }
811 } else {
812
813 c->sign = (sa == PSTM_ZPOS) ? PSTM_NEG : PSTM_ZPOS;
814
815 if ((res = s_pstm_sub (b, a, c)) != PSTM_OKAY) {
816 return res;
817 }
818 }
819 }
820 return PS_SUCCESS;
821}
822
823
824
825
826
827int32 pstm_sub_d(psPool_t *pool, pstm_int *a, pstm_digit b, pstm_int *c)
828{
829 pstm_int tmp;
830 int32 res;
831
832 if (pstm_init_size(pool, &tmp, sizeof(pstm_digit)) != PSTM_OKAY) {
833 return PS_MEM_FAIL;
834 }
835 pstm_set(&tmp, b);
836 res = pstm_sub(a, &tmp, c);
837 pstm_clear(&tmp);
838 return res;
839}
840
841
842
843
844
845int32 pstm_montgomery_setup(pstm_int *a, pstm_digit *rho)
846{
847 pstm_digit x, b;
848
849
850
851
852
853
854
855
856 b = a->dp[0];
857
858 if ((b & 1) == 0) {
859 psTraceCrypto("pstm_montogomery_setup failure\n");
860 return PS_ARG_FAIL;
861 }
862
863 x = (((b + 2) & 4) << 1) + b;
864 x *= 2 - b * x;
865 x *= 2 - b * x;
866 x *= 2 - b * x;
867#ifdef PSTM_64BIT
868 x *= 2 - b * x;
869#endif
870
871 *rho = (pstm_digit)(((pstm_word) 1 << ((pstm_word) DIGIT_BIT)) -
872 ((pstm_word)x));
873 return PSTM_OKAY;
874}
875
876
877
878
879
880
881int32 pstm_montgomery_calc_normalization(pstm_int *a, pstm_int *b)
882{
883 int32 x;
884 int bits;
885
886
887 bits = pstm_count_bits (b) % DIGIT_BIT;
888 if (!bits) bits = DIGIT_BIT;
889
890
891 if (b->used > 1) {
892 if ((x = pstm_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) !=
893 PSTM_OKAY) {
894 return x;
895 }
896 } else {
897 pstm_set(a, 1);
898 bits = 1;
899 }
900
901
902 for (x = bits - 1; x < (int32)DIGIT_BIT; x++) {
903 if (pstm_mul_2 (a, a) != PSTM_OKAY) {
904 return PS_MEM_FAIL;
905 }
906 if (pstm_cmp_mag (a, b) != PSTM_LT) {
907 if (s_pstm_sub (a, b, a) != PSTM_OKAY) {
908 return PS_MEM_FAIL;
909 }
910 }
911 }
912 return PSTM_OKAY;
913}
914
915
916
917
918
919static int32 pstm_mul_2d(pstm_int *a, int b, pstm_int *c)
920{
921 pstm_digit carry, carrytmp, shift;
922 int x;
923
924
925 if (pstm_copy(a, c) != PSTM_OKAY) {
926 return PS_MEM_FAIL;
927 }
928
929
930 if (b >= DIGIT_BIT) {
931 if (pstm_lshd(c, b/DIGIT_BIT) != PSTM_OKAY) {
932 return PS_MEM_FAIL;
933 }
934 }
935 b %= DIGIT_BIT;
936
937
938 if (b != 0) {
939 carry = 0;
940 shift = DIGIT_BIT - b;
941 for (x = 0; x < c->used; x++) {
942 carrytmp = c->dp[x] >> shift;
943 c->dp[x] = (c->dp[x] << b) + carry;
944 carry = carrytmp;
945 }
946
947 if (carry && x < PSTM_MAX_SIZE) {
948 if (c->used == c->alloc) {
949 if (pstm_grow(c, c->alloc + 1) != PSTM_OKAY) {
950 return PS_MEM_FAIL;
951 }
952 }
953 c->dp[c->used++] = carry;
954 }
955 }
956 pstm_clamp(c);
957 return PSTM_OKAY;
958}
959
960
961
962
963
964static int32 pstm_mod_2d(pstm_int *a, int b, pstm_int *c)
965{
966 int x;
967
968
969 if (b <= 0) {
970 pstm_zero(c);
971 return PSTM_OKAY;
972 }
973
974
975 if (pstm_copy(a, c) != PSTM_OKAY) {
976 return PS_MEM_FAIL;
977 }
978
979
980 if (b >= (DIGIT_BIT * a->used)) {
981 return PSTM_OKAY;
982 }
983
984
985 for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++)
986 {
987 c->dp[x] = 0;
988 }
989
990 c->dp[b / DIGIT_BIT] &= ~((pstm_digit)0) >> (DIGIT_BIT - b);
991 pstm_clamp (c);
992 return PSTM_OKAY;
993}
994
995
996
997
998
999
1000int32 pstm_mul_d(pstm_int *a, pstm_digit b, pstm_int *c)
1001{
1002 pstm_word w;
1003 int32 res;
1004 int x, oldused;
1005
1006 if (c->alloc < a->used + 1) {
1007 if ((res = pstm_grow (c, a->used + 1)) != PSTM_OKAY) {
1008 return res;
1009 }
1010 }
1011 oldused = c->used;
1012 c->used = a->used;
1013 c->sign = a->sign;
1014 w = 0;
1015 for (x = 0; x < a->used; x++) {
1016 w = ((pstm_word)a->dp[x]) * ((pstm_word)b) + w;
1017 c->dp[x] = (pstm_digit)w;
1018 w = w >> DIGIT_BIT;
1019 }
1020 if (w != 0 && (a->used != PSTM_MAX_SIZE)) {
1021 c->dp[c->used++] = (pstm_digit)w;
1022 ++x;
1023 }
1024 for (; x < oldused; x++) {
1025 c->dp[x] = 0;
1026 }
1027 pstm_clamp(c);
1028 return PSTM_OKAY;
1029}
1030
1031
1032
1033
1034
1035int32 pstm_div_2d(psPool_t *pool, pstm_int *a, int b, pstm_int *c,
1036 pstm_int *d)
1037{
1038 pstm_digit D, r, rr;
1039 int32 res;
1040 int x;
1041 pstm_int t;
1042
1043
1044 if (b <= 0) {
1045 if (pstm_copy (a, c) != PSTM_OKAY) {
1046 return PS_MEM_FAIL;
1047 }
1048 if (d != NULL) {
1049 pstm_zero (d);
1050 }
1051 return PSTM_OKAY;
1052 }
1053
1054
1055 if (d != NULL) {
1056 if (pstm_init(pool, &t) != PSTM_OKAY) {
1057 return PS_MEM_FAIL;
1058 }
1059 if (pstm_mod_2d (a, b, &t) != PSTM_OKAY) {
1060 res = PS_MEM_FAIL;
1061 goto LBL_DONE;
1062 }
1063 }
1064
1065
1066 if (pstm_copy(a, c) != PSTM_OKAY) {
1067 res = PS_MEM_FAIL;
1068 goto LBL_DONE;
1069 }
1070
1071
1072 if (b >= (int32)DIGIT_BIT) {
1073 pstm_rshd (c, b / DIGIT_BIT);
1074 }
1075
1076
1077 D = (pstm_digit) (b % DIGIT_BIT);
1078 if (D != 0) {
1079 register pstm_digit *tmpc, mask, shift;
1080
1081
1082 mask = (((pstm_digit)1) << D) - 1;
1083
1084
1085 shift = DIGIT_BIT - D;
1086
1087
1088 tmpc = c->dp + (c->used - 1);
1089
1090
1091 r = 0;
1092 for (x = c->used - 1; x >= 0; x--) {
1093
1094 rr = *tmpc & mask;
1095
1096
1097 *tmpc = (*tmpc >> D) | (r << shift);
1098 --tmpc;
1099
1100
1101 r = rr;
1102 }
1103 }
1104 pstm_clamp (c);
1105
1106 res = PSTM_OKAY;
1107LBL_DONE:
1108 if (d != NULL) {
1109 if (pstm_copy(&t, d) != PSTM_OKAY) {
1110 res = PS_MEM_FAIL;
1111 }
1112 pstm_clear(&t);
1113 }
1114 return res;
1115}
1116
1117
1118
1119
1120
1121int32 pstm_div_2(pstm_int * a, pstm_int * b)
1122{
1123 int x, oldused;
1124
1125 if (b->alloc < a->used) {
1126 if (pstm_grow(b, a->used) != PSTM_OKAY) {
1127 return PS_MEM_FAIL;
1128 }
1129 }
1130 oldused = b->used;
1131 b->used = a->used;
1132 {
1133 register pstm_digit r, rr, *tmpa, *tmpb;
1134
1135
1136 tmpa = a->dp + b->used - 1;
1137
1138
1139 tmpb = b->dp + b->used - 1;
1140
1141
1142 r = 0;
1143 for (x = b->used - 1; x >= 0; x--) {
1144
1145 rr = *tmpa & 1;
1146
1147
1148 *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
1149
1150
1151 r = rr;
1152 }
1153
1154
1155 tmpb = b->dp + b->used;
1156 for (x = b->used; x < oldused; x++) {
1157 *tmpb++ = 0;
1158 }
1159 }
1160 b->sign = a->sign;
1161 pstm_clamp (b);
1162 return PSTM_OKAY;
1163}
1164
1165
1166
1167
1168
1169int32 pstm_init_copy(psPool_t *pool, pstm_int * a, pstm_int * b, int toSqr)
1170{
1171 int x;
1172 int32 res;
1173
1174 if (a == b) {
1175 return PSTM_OKAY;
1176 }
1177 x = b->alloc;
1178
1179 if (toSqr) {
1180
1181
1182
1183
1184
1185 if ((b->used * 2) + 2 >= x) {
1186 x = (b->used * 2) + 3;
1187 }
1188 }
1189 if ((res = pstm_init_size(pool, a, x)) != PSTM_OKAY) {
1190 return res;
1191 }
1192 return pstm_copy(b, a);
1193}
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210#if defined(USE_MATRIX_DIV64) && defined(PSTM_32BIT)
1211static uint32 psDiv64(uint64 *numerator, uint32 denominator)
1212{
1213 uint64 rem = *numerator;
1214 uint64 b = denominator;
1215 uint64 res = 0;
1216 uint64 d = 1;
1217 uint32 high = rem >> 32;
1218
1219 if (high >= denominator) {
1220 high /= denominator;
1221 res = (uint64) high << 32;
1222 rem -= (uint64) (high * denominator) << 32;
1223 }
1224 while ((int64)b > 0 && b < rem) {
1225 b = b+b;
1226 d = d+d;
1227 }
1228 do {
1229 if (rem >= b) {
1230 rem -= b;
1231 res += d;
1232 }
1233 b >>= 1;
1234 d >>= 1;
1235 } while (d);
1236 *numerator = res;
1237 return rem;
1238}
1239#endif
1240
1241#if defined(USE_MATRIX_DIV128) && defined(PSTM_64BIT)
1242typedef unsigned long uint128 __attribute__ ((mode(TI)));
1243static uint64 psDiv128(uint128 *numerator, uint64 denominator)
1244{
1245 uint128 rem = *numerator;
1246 uint128 b = denominator;
1247 uint128 res = 0;
1248 uint128 d = 1;
1249 uint64 high = rem >> 64;
1250
1251 if (high >= denominator) {
1252 high /= denominator;
1253 res = (uint128) high << 64;
1254 rem -= (uint128) (high * denominator) << 64;
1255 }
1256 while ((uint128)b > 0 && b < rem) {
1257 b = b+b;
1258 d = d+d;
1259 }
1260 do {
1261 if (rem >= b) {
1262 rem -= b;
1263 res += d;
1264 }
1265 b >>= 1;
1266 d >>= 1;
1267 } while (d);
1268 *numerator = res;
1269 return rem;
1270}
1271#endif
1272
1273
1274
1275
1276
1277int32 pstm_div(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c,
1278 pstm_int *d)
1279{
1280 pstm_int q, x, y, t1, t2;
1281 int32 res;
1282 int n, t, i, norm, neg;
1283
1284
1285 if (pstm_iszero (b) == 1) {
1286 return PS_LIMIT_FAIL;
1287 }
1288
1289
1290 if (pstm_cmp_mag (a, b) == PSTM_LT) {
1291 if (d != NULL) {
1292 if (pstm_copy(a, d) != PSTM_OKAY) {
1293 return PS_MEM_FAIL;
1294 }
1295 }
1296 if (c != NULL) {
1297 pstm_zero (c);
1298 }
1299 return PSTM_OKAY;
1300 }
1301
1302
1303
1304 if ((res = pstm_init_size(pool, &t1, a->alloc)) != PSTM_OKAY) {
1305 return res;
1306 }
1307 if ((res = pstm_init_size(pool, &t2, 3)) != PSTM_OKAY) {
1308 goto LBL_T1;
1309 }
1310 if ((res = pstm_init_copy(pool, &x, a, 0)) != PSTM_OKAY) {
1311 goto LBL_T2;
1312 }
1313
1314
1315
1316 if ((res = pstm_init_size(pool, &y, b->used * 3)) != PSTM_OKAY) {
1317 goto LBL_X;
1318 }
1319 if ((res = pstm_copy(b, &y)) != PSTM_OKAY) {
1320 goto LBL_Y;
1321 }
1322
1323
1324 neg = (a->sign == b->sign) ? PSTM_ZPOS : PSTM_NEG;
1325 x.sign = y.sign = PSTM_ZPOS;
1326
1327
1328 norm = pstm_count_bits(&y) % DIGIT_BIT;
1329 if (norm < (int32)(DIGIT_BIT-1)) {
1330 norm = (DIGIT_BIT-1) - norm;
1331 if ((res = pstm_mul_2d(&x, norm, &x)) != PSTM_OKAY) {
1332 goto LBL_Y;
1333 }
1334 if ((res = pstm_mul_2d(&y, norm, &y)) != PSTM_OKAY) {
1335 goto LBL_Y;
1336 }
1337 } else {
1338 norm = 0;
1339 }
1340
1341
1342 n = x.used - 1;
1343 t = y.used - 1;
1344
1345 if ((res = pstm_init_size(pool, &q, n - t + 1)) != PSTM_OKAY) {
1346 goto LBL_Y;
1347 }
1348 q.used = n - t + 1;
1349
1350
1351 if ((res = pstm_lshd(&y, n - t)) != PSTM_OKAY) {
1352 goto LBL_Q;
1353 }
1354
1355 while (pstm_cmp (&x, &y) != PSTM_LT) {
1356 ++(q.dp[n - t]);
1357 if ((res = pstm_sub(&x, &y, &x)) != PSTM_OKAY) {
1358 goto LBL_Q;
1359 }
1360 }
1361
1362
1363 pstm_rshd (&y, n - t);
1364
1365
1366 for (i = n; i >= (t + 1); i--) {
1367 if (i > x.used) {
1368 continue;
1369 }
1370
1371
1372
1373 if (x.dp[i] == y.dp[t]) {
1374 q.dp[i - t - 1] = (pstm_digit)((((pstm_word)1) << DIGIT_BIT) - 1);
1375 } else {
1376 pstm_word tmp;
1377 tmp = ((pstm_word) x.dp[i]) << ((pstm_word) DIGIT_BIT);
1378 tmp |= ((pstm_word) x.dp[i - 1]);
1379#if defined(USE_MATRIX_DIV64) && defined(PSTM_32BIT)
1380 psDiv64(&tmp, y.dp[t]);
1381#elif defined(USE_MATRIX_DIV128) && defined(PSTM_64BIT)
1382 psDiv128(&tmp, y.dp[t]);
1383#else
1384 tmp /= ((pstm_word) y.dp[t]);
1385#endif
1386 q.dp[i - t - 1] = (pstm_digit) (tmp);
1387 }
1388
1389
1390
1391
1392
1393
1394 q.dp[i - t - 1] = (q.dp[i - t - 1] + 1);
1395 do {
1396 q.dp[i - t - 1] = (q.dp[i - t - 1] - 1);
1397
1398
1399 pstm_zero (&t1);
1400 t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
1401 t1.dp[1] = y.dp[t];
1402 t1.used = 2;
1403 if ((res = pstm_mul_d (&t1, q.dp[i - t - 1], &t1)) != PSTM_OKAY) {
1404 goto LBL_Q;
1405 }
1406
1407
1408 t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
1409 t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
1410 t2.dp[2] = x.dp[i];
1411 t2.used = 3;
1412 } while (pstm_cmp_mag(&t1, &t2) == PSTM_GT);
1413
1414
1415 if ((res = pstm_mul_d(&y, q.dp[i - t - 1], &t1)) != PSTM_OKAY) {
1416 goto LBL_Q;
1417 }
1418
1419 if ((res = pstm_lshd(&t1, i - t - 1)) != PSTM_OKAY) {
1420 goto LBL_Q;
1421 }
1422
1423 if ((res = pstm_sub(&x, &t1, &x)) != PSTM_OKAY) {
1424 goto LBL_Q;
1425 }
1426
1427
1428 if (x.sign == PSTM_NEG) {
1429 if ((res = pstm_copy(&y, &t1)) != PSTM_OKAY) {
1430 goto LBL_Q;
1431 }
1432 if ((res = pstm_lshd (&t1, i - t - 1)) != PSTM_OKAY) {
1433 goto LBL_Q;
1434 }
1435 if ((res = pstm_add (&x, &t1, &x)) != PSTM_OKAY) {
1436 goto LBL_Q;
1437 }
1438 q.dp[i - t - 1] = q.dp[i - t - 1] - 1;
1439 }
1440 }
1441
1442
1443
1444
1445 x.sign = x.used == 0 ? PSTM_ZPOS : a->sign;
1446
1447 if (c != NULL) {
1448 pstm_clamp (&q);
1449 if (pstm_copy (&q, c) != PSTM_OKAY) {
1450 res = PS_MEM_FAIL;
1451 goto LBL_Q;
1452 }
1453 c->sign = neg;
1454 }
1455
1456 if (d != NULL) {
1457 if ((res = pstm_div_2d (pool, &x, norm, &x, NULL)) != PSTM_OKAY) {
1458 goto LBL_Q;
1459 }
1460
1461
1462
1463
1464 for (i = b->used; i < x.used; i++) {
1465 x.dp[i] = 0;
1466 }
1467 pstm_clamp(&x);
1468 if (pstm_copy (&x, d) != PSTM_OKAY) {
1469 res = PS_MEM_FAIL;
1470 goto LBL_Q;
1471 }
1472 }
1473
1474 res = PSTM_OKAY;
1475
1476LBL_Q:pstm_clear (&q);
1477LBL_Y:pstm_clear (&y);
1478LBL_X:pstm_clear (&x);
1479LBL_T2:pstm_clear (&t2);
1480LBL_T1:pstm_clear (&t1);
1481
1482 return res;
1483}
1484
1485
1486
1487
1488
1489
1490void pstm_exch(pstm_int * a, pstm_int * b)
1491{
1492 pstm_int t;
1493
1494 t = *a;
1495 *a = *b;
1496 *b = t;
1497}
1498
1499
1500
1501
1502
1503int32 pstm_mod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c)
1504{
1505 pstm_int t;
1506 int32 err;
1507
1508
1509
1510 if ((err = pstm_init_size(pool, &t, b->alloc)) != PSTM_OKAY) {
1511 return err;
1512 }
1513 if ((err = pstm_div(pool, a, b, NULL, &t)) != PSTM_OKAY) {
1514 pstm_clear (&t);
1515 return err;
1516 }
1517 if (t.sign != b->sign) {
1518 err = pstm_add(&t, b, c);
1519 } else {
1520 pstm_exch (&t, c);
1521 }
1522 pstm_clear (&t);
1523 return err;
1524}
1525
1526
1527
1528
1529
1530int32 pstm_mulmod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c,
1531 pstm_int *d)
1532{
1533 int32 res;
1534 int size;
1535 pstm_int tmp;
1536
1537
1538
1539
1540
1541
1542 size = a->used + b->used + 1;
1543 if ((a == d) && (size < a->alloc)) {
1544 size = a->alloc;
1545 }
1546 if ((res = pstm_init_size(pool, &tmp, size)) != PSTM_OKAY) {
1547 return res;
1548 }
1549 if ((res = pstm_mul_comba(pool, a, b, &tmp, NULL, 0)) != PSTM_OKAY) {
1550 pstm_clear(&tmp);
1551 return res;
1552 }
1553 res = pstm_mod(pool, &tmp, c, d);
1554 pstm_clear(&tmp);
1555 return res;
1556}
1557
1558
1559
1560
1561
1562
1563int32 pstm_exptmod(psPool_t *pool, pstm_int *G, pstm_int *X, pstm_int *P,
1564 pstm_int *Y)
1565{
1566 pstm_int M[32], res;
1567 pstm_digit buf, mp;
1568 pstm_digit *paD;
1569 int32 err, bitbuf;
1570 int bitcpy, bitcnt, mode, digidx, x, y, winsize;
1571 uint32 paDlen;
1572
1573
1574 x = pstm_count_bits(X);
1575 if (x < 50) {
1576 winsize = 2;
1577 } else {
1578 winsize = PS_EXPTMOD_WINSIZE;
1579 }
1580
1581
1582 if ((err = pstm_montgomery_setup (P, &mp)) != PSTM_OKAY) {
1583 return err;
1584 }
1585
1586
1587 if ((err = pstm_init_size(pool, &res, (P->used * 2) + 1)) != PSTM_OKAY) {
1588 return err;
1589 }
1590
1591
1592
1593
1594
1595
1596 if ((err = pstm_montgomery_calc_normalization (&res, P)) != PSTM_OKAY) {
1597 goto LBL_RES;
1598 }
1599
1600
1601
1602
1603 if ((err = pstm_init_size(pool, &M[1], res.used)) != PSTM_OKAY) {
1604 goto LBL_RES;
1605 }
1606
1607
1608 if (pstm_cmp_mag(P, G) != PSTM_GT) {
1609
1610 if ((err = pstm_mod(pool, G, P, &M[1])) != PSTM_OKAY) {
1611 goto LBL_M;
1612 }
1613 } else {
1614 if ((err = pstm_copy(G, &M[1])) != PSTM_OKAY) {
1615 goto LBL_M;
1616 }
1617 }
1618 if ((err = pstm_mulmod (pool, &M[1], &res, P, &M[1])) != PSTM_OKAY) {
1619 goto LBL_M;
1620 }
1621
1622
1623
1624 paDlen = ((M[1].used + 3) * 2) * sizeof(pstm_digit);
1625 paD = xzalloc(paDlen);
1626
1627
1628
1629 if (pstm_init_copy(pool, &M[1 << (winsize - 1)], &M[1], 1) != PSTM_OKAY) {
1630 err = PS_MEM_FAIL;
1631 goto LBL_PAD;
1632 }
1633 for (x = 0; x < (winsize - 1); x++) {
1634 if ((err = pstm_sqr_comba (pool, &M[1 << (winsize - 1)],
1635 &M[1 << (winsize - 1)], paD, paDlen)) != PSTM_OKAY) {
1636 goto LBL_PAD;
1637 }
1638 if ((err = pstm_montgomery_reduce(pool, &M[1 << (winsize - 1)], P, mp,
1639 paD, paDlen)) != PSTM_OKAY) {
1640 goto LBL_PAD;
1641 }
1642 }
1643
1644
1645
1646 for (x = (1<<(winsize-1)) + 1; x < (1 << winsize); x++) {
1647 if ((err = pstm_init_size(pool, &M[x], M[1<<(winsize-1)].alloc + 1))
1648 != PSTM_OKAY) {
1649 for (y = 1<<(winsize-1); y < x; y++) {
1650 pstm_clear(&M[y]);
1651 }
1652 goto LBL_PAD;
1653 }
1654 }
1655
1656
1657 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
1658 if ((err = pstm_mul_comba(pool, &M[x - 1], &M[1], &M[x], paD, paDlen))
1659 != PSTM_OKAY) {
1660 goto LBL_MARRAY;
1661 }
1662 if ((err = pstm_montgomery_reduce(pool, &M[x], P, mp, paD, paDlen)) !=
1663 PSTM_OKAY) {
1664 goto LBL_MARRAY;
1665 }
1666 }
1667
1668
1669 mode = 0;
1670 bitcnt = 1;
1671 buf = 0;
1672 digidx = X->used - 1;
1673 bitcpy = 0;
1674 bitbuf = 0;
1675
1676 for (;;) {
1677
1678 if (--bitcnt == 0) {
1679
1680 if (digidx == -1) {
1681 break;
1682 }
1683
1684 buf = X->dp[digidx--];
1685 bitcnt = (int32)DIGIT_BIT;
1686 }
1687
1688
1689 y = (pstm_digit)(buf >> (DIGIT_BIT - 1)) & 1;
1690 buf <<= (pstm_digit)1;
1691
1692
1693
1694
1695
1696
1697 if (mode == 0 && y == 0) {
1698 continue;
1699 }
1700
1701
1702 if (mode == 1 && y == 0) {
1703 if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
1704 PSTM_OKAY) {
1705 goto LBL_MARRAY;
1706 }
1707 if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
1708 != PSTM_OKAY) {
1709 goto LBL_MARRAY;
1710 }
1711 continue;
1712 }
1713
1714
1715 bitbuf |= (y << (winsize - ++bitcpy));
1716 mode = 2;
1717
1718 if (bitcpy == winsize) {
1719
1720 for (x = 0; x < winsize; x++) {
1721 if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
1722 PSTM_OKAY) {
1723 goto LBL_MARRAY;
1724 }
1725 if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD,
1726 paDlen)) != PSTM_OKAY) {
1727 goto LBL_MARRAY;
1728 }
1729 }
1730
1731
1732 if ((err = pstm_mul_comba(pool, &res, &M[bitbuf], &res, paD,
1733 paDlen)) != PSTM_OKAY) {
1734 goto LBL_MARRAY;
1735 }
1736 if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
1737 != PSTM_OKAY) {
1738 goto LBL_MARRAY;
1739 }
1740
1741
1742 bitcpy = 0;
1743 bitbuf = 0;
1744 mode = 1;
1745 }
1746 }
1747
1748
1749 if (mode == 2 && bitcpy > 0) {
1750
1751 for (x = 0; x < bitcpy; x++) {
1752 if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
1753 PSTM_OKAY) {
1754 goto LBL_MARRAY;
1755 }
1756 if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
1757 != PSTM_OKAY) {
1758 goto LBL_MARRAY;
1759 }
1760
1761
1762 bitbuf <<= 1;
1763 if ((bitbuf & (1 << winsize)) != 0) {
1764
1765 if ((err = pstm_mul_comba(pool, &res, &M[1], &res, paD, paDlen))
1766 != PSTM_OKAY) {
1767 goto LBL_MARRAY;
1768 }
1769 if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD,
1770 paDlen)) != PSTM_OKAY) {
1771 goto LBL_MARRAY;
1772 }
1773 }
1774 }
1775 }
1776
1777
1778
1779
1780
1781 if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen)) !=
1782 PSTM_OKAY) {
1783 goto LBL_MARRAY;
1784 }
1785
1786 if ((err = pstm_copy (&res, Y)) != PSTM_OKAY) {
1787 goto LBL_MARRAY;
1788 }
1789 err = PSTM_OKAY;
1790LBL_MARRAY:
1791 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
1792 pstm_clear(&M[x]);
1793 }
1794LBL_PAD:psFree(paD, pool);
1795LBL_M: pstm_clear(&M[1]);
1796LBL_RES:pstm_clear(&res);
1797 return err;
1798}
1799
1800
1801
1802
1803
1804int32 pstm_add(pstm_int *a, pstm_int *b, pstm_int *c)
1805{
1806 int32 res;
1807 int sa, sb;
1808
1809
1810 sa = a->sign;
1811 sb = b->sign;
1812
1813
1814 if (sa == sb) {
1815
1816 c->sign = sa;
1817 if ((res = s_pstm_add (a, b, c)) != PSTM_OKAY) {
1818 return res;
1819 }
1820 } else {
1821
1822
1823
1824
1825
1826 if (pstm_cmp_mag (a, b) == PSTM_LT) {
1827 c->sign = sb;
1828 if ((res = s_pstm_sub (b, a, c)) != PSTM_OKAY) {
1829 return res;
1830 }
1831 } else {
1832 c->sign = sa;
1833 if ((res = s_pstm_sub (a, b, c)) != PSTM_OKAY) {
1834 return res;
1835 }
1836 }
1837 }
1838 return PS_SUCCESS;
1839}
1840
1841
1842
1843
1844
1845static void pstm_reverse (unsigned char *s, int len)
1846{
1847 int32 ix, iy;
1848 unsigned char t;
1849
1850 ix = 0;
1851 iy = len - 1;
1852 while (ix < iy) {
1853 t = s[ix];
1854 s[ix] = s[iy];
1855 s[iy] = t;
1856 ++ix;
1857 --iy;
1858 }
1859}
1860
1861
1862
1863
1864
1865int32 pstm_to_unsigned_bin_nr(psPool_t *pool, pstm_int *a, unsigned char *b)
1866{
1867 int32 res;
1868 int x;
1869 pstm_int t = { 0 };
1870
1871 if ((res = pstm_init_copy(pool, &t, a, 0)) != PSTM_OKAY) {
1872 return res;
1873 }
1874
1875 x = 0;
1876 while (pstm_iszero (&t) == 0) {
1877 b[x++] = (unsigned char) (t.dp[0] & 255);
1878 if ((res = pstm_div_2d (pool, &t, 8, &t, NULL)) != PSTM_OKAY) {
1879 pstm_clear(&t);
1880 return res;
1881 }
1882 }
1883 pstm_clear(&t);
1884 return PS_SUCCESS;
1885}
1886
1887
1888
1889
1890int32 pstm_to_unsigned_bin(psPool_t *pool, pstm_int *a, unsigned char *b)
1891{
1892 int32 res;
1893 int x;
1894 pstm_int t = { 0 };
1895
1896 if ((res = pstm_init_copy(pool, &t, a, 0)) != PSTM_OKAY) {
1897 return res;
1898 }
1899
1900 x = 0;
1901 while (pstm_iszero (&t) == 0) {
1902 b[x++] = (unsigned char) (t.dp[0] & 255);
1903 if ((res = pstm_div_2d (pool, &t, 8, &t, NULL)) != PSTM_OKAY) {
1904 pstm_clear(&t);
1905 return res;
1906 }
1907 }
1908 pstm_reverse (b, x);
1909 pstm_clear(&t);
1910 return PS_SUCCESS;
1911}
1912
1913
1914
1915
1916
1917int32 pstm_cmp_d(pstm_int *a, pstm_digit b)
1918{
1919
1920 if ((b && a->used == 0) || a->sign == PSTM_NEG) {
1921 return PSTM_LT;
1922 }
1923
1924
1925 if (a->used > 1) {
1926 return PSTM_GT;
1927 }
1928
1929
1930 if (a->dp[0] > b) {
1931 return PSTM_GT;
1932 } else if (a->dp[0] < b) {
1933 return PSTM_LT;
1934 } else {
1935 return PSTM_EQ;
1936 }
1937}
1938
1939
1940
1941
1942
1943
1944
1945#define pstm_invmod_slow(pool, a, b, c) \
1946 pstm_invmod_slow( a, b, c)
1947static int32 pstm_invmod_slow(psPool_t *pool, pstm_int * a, pstm_int * b,
1948 pstm_int * c)
1949{
1950 pstm_int x, y, u, v, A, B, C, D;
1951 int32 res;
1952
1953
1954 if (b->sign == PSTM_NEG || pstm_iszero(b) == 1) {
1955 return PS_LIMIT_FAIL;
1956 }
1957
1958
1959 if (pstm_init_size(pool, &x, b->used) != PSTM_OKAY) {
1960 return PS_MEM_FAIL;
1961 }
1962
1963
1964 if ((res = pstm_mod(pool, a, b, &x)) != PSTM_OKAY) {
1965 goto LBL_X;
1966 }
1967
1968 if (pstm_init_copy(pool, &y, b, 0) != PSTM_OKAY) {
1969 goto LBL_X;
1970 }
1971
1972
1973 if (pstm_iseven (&x) == 1 && pstm_iseven (&y) == 1) {
1974 res = PS_FAILURE;
1975 goto LBL_Y;
1976 }
1977
1978
1979 if ((res = pstm_init_copy(pool, &u, &x, 0)) != PSTM_OKAY) {
1980 goto LBL_Y;
1981 }
1982 if ((res = pstm_init_copy(pool, &v, &y, 0)) != PSTM_OKAY) {
1983 goto LBL_U;
1984 }
1985
1986 if ((res = pstm_init_size(pool, &A, sizeof(pstm_digit))) != PSTM_OKAY) {
1987 goto LBL_V;
1988 }
1989
1990 if ((res = pstm_init_size(pool, &D, sizeof(pstm_digit))) != PSTM_OKAY) {
1991 goto LBL_A;
1992 }
1993 pstm_set (&A, 1);
1994 pstm_set (&D, 1);
1995
1996 if ((res = pstm_init(pool, &B)) != PSTM_OKAY) {
1997 goto LBL_D;
1998 }
1999 if ((res = pstm_init(pool, &C)) != PSTM_OKAY) {
2000 goto LBL_B;
2001 }
2002
2003top:
2004
2005 while (pstm_iseven (&u) == 1) {
2006
2007 if ((res = pstm_div_2 (&u, &u)) != PSTM_OKAY) {
2008 goto LBL_C;
2009 }
2010
2011
2012 if (pstm_isodd (&A) == 1 || pstm_isodd (&B) == 1) {
2013
2014 if ((res = pstm_add (&A, &y, &A)) != PSTM_OKAY) {
2015 goto LBL_C;
2016 }
2017 if ((res = pstm_sub (&B, &x, &B)) != PSTM_OKAY) {
2018 goto LBL_C;
2019 }
2020 }
2021
2022 if ((res = pstm_div_2 (&A, &A)) != PSTM_OKAY) {
2023 goto LBL_C;
2024 }
2025 if ((res = pstm_div_2 (&B, &B)) != PSTM_OKAY) {
2026 goto LBL_C;
2027 }
2028 }
2029
2030
2031 while (pstm_iseven (&v) == 1) {
2032
2033 if ((res = pstm_div_2 (&v, &v)) != PSTM_OKAY) {
2034 goto LBL_C;
2035 }
2036
2037
2038 if (pstm_isodd (&C) == 1 || pstm_isodd (&D) == 1) {
2039
2040 if ((res = pstm_add (&C, &y, &C)) != PSTM_OKAY) {
2041 goto LBL_C;
2042 }
2043 if ((res = pstm_sub (&D, &x, &D)) != PSTM_OKAY) {
2044 goto LBL_C;
2045 }
2046 }
2047
2048 if ((res = pstm_div_2 (&C, &C)) != PSTM_OKAY) {
2049 goto LBL_C;
2050 }
2051 if ((res = pstm_div_2 (&D, &D)) != PSTM_OKAY) {
2052 goto LBL_C;
2053 }
2054 }
2055
2056
2057 if (pstm_cmp (&u, &v) != PSTM_LT) {
2058
2059 if ((res = pstm_sub (&u, &v, &u)) != PSTM_OKAY) {
2060 goto LBL_C;
2061 }
2062 if ((res = pstm_sub (&A, &C, &A)) != PSTM_OKAY) {
2063 goto LBL_C;
2064 }
2065 if ((res = pstm_sub (&B, &D, &B)) != PSTM_OKAY) {
2066 goto LBL_C;
2067 }
2068 } else {
2069
2070 if ((res = pstm_sub (&v, &u, &v)) != PSTM_OKAY) {
2071 goto LBL_C;
2072 }
2073 if ((res = pstm_sub (&C, &A, &C)) != PSTM_OKAY) {
2074 goto LBL_C;
2075 }
2076 if ((res = pstm_sub (&D, &B, &D)) != PSTM_OKAY) {
2077 goto LBL_C;
2078 }
2079 }
2080
2081
2082 if (pstm_iszero (&u) == 0)
2083 goto top;
2084
2085
2086
2087
2088 if (pstm_cmp_d (&v, 1) != PSTM_EQ) {
2089 res = PS_FAILURE;
2090 goto LBL_C;
2091 }
2092
2093
2094 while (pstm_cmp_d(&C, 0) == PSTM_LT) {
2095 if ((res = pstm_add(&C, b, &C)) != PSTM_OKAY) {
2096 goto LBL_C;
2097 }
2098 }
2099
2100
2101 while (pstm_cmp_mag(&C, b) != PSTM_LT) {
2102 if ((res = pstm_sub(&C, b, &C)) != PSTM_OKAY) {
2103 goto LBL_C;
2104 }
2105 }
2106
2107
2108 if ((res = pstm_copy(&C, c)) != PSTM_OKAY) {
2109 goto LBL_C;
2110 }
2111 res = PSTM_OKAY;
2112
2113LBL_C: pstm_clear(&C);
2114LBL_D: pstm_clear(&D);
2115LBL_B: pstm_clear(&B);
2116LBL_A: pstm_clear(&A);
2117LBL_V: pstm_clear(&v);
2118LBL_U: pstm_clear(&u);
2119LBL_Y: pstm_clear(&y);
2120LBL_X: pstm_clear(&x);
2121
2122 return res;
2123}
2124
2125
2126int32 pstm_invmod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c)
2127{
2128 pstm_int x, y, u, v, B, D;
2129 int32 res;
2130 int neg, sanity;
2131
2132
2133 if (pstm_iseven (b) == 1) {
2134 return pstm_invmod_slow(pool, a,b,c);
2135 }
2136
2137
2138 if ((res = pstm_init_copy(pool, &x, b, 0)) != PSTM_OKAY) {
2139 return res;
2140 }
2141
2142 if ((res = pstm_init_size(pool, &y, a->alloc)) != PSTM_OKAY) {
2143 goto LBL_X;
2144 }
2145
2146
2147 pstm_abs(a, &y);
2148
2149
2150 if ((res = pstm_init_copy(pool, &u, &x, 0)) != PSTM_OKAY) {
2151 goto LBL_Y;
2152 }
2153 if ((res = pstm_init_copy(pool, &v, &y, 0)) != PSTM_OKAY) {
2154 goto LBL_U;
2155 }
2156 if ((res = pstm_init(pool, &B)) != PSTM_OKAY) {
2157 goto LBL_V;
2158 }
2159 if ((res = pstm_init(pool, &D)) != PSTM_OKAY) {
2160 goto LBL_B;
2161 }
2162
2163 pstm_set (&D, 1);
2164
2165 sanity = 0;
2166top:
2167
2168 while (pstm_iseven (&u) == 1) {
2169
2170 if ((res = pstm_div_2 (&u, &u)) != PSTM_OKAY) {
2171 goto LBL_D;
2172 }
2173
2174
2175 if (pstm_isodd (&B) == 1) {
2176 if ((res = pstm_sub (&B, &x, &B)) != PSTM_OKAY) {
2177 goto LBL_D;
2178 }
2179 }
2180
2181 if ((res = pstm_div_2 (&B, &B)) != PSTM_OKAY) {
2182 goto LBL_D;
2183 }
2184 }
2185
2186
2187 while (pstm_iseven (&v) == 1) {
2188
2189 if ((res = pstm_div_2 (&v, &v)) != PSTM_OKAY) {
2190 goto LBL_D;
2191 }
2192
2193 if (pstm_isodd (&D) == 1) {
2194
2195 if ((res = pstm_sub (&D, &x, &D)) != PSTM_OKAY) {
2196 goto LBL_D;
2197 }
2198 }
2199
2200 if ((res = pstm_div_2 (&D, &D)) != PSTM_OKAY) {
2201 goto LBL_D;
2202 }
2203 }
2204
2205
2206 if (pstm_cmp (&u, &v) != PSTM_LT) {
2207
2208 if ((res = pstm_sub (&u, &v, &u)) != PSTM_OKAY) {
2209 goto LBL_D;
2210 }
2211 if ((res = pstm_sub (&B, &D, &B)) != PSTM_OKAY) {
2212 goto LBL_D;
2213 }
2214 } else {
2215
2216 if ((res = pstm_sub (&v, &u, &v)) != PSTM_OKAY) {
2217 goto LBL_D;
2218 }
2219 if ((res = pstm_sub (&D, &B, &D)) != PSTM_OKAY) {
2220 goto LBL_D;
2221 }
2222 }
2223
2224
2225 if (sanity++ > 1000) {
2226 res = PS_LIMIT_FAIL;
2227 goto LBL_D;
2228 }
2229 if (pstm_iszero (&u) == 0) {
2230 goto top;
2231 }
2232
2233
2234
2235
2236 if (pstm_cmp_d (&v, 1) != PSTM_EQ) {
2237 res = PS_FAILURE;
2238 goto LBL_D;
2239 }
2240
2241
2242 neg = a->sign;
2243 while (D.sign == PSTM_NEG) {
2244 if ((res = pstm_add (&D, b, &D)) != PSTM_OKAY) {
2245 goto LBL_D;
2246 }
2247 }
2248 if ((res = pstm_copy (&D, c)) != PSTM_OKAY) {
2249 goto LBL_D;
2250 }
2251 c->sign = neg;
2252 res = PSTM_OKAY;
2253
2254LBL_D: pstm_clear(&D);
2255LBL_B: pstm_clear(&B);
2256LBL_V: pstm_clear(&v);
2257LBL_U: pstm_clear(&u);
2258LBL_Y: pstm_clear(&y);
2259LBL_X: pstm_clear(&x);
2260 return res;
2261}
2262#endif
2263
2264