bignum.c

   1 /* bignum.c
   2  *
   3  * bignum operations that are missing from gmp.
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2001 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  23  * MA 02111-1301, USA.
  24  */
  25
  26 #if HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <assert.h>
  31 #include <string.h>
  32
  33 #include "bignum.h"
  34
  35 /* Two's complement negation means that -x = ~x + 1, ~x = -(x+1),
  36  * and we use that x = ~~x = ~(-x-1).
  37  *
  38  * Examples:
  39  *
  40  *   x  ~x = -x+1     ~~x = x
  41  *  -1          0          ff
  42  *  -2          1          fe
  43  * -7f         7e          81
  44  * -80         7f          80
  45  * -81         80        ff7f
  46  */
  47
  48 /* Including extra sign bit, if needed. Also one byte for zero. */
  49 unsigned
  50 nettle_mpz_sizeinbase_256_s(const mpz_t x)
  51 {
  52   if (mpz_sgn(x) >= 0)
  53     return 1 + mpz_sizeinbase(x, 2) / 8;
  54   else
  55     {
  56       /* We'll output ~~x, so we need as many bits as for ~x */
  57       unsigned size;
  58       mpz_t c;
  59
  60       mpz_init(c);
  61       mpz_com(c, x); /* Same as c = - x - 1 = |x| + 1 */
  62       size = 1 + mpz_sizeinbase(c,2) / 8;
  63       mpz_clear(c);
  64
  65       return size;
  66     }
  67 }
  68
  69 unsigned
  70 nettle_mpz_sizeinbase_256_u(const mpz_t x)
  71 {
  72   return (mpz_sizeinbase(x,2) + 7) / 8;
  73 }
  74
  75 static void
  76 nettle_mpz_to_octets(unsigned length, uint8_t *s,
  77                      const mpz_t x, uint8_t sign)
  78 {
  79   uint8_t *dst = s + length - 1;
  80   unsigned size = mpz_size(x);
  81   unsigned i;
  82
  83   for (i = 0; i<size; i++)
  84     {
  85       mp_limb_t limb = mpz_getlimbn(x, i);
  86       unsigned j;
  87
  88       for (j = 0; length && j < sizeof(mp_limb_t); j++)
  89         {
  90           *dst-- = sign ^ (limb & 0xff);
  91           limb >>= 8;
  92           length--;
  93         }
  94     }
  95
  96   if (length)
  97     memset(s, sign, length);
  98 }
  99
 100 void
 101 nettle_mpz_get_str_256(unsigned length, uint8_t *s, const mpz_t x)
 102 {
 103   if (!length)
 104     {
 105       /* x must be zero */
 106       assert(!mpz_sgn(x));
 107       return;
 108     }
 109
 110   if (mpz_sgn(x) >= 0)
 111     {
 112       assert(nettle_mpz_sizeinbase_256_u(x) <= length);
 113       nettle_mpz_to_octets(length, s, x, 0);
 114     }
 115   else
 116     {
 117       mpz_t c;
 118       mpz_init(c);
 119       mpz_com(c, x);
 120
 121       assert(nettle_mpz_sizeinbase_256_u(c) <= length);
 122       nettle_mpz_to_octets(length, s, c, 0xff);
 123
 124       mpz_clear(c);
 125     }
 126 }
 127
 128 /* Converting from strings */
 129
 130 #ifdef mpz_import
 131 /* Was introduced in GMP-4.1 */
 132 # define nettle_mpz_from_octets(x, length, s) \
 133    mpz_import((x), (length), 1, 1, 0, 0, (s))
 134 #else
 135 static void
 136 nettle_mpz_from_octets(mpz_t x,
 137                        unsigned length, const uint8_t *s)
 138 {
 139   unsigned i;
 140
 141   mpz_set_ui(x, 0);
 142
 143   for (i = 0; i < length; i++)
 144     {
 145       mpz_mul_2exp(x, x, 8);
 146       mpz_add_ui(x, x, s[i]);
 147     }
 148 }
 149 #endif
 150
 151 void
 152 nettle_mpz_set_str_256_u(mpz_t x,
 153                          unsigned length, const uint8_t *s)
 154 {
 155   nettle_mpz_from_octets(x, length, s);
 156 }
 157
 158 void
 159 nettle_mpz_init_set_str_256_u(mpz_t x,
 160                               unsigned length, const uint8_t *s)
 161 {
 162   mpz_init(x);
 163   nettle_mpz_from_octets(x, length, s);
 164 }
 165
 166 void
 167 nettle_mpz_set_str_256_s(mpz_t x,
 168                          unsigned length, const uint8_t *s)
 169 {
 170   if (!length)
 171     {
 172       mpz_set_ui(x, 0);
 173       return;
 174     }
 175
 176   nettle_mpz_from_octets(x, length, s);
 177
 178   if (s[0] & 0x80)
 179     {
 180       mpz_t t;
 181
 182       mpz_init_set_ui(t, 1);
 183       mpz_mul_2exp(t, t, length*8);
 184       mpz_sub(x, x, t);
 185       mpz_clear(t);
 186     }
 187 }
 188
 189 void
 190 nettle_mpz_init_set_str_256_s(mpz_t x,
 191                               unsigned length, const uint8_t *s)
 192 {
 193   mpz_init(x);
 194   nettle_mpz_set_str_256_s(x, length, s);
 195 }