lib/mpi/mpi-inv.c

   1 /* mpi-inv.c  -  MPI functions
   2  * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3  *
   4  * This file is part of GnuPG.
   5  *
   6  * GnuPG is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * GnuPG is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  19  */
  20
  21 #include "mpi-internal.h"
  22
  23 /****************
  24  * Calculate the multiplicative inverse X of A mod N
  25  * That is: Find the solution x for
  26  *              1 = (a*x) mod n
  27  */
  28 int mpi_invm(MPI x, const MPI a, const MPI n)
  29 {
  30         /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
  31          * modified according to Michael Penk's solution for Exercice 35
  32          * with further enhancement */
  33         MPI u = NULL, v = NULL;
  34         MPI u1 = NULL, u2 = NULL, u3 = NULL;
  35         MPI v1 = NULL, v2 = NULL, v3 = NULL;
  36         MPI t1 = NULL, t2 = NULL, t3 = NULL;
  37         unsigned k;
  38         int sign;
  39         int odd = 0;
  40         int rc = -ENOMEM;
  41
  42         if (mpi_copy(&u, a) < 0)
  43                 goto cleanup;
  44         if (mpi_copy(&v, n) < 0)
  45                 goto cleanup;
  46
  47         for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) {
  48                 if (mpi_rshift(u, u, 1) < 0)
  49                         goto cleanup;
  50                 if (mpi_rshift(v, v, 1) < 0)
  51                         goto cleanup;
  52         }
  53         odd = mpi_test_bit(v, 0);
  54
  55         u1 = mpi_alloc_set_ui(1);
  56         if (!u1)
  57                 goto cleanup;
  58         if (!odd) {
  59                 u2 = mpi_alloc_set_ui(0);
  60                 if (!u2)
  61                         goto cleanup;
  62         }
  63         if (mpi_copy(&u3, u) < 0)
  64                 goto cleanup;
  65         if (mpi_copy(&v1, v) < 0)
  66                 goto cleanup;
  67         if (!odd) {
  68                 v2 = mpi_alloc(mpi_get_nlimbs(u));
  69                 if (!v2)
  70                         goto cleanup;
  71                 if (mpi_sub(v2, u1, u) < 0)
  72                         goto cleanup;   /* U is used as const 1 */
  73         }
  74         if (mpi_copy(&v3, v) < 0)
  75                 goto cleanup;
  76         if (mpi_test_bit(u, 0)) {       /* u is odd */
  77                 t1 = mpi_alloc_set_ui(0);
  78                 if (!t1)
  79                         goto cleanup;
  80                 if (!odd) {
  81                         t2 = mpi_alloc_set_ui(1);
  82                         if (!t2)
  83                                 goto cleanup;
  84                         t2->sign = 1;
  85                 }
  86                 if (mpi_copy(&t3, v) < 0)
  87                         goto cleanup;
  88                 t3->sign = !t3->sign;
  89                 goto Y4;
  90         } else {
  91                 t1 = mpi_alloc_set_ui(1);
  92                 if (!t1)
  93                         goto cleanup;
  94                 if (!odd) {
  95                         t2 = mpi_alloc_set_ui(0);
  96                         if (!t2)
  97                                 goto cleanup;
  98                 }
  99                 if (mpi_copy(&t3, u) < 0)
 100                         goto cleanup;
 101         }
 102         do {
 103                 do {
 104                         if (!odd) {
 105                                 if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) {       /* one is odd */
 106                                         if (mpi_add(t1, t1, v) < 0)
 107                                                 goto cleanup;
 108                                         if (mpi_sub(t2, t2, u) < 0)
 109                                                 goto cleanup;
 110                                 }
 111                                 if (mpi_rshift(t1, t1, 1) < 0)
 112                                         goto cleanup;
 113                                 if (mpi_rshift(t2, t2, 1) < 0)
 114                                         goto cleanup;
 115                                 if (mpi_rshift(t3, t3, 1) < 0)
 116                                         goto cleanup;
 117                         } else {
 118                                 if (mpi_test_bit(t1, 0))
 119                                         if (mpi_add(t1, t1, v) < 0)
 120                                                 goto cleanup;
 121                                 if (mpi_rshift(t1, t1, 1) < 0)
 122                                         goto cleanup;
 123                                 if (mpi_rshift(t3, t3, 1) < 0)
 124                                         goto cleanup;
 125                         }
 126 Y4:
 127                         ;
 128                 } while (!mpi_test_bit(t3, 0)); /* while t3 is even */
 129
 130                 if (!t3->sign) {
 131                         if (mpi_set(u1, t1) < 0)
 132                                 goto cleanup;
 133                         if (!odd)
 134                                 if (mpi_set(u2, t2) < 0)
 135                                         goto cleanup;
 136                         if (mpi_set(u3, t3) < 0)
 137                                 goto cleanup;
 138                 } else {
 139                         if (mpi_sub(v1, v, t1) < 0)
 140                                 goto cleanup;
 141                         sign = u->sign;
 142                         u->sign = !u->sign;
 143                         if (!odd)
 144                                 if (mpi_sub(v2, u, t2) < 0)
 145                                         goto cleanup;
 146                         u->sign = sign;
 147                         sign = t3->sign;
 148                         t3->sign = !t3->sign;
 149                         if (mpi_set(v3, t3) < 0)
 150                                 goto cleanup;
 151                         t3->sign = sign;
 152                 }
 153                 if (mpi_sub(t1, u1, v1) < 0)
 154                         goto cleanup;
 155                 if (!odd)
 156                         if (mpi_sub(t2, u2, v2) < 0)
 157                                 goto cleanup;
 158                 if (mpi_sub(t3, u3, v3) < 0)
 159                         goto cleanup;
 160                 if (t1->sign) {
 161                         if (mpi_add(t1, t1, v) < 0)
 162                                 goto cleanup;
 163                         if (!odd)
 164                                 if (mpi_sub(t2, t2, u) < 0)
 165                                         goto cleanup;
 166                 }
 167         } while (mpi_cmp_ui(t3, 0));    /* while t3 != 0 */
 168         /* mpi_lshift( u3, k ); */
 169         rc = mpi_set(x, u1);
 170
 171 cleanup:
 172         mpi_free(u1);
 173         mpi_free(v1);
 174         mpi_free(t1);
 175         if (!odd) {
 176                 mpi_free(u2);
 177                 mpi_free(v2);
 178                 mpi_free(t2);
 179         }
 180         mpi_free(u3);
 181         mpi_free(v3);
 182         mpi_free(t3);
 183
 184         mpi_free(u);
 185         mpi_free(v);
 186         return rc;
 187 }