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