From fbd10abc057453789017f11c7f1fc8e6c61b79a3 Mon Sep 17 00:00:00 2001
From: NIIBE Yutaka <gniibe@fsij.org>
Date: Tue, 4 Apr 2017 17:38:05 +0900
Subject: [PATCH] mpi: Simplify mpi_powm.

* mpi/mpi-pow.c (_gcry_mpi_powm): Simplify the loop.

--

This fix is not a solution for the problem reported (yet).  The
problem is that the current algorithm of _gcry_mpi_powm depends on
exponent and some information leaks is possible.

Reported-by: Andreas Zankl <andreas.zankl@aisec.fraunhofer.de>
Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>

(backport from master commit:
719468e53133d3bdf12156c5bfdea2bf15f9f6f1)
---
 mpi/mpi-pow.c | 105 +++++++++++++++++-----------------------------------------
 1 file changed, 30 insertions(+), 75 deletions(-)

Index: libgcrypt20-1.6.5/mpi/mpi-pow.c
===================================================================
--- libgcrypt20-1.6.5.orig/mpi/mpi-pow.c	2017-07-03 08:16:07.341489918 -0400
+++ libgcrypt20-1.6.5/mpi/mpi-pow.c	2017-07-03 08:16:07.341489918 -0400
@@ -613,12 +613,8 @@ _gcry_mpi_powm (gcry_mpi_t res,
       if (e == 0)
         {
           j += c;
-          i--;
-          if ( i < 0 )
-            {
-              c = 0;
-              break;
-            }
+          if ( --i < 0 )
+            break;
 
           e = ep[i];
           c = BITS_PER_MPI_LIMB;
@@ -633,38 +629,33 @@ _gcry_mpi_powm (gcry_mpi_t res,
           c -= c0;
           j += c0;
 
+          e0 = (e >> (BITS_PER_MPI_LIMB - W));
           if (c >= W)
-            {
-              e0 = (e >> (BITS_PER_MPI_LIMB - W));
-              e = (e << W);
-              c -= W;
-            }
+            c0 = 0;
           else
             {
-              i--;
-              if ( i < 0 )
+              if ( --i < 0 )
                 {
-                  e = (e >> (BITS_PER_MPI_LIMB - c));
-                  break;
+                  e0 = (e >> (BITS_PER_MPI_LIMB - c));
+                  j += c - W;
+                  goto last_step;
+                }
+              else
+                {
+                  c0 = c;
+                  e = ep[i];
+                  c = BITS_PER_MPI_LIMB;
+                  e0 |= (e >> (BITS_PER_MPI_LIMB - (W - c0)));
                 }
-
-              c0 = c;
-              e0 = (e >> (BITS_PER_MPI_LIMB - W))
-                | (ep[i] >> (BITS_PER_MPI_LIMB - W + c0));
-              e = (ep[i] << (W - c0));
-              c = BITS_PER_MPI_LIMB - W + c0;
             }
 
+          e = e << (W - c0);
+          c -= (W - c0);
+
+        last_step:
           count_trailing_zeros (c0, e0);
           e0 = (e0 >> c0) >> 1;
 
-          for (j += W - c0; j; j--)
-            {
-              mul_mod (xp, &xsize, rp, rsize, rp, rsize, mp, msize, &karactx);
-              tp = rp; rp = xp; xp = tp;
-              rsize = xsize;
-            }
-
           /*
            *  base_u <= precomp[e0]
            *  base_u_size <= precomp_size[e0]
@@ -681,25 +672,23 @@ _gcry_mpi_powm (gcry_mpi_t res,
               u.d = precomp[k];
 
               mpi_set_cond (&w, &u, k == e0);
-              base_u_size |= (precomp_size[k] & ((mpi_size_t)0 - (k == e0)) );
+              base_u_size |= ( precomp_size[k] & ((mpi_size_t)0 - (k == e0)) );
             }
 
-          mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
-                   mp, msize, &karactx);
-          tp = rp; rp = xp; xp = tp;
-          rsize = xsize;
+          for (j += W - c0; j >= 0; j--)
+            {
+              mul_mod (xp, &xsize, rp, rsize,
+                       j == 0 ? base_u : rp, j == 0 ? base_u_size : rsize,
+                       mp, msize, &karactx);
+              tp = rp; rp = xp; xp = tp;
+              rsize = xsize;
+            }
 
           j = c0;
+          if ( i < 0 )
+            break;
         }
 
-    if (c != 0)
-      {
-        j += c;
-        count_trailing_zeros (c, e);
-        e = (e >> c);
-        j -= c;
-      }
-
     while (j--)
       {
         mul_mod (xp, &xsize, rp, rsize, rp, rsize, mp, msize, &karactx);
@@ -707,40 +696,6 @@ _gcry_mpi_powm (gcry_mpi_t res,
         rsize = xsize;
       }
 
-    if (e != 0)
-      {
-        /*
-         * base_u <= precomp[(e>>1)]
-         * base_u_size <= precomp_size[(e>>1)]
-         */
-        base_u_size = 0;
-        for (k = 0; k < (1<< (W - 1)); k++)
-          {
-            struct gcry_mpi w, u;
-            w.alloced = w.nlimbs = precomp_size[k];
-            u.alloced = u.nlimbs = precomp_size[k];
-            w.sign = u.sign = 0;
-            w.flags = u.flags = 0;
-            w.d = base_u;
-            u.d = precomp[k];
-
-            mpi_set_cond (&w, &u, k == (e>>1));
-            base_u_size |= (precomp_size[k] & ((mpi_size_t)0 - (k == (e>>1))) );
-          }
-
-        mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
-                 mp, msize, &karactx);
-        tp = rp; rp = xp; xp = tp;
-        rsize = xsize;
-
-        for (; c; c--)
-          {
-            mul_mod (xp, &xsize, rp, rsize, rp, rsize, mp, msize, &karactx);
-            tp = rp; rp = xp; xp = tp;
-            rsize = xsize;
-          }
-      }
-
     /* We shifted MOD, the modulo reduction argument, left
        MOD_SHIFT_CNT steps.  Adjust the result by reducing it with the
        original MOD.