Coverage Report

Created: 2023-09-25 06:08

/src/dropbear/libtommath/bn_mp_montgomery_setup.c
Line
Count
Source (jump to first uncovered line)
1
#include "tommath_private.h"
2
#ifdef BN_MP_MONTGOMERY_SETUP_C
3
/* LibTomMath, multiple-precision integer library -- Tom St Denis */
4
/* SPDX-License-Identifier: Unlicense */
5
6
/* setups the montgomery reduction stuff */
7
mp_err mp_montgomery_setup(const mp_int *n, mp_digit *rho)
8
3.32k
{
9
3.32k
   mp_digit x, b;
10
11
   /* fast inversion mod 2**k
12
    *
13
    * Based on the fact that
14
    *
15
    * XA = 1 (mod 2**n)  =>  (X(2-XA)) A = 1 (mod 2**2n)
16
    *                    =>  2*X*A - X*X*A*A = 1
17
    *                    =>  2*(1) - (1)     = 1
18
    */
19
3.32k
   b = n->dp[0];
20
21
3.32k
   if ((b & 1u) == 0u) {
22
0
      return MP_VAL;
23
0
   }
24
25
3.32k
   x = (((b + 2u) & 4u) << 1) + b; /* here x*a==1 mod 2**4 */
26
3.32k
   x *= 2u - (b * x);              /* here x*a==1 mod 2**8 */
27
3.32k
#if !defined(MP_8BIT)
28
3.32k
   x *= 2u - (b * x);              /* here x*a==1 mod 2**16 */
29
3.32k
#endif
30
3.32k
#if defined(MP_64BIT) || !(defined(MP_8BIT) || defined(MP_16BIT))
31
3.32k
   x *= 2u - (b * x);              /* here x*a==1 mod 2**32 */
32
3.32k
#endif
33
3.32k
#ifdef MP_64BIT
34
3.32k
   x *= 2u - (b * x);              /* here x*a==1 mod 2**64 */
35
3.32k
#endif
36
37
   /* rho = -1/m mod b */
38
3.32k
   *rho = (mp_digit)(((mp_word)1 << (mp_word)MP_DIGIT_BIT) - x) & MP_MASK;
39
40
3.32k
   return MP_OKAY;
41
3.32k
}
42
#endif