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 #define DESC_DEF_ONLY
12 #include "tomcrypt_private.h"
13 
14 #ifdef GMP_DESC
15 
16 #include <stdio.h>
17 #include <gmp.h>
18 
init(void ** a)19 static int init(void **a)
20 {
21    LTC_ARGCHK(a != NULL);
22 
23    *a = XCALLOC(1, sizeof(__mpz_struct));
24    if (*a == NULL) {
25       return CRYPT_MEM;
26    }
27    mpz_init(((__mpz_struct *)*a));
28    return CRYPT_OK;
29 }
30 
deinit(void * a)31 static void deinit(void *a)
32 {
33    LTC_ARGCHKVD(a != NULL);
34    mpz_clear(a);
35    XFREE(a);
36 }
37 
neg(void * a,void * b)38 static int neg(void *a, void *b)
39 {
40    LTC_ARGCHK(a != NULL);
41    LTC_ARGCHK(b != NULL);
42    mpz_neg(b, a);
43    return CRYPT_OK;
44 }
45 
copy(void * a,void * b)46 static int copy(void *a, void *b)
47 {
48    LTC_ARGCHK(a != NULL);
49    LTC_ARGCHK(b != NULL);
50    mpz_set(b, a);
51    return CRYPT_OK;
52 }
53 
init_copy(void ** a,void * b)54 static int init_copy(void **a, void *b)
55 {
56    if (init(a) != CRYPT_OK) {
57       return CRYPT_MEM;
58    }
59    return copy(b, *a);
60 }
61 
62 /* ---- trivial ---- */
set_int(void * a,ltc_mp_digit b)63 static int set_int(void *a, ltc_mp_digit b)
64 {
65    LTC_ARGCHK(a != NULL);
66    mpz_set_ui(((__mpz_struct *)a), b);
67    return CRYPT_OK;
68 }
69 
get_int(void * a)70 static unsigned long get_int(void *a)
71 {
72    LTC_ARGCHK(a != NULL);
73    return mpz_get_ui(a);
74 }
75 
get_digit(void * a,int n)76 static ltc_mp_digit get_digit(void *a, int n)
77 {
78    LTC_ARGCHK(a != NULL);
79    return mpz_getlimbn(a, n);
80 }
81 
get_digit_count(void * a)82 static int get_digit_count(void *a)
83 {
84    LTC_ARGCHK(a != NULL);
85    return mpz_size(a);
86 }
87 
compare(void * a,void * b)88 static int compare(void *a, void *b)
89 {
90    int ret;
91    LTC_ARGCHK(a != NULL);
92    LTC_ARGCHK(b != NULL);
93    ret = mpz_cmp(a, b);
94    if (ret < 0) {
95       return LTC_MP_LT;
96    } else if (ret > 0) {
97       return LTC_MP_GT;
98    } else {
99       return LTC_MP_EQ;
100    }
101 }
102 
compare_d(void * a,ltc_mp_digit b)103 static int compare_d(void *a, ltc_mp_digit b)
104 {
105    int ret;
106    LTC_ARGCHK(a != NULL);
107    ret = mpz_cmp_ui(((__mpz_struct *)a), b);
108    if (ret < 0) {
109       return LTC_MP_LT;
110    } else if (ret > 0) {
111       return LTC_MP_GT;
112    } else {
113       return LTC_MP_EQ;
114    }
115 }
116 
count_bits(void * a)117 static int count_bits(void *a)
118 {
119    LTC_ARGCHK(a != NULL);
120    return mpz_sizeinbase(a, 2);
121 }
122 
count_lsb_bits(void * a)123 static int count_lsb_bits(void *a)
124 {
125    LTC_ARGCHK(a != NULL);
126    return mpz_scan1(a, 0);
127 }
128 
129 
twoexpt(void * a,int n)130 static int twoexpt(void *a, int n)
131 {
132    LTC_ARGCHK(a != NULL);
133    mpz_set_ui(a, 0);
134    mpz_setbit(a, n);
135    return CRYPT_OK;
136 }
137 
138 /* ---- conversions ---- */
139 
140 static const char rmap[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
141 
142 /* read ascii string */
read_radix(void * a,const char * b,int radix)143 static int read_radix(void *a, const char *b, int radix)
144 {
145    int ret;
146    LTC_ARGCHK(a != NULL);
147    LTC_ARGCHK(b != NULL);
148    if (radix == 64) {
149       /* Sadly, GMP only supports radixes up to 62, but we need 64.
150        * So, although this is not the most elegant or efficient way,
151        * let's just convert the base 64 string (6 bits per digit) to
152        * an octal string (3 bits per digit) that's twice as long. */
153       char c, *tmp, *q;
154       const char *p;
155       int i;
156       tmp = XMALLOC (1 + 2 * strlen (b));
157       if (tmp == NULL) {
158          return CRYPT_MEM;
159       }
160       p = b;
161       q = tmp;
162       while ((c = *p++) != 0) {
163          for (i = 0; i < 64; i++) {
164             if (c == rmap[i])
165                break;
166          }
167          if (i == 64) {
168             XFREE (tmp);
169             /* printf ("c = '%c'\n", c); */
170             return CRYPT_ERROR;
171          }
172          *q++ = '0' + (i / 8);
173          *q++ = '0' + (i % 8);
174       }
175       *q = 0;
176       ret = mpz_set_str(a, tmp, 8);
177       /* printf ("ret = %d for '%s'\n", ret, tmp); */
178       XFREE (tmp);
179    } else {
180       ret = mpz_set_str(a, b, radix);
181    }
182    return (ret == 0 ? CRYPT_OK : CRYPT_ERROR);
183 }
184 
185 /* write one */
write_radix(void * a,char * b,int radix)186 static int write_radix(void *a, char *b, int radix)
187 {
188    LTC_ARGCHK(a != NULL);
189    LTC_ARGCHK(b != NULL);
190    if (radix >= 11 && radix <= 36)
191       /* If radix is positive, GMP uses lowercase, and if negative, uppercase.
192        * We want it to use uppercase, to match the test vectors (presumably
193        * generated with LibTomMath). */
194       radix = -radix;
195    mpz_get_str(b, radix, a);
196    return CRYPT_OK;
197 }
198 
199 /* get size as unsigned char string */
unsigned_size(void * a)200 static unsigned long unsigned_size(void *a)
201 {
202    unsigned long t;
203    LTC_ARGCHK(a != NULL);
204    t = mpz_sizeinbase(a, 2);
205    if (mpz_cmp_ui(((__mpz_struct *)a), 0) == 0) return 0;
206    return (t>>3) + ((t&7)?1:0);
207 }
208 
209 /* store */
unsigned_write(void * a,unsigned char * b)210 static int unsigned_write(void *a, unsigned char *b)
211 {
212    LTC_ARGCHK(a != NULL);
213    LTC_ARGCHK(b != NULL);
214    mpz_export(b, NULL, 1, 1, 1, 0, ((__mpz_struct*)a));
215    return CRYPT_OK;
216 }
217 
218 /* read */
unsigned_read(void * a,unsigned char * b,unsigned long len)219 static int unsigned_read(void *a, unsigned char *b, unsigned long len)
220 {
221    LTC_ARGCHK(a != NULL);
222    LTC_ARGCHK(b != NULL);
223    mpz_import(a, len, 1, 1, 1, 0, b);
224    return CRYPT_OK;
225 }
226 
227 /* add */
add(void * a,void * b,void * c)228 static int add(void *a, void *b, void *c)
229 {
230    LTC_ARGCHK(a != NULL);
231    LTC_ARGCHK(b != NULL);
232    LTC_ARGCHK(c != NULL);
233    mpz_add(c, a, b);
234    return CRYPT_OK;
235 }
236 
addi(void * a,ltc_mp_digit b,void * c)237 static int addi(void *a, ltc_mp_digit b, void *c)
238 {
239    LTC_ARGCHK(a != NULL);
240    LTC_ARGCHK(c != NULL);
241    mpz_add_ui(c, a, b);
242    return CRYPT_OK;
243 }
244 
245 /* sub */
sub(void * a,void * b,void * c)246 static int sub(void *a, void *b, void *c)
247 {
248    LTC_ARGCHK(a != NULL);
249    LTC_ARGCHK(b != NULL);
250    LTC_ARGCHK(c != NULL);
251    mpz_sub(c, a, b);
252    return CRYPT_OK;
253 }
254 
subi(void * a,ltc_mp_digit b,void * c)255 static int subi(void *a, ltc_mp_digit b, void *c)
256 {
257    LTC_ARGCHK(a != NULL);
258    LTC_ARGCHK(c != NULL);
259    mpz_sub_ui(c, a, b);
260    return CRYPT_OK;
261 }
262 
263 /* mul */
mul(void * a,void * b,void * c)264 static int mul(void *a, void *b, void *c)
265 {
266    LTC_ARGCHK(a != NULL);
267    LTC_ARGCHK(b != NULL);
268    LTC_ARGCHK(c != NULL);
269    mpz_mul(c, a, b);
270    return CRYPT_OK;
271 }
272 
muli(void * a,ltc_mp_digit b,void * c)273 static int muli(void *a, ltc_mp_digit b, void *c)
274 {
275    LTC_ARGCHK(a != NULL);
276    LTC_ARGCHK(c != NULL);
277    mpz_mul_ui(c, a, b);
278    return CRYPT_OK;
279 }
280 
281 /* sqr */
sqr(void * a,void * b)282 static int sqr(void *a, void *b)
283 {
284    LTC_ARGCHK(a != NULL);
285    LTC_ARGCHK(b != NULL);
286    mpz_mul(b, a, a);
287    return CRYPT_OK;
288 }
289 
290 /* sqrtmod_prime */
sqrtmod_prime(void * n,void * prime,void * ret)291 static int sqrtmod_prime(void *n, void *prime, void *ret)
292 {
293    int res, legendre, i;
294    mpz_t t1, C, Q, S, Z, M, T, R, two;
295 
296    LTC_ARGCHK(n     != NULL);
297    LTC_ARGCHK(prime != NULL);
298    LTC_ARGCHK(ret   != NULL);
299 
300    /* first handle the simple cases */
301    if (mpz_cmp_ui(((__mpz_struct *)n), 0) == 0) {
302       mpz_set_ui(ret, 0);
303       return CRYPT_OK;
304    }
305    if (mpz_cmp_ui(((__mpz_struct *)prime), 2) == 0)     return CRYPT_ERROR; /* prime must be odd */
306    legendre = mpz_legendre(n, prime);
307    if (legendre == -1)                                  return CRYPT_ERROR; /* quadratic non-residue mod prime */
308 
309    mpz_init(t1); mpz_init(C); mpz_init(Q);
310    mpz_init(S);  mpz_init(Z); mpz_init(M);
311    mpz_init(T);  mpz_init(R); mpz_init(two);
312 
313    /* SPECIAL CASE: if prime mod 4 == 3
314     * compute directly: res = n^(prime+1)/4 mod prime
315     * Handbook of Applied Cryptography algorithm 3.36
316     */
317    i = mpz_mod_ui(t1, prime, 4); /* t1 is ignored here */
318    if (i == 3) {
319       mpz_add_ui(t1, prime, 1);
320       mpz_fdiv_q_2exp(t1, t1, 2);
321       mpz_powm(ret, n, t1, prime);
322       res = CRYPT_OK;
323       goto cleanup;
324    }
325 
326    /* NOW: Tonelli-Shanks algorithm */
327 
328    /* factor out powers of 2 from prime-1, defining Q and S as: prime-1 = Q*2^S */
329    mpz_set(Q, prime);
330    mpz_sub_ui(Q, Q, 1);
331    /* Q = prime - 1 */
332    mpz_set_ui(S, 0);
333    /* S = 0 */
334    while (mpz_even_p(Q)) {
335       mpz_fdiv_q_2exp(Q, Q, 1);
336       /* Q = Q / 2 */
337       mpz_add_ui(S, S, 1);
338       /* S = S + 1 */
339    }
340 
341    /* find a Z such that the Legendre symbol (Z|prime) == -1 */
342    mpz_set_ui(Z, 2);
343    /* Z = 2 */
344    while(1) {
345       legendre = mpz_legendre(Z, prime);
346       if (legendre == -1) break;
347       mpz_add_ui(Z, Z, 1);
348       /* Z = Z + 1 */
349    }
350 
351    mpz_powm(C, Z, Q, prime);
352    /* C = Z ^ Q mod prime */
353    mpz_add_ui(t1, Q, 1);
354    mpz_fdiv_q_2exp(t1, t1, 1);
355    /* t1 = (Q + 1) / 2 */
356    mpz_powm(R, n, t1, prime);
357    /* R = n ^ ((Q + 1) / 2) mod prime */
358    mpz_powm(T, n, Q, prime);
359    /* T = n ^ Q mod prime */
360    mpz_set(M, S);
361    /* M = S */
362    mpz_set_ui(two, 2);
363 
364    while (1) {
365       mpz_set(t1, T);
366       i = 0;
367       while (1) {
368          if (mpz_cmp_ui(((__mpz_struct *)t1), 1) == 0) break;
369          mpz_powm(t1, t1, two, prime);
370          i++;
371       }
372       if (i == 0) {
373          mpz_set(ret, R);
374          res = CRYPT_OK;
375          goto cleanup;
376       }
377       mpz_sub_ui(t1, M, i);
378       mpz_sub_ui(t1, t1, 1);
379       mpz_powm(t1, two, t1, prime);
380       /* t1 = 2 ^ (M - i - 1) */
381       mpz_powm(t1, C, t1, prime);
382       /* t1 = C ^ (2 ^ (M - i - 1)) mod prime */
383       mpz_mul(C, t1, t1);
384       mpz_mod(C, C, prime);
385       /* C = (t1 * t1) mod prime */
386       mpz_mul(R, R, t1);
387       mpz_mod(R, R, prime);
388       /* R = (R * t1) mod prime */
389       mpz_mul(T, T, C);
390       mpz_mod(T, T, prime);
391       /* T = (T * C) mod prime */
392       mpz_set_ui(M, i);
393       /* M = i */
394    }
395 
396 cleanup:
397    mpz_clear(t1); mpz_clear(C); mpz_clear(Q);
398    mpz_clear(S);  mpz_clear(Z); mpz_clear(M);
399    mpz_clear(T);  mpz_clear(R); mpz_clear(two);
400    return res;
401 }
402 
403 /* div */
divide(void * a,void * b,void * c,void * d)404 static int divide(void *a, void *b, void *c, void *d)
405 {
406    mpz_t tmp;
407    LTC_ARGCHK(a != NULL);
408    LTC_ARGCHK(b != NULL);
409    if (c != NULL) {
410       mpz_init(tmp);
411       mpz_divexact(tmp, a, b);
412    }
413    if (d != NULL) {
414       mpz_mod(d, a, b);
415    }
416    if (c != NULL) {
417       mpz_set(c, tmp);
418       mpz_clear(tmp);
419    }
420    return CRYPT_OK;
421 }
422 
div_2(void * a,void * b)423 static int div_2(void *a, void *b)
424 {
425    LTC_ARGCHK(a != NULL);
426    LTC_ARGCHK(b != NULL);
427    mpz_divexact_ui(b, a, 2);
428    return CRYPT_OK;
429 }
430 
431 /* modi */
modi(void * a,ltc_mp_digit b,ltc_mp_digit * c)432 static int modi(void *a, ltc_mp_digit b, ltc_mp_digit *c)
433 {
434    LTC_ARGCHK(a != NULL);
435    LTC_ARGCHK(c != NULL);
436 
437    *c = mpz_fdiv_ui(a, b);
438    return CRYPT_OK;
439 }
440 
441 /* gcd */
gcd(void * a,void * b,void * c)442 static int gcd(void *a, void *b, void *c)
443 {
444    LTC_ARGCHK(a != NULL);
445    LTC_ARGCHK(b != NULL);
446    LTC_ARGCHK(c != NULL);
447    mpz_gcd(c, a, b);
448    return CRYPT_OK;
449 }
450 
451 /* lcm */
lcm(void * a,void * b,void * c)452 static int lcm(void *a, void *b, void *c)
453 {
454    LTC_ARGCHK(a != NULL);
455    LTC_ARGCHK(b != NULL);
456    LTC_ARGCHK(c != NULL);
457    mpz_lcm(c, a, b);
458    return CRYPT_OK;
459 }
460 
addmod(void * a,void * b,void * c,void * d)461 static int addmod(void *a, void *b, void *c, void *d)
462 {
463    LTC_ARGCHK(a != NULL);
464    LTC_ARGCHK(b != NULL);
465    LTC_ARGCHK(c != NULL);
466    LTC_ARGCHK(d != NULL);
467    mpz_add(d, a, b);
468    mpz_mod(d, d, c);
469    return CRYPT_OK;
470 }
471 
submod(void * a,void * b,void * c,void * d)472 static int submod(void *a, void *b, void *c, void *d)
473 {
474    LTC_ARGCHK(a != NULL);
475    LTC_ARGCHK(b != NULL);
476    LTC_ARGCHK(c != NULL);
477    LTC_ARGCHK(d != NULL);
478    mpz_sub(d, a, b);
479    mpz_mod(d, d, c);
480    return CRYPT_OK;
481 }
482 
mulmod(void * a,void * b,void * c,void * d)483 static int mulmod(void *a, void *b, void *c, void *d)
484 {
485    LTC_ARGCHK(a != NULL);
486    LTC_ARGCHK(b != NULL);
487    LTC_ARGCHK(c != NULL);
488    LTC_ARGCHK(d != NULL);
489    mpz_mul(d, a, b);
490    mpz_mod(d, d, c);
491    return CRYPT_OK;
492 }
493 
sqrmod(void * a,void * b,void * c)494 static int sqrmod(void *a, void *b, void *c)
495 {
496    LTC_ARGCHK(a != NULL);
497    LTC_ARGCHK(b != NULL);
498    LTC_ARGCHK(c != NULL);
499    mpz_mul(c, a, a);
500    mpz_mod(c, c, b);
501    return CRYPT_OK;
502 }
503 
504 /* invmod */
invmod(void * a,void * b,void * c)505 static int invmod(void *a, void *b, void *c)
506 {
507    LTC_ARGCHK(a != NULL);
508    LTC_ARGCHK(b != NULL);
509    LTC_ARGCHK(c != NULL);
510    mpz_invert(c, a, b);
511    return CRYPT_OK;
512 }
513 
514 /* setup */
montgomery_setup(void * a,void ** b)515 static int montgomery_setup(void *a, void **b)
516 {
517    LTC_ARGCHK(a != NULL);
518    LTC_ARGCHK(b != NULL);
519    *b = (void *)1;
520    return CRYPT_OK;
521 }
522 
523 /* get normalization value */
montgomery_normalization(void * a,void * b)524 static int montgomery_normalization(void *a, void *b)
525 {
526    LTC_ARGCHK(a != NULL);
527    LTC_ARGCHK(b != NULL);
528    mpz_set_ui(a, 1);
529    return CRYPT_OK;
530 }
531 
532 /* reduce */
montgomery_reduce(void * a,void * b,void * c)533 static int montgomery_reduce(void *a, void *b, void *c)
534 {
535    LTC_ARGCHK(a != NULL);
536    LTC_ARGCHK(b != NULL);
537    LTC_ARGCHK(c != NULL);
538    mpz_mod(a, a, b);
539    return CRYPT_OK;
540 }
541 
542 /* clean up */
montgomery_deinit(void * a)543 static void montgomery_deinit(void *a)
544 {
545   LTC_UNUSED_PARAM(a);
546 }
547 
exptmod(void * a,void * b,void * c,void * d)548 static int exptmod(void *a, void *b, void *c, void *d)
549 {
550    LTC_ARGCHK(a != NULL);
551    LTC_ARGCHK(b != NULL);
552    LTC_ARGCHK(c != NULL);
553    LTC_ARGCHK(d != NULL);
554    mpz_powm(d, a, b, c);
555    return CRYPT_OK;
556 }
557 
isprime(void * a,int b,int * c)558 static int isprime(void *a, int b, int *c)
559 {
560    LTC_ARGCHK(a != NULL);
561    LTC_ARGCHK(c != NULL);
562    if (b == 0) {
563        b = LTC_MILLER_RABIN_REPS;
564    } /* if */
565    *c = mpz_probab_prime_p(a, b) > 0 ? LTC_MP_YES : LTC_MP_NO;
566    return CRYPT_OK;
567 }
568 
set_rand(void * a,int size)569 static int set_rand(void *a, int size)
570 {
571    LTC_ARGCHK(a != NULL);
572    mpz_random(a, size);
573    return CRYPT_OK;
574 }
575 
576 const ltc_math_descriptor gmp_desc = {
577    "GNU MP",
578    sizeof(mp_limb_t) * CHAR_BIT - GMP_NAIL_BITS,
579 
580    &init,
581    &init_copy,
582    &deinit,
583 
584    &neg,
585    &copy,
586 
587    &set_int,
588    &get_int,
589    &get_digit,
590    &get_digit_count,
591    &compare,
592    &compare_d,
593    &count_bits,
594    &count_lsb_bits,
595    &twoexpt,
596 
597    &read_radix,
598    &write_radix,
599    &unsigned_size,
600    &unsigned_write,
601    &unsigned_read,
602 
603    &add,
604    &addi,
605    &sub,
606    &subi,
607    &mul,
608    &muli,
609    &sqr,
610    &sqrtmod_prime,
611    &divide,
612    &div_2,
613    &modi,
614    &gcd,
615    &lcm,
616 
617    &mulmod,
618    &sqrmod,
619    &invmod,
620 
621    &montgomery_setup,
622    &montgomery_normalization,
623    &montgomery_reduce,
624    &montgomery_deinit,
625 
626    &exptmod,
627    &isprime,
628 
629 #ifdef LTC_MECC
630 #ifdef LTC_MECC_FP
631    &ltc_ecc_fp_mulmod,
632 #else
633    &ltc_ecc_mulmod,
634 #endif /* LTC_MECC_FP */
635    &ltc_ecc_projective_add_point,
636    &ltc_ecc_projective_dbl_point,
637    &ltc_ecc_map,
638 #ifdef LTC_ECC_SHAMIR
639 #ifdef LTC_MECC_FP
640    &ltc_ecc_fp_mul2add,
641 #else
642    &ltc_ecc_mul2add,
643 #endif /* LTC_MECC_FP */
644 #else
645    NULL,
646 #endif /* LTC_ECC_SHAMIR */
647 #else
648    NULL, NULL, NULL, NULL, NULL,
649 #endif /* LTC_MECC */
650 
651 #ifdef LTC_MRSA
652    &rsa_make_key,
653    &rsa_exptmod,
654 #else
655    NULL, NULL,
656 #endif
657    &addmod,
658    &submod,
659 
660    &set_rand,
661 
662 };
663 
664 
665 #endif
666 
667 /* ref:         $Format:%D$ */
668 /* git commit:  $Format:%H$ */
669 /* commit time: $Format:%ai$ */
670