release/src/router/matrixssl/src/crypto/peersec/mpi.h

   1 /*
   2  *      mpi.h
   3  *      Release $Name: MATRIXSSL_1_8_8_OPEN $
   4  *
   5  *      multiple-precision integer library
   6  */
   7 /*
   8  *      Copyright (c) PeerSec Networks, 2002-2009. All Rights Reserved.
   9  *      The latest version of this code is available at http://www.matrixssl.org
  10  *
  11  *      This software is open source; you can redistribute it and/or modify
  12  *      it under the terms of the GNU General Public License as published by
  13  *      the Free Software Foundation; either version 2 of the License, or
  14  *      (at your option) any later version.
  15  *
  16  *      This General Public License does NOT permit incorporating this software
  17  *      into proprietary programs.  If you are unable to comply with the GPL, a
  18  *      commercial license for this software may be purchased from PeerSec Networks
  19  *      at http://www.peersec.com
  20  *
  21  *      This program is distributed in WITHOUT ANY WARRANTY; without even the
  22  *      implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  23  *      See the GNU General Public License for more details.
  24  *
  25  *      You should have received a copy of the GNU General Public License
  26  *      along with this program; if not, write to the Free Software
  27  *      Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  28  *      http://www.gnu.org/copyleft/gpl.html
  29  */
  30 /******************************************************************************/
  31
  32
  33 #ifndef _h_MPI
  34 #define _h_MPI
  35
  36 #include <stdio.h>
  37 #include <string.h>
  38 #include <stdlib.h>
  39 #include <ctype.h>
  40 #include <limits.h>
  41
  42 #undef MIN
  43 #define MIN(x,y) ((x)<(y)?(x):(y))
  44 #undef MAX
  45 #define MAX(x,y) ((x)>(y)?(x):(y))
  46
  47 #ifdef __cplusplus
  48 extern "C" {
  49
  50
  51 /*
  52         C++ compilers don't like assigning void * to mp_digit *
  53  */
  54 #define  OPT_CAST(x)  (x *)
  55
  56 #else
  57
  58 /*
  59         C on the other hand doesn't care
  60  */
  61 #define  OPT_CAST(x)
  62
  63 #endif /* __cplusplus */
  64
  65 /******************************************************************************/
  66 /*
  67         some default configurations.
  68
  69         A "mp_digit" must be able to hold DIGIT_BIT + 1 bits
  70         A "mp_word" must be able to hold 2*DIGIT_BIT + 1 bits
  71
  72         At the very least a mp_digit must be able to hold 7 bits
  73         [any size beyond that is ok provided it doesn't overflow the data type]
  74  */
  75 #ifdef MP_8BIT
  76         typedef unsigned char           mp_digit;
  77         typedef unsigned short          mp_word;
  78 #elif defined(MP_16BIT)
  79         typedef unsigned short          mp_digit;
  80         typedef unsigned long           mp_word;
  81 #elif defined(MP_64BIT)
  82 /*
  83         for GCC only on supported platforms
  84  */
  85         #ifndef CRYPT
  86                 typedef unsigned long long      ulong64;
  87                 typedef signed long long        long64;
  88         #endif /* CRYPT */
  89
  90         typedef ulong64                         mp_digit;
  91         typedef unsigned long           mp_word __attribute__ ((mode(TI)));
  92
  93         #define DIGIT_BIT                       60
  94 #else  /* MP_8BIT */
  95 /*
  96         this is the default case, 28-bit digits
  97  */
  98         #ifndef CRYPT
  99                 #if defined(_MSC_VER) || defined(__BORLANDC__)
 100                         typedef unsigned __int64        ulong64;
 101                         typedef signed __int64          long64;
 102                 #else
 103                         typedef unsigned long long      ulong64;
 104                         typedef signed long long        long64;
 105                 #endif
 106         #endif /* CRYPT */
 107
 108         typedef unsigned long           mp_digit;
 109         typedef ulong64                         mp_word;
 110
 111         #ifdef MP_31BIT
 112 /*
 113                 this is an extension that uses 31-bit digits
 114  */
 115                 #define DIGIT_BIT               31
 116         #else /* MP_31BIT */
 117 /*
 118                 default case is 28-bit digits, defines MP_28BIT as a handy macro to test
 119  */
 120                 #define DIGIT_BIT               28
 121                 #define MP_28BIT
 122         #endif /* MP_31BIT */
 123 #endif /* MP_8BIT */
 124
 125 /*
 126         otherwise the bits per digit is calculated automatically from the size of
 127         a mp_digit
 128  */
 129 #ifndef DIGIT_BIT
 130         #define DIGIT_BIT       ((int32)((CHAR_BIT * sizeof(mp_digit) - 1)))    /* bits per digit */
 131 #endif /* DIGIT_BIT */
 132
 133 #define MP_DIGIT_BIT            DIGIT_BIT
 134 #define MP_MASK                         ((((mp_digit)1)<<((mp_digit)DIGIT_BIT))-((mp_digit)1))
 135 #define MP_DIGIT_MAX            MP_MASK
 136
 137 /******************************************************************************/
 138 /*
 139         equalities
 140  */
 141 #define MP_LT                   -1              /* less than */
 142 #define MP_EQ                   0               /* equal to */
 143 #define MP_GT                   1               /* greater than */
 144
 145 #define MP_ZPOS                 0               /* positive integer */
 146 #define MP_NEG                  1               /* negative */
 147
 148 #define MP_OKAY                 0               /* ok result */
 149 #define MP_MEM                  -2              /* out of mem */
 150 #define MP_VAL                  -3              /* invalid input */
 151 #define MP_RANGE                MP_VAL
 152
 153 #define MP_YES                  1               /* yes response */
 154 #define MP_NO                   0               /* no response */
 155
 156 typedef int32                           mp_err;
 157
 158 /******************************************************************************/
 159 /*
 160         various build options
 161  */
 162 #define MP_PREC                 64              /* default digits of precision */
 163
 164 /*
 165         define this to use lower memory usage routines (exptmods mostly)
 166  */
 167 #define MP_LOW_MEM
 168
 169 /*
 170         size of comba arrays, should be at least
 171         2 * 2**(BITS_PER_WORD - BITS_PER_DIGIT*2)
 172  */
 173 #define MP_WARRAY               (1 << (sizeof(mp_word) * CHAR_BIT - 2 * DIGIT_BIT + 1))
 174
 175 typedef struct  {
 176         int32 used, alloc, sign;
 177         mp_digit *dp;
 178 } mp_int;
 179
 180 #define USED(m)         ((m)->used)
 181 #define DIGIT(m,k)      ((m)->dp[(k)])
 182 #define SIGN(m)         ((m)->sign)
 183
 184 /******************************************************************************/
 185 /*
 186         init and deinit bignum functions
 187  */
 188
 189 /*
 190         init a bignum
 191  */
 192 extern int32 mp_init(psPool_t *pool, mp_int *a);
 193
 194 /*
 195         free a bignum
 196  */
 197 extern void mp_clear(mp_int *a);
 198
 199 /*
 200         init a series of arguments
 201  */
 202 extern int32 _mp_init_multi(psPool_t *pool, mp_int *mp0, mp_int *mp1, mp_int *mp2,
 203                                                         mp_int *mp3, mp_int *mp4, mp_int *mp5, mp_int *mp6,
 204                                                         mp_int *mp7);
 205
 206 /*
 207         clear a  series of arguments
 208  */
 209 extern void _mp_clear_multi(mp_int *mp0, mp_int *mp1, mp_int *mp2, mp_int *mp3,
 210                                         mp_int *mp4, mp_int *mp5, mp_int *mp6, mp_int *mp7);
 211
 212 /*
 213         exchange two ints
 214  */
 215 extern void mp_exch(mp_int *a, mp_int *b);
 216
 217 /*
 218         shrink ram required for a bignum
 219  */
 220 extern int32 mp_shrink(mp_int *a);
 221
 222 /*
 223         grow an int32 to a given size
 224  */
 225 extern int32 mp_grow(mp_int *a, int32 size);
 226
 227 /*
 228         init to a given number of digits
 229  */
 230 extern int32 mp_init_size(psPool_t *pool, mp_int *a, int32 size);
 231
 232 /******************************************************************************/
 233 /*
 234         Basic Manipulations
 235  */
 236 #define mp_iszero(a) (((a)->used == 0) ? MP_YES : MP_NO)
 237 #define mp_iseven(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 0)) ? MP_YES : MP_NO)
 238 #define mp_isodd(a)  (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? MP_YES : MP_NO)
 239
 240 extern int32 mp_add_d (mp_int * a, mp_digit b, mp_int * c);
 241 extern int32 mp_sub_d (mp_int * a, mp_digit b, mp_int * c);
 242 /*
 243         set to zero
 244  */
 245 extern void mp_zero(mp_int *a);
 246
 247 /*
 248         set to a digit
 249  */
 250 extern void mp_set(mp_int *a, mp_digit b);
 251
 252 /*
 253         copy, b = a
 254  */
 255 extern int32 mp_copy(mp_int *a, mp_int *b);
 256
 257 /*
 258         inits and copies, a = b
 259  */
 260 extern int32 mp_init_copy(psPool_t *pool, mp_int *a, mp_int *b);
 261
 262 /*
 263         trim unused digits
 264  */
 265 extern void mp_clamp(mp_int *a);
 266
 267 /******************************************************************************/
 268 /*
 269         digit manipulation
 270 */
 271
 272 /*
 273         right shift by "b" digits
 274  */
 275 extern void mp_rshd(mp_int *a, int32 b);
 276
 277 /*
 278         left shift by "b" digits
 279  */
 280 extern int32 mp_lshd(mp_int *a, int32 b);
 281
 282 /*
 283         c = a / 2**b
 284  */
 285 extern int32 mp_div_2d(psPool_t *pool, mp_int *a, int32 b, mp_int *c, mp_int *d);
 286
 287 /*
 288         b = a/2
 289  */
 290 extern int32 mp_div_2(mp_int *a, mp_int *b);
 291
 292 /*
 293         c = a * 2**b
 294  */
 295 extern int32 mp_mul_2d(mp_int *a, int32 b, mp_int *c);
 296
 297 /*
 298         c = a mod 2**d
 299  */
 300 extern int32 mp_mod_2d(mp_int *a, int32 b, mp_int *c);
 301
 302 /*
 303         computes a = 2**b
 304  */
 305 extern int32 mp_2expt(mp_int *a, int32 b);
 306
 307 /******************************************************************************/
 308 /*
 309         Basic arithmetic
 310  */
 311
 312 /*
 313         b = |a|
 314  */
 315 extern int32 mp_abs(mp_int *a, mp_int *b);
 316
 317 /*
 318         compare a to b
 319  */
 320 extern int32 mp_cmp(mp_int *a, mp_int *b);
 321
 322 /*
 323         compare |a| to |b|
 324  */
 325 extern int32 mp_cmp_mag(mp_int *a, mp_int *b);
 326
 327 /*
 328         c = a + b
 329  */
 330 extern int32 mp_add(mp_int *a, mp_int *b, mp_int *c);
 331
 332 /*
 333         c = a - b
 334  */
 335 extern int32 mp_sub(mp_int *a, mp_int *b, mp_int *c);
 336
 337 /*
 338         c = a * b
 339         b = a*a
 340  */
 341 /* moved mp_mul out of SLOW case */
 342 extern int32 mp_mul(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c);
 343 #ifdef USE_SMALL_WORD
 344 extern int32 mp_sqr(psPool_t *pool, mp_int *a, mp_int *b);
 345 #endif
 346
 347 /*
 348         a/b => cb + d == a
 349  */
 350 extern int32 mp_div(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c, mp_int *d);
 351
 352 /*
 353         c = a mod b, 0 <= c < b
 354  */
 355 extern int32 mp_mod(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c);
 356
 357 /******************************************************************************/
 358 /*
 359         single digit functions
 360  */
 361
 362 /*
 363         compare against a single digit
 364  */
 365 extern int32 mp_cmp_d(mp_int *a, mp_digit b);
 366
 367 /*
 368         c = a * b
 369  */
 370 extern int32 mp_mul_d(mp_int *a, mp_digit b, mp_int *c);
 371
 372 /******************************************************************************/
 373 /*
 374         number theory
 375  */
 376
 377 /*
 378         d = a + b (mod c)
 379  */
 380 extern int32 mp_addmod(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c, mp_int *d);
 381
 382 /*
 383         d = a * b (mod c)
 384  */
 385 extern int32 mp_mulmod(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c, mp_int *d);
 386
 387 /*
 388         c = 1/a (mod b)
 389  */
 390 extern int32 mp_invmodSSH(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c);
 391
 392 /*
 393         setups the montgomery reduction
 394  */
 395 extern int32 mp_montgomery_setup(mp_int *a, mp_digit *mp);
 396
 397 /*
 398         computes a = B**n mod b without division or multiplication useful for
 399         normalizing numbers in a Montgomery system.
 400  */
 401 extern int32 mp_montgomery_calc_normalization(mp_int *a, mp_int *b);
 402
 403 /*
 404         computes x/R == x (mod N) via Montgomery Reduction
 405  */
 406 #ifdef USE_SMALL_WORD
 407 extern int32 mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp);
 408 #endif
 409
 410 /*
 411         d = a**b (mod c)
 412  */
 413 extern int32 mp_exptmod(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c, mp_int *d);
 414
 415 /******************************************************************************/
 416 /*
 417         If we're using 1024 or 2048 bit keys and 28 bit digits, we only need the
 418         fast_ versions of these functions, removing the others to save space.
 419         Otherwise, we include the slow versions as well and which version to use
 420         is done at runtime.
 421 */
 422 #ifdef USE_SMALL_WORD
 423 extern int32 s_mp_mul_digs(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c,
 424                                                    int32 digs);
 425 extern int32 s_mp_sqr(psPool_t *pool, mp_int *a, mp_int *b);
 426
 427 #else
 428 #define mp_montgomery_reduce fast_mp_montgomery_reduce
 429 #define mp_sqr  fast_s_mp_sqr
 430 #define s_mp_mul_digs   fast_s_mp_mul_digs
 431 #define mp_invmod       fast_mp_invmod
 432 #endif
 433
 434 /******************************************************************************/
 435 /*
 436         radix conversion
 437  */
 438 extern int32 mp_count_bits(mp_int *a);
 439
 440 extern int32 mp_unsigned_bin_size(mp_int *a);
 441 extern int32 mp_read_unsigned_bin(mp_int *a, unsigned char *b, int32 c);
 442 extern int32 mp_to_unsigned_bin(psPool_t *pool, mp_int *a, unsigned char *b);
 443
 444 extern int32 mp_signed_bin_size(mp_int *a);
 445
 446 /*
 447         lowlevel functions, do not call!
 448  */
 449 /* define this in all cases for now FUTURE*/
 450 #define s_mp_mul(P, A, B, C) s_mp_mul_digs(P, A, B, C, (A)->used + (B)->used + 1)
 451
 452
 453 /*
 454         b = a*2
 455  */
 456 extern int32 mp_mul_2(mp_int *a, mp_int *b);
 457
 458 extern int32 s_mp_add(mp_int *a, mp_int *b, mp_int *c);
 459 extern int32 s_mp_sub(mp_int *a, mp_int *b, mp_int *c);
 460
 461 extern int32 fast_s_mp_mul_digs(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c,
 462                                                                 int32 digs);
 463 extern int32 fast_s_mp_sqr(psPool_t *pool, mp_int *a, mp_int *b);
 464
 465 extern int32 fast_mp_invmod(psPool_t *pool, mp_int *a, mp_int *b, mp_int *c);
 466 extern int32 fast_mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp);
 467
 468 extern void bn_reverse(unsigned char *s, int32 len);
 469
 470
 471 #ifdef __cplusplus
 472    }
 473 #endif /* __cplusplus */
 474
 475 #endif /* _h_MPI */
 476