dropbear: libtommath/bn_mp_exptmod.c annotate

annotate libtommath/bn_mp_exptmod.c @ 1902:4a6725ac957c

Revert "Don't include sk keys at all in KEX list" This reverts git commit f972813ecdc7bb981d25b5a63638bd158f1c8e72. The sk algorithms need to remain in the sigalgs list so that they are included in the server-sig-algs ext-info message sent by the server. RFC8308 for server-sig-algs requires that all algorithms are listed (though OpenSSH client 8.4p1 tested doesn't require that)

author	Matt Johnston <matt@ucc.asn.au>
date	Thu, 24 Mar 2022 13:42:08 +0800
parents	1051e4eea25a
children

rev	line source
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	1 #include "tommath_private.h"
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	2 #ifdef BN_MP_EXPTMOD_C
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	4 /* SPDX-License-Identifier: Unlicense */
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	5
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	6 /* this is a shell function that calls either the normal or Montgomery
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	7 * exptmod functions. Originally the call to the montgomery code was
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	8 * embedded in the normal function but that wasted alot of stack space
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	9 * for nothing (since 99% of the time the Montgomery code would be called)
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	10 */
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	11 mp_err mp_exptmod(const mp_int G, const mp_int X, const mp_int P, mp_int Y)
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	12 {
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	13 int dr;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	14
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	15 /* modulus P must be positive */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	16 if (P->sign == MP_NEG) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	17 return MP_VAL;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	18 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	19
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	20 /* if exponent X is negative we have to recurse */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	21 if (X->sign == MP_NEG) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	22 mp_int tmpG, tmpX;
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	23 mp_err err;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	24
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	25 if (!MP_HAS(MP_INVMOD)) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	26 return MP_VAL;
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	27 }
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	28
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	29 if ((err = mp_init_multi(&tmpG, &tmpX, NULL)) != MP_OKAY) {
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	30 return err;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	31 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	32
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	33 /* first compute 1/G mod P */
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	34 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	35 goto LBL_ERR;
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	36 }
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	37
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	38 /* now get \|X\| */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	39 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	40 goto LBL_ERR;
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	41 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	42
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	43 /* and now compute (1/G)\|X\| instead of GX [X < 0] */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	44 err = mp_exptmod(&tmpG, &tmpX, P, Y);
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	45 LBL_ERR:
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	46 mp_clear_multi(&tmpG, &tmpX, NULL);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	47 return err;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	48 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	49
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	50 /* modified diminished radix reduction */
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	51 if (MP_HAS(MP_REDUCE_IS_2K_L) && MP_HAS(MP_REDUCE_2K_L) && MP_HAS(S_MP_EXPTMOD) &&
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	52 (mp_reduce_is_2k_l(P) == MP_YES)) {
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	53 return s_mp_exptmod(G, X, P, Y, 1);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	54 }
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	55
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	56 /* is it a DR modulus? default to no */
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	57 dr = (MP_HAS(MP_DR_IS_MODULUS) && (mp_dr_is_modulus(P) == MP_YES)) ? 1 : 0;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	58
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	59 /* if not, is it a unrestricted DR modulus? */
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	60 if (MP_HAS(MP_REDUCE_IS_2K) && (dr == 0)) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	61 dr = (mp_reduce_is_2k(P) == MP_YES) ? 2 : 0;
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	62 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	63
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	64 /* if the modulus is odd or dr != 0 use the montgomery method */
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	65 if (MP_HAS(S_MP_EXPTMOD_FAST) && (MP_IS_ODD(P) \|\| (dr != 0))) {
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	66 return s_mp_exptmod_fast(G, X, P, Y, dr);
1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	67 } else if (MP_HAS(S_MP_EXPTMOD)) {
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	68 /* otherwise use the generic Barrett reduction technique */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	69 return s_mp_exptmod(G, X, P, Y, 0);
1692 1051e4eea25a Update LibTomMath to 1.2.0 (#84) Steffen Jaeckel <s@jaeckel.eu> parents: 1655 diff changeset	70 } else {
1655 f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	71 /* no exptmod for evens */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	72 return MP_VAL;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) Steffen Jaeckel <s_jaeckel@gmx.de> parents: 1470 diff changeset	73 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	74 }
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	75
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	76 #endif

Mercurial > dropbear

annotate libtommath/bn_mp_exptmod.c @ 1902:4a6725ac957c