pd.if.org Git - zpackage/blob - libtomcrypt/src/headers/tomcrypt_math.h

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