bignum.c 3.99 KB
Newer Older
1 2 3 4 5 6 7
/* bignum.c
 *
 * bignum operations that are missing from gmp.
 */

/* nettle, low-level cryptographics library
 *
Niels Möller's avatar
Niels Möller committed
8
 * Copyright (C) 2001 Niels Möller
9 10 11 12 13 14 15 16 17 18 19 20 21
 *  
 * The nettle library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 * 
 * The nettle library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
22 23
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02111-1301, USA.
24 25 26
 */

#if HAVE_CONFIG_H
27
# include "config.h"
28 29 30 31 32
#endif

#include <assert.h>
#include <string.h>

33 34
#include "bignum.h"

35 36 37 38 39 40 41 42 43 44 45 46 47 48
/* Two's complement negation means that -x = ~x + 1, ~x = -(x+1),
 * and we use that x = ~~x = ~(-x-1).
 *
 * Examples:
 *
 *   x  ~x = -x+1     ~~x = x
 *  -1          0          ff
 *  -2          1          fe
 * -7f         7e          81
 * -80         7f          80
 * -81         80        ff7f
 */

/* Including extra sign bit, if needed. Also one byte for zero. */
49
size_t
50
nettle_mpz_sizeinbase_256_s(const mpz_t x)
51
{
52 53 54 55 56
  if (mpz_sgn(x) >= 0)
    return 1 + mpz_sizeinbase(x, 2) / 8;
  else
    {
      /* We'll output ~~x, so we need as many bits as for ~x */
57
      size_t size;
58 59 60 61 62 63 64 65 66
      mpz_t c;

      mpz_init(c);
      mpz_com(c, x); /* Same as c = - x - 1 = |x| + 1 */
      size = 1 + mpz_sizeinbase(c,2) / 8;
      mpz_clear(c);

      return size;
    }
67 68
}

69
size_t
70 71 72 73 74 75
nettle_mpz_sizeinbase_256_u(const mpz_t x)
{
  return (mpz_sizeinbase(x,2) + 7) / 8;
}

static void
76
nettle_mpz_to_octets(size_t length, uint8_t *s,
77
		     const mpz_t x, uint8_t sign)
78 79
{
  uint8_t *dst = s + length - 1;
80 81
  size_t size = mpz_size(x);
  size_t i;
82 83 84 85
  
  for (i = 0; i<size; i++)
    {
      mp_limb_t limb = mpz_getlimbn(x, i);
86
      size_t j;
87 88 89

      for (j = 0; length && j < sizeof(mp_limb_t); j++)
        {
90
          *dst-- = sign ^ (limb & 0xff);
91 92 93 94 95 96
          limb >>= 8;
          length--;
	}
    }
  
  if (length)
97
    memset(s, sign, length);
98 99 100
}

void
101
nettle_mpz_get_str_256(size_t length, uint8_t *s, const mpz_t x)
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
{
  if (!length)
    {
      /* x must be zero */
      assert(!mpz_sgn(x));
      return;
    }

  if (mpz_sgn(x) >= 0)
    {
      assert(nettle_mpz_sizeinbase_256_u(x) <= length);
      nettle_mpz_to_octets(length, s, x, 0);
    }
  else
    {
      mpz_t c;
      mpz_init(c);
      mpz_com(c, x);
120

121 122 123 124 125 126 127 128
      assert(nettle_mpz_sizeinbase_256_u(c) <= length);
      nettle_mpz_to_octets(length, s, c, 0xff);

      mpz_clear(c);
    }
}

/* Converting from strings */
129 130 131 132 133 134

#ifdef mpz_import
/* Was introduced in GMP-4.1 */
# define nettle_mpz_from_octets(x, length, s) \
   mpz_import((x), (length), 1, 1, 0, 0, (s))
#else
135 136
static void
nettle_mpz_from_octets(mpz_t x,
137
		       size_t length, const uint8_t *s)
138
{
139
  size_t i;
140

141 142
  mpz_set_ui(x, 0);

143 144
  for (i = 0; i < length; i++)
    {
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
			 size_t length, const uint8_t *s)
154
{
155
  nettle_mpz_from_octets(x, length, s);
156 157 158 159
}

void
nettle_mpz_init_set_str_256_u(mpz_t x,
160
			      size_t length, const uint8_t *s)
161
{
162 163
  mpz_init(x);
  nettle_mpz_from_octets(x, length, s);
164 165 166 167
}

void
nettle_mpz_set_str_256_s(mpz_t x,
168
			 size_t length, const uint8_t *s)
169 170
{
  if (!length)
171 172 173 174
    {
      mpz_set_ui(x, 0);
      return;
    }
175
  
176 177
  nettle_mpz_from_octets(x, length, s);

178 179
  if (s[0] & 0x80)
    {
180 181 182 183 184 185
      mpz_t t;

      mpz_init_set_ui(t, 1);
      mpz_mul_2exp(t, t, length*8);
      mpz_sub(x, x, t);
      mpz_clear(t);
186 187 188 189 190
    }
}

void
nettle_mpz_init_set_str_256_s(mpz_t x,
191
			      size_t length, const uint8_t *s)
192 193
{
  mpz_init(x);
194
  nettle_mpz_set_str_256_s(x, length, s);
195
}