libs/libtomcrypt/headers/tomcrypt_math.h

   1 /** math functions **/
   2
   3 #define LTC_MP_LT   -1
   4 #define LTC_MP_EQ    0
   5 #define LTC_MP_GT    1
   6
   7 #define LTC_MP_NO    0
   8 #define LTC_MP_YES   1
   9
  10 #ifndef MECC
  11    typedef void ecc_point;
  12 #endif
  13
  14 #ifndef MRSA
  15    typedef void rsa_key;
  16 #endif
  17
  18 /** math descriptor */
  19 typedef struct {
  20    /** Name of the math provider */
  21    char *name;
  22
  23    /** Bits per digit, amount of bits must fit in an unsigned long */
  24    int  bits_per_digit;
  25
  26 /* ---- init/deinit functions ---- */
  27
  28    /** initialize a bignum
  29      @param   a     The number to initialize
  30      @return  CRYPT_OK on success
  31    */
  32    int (*init)(void **a);
  33
  34    /** init copy
  35      @param  dst    The number to initialize and write to
  36      @param  src    The number to copy from
  37      @return CRYPT_OK on success
  38    */
  39    int (*init_copy)(void **dst, void *src);
  40
  41    /** deinit
  42       @param   a    The number to free
  43       @return CRYPT_OK on success
  44    */
  45    void (*deinit)(void *a);
  46
  47 /* ---- data movement ---- */
  48
  49    /** negate
  50       @param   src   The number to negate
  51       @param   dst   The destination
  52       @return CRYPT_OK on success
  53    */
  54    int (*neg)(void *src, void *dst);
  55
  56    /** copy
  57       @param   src   The number to copy from
  58       @param   dst   The number to write to
  59       @return CRYPT_OK on success
  60    */
  61    int (*copy)(void *src, void *dst);
  62
  63 /* ---- trivial low level functions ---- */
  64
  65    /** set small constant
  66       @param a    Number to write to
  67       @param n    Source upto bits_per_digit (actually meant for very small constants)
  68       @return CRYPT_OK on succcess
  69    */
  70    int (*set_int)(void *a, unsigned long n);
  71
  72    /** get small constant
  73       @param a    Number to read, only fetches upto bits_per_digit from the number
  74       @return  The lower bits_per_digit of the integer (unsigned)
  75    */
  76    unsigned long (*get_int)(void *a);
  77
  78    /** get digit n
  79      @param a  The number to read from
  80      @param n  The number of the digit to fetch
  81      @return  The bits_per_digit  sized n'th digit of a
  82    */
  83    unsigned long (*get_digit)(void *a, int n);
  84
  85    /** Get the number of digits that represent the number
  86      @param a   The number to count
  87      @return The number of digits used to represent the number
  88    */
  89    int (*get_digit_count)(void *a);
  90
  91    /** compare two integers
  92      @param a   The left side integer
  93      @param b   The right side integer
  94      @return LTC_MP_LT if a < b, LTC_MP_GT if a > b and LTC_MP_EQ otherwise.  (signed comparison)
  95    */
  96    int (*compare)(void *a, void *b);
  97
  98    /** compare against int
  99      @param a   The left side integer
 100      @param b   The right side integer (upto bits_per_digit)
 101      @return LTC_MP_LT if a < b, LTC_MP_GT if a > b and LTC_MP_EQ otherwise.  (signed comparison)
 102    */
 103    int (*compare_d)(void *a, unsigned long n);
 104
 105    /** Count the number of bits used to represent the integer
 106      @param a   The integer to count
 107      @return The number of bits required to represent the integer
 108    */
 109    int (*count_bits)(void * a);
 110
 111    /** Count the number of LSB bits which are zero
 112      @param a   The integer to count
 113      @return The number of contiguous zero LSB bits
 114    */
 115    int (*count_lsb_bits)(void *a);
 116
 117    /** Compute a power of two
 118      @param a  The integer to store the power in
 119      @param n  The power of two you want to store (a = 2^n)
 120      @return CRYPT_OK on success
 121    */
 122    int (*twoexpt)(void *a , int n);
 123
 124 /* ---- radix conversions ---- */
 125
 126    /** read ascii string
 127      @param a     The integer to store into
 128      @param str   The string to read
 129      @param radix The radix the integer has been represented in (2-64)
 130      @return CRYPT_OK on success
 131    */
 132    int (*read_radix)(void *a, const char *str, int radix);
 133
 134    /** write number to string
 135      @param a     The integer to store
 136      @param str   The destination for the string
 137      @param radix The radix the integer is to be represented in (2-64)
 138      @return CRYPT_OK on success
 139    */
 140    int (*write_radix)(void *a, char *str, int radix);
 141
 142    /** get size as unsigned char string
 143      @param a     The integer to get the size (when stored in array of octets)
 144      @return The length of the integer
 145    */
 146    unsigned long (*unsigned_size)(void *a);
 147
 148    /** store an integer as an array of octets
 149      @param src   The integer to store
 150      @param dst   The buffer to store the integer in
 151      @return CRYPT_OK on success
 152    */
 153    int (*unsigned_write)(void *src, unsigned char *dst);
 154
 155    /** read an array of octets and store as integer
 156      @param dst   The integer to load
 157      @param src   The array of octets
 158      @param len   The number of octets
 159      @return CRYPT_OK on success
 160    */
 161    int (*unsigned_read)(void *dst, unsigned char *src, unsigned long len);
 162
 163 /* ---- basic math ---- */
 164
 165    /** add two integers
 166      @param a   The first source integer
 167      @param b   The second source integer
 168      @param c   The destination of "a + b"
 169      @return CRYPT_OK on success
 170    */
 171    int (*add)(void *a, void *b, void *c);
 172
 173
 174    /** add two integers
 175      @param a   The first source integer
 176      @param b   The second source integer (single digit of upto bits_per_digit in length)
 177      @param c   The destination of "a + b"
 178      @return CRYPT_OK on success
 179    */
 180    int (*addi)(void *a, unsigned long b, void *c);
 181
 182    /** subtract two integers
 183      @param a   The first source integer
 184      @param b   The second source integer
 185      @param c   The destination of "a - b"
 186      @return CRYPT_OK on success
 187    */
 188    int (*sub)(void *a, void *b, void *c);
 189
 190    /** subtract two integers
 191      @param a   The first source integer
 192      @param b   The second source integer (single digit of upto bits_per_digit in length)
 193      @param c   The destination of "a - b"
 194      @return CRYPT_OK on success
 195    */
 196    int (*subi)(void *a, unsigned long b, void *c);
 197
 198    /** multiply two integers
 199      @param a   The first source integer
 200      @param b   The second source integer (single digit of upto bits_per_digit in length)
 201      @param c   The destination of "a * b"
 202      @return CRYPT_OK on success
 203    */
 204    int (*mul)(void *a, void *b, void *c);
 205
 206    /** multiply two integers
 207      @param a   The first source integer
 208      @param b   The second source integer (single digit of upto bits_per_digit in length)
 209      @param c   The destination of "a * b"
 210      @return CRYPT_OK on success
 211    */
 212    int (*muli)(void *a, unsigned long b, void *c);
 213
 214    /** Square an integer
 215      @param a    The integer to square
 216      @param b    The destination
 217      @return CRYPT_OK on success
 218    */
 219    int (*sqr)(void *a, void *b);
 220
 221    /** Divide an integer
 222      @param a    The dividend
 223      @param b    The divisor
 224      @param c    The quotient (can be NULL to signify don't care)
 225      @param d    The remainder (can be NULL to signify don't care)
 226      @return CRYPT_OK on success
 227    */
 228    int (*mpdiv)(void *a, void *b, void *c, void *d);
 229
 230    /** divide by two
 231       @param  a   The integer to divide (shift right)
 232       @param  b   The destination
 233       @return CRYPT_OK on success
 234    */
 235    int (*div_2)(void *a, void *b);
 236
 237    /** Get remainder (small value)
 238       @param  a    The integer to reduce
 239       @param  b    The modulus (upto bits_per_digit in length)
 240       @param  c    The destination for the residue
 241       @return CRYPT_OK on success
 242    */
 243    int (*modi)(void *a, unsigned long b, unsigned long *c);
 244
 245    /** gcd
 246       @param  a     The first integer
 247       @param  b     The second integer
 248       @param  c     The destination for (a, b)
 249       @return CRYPT_OK on success
 250    */
 251    int (*gcd)(void *a, void *b, void *c);
 252
 253    /** lcm
 254       @param  a     The first integer
 255       @param  b     The second integer
 256       @param  c     The destination for [a, b]
 257       @return CRYPT_OK on success
 258    */
 259    int (*lcm)(void *a, void *b, void *c);
 260
 261    /** Modular multiplication
 262       @param  a     The first source
 263       @param  b     The second source
 264       @param  c     The modulus
 265       @param  d     The destination (a*b mod c)
 266       @return CRYPT_OK on success
 267    */
 268    int (*mulmod)(void *a, void *b, void *c, void *d);
 269
 270    /** Modular squaring
 271       @param  a     The first source
 272       @param  b     The modulus
 273       @param  c     The destination (a*a mod b)
 274       @return CRYPT_OK on success
 275    */
 276    int (*sqrmod)(void *a, void *b, void *c);
 277
 278    /** Modular inversion
 279       @param  a     The value to invert
 280       @param  b     The modulus
 281       @param  c     The destination (1/a mod b)
 282       @return CRYPT_OK on success
 283    */
 284    int (*invmod)(void *, void *, void *);
 285
 286 /* ---- reduction ---- */
 287
 288    /** setup montgomery
 289        @param a  The modulus
 290        @param b  The destination for the reduction digit
 291        @return CRYPT_OK on success
 292    */
 293    int (*montgomery_setup)(void *a, void **b);
 294
 295    /** get normalization value
 296        @param a   The destination for the normalization value
 297        @param b   The modulus
 298        @return  CRYPT_OK on success
 299    */
 300    int (*montgomery_normalization)(void *a, void *b);
 301
 302    /** reduce a number
 303        @param a   The number [and dest] to reduce
 304        @param b   The modulus
 305        @param c   The value "b" from montgomery_setup()
 306        @return CRYPT_OK on success
 307    */
 308    int (*montgomery_reduce)(void *a, void *b, void *c);
 309
 310    /** clean up  (frees memory)
 311        @param a   The value "b" from montgomery_setup()
 312        @return CRYPT_OK on success
 313    */
 314    void (*montgomery_deinit)(void *a);
 315
 316 /* ---- exponentiation ---- */
 317
 318    /** Modular exponentiation
 319        @param a    The base integer
 320        @param b    The power (can be negative) integer
 321        @param c    The modulus integer
 322        @param d    The destination
 323        @return CRYPT_OK on success
 324    */
 325    int (*exptmod)(void *a, void *b, void *c, void *d);
 326
 327    /** Primality testing
 328        @param a     The integer to test
 329        @param b     The destination of the result (FP_YES if prime)
 330        @return CRYPT_OK on success
 331    */
 332    int (*isprime)(void *a, int *b);
 333
 334 /* ----  (optional) ecc point math ---- */
 335
 336    /** ECC GF(p) point multiplication (from the NIST curves)
 337        @param k   The integer to multiply the point by
 338        @param G   The point to multiply
 339        @param R   The destination for kG
 340        @param modulus  The modulus for the field
 341        @param map Boolean indicated whether to map back to affine or not (can be ignored if you work in affine only)
 342        @return CRYPT_OK on success
 343    */
 344    int (*ecc_ptmul)(void *k, ecc_point *G, ecc_point *R, void *modulus, int map);
 345
 346    /** ECC GF(p) point addition
 347        @param P    The first point
 348        @param Q    The second point
 349        @param R    The destination of P + Q
 350        @param modulus  The modulus
 351        @param mp   The "b" value from montgomery_setup()
 352        @return CRYPT_OK on success
 353    */
 354    int (*ecc_ptadd)(ecc_point *P, ecc_point *Q, ecc_point *R, void *modulus, void *mp);
 355
 356    /** ECC GF(p) point double
 357        @param P    The first point
 358        @param R    The destination of 2P
 359        @param modulus  The modulus
 360        @param mp   The "b" value from montgomery_setup()
 361        @return CRYPT_OK on success
 362    */
 363    int (*ecc_ptdbl)(ecc_point *P, ecc_point *R, void *modulus, void *mp);
 364
 365    /** ECC mapping from projective to affine, currently uses (x,y,z) => (x/z^2, y/z^3, 1)
 366        @param P     The point to map
 367        @param modulus The modulus
 368        @param mp    The "b" value from montgomery_setup()
 369        @return CRYPT_OK on success
 370        @remark  The mapping can be different but keep in mind a ecc_point only has three
 371                 integers (x,y,z) so if you use a different mapping you have to make it fit.
 372    */
 373    int (*ecc_map)(ecc_point *P, void *modulus, void *mp);
 374
 375    /** Computes kA*A + kB*B = C using Shamir's Trick
 376        @param A        First point to multiply
 377        @param kA       What to multiple A by
 378        @param B        Second point to multiply
 379        @param kB       What to multiple B by
 380        @param C        [out] Destination point (can overlap with A or B
 381        @param modulus  Modulus for curve
 382        @return CRYPT_OK on success
 383    */
 384    int (*ecc_mul2add)(ecc_point *A, void *kA,
 385                       ecc_point *B, void *kB,
 386                       ecc_point *C,
 387                            void *modulus);
 388
 389 /* ---- (optional) rsa optimized math (for internal CRT) ---- */
 390
 391    /** RSA Key Generation
 392        @param prng     An active PRNG state
 393        @param wprng    The index of the PRNG desired
 394        @param size     The size of the modulus (key size) desired (octets)
 395        @param e        The "e" value (public key).  e==65537 is a good choice
 396        @param key      [out] Destination of a newly created private key pair
 397        @return CRYPT_OK if successful, upon error all allocated ram is freed
 398     */
 399     int (*rsa_keygen)(prng_state *prng, int wprng, int size, long e, rsa_key *key);
 400
 401
 402    /** RSA exponentiation
 403       @param in       The octet array representing the base
 404       @param inlen    The length of the input
 405       @param out      The destination (to be stored in an octet array format)
 406       @param outlen   The length of the output buffer and the resulting size (zero padded to the size of the modulus)
 407       @param which    PK_PUBLIC for public RSA and PK_PRIVATE for private RSA
 408       @param key      The RSA key to use
 409       @return CRYPT_OK on success
 410    */
 411    int (*rsa_me)(const unsigned char *in,   unsigned long inlen,
 412                        unsigned char *out,  unsigned long *outlen, int which,
 413                        rsa_key *key);
 414 } ltc_math_descriptor;
 415
 416 extern ltc_math_descriptor ltc_mp;
 417
 418 int ltc_init_multi(void **a, ...);
 419 void ltc_deinit_multi(void *a, ...);
 420
 421 #ifdef LTM_DESC
 422 extern const ltc_math_descriptor ltm_desc;
 423 #endif
 424
 425 #ifdef TFM_DESC
 426 extern const ltc_math_descriptor tfm_desc;
 427 #endif
 428
 429 #ifdef GMP_DESC
 430 extern const ltc_math_descriptor gmp_desc;
 431 #endif
 432
 433 #if !defined(DESC_DEF_ONLY) && defined(LTC_SOURCE)
 434
 435 #define MP_DIGIT_BIT                 ltc_mp.bits_per_digit
 436
 437 /* some handy macros */
 438 #define mp_init(a)                   ltc_mp.init(a)
 439 #define mp_init_multi                ltc_init_multi
 440 #define mp_clear(a)                  ltc_mp.deinit(a)
 441 #define mp_clear_multi               ltc_deinit_multi
 442 #define mp_init_copy(a, b)           ltc_mp.init_copy(a, b)
 443
 444 #define mp_neg(a, b)                 ltc_mp.neg(a, b)
 445 #define mp_copy(a, b)                ltc_mp.copy(a, b)
 446
 447 #define mp_set(a, b)                 ltc_mp.set_int(a, b)
 448 #define mp_set_int(a, b)             ltc_mp.set_int(a, b)
 449 #define mp_get_int(a)                ltc_mp.get_int(a)
 450 #define mp_get_digit(a, n)           ltc_mp.get_digit(a, n)
 451 #define mp_get_digit_count(a)        ltc_mp.get_digit_count(a)
 452 #define mp_cmp(a, b)                 ltc_mp.compare(a, b)
 453 #define mp_cmp_d(a, b)               ltc_mp.compare_d(a, b)
 454 #define mp_count_bits(a)             ltc_mp.count_bits(a)
 455 #define mp_cnt_lsb(a)                ltc_mp.count_lsb_bits(a)
 456 #define mp_2expt(a, b)               ltc_mp.twoexpt(a, b)
 457
 458 #define mp_read_radix(a, b, c)       ltc_mp.read_radix(a, b, c)
 459 #define mp_toradix(a, b, c)          ltc_mp.write_radix(a, b, c)
 460 #define mp_unsigned_bin_size(a)      ltc_mp.unsigned_size(a)
 461 #define mp_to_unsigned_bin(a, b)     ltc_mp.unsigned_write(a, b)
 462 #define mp_read_unsigned_bin(a, b, c) ltc_mp.unsigned_read(a, b, c)
 463
 464 #define mp_add(a, b, c)              ltc_mp.add(a, b, c)
 465 #define mp_add_d(a, b, c)            ltc_mp.addi(a, b, c)
 466 #define mp_sub(a, b, c)              ltc_mp.sub(a, b, c)
 467 #define mp_sub_d(a, b, c)            ltc_mp.subi(a, b, c)
 468 #define mp_mul(a, b, c)              ltc_mp.mul(a, b, c)
 469 #define mp_mul_d(a, b, c)            ltc_mp.muli(a, b, c)
 470 #define mp_sqr(a, b)                 ltc_mp.sqr(a, b)
 471 #define mp_div(a, b, c, d)           ltc_mp.mpdiv(a, b, c, d)
 472 #define mp_div_2(a, b)               ltc_mp.div_2(a, b)
 473 #define mp_mod(a, b, c)              ltc_mp.mpdiv(a, b, NULL, c)
 474 #define mp_mod_d(a, b, c)            ltc_mp.modi(a, b, c)
 475 #define mp_gcd(a, b, c)              ltc_mp.gcd(a, b, c)
 476 #define mp_lcm(a, b, c)              ltc_mp.lcm(a, b, c)
 477
 478 #define mp_mulmod(a, b, c, d)        ltc_mp.mulmod(a, b, c, d)
 479 #define mp_sqrmod(a, b, c)           ltc_mp.sqrmod(a, b, c)
 480 #define mp_invmod(a, b, c)           ltc_mp.invmod(a, b, c)
 481
 482 #define mp_montgomery_setup(a, b)    ltc_mp.montgomery_setup(a, b)
 483 #define mp_montgomery_normalization(a, b) ltc_mp.montgomery_normalization(a, b)
 484 #define mp_montgomery_reduce(a, b, c)   ltc_mp.montgomery_reduce(a, b, c)
 485 #define mp_montgomery_free(a)        ltc_mp.montgomery_deinit(a)
 486
 487 #define mp_exptmod(a,b,c,d)          ltc_mp.exptmod(a,b,c,d)
 488 #define mp_prime_is_prime(a, b, c)   ltc_mp.isprime(a, c)
 489
 490 #define mp_iszero(a)                 (mp_cmp_d(a, 0) == LTC_MP_EQ ? LTC_MP_YES : LTC_MP_NO)
 491 #define mp_isodd(a)                  (mp_get_digit_count(a) > 0 ? (mp_get_digit(a, 0) & 1 ? LTC_MP_YES : LTC_MP_NO) : LTC_MP_NO)
 492 #define mp_exch(a, b)                do { void *ABC__tmp = a; a = b; b = ABC__tmp; } while(0);
 493
 494 #define mp_tohex(a, b)               mp_toradix(a, b, 16)
 495
 496 #endif
 497
 498 /* $Source: /cvs/libtom/libtomcrypt/src/headers/tomcrypt_math.h,v $ */
 499 /* $Revision: 1.43 $ */
 500 /* $Date: 2006/12/02 19:23:13 $ */