Mercurial > dropbear

comparison libtommath/bn_mp_exptmod.c @ 1733:d529a52b2f7c coverity coverity

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge coverity from main
author Matt Johnston <matt@ucc.asn.au>
date Fri, 26 Jun 2020 21:07:34 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1643:b59623a64678 1733:d529a52b2f7c
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 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */
17
18 5
19 /* 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
20 * exptmod functions. Originally the call to the montgomery code was 7 * exptmod functions. Originally the call to the montgomery code was
21 * 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
22 * 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)
23 */ 10 */
24 int mp_exptmod (mp_int * G, mp_int * X, 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)
25 { 12 {
26 int dr; 13 int dr;
27 14
28 /* modulus P must be positive */ 15 /* modulus P must be positive */
29 if (P->sign == MP_NEG) { 16 if (P->sign == MP_NEG) {
30 return MP_VAL; 17 return MP_VAL;
31 } 18 }
32 19
33 /* if exponent X is negative we have to recurse */ 20 /* if exponent X is negative we have to recurse */
34 if (X->sign == MP_NEG) { 21 if (X->sign == MP_NEG) {
35 #ifdef BN_MP_INVMOD_C 22 mp_int tmpG, tmpX;
36 mp_int tmpG, tmpX; 23 mp_err err;
37 int err;
38 24
39 /* first compute 1/G mod P */ 25 if (!MP_HAS(MP_INVMOD)) {
40 if ((err = mp_init(&tmpG)) != MP_OKAY) { 26 return MP_VAL;
41 return err; 27 }
42 }
43 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
44 mp_clear(&tmpG);
45 return err;
46 }
47 28
48 /* now get |X| */ 29 if ((err = mp_init_multi(&tmpG, &tmpX, NULL)) != MP_OKAY) {
49 if ((err = mp_init(&tmpX)) != MP_OKAY) { 30 return err;
50 mp_clear(&tmpG); 31 }
51 return err;
52 }
53 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
54 mp_clear_multi(&tmpG, &tmpX, NULL);
55 return err;
56 }
57 32
58 /* and now compute (1/G)**|X| instead of G**X [X < 0] */ 33 /* first compute 1/G mod P */
59 err = mp_exptmod(&tmpG, &tmpX, P, Y); 34 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
60 mp_clear_multi(&tmpG, &tmpX, NULL); 35 goto LBL_ERR;
61 return err; 36 }
62 #else
63 /* no invmod */
64 return MP_VAL;
65 #endif
66 }
67 37
68 /* modified diminished radix reduction */ 38 /* now get |X| */
69 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C) 39 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
70 if (mp_reduce_is_2k_l(P) == MP_YES) { 40 goto LBL_ERR;
71 return s_mp_exptmod(G, X, P, Y, 1); 41 }
72 }
73 #endif
74 42
75 #ifdef BN_MP_DR_IS_MODULUS_C 43 /* and now compute (1/G)**|X| instead of G**X [X < 0] */
76 /* is it a DR modulus? */ 44 err = mp_exptmod(&tmpG, &tmpX, P, Y);
77 dr = mp_dr_is_modulus(P); 45 LBL_ERR:
78 #else 46 mp_clear_multi(&tmpG, &tmpX, NULL);
79 /* default to no */ 47 return err;
80 dr = 0; 48 }
81 #endif
82 49
83 #ifdef BN_MP_REDUCE_IS_2K_C 50 /* modified diminished radix reduction */
84 /* if not, is it a unrestricted DR modulus? */ 51 if (MP_HAS(MP_REDUCE_IS_2K_L) && MP_HAS(MP_REDUCE_2K_L) && MP_HAS(S_MP_EXPTMOD) &&
85 if (dr == 0) { 52 (mp_reduce_is_2k_l(P) == MP_YES)) {
86 dr = mp_reduce_is_2k(P) << 1; 53 return s_mp_exptmod(G, X, P, Y, 1);
87 } 54 }
88 #endif 55
89 56 /* is it a DR modulus? default to no */
90 /* if the modulus is odd or dr != 0 use the montgomery method */ 57 dr = (MP_HAS(MP_DR_IS_MODULUS) && (mp_dr_is_modulus(P) == MP_YES)) ? 1 : 0;
91 #ifdef BN_MP_EXPTMOD_FAST_C 58
92 if ((mp_isodd (P) == MP_YES) || (dr != 0)) { 59 /* if not, is it a unrestricted DR modulus? */
93 return mp_exptmod_fast (G, X, P, Y, dr); 60 if (MP_HAS(MP_REDUCE_IS_2K) && (dr == 0)) {
94 } else { 61 dr = (mp_reduce_is_2k(P) == MP_YES) ? 2 : 0;
95 #endif 62 }
96 #ifdef BN_S_MP_EXPTMOD_C 63
97 /* otherwise use the generic Barrett reduction technique */ 64 /* if the modulus is odd or dr != 0 use the montgomery method */
98 return s_mp_exptmod (G, X, P, Y, 0); 65 if (MP_HAS(S_MP_EXPTMOD_FAST) && (MP_IS_ODD(P) || (dr != 0))) {
99 #else 66 return s_mp_exptmod_fast(G, X, P, Y, dr);
100 /* no exptmod for evens */ 67 } else if (MP_HAS(S_MP_EXPTMOD)) {
101 return MP_VAL; 68 /* otherwise use the generic Barrett reduction technique */
102 #endif 69 return s_mp_exptmod(G, X, P, Y, 0);
103 #ifdef BN_MP_EXPTMOD_FAST_C 70 } else {
104 } 71 /* no exptmod for evens */
105 #endif 72 return MP_VAL;
73 }
106 } 74 }
107 75
108 #endif 76 #endif
109
110 /* ref: $Format:%D$ */
111 /* git commit: $Format:%H$ */
112 /* commit time: $Format:%ai$ */