1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
6 * The library is free for all purposes without any express
10 /** math functions **/
20 typedef void ecc_point;
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
34 int radix_to_bin(const void *in, int radix, void *out, unsigned long *len);
36 /** math descriptor */
38 /** Name of the math provider */
41 /** Bits per digit, amount of bits must fit in an unsigned long */
44 /* ---- init/deinit functions ---- */
46 /** initialize a bignum
47 @param a The number to initialize
48 @return CRYPT_OK on success
50 int (*init)(void **a);
53 @param dst The number to initialize and write to
54 @param src The number to copy from
55 @return CRYPT_OK on success
57 int (*init_copy)(void **dst, void *src);
60 @param a The number to free
61 @return CRYPT_OK on success
63 void (*deinit)(void *a);
65 /* ---- data movement ---- */
68 @param src The number to negate
69 @param dst The destination
70 @return CRYPT_OK on success
72 int (*neg)(void *src, void *dst);
75 @param src The number to copy from
76 @param dst The number to write to
77 @return CRYPT_OK on success
79 int (*copy)(void *src, void *dst);
81 /* ---- trivial low level functions ---- */
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
88 int (*set_int)(void *a, ltc_mp_digit n);
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)
95 unsigned long (*get_int)(void *a);
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
102 ltc_mp_digit (*get_digit)(void *a, int n);
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
108 int (*get_digit_count)(void *a);
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)
117 int (*compare)(void *a, void *b);
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)
126 int (*compare_d)(void *a, ltc_mp_digit n);
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
132 int (*count_bits)(void * a);
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
138 int (*count_lsb_bits)(void *a);
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
145 int (*twoexpt)(void *a , int n);
147 /* ---- radix conversions ---- */
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
155 int (*read_radix)(void *a, const char *str, int radix);
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
163 int (*write_radix)(void *a, char *str, int radix);
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
169 unsigned long (*unsigned_size)(void *a);
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
176 int (*unsigned_write)(void *src, unsigned char *dst);
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
184 int (*unsigned_read)( void *dst,
188 /* ---- basic math ---- */
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
196 int (*add)(void *a, void *b, void *c);
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
205 int (*addi)(void *a, ltc_mp_digit b, void *c);
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
213 int (*sub)(void *a, void *b, void *c);
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
222 int (*subi)(void *a, ltc_mp_digit b, void *c);
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
231 int (*mul)(void *a, void *b, void *c);
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
240 int (*muli)(void *a, ltc_mp_digit b, void *c);
242 /** Square an integer
243 @param a The integer to square
244 @param b The destination
245 @return CRYPT_OK on success
247 int (*sqr)(void *a, void *b);
249 /** Divide an integer
250 @param a The dividend
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
256 int (*mpdiv)(void *a, void *b, void *c, void *d);
259 @param a The integer to divide (shift right)
260 @param b The destination
261 @return CRYPT_OK on success
263 int (*div_2)(void *a, void *b);
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
271 int (*modi)(void *a, ltc_mp_digit b, ltc_mp_digit *c);
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
279 int (*gcd)(void *a, void *b, void *c);
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
287 int (*lcm)(void *a, void *b, void *c);
289 /** Modular multiplication
290 @param a The first source
291 @param b The second source
293 @param d The destination (a*b mod c)
294 @return CRYPT_OK on success
296 int (*mulmod)(void *a, void *b, void *c, void *d);
299 @param a The first source
301 @param c The destination (a*a mod b)
302 @return CRYPT_OK on success
304 int (*sqrmod)(void *a, void *b, void *c);
306 /** Modular inversion
307 @param a The value to invert
309 @param c The destination (1/a mod b)
310 @return CRYPT_OK on success
312 int (*invmod)(void *, void *, void *);
314 /* ---- reduction ---- */
318 @param b The destination for the reduction digit
319 @return CRYPT_OK on success
321 int (*montgomery_setup)(void *a, void **b);
323 /** get normalization value
324 @param a The destination for the normalization value
326 @return CRYPT_OK on success
328 int (*montgomery_normalization)(void *a, void *b);
331 @param a The number [and dest] to reduce
333 @param c The value "b" from montgomery_setup()
334 @return CRYPT_OK on success
336 int (*montgomery_reduce)(void *a, void *b, void *c);
338 /** clean up (frees memory)
339 @param a The value "b" from montgomery_setup()
340 @return CRYPT_OK on success
342 void (*montgomery_deinit)(void *a);
344 /* ---- exponentiation ---- */
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
353 int (*exptmod)(void *a, void *b, void *c, void *d);
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
361 int (*isprime)(void *a, int b, int *c);
363 /* ---- (optional) ecc point math ---- */
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
374 int (*ecc_ptmul)( void *k,
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
388 int (*ecc_ptadd)(ecc_point *P,
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
401 int (*ecc_ptdbl)(ecc_point *P,
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.
416 int (*ecc_map)(ecc_point *P, void *modulus, void *mp);
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
427 int (*ecc_mul2add)(ecc_point *A, void *kA,
428 ecc_point *B, void *kB,
432 /* ---- (optional) rsa optimized math (for internal CRT) ---- */
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
443 int (*rsa_keygen)(prng_state *prng,
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
459 int (*rsa_me)(const unsigned char *in, unsigned long inlen,
460 unsigned char *out, unsigned long *outlen, int which,
463 /* ---- basic math continued ---- */
466 @param a The first source
467 @param b The second source
469 @param d The destination (a + b mod c)
470 @return CRYPT_OK on success
472 int (*addmod)(void *a, void *b, void *c, void *d);
474 /** Modular substraction
475 @param a The first source
476 @param b The second source
478 @param d The destination (a - b mod c)
479 @return CRYPT_OK on success
481 int (*submod)(void *a, void *b, void *c, void *d);
483 /* ---- misc stuff ---- */
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
490 int (*rand)(void *a, int size);
491 } ltc_math_descriptor;
493 extern ltc_math_descriptor ltc_mp;
495 int ltc_init_multi(void **a, ...);
496 void ltc_deinit_multi(void *a, ...);
497 void ltc_cleanup_multi(void **a, ...);
500 extern const ltc_math_descriptor ltm_desc;
504 extern const ltc_math_descriptor tfm_desc;
508 extern const ltc_math_descriptor gmp_desc;
511 #if !defined(DESC_DEF_ONLY) && defined(LTC_SOURCE)
513 #define MP_DIGIT_BIT ltc_mp.bits_per_digit
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)
523 #define mp_neg(a, b) ltc_mp.neg(a, b)
524 #define mp_copy(a, b) ltc_mp.copy(a, b)
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)
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)
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)
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)
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)
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)
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)
575 #define mp_tohex(a, b) mp_toradix(a, b, 16)
577 #define mp_rand(a, b) ltc_mp.rand(a, b)
581 /* ref: $Format:%D$ */
582 /* git commit: $Format:%H$ */
583 /* commit time: $Format:%ai$ */