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 ©,
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 ÷,
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 <c_ecc_fp_mulmod,
625 #else
626 <c_ecc_mulmod,
627 #endif /* LTC_MECC_FP */
628 <c_ecc_projective_add_point,
629 <c_ecc_projective_dbl_point,
630 <c_ecc_map,
631 #ifdef LTC_ECC_SHAMIR
632 #ifdef LTC_MECC_FP
633 <c_ecc_fp_mul2add,
634 #else
635 <c_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