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 LTC_MECC 11 typedef void ecc_point; 12 #endif 13 14 #ifndef LTC_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.44 $ */ 500 /* $Date: 2007/05/12 14:32:35 $ */ 501