lib/nettle/wmnaf.c

   1 /*
   2  * Copyright (C) 2011-2012 Free Software Foundation, Inc.
   3  *
   4  * Author: Ilya Tumaykin
   5  *
   6  * This file is part of GNUTLS.
   7  *
   8  * The GNUTLS library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public License
  10  * as published by the Free Software Foundation; either version 3 of
  11  * the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  20  *
  21  */
  22
  23 #include <config.h>
  24
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27 #include <gmp.h>
  28
  29 #include "ecc.h"
  30
  31 /* needed constants */
  32 #define BASEW   (1 << WMNAF_WINSIZE)    /* 2^w */
  33 #define BASEWW  (1 << (WMNAF_WINSIZE + 1))      /* 2^(w+1) */
  34 #define WBITS   (BASEWW - 1)
  35
  36 #define ABS(x) ((x) >= 0 ? (x) : -(x))
  37
  38 /* GMP lacks this typedef in versions prior to 5 */
  39 #if __GNU_MP__ < 5
  40 typedef unsigned long int mp_bitcnt_t;
  41 #endif
  42
  43 /*
  44  * A local replacement for mpz_tstbit.
  45  * It is needed because original mpz_tstbit process negative numbers
  46  * in a two-complement manner and we don't want it.
  47  * This function mimics mpz_tstbit behavior for positive numbers in both cases.
  48  */
  49 static int
  50 mpz_unitstbit (mpz_t u, mp_bitcnt_t bit_index)
  51   __GMP_NOTHROW
  52 {
  53   mp_srcptr u_ptr = u->_mp_d;
  54   mp_size_t size = u->_mp_size;
  55   mp_size_t abs_size = ABS (size);
  56   mp_size_t limb_index = bit_index / GMP_NUMB_BITS;
  57   mp_srcptr p = u_ptr + limb_index;
  58   mp_limb_t limb;
  59
  60   if (limb_index >= abs_size)
  61     return (size < 0);
  62
  63   limb = *p;
  64
  65   return (limb >> (bit_index % GMP_NUMB_BITS)) & 1;
  66 }
  67
  68 /*
  69  * Return an array with wMNAF representation together with its length.
  70  * The result is the array with elements from the set {0, +-1, +-3, +-5, ..., +-(2^w - 1)}
  71  * such that at most one of any (w + 1) consecutive digits is non-zero
  72  * with exception for the the most significant (w + 1) bits.
  73  * With the last property it is modified version of wNAF.
  74  * Overview of this algorithm can be found, for exmaple, in
  75  * Bodo Moller, Improved Techniques for Fast Exponentiation.
  76  * Information Security and Cryptology – ICISC 2002, Springer-Verlag LNCS 2587, pp. 298–312
  77  */
  78 /*
  79    @param x        The number to get wMNAF for
  80    @param len      [out] Destination for the length of wMNAF
  81    @return         array with wMNAF representation
  82    @return         NULL in case of errors
  83  */
  84 signed char *
  85 ecc_wMNAF (mpz_t x, size_t * wmnaf_len)
  86 {
  87   int b, c;
  88   char sign = 1;
  89   size_t i, len;
  90
  91   signed char *ret = NULL;
  92
  93   if (!(sign = mpz_sgn (x)))
  94     {
  95       /* x == 0 */
  96       ret = malloc (1);
  97       if (ret == NULL)
  98         goto done;
  99
 100       ret[0] = 0;
 101       *wmnaf_len = 1;
 102       goto done;
 103     }
 104
 105   /* total number of bits */
 106   len = mpz_sizeinbase (x, 2);
 107
 108   /* wMNAF is at most (len + 1) bits long */
 109   ret = malloc (len + 1);
 110   if (ret == NULL)
 111     goto done;
 112
 113   /* get (w + 1) Least Significant Bits */
 114   c = (mpz_getlimbn (x, 0)) & WBITS;
 115
 116   /* how many bits we've already processed */
 117   i = 0;
 118
 119   while ((c != 0) || (i + WMNAF_WINSIZE + 1 < len))
 120     {
 121       if (c & 1)
 122         {
 123           /* LSB == 1 */
 124           if (c >= BASEW)
 125             {
 126               b = c - BASEWW;
 127             }
 128           else
 129             {
 130               b = c;
 131             }
 132
 133           c -= b;
 134         }
 135       else
 136         {
 137           b = 0;
 138         }
 139
 140       ret[i++] = sign * b;
 141
 142       /* fill c with next LSB */
 143       c >>= 1;
 144       c += BASEW * mpz_unitstbit (x, i + WMNAF_WINSIZE);
 145     }
 146
 147   *wmnaf_len = i--;
 148
 149   /* do modified wNAF
 150    * check if wNAF starts with 1 and
 151    * (w + 1)th bit is negative */
 152   if ((ret[i] == 1) && (ret[i - (WMNAF_WINSIZE + 1)] < 0))
 153     {
 154       ret[i - (WMNAF_WINSIZE + 1)] += BASEW;
 155       ret[i - 1] = 1;
 156       *wmnaf_len = i;
 157     }
 158 done:
 159   return ret;
 160 }