src/crypto/matrixssl/mpi.h

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