Mercurial > dropbear

comparison libtommath/bn_mp_exptmod.c @ 1655:f52919ffd3b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) * make key-generation compliant to FIPS 186.4 * fix includes in tommath_class.h * update fuzzcorpus instead of error-out * fixup fuzzing make-targets * update Makefile.in * apply necessary patches to ltm sources * clean-up not required ltm files * update to vanilla ltm 1.1.0 this already only contains the required files * remove set/get double
author Steffen Jaeckel <s_jaeckel@gmx.de>
date Mon, 16 Sep 2019 15:50:38 +0200
parents 8bba51a55704
children 1051e4eea25a
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
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 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
7 * 7 *
8 * The library was designed directly after the MPI library by 8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with 9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * SPDX-License-Identifier: Unlicense
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */ 13 */
17 14
18 15
19 /* this is a shell function that calls either the normal or Montgomery 16 /* this is a shell function that calls either the normal or Montgomery
20 * exptmod functions. Originally the call to the montgomery code was 17 * exptmod functions. Originally the call to the montgomery code was
21 * embedded in the normal function but that wasted alot of stack space 18 * 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) 19 * for nothing (since 99% of the time the Montgomery code would be called)
23 */ 20 */
24 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y) 21 int mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y)
25 { 22 {
26 int dr; 23 int dr;
27 24
28 /* modulus P must be positive */ 25 /* modulus P must be positive */
29 if (P->sign == MP_NEG) { 26 if (P->sign == MP_NEG) {
30 return MP_VAL; 27 return MP_VAL;
31 } 28 }
32 29
33 /* if exponent X is negative we have to recurse */ 30 /* if exponent X is negative we have to recurse */
34 if (X->sign == MP_NEG) { 31 if (X->sign == MP_NEG) {
35 #ifdef BN_MP_INVMOD_C 32 #ifdef BN_MP_INVMOD_C
36 mp_int tmpG, tmpX; 33 mp_int tmpG, tmpX;
37 int err; 34 int err;
38 35
39 /* first compute 1/G mod P */ 36 /* first compute 1/G mod P */
40 if ((err = mp_init(&tmpG)) != MP_OKAY) { 37 if ((err = mp_init(&tmpG)) != MP_OKAY) {
41 return err; 38 return err;
42 } 39 }
43 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) { 40 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
44 mp_clear(&tmpG); 41 mp_clear(&tmpG);
45 return err; 42 return err;
46 } 43 }
47 44
48 /* now get |X| */ 45 /* now get |X| */
49 if ((err = mp_init(&tmpX)) != MP_OKAY) { 46 if ((err = mp_init(&tmpX)) != MP_OKAY) {
50 mp_clear(&tmpG); 47 mp_clear(&tmpG);
51 return err; 48 return err;
52 } 49 }
53 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) { 50 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
54 mp_clear_multi(&tmpG, &tmpX, NULL); 51 mp_clear_multi(&tmpG, &tmpX, NULL);
55 return err; 52 return err;
56 } 53 }
57 54
58 /* and now compute (1/G)**|X| instead of G**X [X < 0] */ 55 /* and now compute (1/G)**|X| instead of G**X [X < 0] */
59 err = mp_exptmod(&tmpG, &tmpX, P, Y); 56 err = mp_exptmod(&tmpG, &tmpX, P, Y);
60 mp_clear_multi(&tmpG, &tmpX, NULL); 57 mp_clear_multi(&tmpG, &tmpX, NULL);
61 return err; 58 return err;
62 #else 59 #else
63 /* no invmod */ 60 /* no invmod */
64 return MP_VAL; 61 return MP_VAL;
65 #endif 62 #endif
66 } 63 }
67 64
68 /* modified diminished radix reduction */ 65 /* modified diminished radix reduction */
69 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C) 66 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C)
70 if (mp_reduce_is_2k_l(P) == MP_YES) { 67 if (mp_reduce_is_2k_l(P) == MP_YES) {
71 return s_mp_exptmod(G, X, P, Y, 1); 68 return s_mp_exptmod(G, X, P, Y, 1);
72 } 69 }
73 #endif 70 #endif
74 71
75 #ifdef BN_MP_DR_IS_MODULUS_C 72 #ifdef BN_MP_DR_IS_MODULUS_C
76 /* is it a DR modulus? */ 73 /* is it a DR modulus? */
77 dr = mp_dr_is_modulus(P); 74 dr = mp_dr_is_modulus(P);
78 #else 75 #else
79 /* default to no */ 76 /* default to no */
80 dr = 0; 77 dr = 0;
81 #endif 78 #endif
82 79
83 #ifdef BN_MP_REDUCE_IS_2K_C 80 #ifdef BN_MP_REDUCE_IS_2K_C
84 /* if not, is it a unrestricted DR modulus? */ 81 /* if not, is it a unrestricted DR modulus? */
85 if (dr == 0) { 82 if (dr == 0) {
86 dr = mp_reduce_is_2k(P) << 1; 83 dr = mp_reduce_is_2k(P) << 1;
87 } 84 }
88 #endif 85 #endif
89 86
90 /* if the modulus is odd or dr != 0 use the montgomery method */ 87 /* if the modulus is odd or dr != 0 use the montgomery method */
91 #ifdef BN_MP_EXPTMOD_FAST_C 88 #ifdef BN_MP_EXPTMOD_FAST_C
92 if ((mp_isodd (P) == MP_YES) || (dr != 0)) { 89 if ((mp_isodd(P) == MP_YES) || (dr != 0)) {
93 return mp_exptmod_fast (G, X, P, Y, dr); 90 return mp_exptmod_fast(G, X, P, Y, dr);
94 } else { 91 } else {
95 #endif 92 #endif
96 #ifdef BN_S_MP_EXPTMOD_C 93 #ifdef BN_S_MP_EXPTMOD_C
97 /* otherwise use the generic Barrett reduction technique */ 94 /* otherwise use the generic Barrett reduction technique */
98 return s_mp_exptmod (G, X, P, Y, 0); 95 return s_mp_exptmod(G, X, P, Y, 0);
99 #else 96 #else
100 /* no exptmod for evens */ 97 /* no exptmod for evens */
101 return MP_VAL; 98 return MP_VAL;
102 #endif 99 #endif
103 #ifdef BN_MP_EXPTMOD_FAST_C 100 #ifdef BN_MP_EXPTMOD_FAST_C
104 } 101 }
105 #endif 102 #endif
106 } 103 }
107 104
108 #endif 105 #endif
109 106
110 /* ref: $Format:%D$ */ 107 /* ref: HEAD -> master, tag: v1.1.0 */
111 /* git commit: $Format:%H$ */ 108 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
112 /* commit time: $Format:%ai$ */ 109 /* commit time: 2019-01-28 20:32:32 +0100 */