/src/dropbear/libtommath/bn_mp_exptmod.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_EXPTMOD_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* this is a shell function that calls either the normal or Montgomery |
7 | | * exptmod functions. Originally the call to the montgomery code was |
8 | | * embedded in the normal function but that wasted alot of stack space |
9 | | * for nothing (since 99% of the time the Montgomery code would be called) |
10 | | */ |
11 | | mp_err mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y) |
12 | 3.05k | { |
13 | 3.05k | int dr; |
14 | | |
15 | | /* modulus P must be positive */ |
16 | 3.05k | if (P->sign == MP_NEG) { |
17 | 0 | return MP_VAL; |
18 | 0 | } |
19 | | |
20 | | /* if exponent X is negative we have to recurse */ |
21 | 3.05k | if (X->sign == MP_NEG) { |
22 | 0 | mp_int tmpG, tmpX; |
23 | 0 | mp_err err; |
24 | |
|
25 | 0 | if (!MP_HAS(MP_INVMOD)) { |
26 | 0 | return MP_VAL; |
27 | 0 | } |
28 | | |
29 | 0 | if ((err = mp_init_multi(&tmpG, &tmpX, NULL)) != MP_OKAY) { |
30 | 0 | return err; |
31 | 0 | } |
32 | | |
33 | | /* first compute 1/G mod P */ |
34 | 0 | if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) { |
35 | 0 | goto LBL_ERR; |
36 | 0 | } |
37 | | |
38 | | /* now get |X| */ |
39 | 0 | if ((err = mp_abs(X, &tmpX)) != MP_OKAY) { |
40 | 0 | goto LBL_ERR; |
41 | 0 | } |
42 | | |
43 | | /* and now compute (1/G)**|X| instead of G**X [X < 0] */ |
44 | 0 | err = mp_exptmod(&tmpG, &tmpX, P, Y); |
45 | 0 | LBL_ERR: |
46 | 0 | mp_clear_multi(&tmpG, &tmpX, NULL); |
47 | 0 | return err; |
48 | 0 | } |
49 | | |
50 | | /* modified diminished radix reduction */ |
51 | 3.05k | if (MP_HAS(MP_REDUCE_IS_2K_L) && MP_HAS(MP_REDUCE_2K_L) && MP_HAS(S_MP_EXPTMOD) && |
52 | 3.05k | (mp_reduce_is_2k_l(P) == MP_YES)) { |
53 | 159 | return s_mp_exptmod(G, X, P, Y, 1); |
54 | 159 | } |
55 | | |
56 | | /* is it a DR modulus? default to no */ |
57 | 2.89k | dr = (MP_HAS(MP_DR_IS_MODULUS) && (mp_dr_is_modulus(P) == MP_YES)) ? 1 : 0; |
58 | | |
59 | | /* if not, is it a unrestricted DR modulus? */ |
60 | 2.89k | if (MP_HAS(MP_REDUCE_IS_2K) && (dr == 0)) { |
61 | 2.89k | dr = (mp_reduce_is_2k(P) == MP_YES) ? 2 : 0; |
62 | 2.89k | } |
63 | | |
64 | | /* if the modulus is odd or dr != 0 use the montgomery method */ |
65 | 2.89k | if (MP_HAS(S_MP_EXPTMOD_FAST) && (MP_IS_ODD(P) || (dr != 0))) { |
66 | 2.58k | return s_mp_exptmod_fast(G, X, P, Y, dr); |
67 | 2.58k | } else if (MP_HAS(S_MP_EXPTMOD)) { |
68 | | /* otherwise use the generic Barrett reduction technique */ |
69 | 303 | return s_mp_exptmod(G, X, P, Y, 0); |
70 | 303 | } else { |
71 | | /* no exptmod for evens */ |
72 | 0 | return MP_VAL; |
73 | 0 | } |
74 | 2.89k | } |
75 | | |
76 | | #endif |