Mercurial > dropbear

comparison libtommath/bn_mp_exptmod.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.h" 1 #include "tommath_private.h"
2 #ifdef BN_MP_EXPTMOD_C 2 #ifdef BN_MP_EXPTMOD_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 * 4 /* SPDX-License-Identifier: Unlicense */
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * SPDX-License-Identifier: Unlicense
13 */
14
15 5
16 /* this is a shell function that calls either the normal or Montgomery 6 /* this is a shell function that calls either the normal or Montgomery
17 * exptmod functions. Originally the call to the montgomery code was 7 * exptmod functions. Originally the call to the montgomery code was
18 * embedded in the normal function but that wasted alot of stack space 8 * embedded in the normal function but that wasted alot of stack space
19 * for nothing (since 99% of the time the Montgomery code would be called) 9 * for nothing (since 99% of the time the Montgomery code would be called)
20 */ 10 */
21 int mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y) 11 mp_err mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y)
22 { 12 {
23 int dr; 13 int dr;
24 14
25 /* modulus P must be positive */ 15 /* modulus P must be positive */
26 if (P->sign == MP_NEG) { 16 if (P->sign == MP_NEG) {
27 return MP_VAL; 17 return MP_VAL;
28 } 18 }
29 19
30 /* if exponent X is negative we have to recurse */ 20 /* if exponent X is negative we have to recurse */
31 if (X->sign == MP_NEG) { 21 if (X->sign == MP_NEG) {
32 #ifdef BN_MP_INVMOD_C
33 mp_int tmpG, tmpX; 22 mp_int tmpG, tmpX;
34 int err; 23 mp_err err;
35 24
36 /* first compute 1/G mod P */ 25 if (!MP_HAS(MP_INVMOD)) {
37 if ((err = mp_init(&tmpG)) != MP_OKAY) { 26 return MP_VAL;
38 return err;
39 } 27 }
40 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) { 28
41 mp_clear(&tmpG); 29 if ((err = mp_init_multi(&tmpG, &tmpX, NULL)) != MP_OKAY) {
42 return err; 30 return err;
43 } 31 }
44 32
33 /* first compute 1/G mod P */
34 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
35 goto LBL_ERR;
36 }
37
45 /* now get |X| */ 38 /* now get |X| */
46 if ((err = mp_init(&tmpX)) != MP_OKAY) {
47 mp_clear(&tmpG);
48 return err;
49 }
50 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) { 39 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
51 mp_clear_multi(&tmpG, &tmpX, NULL); 40 goto LBL_ERR;
52 return err;
53 } 41 }
54 42
55 /* and now compute (1/G)**|X| instead of G**X [X < 0] */ 43 /* and now compute (1/G)**|X| instead of G**X [X < 0] */
56 err = mp_exptmod(&tmpG, &tmpX, P, Y); 44 err = mp_exptmod(&tmpG, &tmpX, P, Y);
45 LBL_ERR:
57 mp_clear_multi(&tmpG, &tmpX, NULL); 46 mp_clear_multi(&tmpG, &tmpX, NULL);
58 return err; 47 return err;
59 #else
60 /* no invmod */
61 return MP_VAL;
62 #endif
63 } 48 }
64 49
65 /* modified diminished radix reduction */ 50 /* modified diminished radix reduction */
66 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C) 51 if (MP_HAS(MP_REDUCE_IS_2K_L) && MP_HAS(MP_REDUCE_2K_L) && MP_HAS(S_MP_EXPTMOD) &&
67 if (mp_reduce_is_2k_l(P) == MP_YES) { 52 (mp_reduce_is_2k_l(P) == MP_YES)) {
68 return s_mp_exptmod(G, X, P, Y, 1); 53 return s_mp_exptmod(G, X, P, Y, 1);
69 } 54 }
70 #endif
71 55
72 #ifdef BN_MP_DR_IS_MODULUS_C 56 /* is it a DR modulus? default to no */
73 /* is it a DR modulus? */ 57 dr = (MP_HAS(MP_DR_IS_MODULUS) && (mp_dr_is_modulus(P) == MP_YES)) ? 1 : 0;
74 dr = mp_dr_is_modulus(P);
75 #else
76 /* default to no */
77 dr = 0;
78 #endif
79 58
80 #ifdef BN_MP_REDUCE_IS_2K_C
81 /* if not, is it a unrestricted DR modulus? */ 59 /* if not, is it a unrestricted DR modulus? */
82 if (dr == 0) { 60 if (MP_HAS(MP_REDUCE_IS_2K) && (dr == 0)) {
83 dr = mp_reduce_is_2k(P) << 1; 61 dr = (mp_reduce_is_2k(P) == MP_YES) ? 2 : 0;
84 } 62 }
85 #endif
86 63
87 /* if the modulus is odd or dr != 0 use the montgomery method */ 64 /* if the modulus is odd or dr != 0 use the montgomery method */
88 #ifdef BN_MP_EXPTMOD_FAST_C 65 if (MP_HAS(S_MP_EXPTMOD_FAST) && (MP_IS_ODD(P) || (dr != 0))) {
89 if ((mp_isodd(P) == MP_YES) || (dr != 0)) { 66 return s_mp_exptmod_fast(G, X, P, Y, dr);
90 return mp_exptmod_fast(G, X, P, Y, dr); 67 } else if (MP_HAS(S_MP_EXPTMOD)) {
91 } else {
92 #endif
93 #ifdef BN_S_MP_EXPTMOD_C
94 /* otherwise use the generic Barrett reduction technique */ 68 /* otherwise use the generic Barrett reduction technique */
95 return s_mp_exptmod(G, X, P, Y, 0); 69 return s_mp_exptmod(G, X, P, Y, 0);
96 #else 70 } else {
97 /* no exptmod for evens */ 71 /* no exptmod for evens */
98 return MP_VAL; 72 return MP_VAL;
99 #endif
100 #ifdef BN_MP_EXPTMOD_FAST_C
101 } 73 }
102 #endif
103 } 74 }
104 75
105 #endif 76 #endif
106
107 /* ref: HEAD -> master, tag: v1.1.0 */
108 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
109 /* commit time: 2019-01-28 20:32:32 +0100 */