Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_S_MP_INVMOD_SLOW_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* hac 14.61, pp608 */
       7           0 : mp_err s_mp_invmod_slow(const mp_int *a, const mp_int *b, mp_int *c)
       8             : {
       9             :    mp_int  x, y, u, v, A, B, C, D;
      10             :    mp_err  err;
      11             : 
      12             :    /* b cannot be negative */
      13           0 :    if ((b->sign == MP_NEG) || MP_IS_ZERO(b)) {
      14           0 :       return MP_VAL;
      15             :    }
      16             : 
      17             :    /* init temps */
      18           0 :    if ((err = mp_init_multi(&x, &y, &u, &v,
      19             :                             &A, &B, &C, &D, NULL)) != MP_OKAY) {
      20           0 :       return err;
      21             :    }
      22             : 
      23             :    /* x = a, y = b */
      24           0 :    if ((err = mp_mod(a, b, &x)) != MP_OKAY)                       goto LBL_ERR;
      25           0 :    if ((err = mp_copy(b, &y)) != MP_OKAY)                         goto LBL_ERR;
      26             : 
      27             :    /* 2. [modified] if x,y are both even then return an error! */
      28           0 :    if (MP_IS_EVEN(&x) && MP_IS_EVEN(&y)) {
      29           0 :       err = MP_VAL;
      30           0 :       goto LBL_ERR;
      31             :    }
      32             : 
      33             :    /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
      34           0 :    if ((err = mp_copy(&x, &u)) != MP_OKAY)                        goto LBL_ERR;
      35           0 :    if ((err = mp_copy(&y, &v)) != MP_OKAY)                        goto LBL_ERR;
      36           0 :    mp_set(&A, 1uL);
      37           0 :    mp_set(&D, 1uL);
      38             : 
      39           0 : top:
      40             :    /* 4.  while u is even do */
      41           0 :    while (MP_IS_EVEN(&u)) {
      42             :       /* 4.1 u = u/2 */
      43           0 :       if ((err = mp_div_2(&u, &u)) != MP_OKAY)                    goto LBL_ERR;
      44             : 
      45             :       /* 4.2 if A or B is odd then */
      46           0 :       if (MP_IS_ODD(&A) || MP_IS_ODD(&B)) {
      47             :          /* A = (A+y)/2, B = (B-x)/2 */
      48           0 :          if ((err = mp_add(&A, &y, &A)) != MP_OKAY)               goto LBL_ERR;
      49           0 :          if ((err = mp_sub(&B, &x, &B)) != MP_OKAY)               goto LBL_ERR;
      50             :       }
      51             :       /* A = A/2, B = B/2 */
      52           0 :       if ((err = mp_div_2(&A, &A)) != MP_OKAY)                    goto LBL_ERR;
      53           0 :       if ((err = mp_div_2(&B, &B)) != MP_OKAY)                    goto LBL_ERR;
      54             :    }
      55             : 
      56             :    /* 5.  while v is even do */
      57           0 :    while (MP_IS_EVEN(&v)) {
      58             :       /* 5.1 v = v/2 */
      59           0 :       if ((err = mp_div_2(&v, &v)) != MP_OKAY)                    goto LBL_ERR;
      60             : 
      61             :       /* 5.2 if C or D is odd then */
      62           0 :       if (MP_IS_ODD(&C) || MP_IS_ODD(&D)) {
      63             :          /* C = (C+y)/2, D = (D-x)/2 */
      64           0 :          if ((err = mp_add(&C, &y, &C)) != MP_OKAY)               goto LBL_ERR;
      65           0 :          if ((err = mp_sub(&D, &x, &D)) != MP_OKAY)               goto LBL_ERR;
      66             :       }
      67             :       /* C = C/2, D = D/2 */
      68           0 :       if ((err = mp_div_2(&C, &C)) != MP_OKAY)                    goto LBL_ERR;
      69           0 :       if ((err = mp_div_2(&D, &D)) != MP_OKAY)                    goto LBL_ERR;
      70             :    }
      71             : 
      72             :    /* 6.  if u >= v then */
      73           0 :    if (mp_cmp(&u, &v) != MP_LT) {
      74             :       /* u = u - v, A = A - C, B = B - D */
      75           0 :       if ((err = mp_sub(&u, &v, &u)) != MP_OKAY)                  goto LBL_ERR;
      76             : 
      77           0 :       if ((err = mp_sub(&A, &C, &A)) != MP_OKAY)                  goto LBL_ERR;
      78             : 
      79           0 :       if ((err = mp_sub(&B, &D, &B)) != MP_OKAY)                  goto LBL_ERR;
      80             :    } else {
      81             :       /* v - v - u, C = C - A, D = D - B */
      82           0 :       if ((err = mp_sub(&v, &u, &v)) != MP_OKAY)                  goto LBL_ERR;
      83             : 
      84           0 :       if ((err = mp_sub(&C, &A, &C)) != MP_OKAY)                  goto LBL_ERR;
      85             : 
      86           0 :       if ((err = mp_sub(&D, &B, &D)) != MP_OKAY)                  goto LBL_ERR;
      87             :    }
      88             : 
      89             :    /* if not zero goto step 4 */
      90           0 :    if (!MP_IS_ZERO(&u)) {
      91           0 :       goto top;
      92             :    }
      93             : 
      94             :    /* now a = C, b = D, gcd == g*v */
      95             : 
      96             :    /* if v != 1 then there is no inverse */
      97           0 :    if (mp_cmp_d(&v, 1uL) != MP_EQ) {
      98           0 :       err = MP_VAL;
      99           0 :       goto LBL_ERR;
     100             :    }
     101             : 
     102             :    /* if its too low */
     103           0 :    while (mp_cmp_d(&C, 0uL) == MP_LT) {
     104           0 :       if ((err = mp_add(&C, b, &C)) != MP_OKAY)                   goto LBL_ERR;
     105             :    }
     106             : 
     107             :    /* too big */
     108           0 :    while (mp_cmp_mag(&C, b) != MP_LT) {
     109           0 :       if ((err = mp_sub(&C, b, &C)) != MP_OKAY)                   goto LBL_ERR;
     110             :    }
     111             : 
     112             :    /* C is now the inverse */
     113           0 :    mp_exch(&C, c);
     114           0 :    err = MP_OKAY;
     115           0 : LBL_ERR:
     116           0 :    mp_clear_multi(&x, &y, &u, &v, &A, &B, &C, &D, NULL);
     117           0 :    return err;
     118             : }
     119             : #endif