dropbear: libtommath/bn_mp

annotate libtommath/bn_mp_div.c @ 1681:435cfb9ec96e

send and handle SSH_MSG_EXT_INFO only at the correct point - other fixes for rsa pubkey auth - only include ext-info handling when rsa pubkey auth is compiled

author	Matt Johnston <matt@ucc.asn.au>
date	Sun, 24 May 2020 14:16:58 +0800
parents	f52919ffd3b1
children	1051e4eea25a

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_DIV_C
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	4 *
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	5 * LibTomMath is a library that provides multiple-precision
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	6 * integer arithmetic as well as number theoretic functionality.
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	7 *
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	8 * The library was designed directly after the MPI library by
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	9 * Michael Fromberger but has been written from scratch with
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	10 * additional optimizations in place.
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	11 *
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	12 * 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	13 */
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	14
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	15 #ifdef BN_MP_DIV_SMALL
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	16
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	17 /* slower bit-bang division... also smaller */
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	18 int mp_div(const mp_int a, const mp_int b, mp_int c, mp_int d)
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	19 {
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	20 mp_int ta, tb, tq, q;
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	21 int res, n, n2;
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	22
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	23 /* is divisor zero ? */
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	24 if (mp_iszero(b) == MP_YES) {
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	25 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	26 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	27
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	28 /* if a < b then q=0, r = a */
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	29 if (mp_cmp_mag(a, b) == MP_LT) {
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 if (d != 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	31 res = mp_copy(a, d);
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	32 } else {
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	33 res = MP_OKAY;
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	34 }
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	35 if (c != 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	36 mp_zero(c);
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	37 }
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 return res;
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 }
1436 60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	40
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 /* init our temps */
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	42 if ((res = mp_init_multi(&ta, &tb, &tq, &q, NULL)) != MP_OKAY) {
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 return res;
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 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	45
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	46
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	47 mp_set(&tq, 1uL);
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 n = mp_count_bits(a) - mp_count_bits(b);
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	49 if (((res = mp_abs(a, &ta)) != MP_OKAY) \|\|
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 ((res = mp_abs(b, &tb)) != MP_OKAY) \|\|
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	51 ((res = mp_mul_2d(&tb, n, &tb)) != MP_OKAY) \|\|
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	52 ((res = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)) {
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	53 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	54 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	55
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	56 while (n-- >= 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	57 if (mp_cmp(&tb, &ta) != MP_GT) {
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	58 if (((res = mp_sub(&ta, &tb, &ta)) != MP_OKAY) \|\|
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 ((res = mp_add(&q, &tq, &q)) != MP_OKAY)) {
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	60 goto LBL_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	61 }
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 if (((res = mp_div_2d(&tb, 1, &tb, NULL)) != MP_OKAY) \|\|
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 ((res = mp_div_2d(&tq, 1, &tq, NULL)) != MP_OKAY)) {
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	65 goto LBL_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	66 }
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	67 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	68
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	69 /* now q == quotient and ta == remainder */
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	70 n = a->sign;
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 n2 = (a->sign == b->sign) ? MP_ZPOS : 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	72 if (c != 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	73 mp_exch(c, &q);
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	74 c->sign = (mp_iszero(c) == MP_YES) ? MP_ZPOS : n2;
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	75 }
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	76 if (d != 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	77 mp_exch(d, &ta);
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	78 d->sign = (mp_iszero(d) == MP_YES) ? MP_ZPOS : n;
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	79 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	80 LBL_ERR:
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	81 mp_clear_multi(&ta, &tb, &tq, &q, NULL);
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	82 return res;
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	83 }
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	84
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	85 #else
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	86
1436 60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	87 /* integer signed division.
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	88 * c*b + d == a [e.g. a/b, c=quotient, d=remainder]
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	89 * HAC pp.598 Algorithm 14.20
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	90 *
1436 60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	91 * Note that the description in HAC is horribly
60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	92 * incomplete. For example, it doesn't consider
60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	93 * the case where digits are removed from 'x' in
60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	94 * the inner loop. It also doesn't consider the
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	95 * case that y has fewer than three digits, etc..
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	96 *
1436 60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	97 * The overall algorithm is as described as
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	98 * 14.20 from HAC but fixed to treat these cases.
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	99 */
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	100 int mp_div(const mp_int a, const mp_int b, mp_int c, mp_int d)
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	101 {
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	102 mp_int q, x, y, t1, t2;
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	103 int res, n, t, i, norm, neg;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	104
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	105 /* is divisor zero ? */
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	106 if (mp_iszero(b) == MP_YES) {
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	107 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	108 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	109
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	110 /* if a < b then q=0, r = a */
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	111 if (mp_cmp_mag(a, b) == MP_LT) {
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	112 if (d != 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	113 res = mp_copy(a, d);
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	114 } else {
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	115 res = MP_OKAY;
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	116 }
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	117 if (c != 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	118 mp_zero(c);
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	119 }
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	120 return res;
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	121 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	122
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	123 if ((res = mp_init_size(&q, a->used + 2)) != MP_OKAY) {
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	124 return res;
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	125 }
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	126 q.used = a->used + 2;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	127
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	128 if ((res = mp_init(&t1)) != MP_OKAY) {
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	129 goto LBL_Q;
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	130 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	131
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	132 if ((res = mp_init(&t2)) != MP_OKAY) {
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	133 goto LBL_T1;
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	134 }
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	135
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	136 if ((res = mp_init_copy(&x, a)) != MP_OKAY) {
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	137 goto LBL_T2;
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	138 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	139
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	140 if ((res = mp_init_copy(&y, b)) != MP_OKAY) {
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	141 goto LBL_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	142 }
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	143
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	144 /* fix the sign */
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	145 neg = (a->sign == b->sign) ? MP_ZPOS : 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	146 x.sign = y.sign = MP_ZPOS;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	147
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	148 /* normalize both x and y, ensure that y >= b/2, [b == 2*DIGIT_BIT] /
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	149 norm = mp_count_bits(&y) % DIGIT_BIT;
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	150 if (norm < (DIGIT_BIT - 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	151 norm = (DIGIT_BIT - 1) - norm;
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	152 if ((res = mp_mul_2d(&x, norm, &x)) != MP_OKAY) {
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	153 goto LBL_Y;
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	154 }
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	155 if ((res = mp_mul_2d(&y, norm, &y)) != MP_OKAY) {
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	156 goto LBL_Y;
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	157 }
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	158 } else {
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	159 norm = 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	160 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	161
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	162 /* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */
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	163 n = x.used - 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	164 t = y.used - 1;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	165
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	166 /* while (x >= ybn-t) do { q[n-t] += 1; x -= yb*{n-t} } /
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	167 if ((res = mp_lshd(&y, n - t)) != MP_OKAY) { /* y = yb{n-t} /
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	168 goto LBL_Y;
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	169 }
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	170
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	171 while (mp_cmp(&x, &y) != MP_LT) {
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	172 ++(q.dp[n - t]);
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	173 if ((res = mp_sub(&x, &y, &x)) != MP_OKAY) {
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	174 goto LBL_Y;
1436 60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	175 }
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	176 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	177
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	178 /* reset y by shifting it back down */
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	179 mp_rshd(&y, n - t);
1436 60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	180
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	181 /* step 3. for i from n down to (t + 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	182 for (i = n; i >= (t + 1); i--) {
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	183 if (i > x.used) {
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	184 continue;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	185 }
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	186
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	187 /* step 3.1 if xi == yt then set q{i-t-1} to b-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	188 * otherwise set q{i-t-1} to (xib + x{i-1})/yt /
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	189 if (x.dp[i] == y.dp[t]) {
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	190 q.dp[(i - t) - 1] = ((mp_digit)1 << (mp_digit)DIGIT_BIT) - (mp_digit)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	191 } else {
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	192 mp_word tmp;
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	193 tmp = (mp_word)x.dp[i] << (mp_word)DIGIT_BIT;
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	194 tmp \|= (mp_word)x.dp[i - 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	195 tmp /= (mp_word)y.dp[t];
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	196 if (tmp > (mp_word)MP_MASK) {
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	197 tmp = MP_MASK;
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	198 }
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	199 q.dp[(i - t) - 1] = (mp_digit)(tmp & (mp_word)MP_MASK);
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	200 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	201
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	202 /* while (q{i-t-1} * (yt * b + y{t-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	203 xi * b*2 + xi-1 b + xi-2
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	204
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	205 do q{i-t-1} -= 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	206 */
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	207 q.dp[(i - t) - 1] = (q.dp[(i - t) - 1] + 1uL) & (mp_digit)MP_MASK;
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	208 do {
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	209 q.dp[(i - t) - 1] = (q.dp[(i - t) - 1] - 1uL) & (mp_digit)MP_MASK;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	210
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	211 /* find left hand */
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	212 mp_zero(&t1);
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	213 t1.dp[0] = ((t - 1) < 0) ? 0u : y.dp[t - 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	214 t1.dp[1] = y.dp[t];
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	215 t1.used = 2;
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	216 if ((res = mp_mul_d(&t1, q.dp[(i - t) - 1], &t1)) != MP_OKAY) {
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	217 goto LBL_Y;
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	218 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	219
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	220 /* find right hand */
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	221 t2.dp[0] = ((i - 2) < 0) ? 0u : x.dp[i - 2];
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	222 t2.dp[1] = ((i - 1) < 0) ? 0u : x.dp[i - 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	223 t2.dp[2] = x.dp[i];
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	224 t2.used = 3;
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	225 } while (mp_cmp_mag(&t1, &t2) == MP_GT);
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	226
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	227 /* step 3.3 x = x - q{i-t-1} * y * b*{i-t-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	228 if ((res = mp_mul_d(&y, q.dp[(i - t) - 1], &t1)) != MP_OKAY) {
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	229 goto LBL_Y;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	230 }
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	231
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	232 if ((res = mp_lshd(&t1, (i - t) - 1)) != MP_OKAY) {
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	233 goto LBL_Y;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	234 }
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	235
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	236 if ((res = mp_sub(&x, &t1, &x)) != MP_OKAY) {
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	237 goto LBL_Y;
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	238 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	239
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	240 /* if x < 0 then { x = x + yb{i-t-1}; q{i-t-1} -= 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	241 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	242 if ((res = mp_copy(&y, &t1)) != MP_OKAY) {
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	243 goto LBL_Y;
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	244 }
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	245 if ((res = mp_lshd(&t1, (i - t) - 1)) != MP_OKAY) {
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	246 goto LBL_Y;
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	247 }
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	248 if ((res = mp_add(&x, &t1, &x)) != MP_OKAY) {
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	249 goto LBL_Y;
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	250 }
1436 60fc6476e044 Update to libtommath v1.0 Matt Johnston <matt@ucc.asn.au> parents: 389 diff changeset	251
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	252 q.dp[(i - t) - 1] = (q.dp[(i - t) - 1] - 1uL) & MP_MASK;
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	253 }
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	254 }
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	255
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	256 /* now q is the quotient and x is the remainder
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	257 * [which we have to normalize]
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	258 */
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	259
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	260 /* get sign before writing to c */
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	261 x.sign = (x.used == 0) ? MP_ZPOS : a->sign;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	262
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	263 if (c != 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	264 mp_clamp(&q);
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	265 mp_exch(&q, c);
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	266 c->sign = 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	267 }
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	268
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	269 if (d != 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	270 if ((res = mp_div_2d(&x, norm, &x, NULL)) != MP_OKAY) {
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	271 goto LBL_Y;
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	272 }
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	273 mp_exch(&x, d);
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	274 }
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	275
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	276 res = MP_OKAY;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	277
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	278 LBL_Y:
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	279 mp_clear(&y);
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	280 LBL_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	281 mp_clear(&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	282 LBL_T2:
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	283 mp_clear(&t2);
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	284 LBL_T1:
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	285 mp_clear(&t1);
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	286 LBL_Q:
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	287 mp_clear(&q);
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	288 return res;
284 eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	289 }
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	290
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	291 #endif
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	292
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583) Matt Johnston <matt@ucc.asn.au> parents: diff changeset	293 #endif
389 5ff8218bcee9 propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 2af95f00ebd5bb7a28b3817db1218442c935388e) Matt Johnston <matt@ucc.asn.au> parents: 338 diff changeset	294
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	295 /* ref: HEAD -> master, tag: v1.1.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	296 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
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	297 /* commit time: 2019-01-28 20:32:32 +0100 */

Mercurial > dropbear

annotate libtommath/bn_mp_div.c @ 1681:435cfb9ec96e