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