LCOV - code coverage report
Current view: top level - source4/heimdal/lib/hcrypto/libtommath - bn_mp_invmod_slow.c (source / functions) Hit Total Coverage
Test: coverage report for abartlet/fix-coverage dd10fb34 Lines: 0 71 0.0 %
Date: 2021-09-23 10:06:22 Functions: 0 1 0.0 %

          Line data    Source code
       1             : #include <tommath.h>
       2             : #ifdef BN_MP_INVMOD_SLOW_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis
       4             :  *
       5             :  * LibTomMath is a library that provides multiple-precision
       6             :  * integer arithmetic as well as number theoretic functionality.
       7             :  *
       8             :  * The library was designed directly after the MPI library by
       9             :  * Michael Fromberger but has been written from scratch with
      10             :  * additional optimizations in place.
      11             :  *
      12             :  * The library is free for all purposes without any express
      13             :  * guarantee it works.
      14             :  *
      15             :  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
      16             :  */
      17             : 
      18             : /* hac 14.61, pp608 */
      19           0 : int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c)
      20             : {
      21             :   mp_int  x, y, u, v, A, B, C, D;
      22             :   int     res;
      23             : 
      24             :   /* b cannot be negative */
      25           0 :   if (b->sign == MP_NEG || mp_iszero(b) == 1) {
      26           0 :     return MP_VAL;
      27             :   }
      28             : 
      29             :   /* init temps */
      30           0 :   if ((res = mp_init_multi(&x, &y, &u, &v,
      31             :                            &A, &B, &C, &D, NULL)) != MP_OKAY) {
      32           0 :      return res;
      33             :   }
      34             : 
      35             :   /* x = a, y = b */
      36           0 :   if ((res = mp_mod(a, b, &x)) != MP_OKAY) {
      37           0 :       goto LBL_ERR;
      38             :   }
      39           0 :   if ((res = mp_copy (b, &y)) != MP_OKAY) {
      40           0 :     goto LBL_ERR;
      41             :   }
      42             : 
      43             :   /* 2. [modified] if x,y are both even then return an error! */
      44           0 :   if (mp_iseven (&x) == 1 && mp_iseven (&y) == 1) {
      45           0 :     res = MP_VAL;
      46           0 :     goto LBL_ERR;
      47             :   }
      48             : 
      49             :   /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
      50           0 :   if ((res = mp_copy (&x, &u)) != MP_OKAY) {
      51           0 :     goto LBL_ERR;
      52             :   }
      53           0 :   if ((res = mp_copy (&y, &v)) != MP_OKAY) {
      54           0 :     goto LBL_ERR;
      55             :   }
      56           0 :   mp_set (&A, 1);
      57           0 :   mp_set (&D, 1);
      58             : 
      59           0 : top:
      60             :   /* 4.  while u is even do */
      61           0 :   while (mp_iseven (&u) == 1) {
      62             :     /* 4.1 u = u/2 */
      63           0 :     if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
      64           0 :       goto LBL_ERR;
      65             :     }
      66             :     /* 4.2 if A or B is odd then */
      67           0 :     if (mp_isodd (&A) == 1 || mp_isodd (&B) == 1) {
      68             :       /* A = (A+y)/2, B = (B-x)/2 */
      69           0 :       if ((res = mp_add (&A, &y, &A)) != MP_OKAY) {
      70           0 :          goto LBL_ERR;
      71             :       }
      72           0 :       if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
      73           0 :          goto LBL_ERR;
      74             :       }
      75             :     }
      76             :     /* A = A/2, B = B/2 */
      77           0 :     if ((res = mp_div_2 (&A, &A)) != MP_OKAY) {
      78           0 :       goto LBL_ERR;
      79             :     }
      80           0 :     if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
      81           0 :       goto LBL_ERR;
      82             :     }
      83             :   }
      84             : 
      85             :   /* 5.  while v is even do */
      86           0 :   while (mp_iseven (&v) == 1) {
      87             :     /* 5.1 v = v/2 */
      88           0 :     if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
      89           0 :       goto LBL_ERR;
      90             :     }
      91             :     /* 5.2 if C or D is odd then */
      92           0 :     if (mp_isodd (&C) == 1 || mp_isodd (&D) == 1) {
      93             :       /* C = (C+y)/2, D = (D-x)/2 */
      94           0 :       if ((res = mp_add (&C, &y, &C)) != MP_OKAY) {
      95           0 :          goto LBL_ERR;
      96             :       }
      97           0 :       if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
      98           0 :          goto LBL_ERR;
      99             :       }
     100             :     }
     101             :     /* C = C/2, D = D/2 */
     102           0 :     if ((res = mp_div_2 (&C, &C)) != MP_OKAY) {
     103           0 :       goto LBL_ERR;
     104             :     }
     105           0 :     if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
     106           0 :       goto LBL_ERR;
     107             :     }
     108             :   }
     109             : 
     110             :   /* 6.  if u >= v then */
     111           0 :   if (mp_cmp (&u, &v) != MP_LT) {
     112             :     /* u = u - v, A = A - C, B = B - D */
     113           0 :     if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
     114           0 :       goto LBL_ERR;
     115             :     }
     116             : 
     117           0 :     if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) {
     118           0 :       goto LBL_ERR;
     119             :     }
     120             : 
     121           0 :     if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
     122           0 :       goto LBL_ERR;
     123             :     }
     124             :   } else {
     125             :     /* v - v - u, C = C - A, D = D - B */
     126           0 :     if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
     127           0 :       goto LBL_ERR;
     128             :     }
     129             : 
     130           0 :     if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) {
     131           0 :       goto LBL_ERR;
     132             :     }
     133             : 
     134           0 :     if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
     135           0 :       goto LBL_ERR;
     136             :     }
     137             :   }
     138             : 
     139             :   /* if not zero goto step 4 */
     140           0 :   if (mp_iszero (&u) == 0)
     141           0 :     goto top;
     142             : 
     143             :   /* now a = C, b = D, gcd == g*v */
     144             : 
     145             :   /* if v != 1 then there is no inverse */
     146           0 :   if (mp_cmp_d (&v, 1) != MP_EQ) {
     147           0 :     res = MP_VAL;
     148           0 :     goto LBL_ERR;
     149             :   }
     150             : 
     151             :   /* if its too low */
     152           0 :   while (mp_cmp_d(&C, 0) == MP_LT) {
     153           0 :       if ((res = mp_add(&C, b, &C)) != MP_OKAY) {
     154           0 :          goto LBL_ERR;
     155             :       }
     156             :   }
     157             : 
     158             :   /* too big */
     159           0 :   while (mp_cmp_mag(&C, b) != MP_LT) {
     160           0 :       if ((res = mp_sub(&C, b, &C)) != MP_OKAY) {
     161           0 :          goto LBL_ERR;
     162             :       }
     163             :   }
     164             : 
     165             :   /* C is now the inverse */
     166           0 :   mp_exch (&C, c);
     167           0 :   res = MP_OKAY;
     168           0 : LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
     169           0 :   return res;
     170             : }
     171             : #endif
     172             : 
     173             : /* $Source: /cvs/libtom/libtommath/bn_mp_invmod_slow.c,v $ */
     174             : /* $Revision: 1.4 $ */
     175             : /* $Date: 2006/12/28 01:25:13 $ */

Generated by: LCOV version 1.13