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