userapps/opensource/sshd/libtommath/bn_mp_invmod.c

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