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 ©,
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 ÷,
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 <c_ecc_fp_mulmod,
632 #else
633 <c_ecc_mulmod,
634 #endif /* LTC_MECC_FP */
635 <c_ecc_projective_add_point,
636 <c_ecc_projective_dbl_point,
637 <c_ecc_map,
638 #ifdef LTC_ECC_SHAMIR
639 #ifdef LTC_MECC_FP
640 <c_ecc_fp_mul2add,
641 #else
642 <c_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