Dogcows Code - chaz/p5-File-KDBX-XS/blob - libtomcrypt/src/headers/tomcrypt_math.h

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