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