Mercurial > dropbear
diff libtommath/bn_mp_montgomery_reduce.c @ 1655:f52919ffd3b1
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 |
line wrap: on
line diff
--- a/libtommath/bn_mp_montgomery_reduce.c Wed May 15 21:59:45 2019 +0800 +++ b/libtommath/bn_mp_montgomery_reduce.c Mon Sep 16 15:50:38 2019 +0200 @@ -1,4 +1,4 @@ -#include <tommath_private.h> +#include "tommath_private.h" #ifdef BN_MP_MONTGOMERY_REDUCE_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * @@ -9,110 +9,107 @@ * Michael Fromberger but has been written from scratch with * additional optimizations in place. * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, [email protected], http://libtom.org + * SPDX-License-Identifier: Unlicense */ /* computes xR**-1 == x (mod N) via Montgomery Reduction */ -int -mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho) +int mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho) { - int ix, res, digs; - mp_digit mu; + int ix, res, digs; + mp_digit mu; - /* can the fast reduction [comba] method be used? - * - * Note that unlike in mul you're safely allowed *less* - * than the available columns [255 per default] since carries - * are fixed up in the inner loop. - */ - digs = (n->used * 2) + 1; - if ((digs < MP_WARRAY) && - (n->used < - (1 << ((CHAR_BIT * sizeof(mp_word)) - (2 * DIGIT_BIT))))) { - return fast_mp_montgomery_reduce (x, n, rho); - } + /* can the fast reduction [comba] method be used? + * + * Note that unlike in mul you're safely allowed *less* + * than the available columns [255 per default] since carries + * are fixed up in the inner loop. + */ + digs = (n->used * 2) + 1; + if ((digs < (int)MP_WARRAY) && + (x->used <= (int)MP_WARRAY) && + (n->used < + (int)(1u << (((size_t)CHAR_BIT * sizeof(mp_word)) - (2u * (size_t)DIGIT_BIT))))) { + return fast_mp_montgomery_reduce(x, n, rho); + } - /* grow the input as required */ - if (x->alloc < digs) { - if ((res = mp_grow (x, digs)) != MP_OKAY) { - return res; - } - } - x->used = digs; + /* grow the input as required */ + if (x->alloc < digs) { + if ((res = mp_grow(x, digs)) != MP_OKAY) { + return res; + } + } + x->used = digs; - for (ix = 0; ix < n->used; ix++) { - /* mu = ai * rho mod b - * - * The value of rho must be precalculated via - * montgomery_setup() such that - * it equals -1/n0 mod b this allows the - * following inner loop to reduce the - * input one digit at a time - */ - mu = (mp_digit) (((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK); + for (ix = 0; ix < n->used; ix++) { + /* mu = ai * rho mod b + * + * The value of rho must be precalculated via + * montgomery_setup() such that + * it equals -1/n0 mod b this allows the + * following inner loop to reduce the + * input one digit at a time + */ + mu = (mp_digit)(((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK); - /* a = a + mu * m * b**i */ - { - int iy; - mp_digit *tmpn, *tmpx, u; - mp_word r; + /* a = a + mu * m * b**i */ + { + int iy; + mp_digit *tmpn, *tmpx, u; + mp_word r; - /* alias for digits of the modulus */ - tmpn = n->dp; + /* alias for digits of the modulus */ + tmpn = n->dp; - /* alias for the digits of x [the input] */ - tmpx = x->dp + ix; + /* alias for the digits of x [the input] */ + tmpx = x->dp + ix; - /* set the carry to zero */ - u = 0; + /* set the carry to zero */ + u = 0; - /* Multiply and add in place */ - for (iy = 0; iy < n->used; iy++) { - /* compute product and sum */ - r = ((mp_word)mu * (mp_word)*tmpn++) + - (mp_word) u + (mp_word) *tmpx; + /* Multiply and add in place */ + for (iy = 0; iy < n->used; iy++) { + /* compute product and sum */ + r = ((mp_word)mu * (mp_word)*tmpn++) + + (mp_word)u + (mp_word)*tmpx; - /* get carry */ - u = (mp_digit)(r >> ((mp_word) DIGIT_BIT)); + /* get carry */ + u = (mp_digit)(r >> (mp_word)DIGIT_BIT); - /* fix digit */ - *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK)); - } - /* At this point the ix'th digit of x should be zero */ + /* fix digit */ + *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK); + } + /* At this point the ix'th digit of x should be zero */ - /* propagate carries upwards as required*/ - while (u != 0) { - *tmpx += u; - u = *tmpx >> DIGIT_BIT; - *tmpx++ &= MP_MASK; + /* propagate carries upwards as required*/ + while (u != 0u) { + *tmpx += u; + u = *tmpx >> DIGIT_BIT; + *tmpx++ &= MP_MASK; + } } - } - } + } - /* at this point the n.used'th least - * significant digits of x are all zero - * which means we can shift x to the - * right by n.used digits and the - * residue is unchanged. - */ + /* at this point the n.used'th least + * significant digits of x are all zero + * which means we can shift x to the + * right by n.used digits and the + * residue is unchanged. + */ - /* x = x/b**n.used */ - mp_clamp(x); - mp_rshd (x, n->used); + /* x = x/b**n.used */ + mp_clamp(x); + mp_rshd(x, n->used); - /* if x >= n then x = x - n */ - if (mp_cmp_mag (x, n) != MP_LT) { - return s_mp_sub (x, n, x); - } + /* if x >= n then x = x - n */ + if (mp_cmp_mag(x, n) != MP_LT) { + return s_mp_sub(x, n, x); + } - return MP_OKAY; + return MP_OKAY; } #endif -/* ref: $Format:%D$ */ -/* git commit: $Format:%H$ */ -/* commit time: $Format:%ai$ */ +/* ref: HEAD -> master, tag: v1.1.0 */ +/* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ +/* commit time: 2019-01-28 20:32:32 +0100 */