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