1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
6 * The library is free for all purposes without any express
18 int tfm_code, ltc_code;
19 } tfm_to_ltc_codes[] = {
20 { FP_OKAY , CRYPT_OK},
21 { FP_MEM , CRYPT_MEM},
22 { FP_VAL , CRYPT_INVALID_ARG},
26 Convert a tfm error to a LTC error (Possibly the most powerful function ever! Oh wait... no)
27 @param err The error to convert
28 @return The equivalent LTC error code or CRYPT_ERROR if none found
30 static int tfm_to_ltc_error(int err)
34 for (x = 0; x < (int)(sizeof(tfm_to_ltc_codes)/sizeof(tfm_to_ltc_codes[0])); x++) {
35 if (err == tfm_to_ltc_codes[x].tfm_code) {
36 return tfm_to_ltc_codes[x].ltc_code;
42 static int init(void **a)
44 LTC_ARGCHK(a != NULL);
46 *a = XCALLOC(1, sizeof(fp_int));
54 static void deinit(void *a)
56 LTC_ARGCHKVD(a != NULL);
60 static int neg(void *a, void *b)
62 LTC_ARGCHK(a != NULL);
63 LTC_ARGCHK(b != NULL);
64 fp_neg(((fp_int*)a), ((fp_int*)b));
68 static int copy(void *a, void *b)
70 LTC_ARGCHK(a != NULL);
71 LTC_ARGCHK(b != NULL);
76 static int init_copy(void **a, void *b)
78 if (init(a) != CRYPT_OK) {
84 /* ---- trivial ---- */
85 static int set_int(void *a, ltc_mp_digit b)
87 LTC_ARGCHK(a != NULL);
92 static unsigned long get_int(void *a)
95 LTC_ARGCHK(a != NULL);
97 return A->used > 0 ? A->dp[0] : 0;
100 static ltc_mp_digit get_digit(void *a, int n)
103 LTC_ARGCHK(a != NULL);
105 return (n >= A->used || n < 0) ? 0 : A->dp[n];
108 static int get_digit_count(void *a)
111 LTC_ARGCHK(a != NULL);
116 static int compare(void *a, void *b)
119 LTC_ARGCHK(a != NULL);
120 LTC_ARGCHK(b != NULL);
123 case FP_LT: return LTC_MP_LT;
124 case FP_EQ: return LTC_MP_EQ;
125 case FP_GT: return LTC_MP_GT;
130 static int compare_d(void *a, ltc_mp_digit b)
133 LTC_ARGCHK(a != NULL);
134 ret = fp_cmp_d(a, b);
136 case FP_LT: return LTC_MP_LT;
137 case FP_EQ: return LTC_MP_EQ;
138 case FP_GT: return LTC_MP_GT;
143 static int count_bits(void *a)
145 LTC_ARGCHK(a != NULL);
146 return fp_count_bits(a);
149 static int count_lsb_bits(void *a)
151 LTC_ARGCHK(a != NULL);
152 return fp_cnt_lsb(a);
155 static int twoexpt(void *a, int n)
157 LTC_ARGCHK(a != NULL);
162 /* ---- conversions ---- */
164 /* read ascii string */
165 static int read_radix(void *a, const char *b, int radix)
167 LTC_ARGCHK(a != NULL);
168 LTC_ARGCHK(b != NULL);
169 return tfm_to_ltc_error(fp_read_radix(a, (char *)b, radix));
173 static int write_radix(void *a, char *b, int radix)
175 LTC_ARGCHK(a != NULL);
176 LTC_ARGCHK(b != NULL);
177 return tfm_to_ltc_error(fp_toradix(a, b, radix));
180 /* get size as unsigned char string */
181 static unsigned long unsigned_size(void *a)
183 LTC_ARGCHK(a != NULL);
184 return fp_unsigned_bin_size(a);
188 static int unsigned_write(void *a, unsigned char *b)
190 LTC_ARGCHK(a != NULL);
191 LTC_ARGCHK(b != NULL);
192 fp_to_unsigned_bin(a, b);
197 static int unsigned_read(void *a, unsigned char *b, unsigned long len)
199 LTC_ARGCHK(a != NULL);
200 LTC_ARGCHK(b != NULL);
201 fp_read_unsigned_bin(a, b, len);
206 static int add(void *a, void *b, void *c)
208 LTC_ARGCHK(a != NULL);
209 LTC_ARGCHK(b != NULL);
210 LTC_ARGCHK(c != NULL);
215 static int addi(void *a, ltc_mp_digit b, void *c)
217 LTC_ARGCHK(a != NULL);
218 LTC_ARGCHK(c != NULL);
224 static int sub(void *a, void *b, void *c)
226 LTC_ARGCHK(a != NULL);
227 LTC_ARGCHK(b != NULL);
228 LTC_ARGCHK(c != NULL);
233 static int subi(void *a, ltc_mp_digit b, void *c)
235 LTC_ARGCHK(a != NULL);
236 LTC_ARGCHK(c != NULL);
242 static int mul(void *a, void *b, void *c)
244 LTC_ARGCHK(a != NULL);
245 LTC_ARGCHK(b != NULL);
246 LTC_ARGCHK(c != NULL);
251 static int muli(void *a, ltc_mp_digit b, void *c)
253 LTC_ARGCHK(a != NULL);
254 LTC_ARGCHK(c != NULL);
260 static int sqr(void *a, void *b)
262 LTC_ARGCHK(a != NULL);
263 LTC_ARGCHK(b != NULL);
269 static int divide(void *a, void *b, void *c, void *d)
271 LTC_ARGCHK(a != NULL);
272 LTC_ARGCHK(b != NULL);
273 return tfm_to_ltc_error(fp_div(a, b, c, d));
276 static int div_2(void *a, void *b)
278 LTC_ARGCHK(a != NULL);
279 LTC_ARGCHK(b != NULL);
285 static int modi(void *a, ltc_mp_digit b, ltc_mp_digit *c)
290 LTC_ARGCHK(a != NULL);
291 LTC_ARGCHK(c != NULL);
293 if ((err = tfm_to_ltc_error(fp_mod_d(a, b, &tmp))) != CRYPT_OK) {
301 static int gcd(void *a, void *b, void *c)
303 LTC_ARGCHK(a != NULL);
304 LTC_ARGCHK(b != NULL);
305 LTC_ARGCHK(c != NULL);
311 static int lcm(void *a, void *b, void *c)
313 LTC_ARGCHK(a != NULL);
314 LTC_ARGCHK(b != NULL);
315 LTC_ARGCHK(c != NULL);
320 static int addmod(void *a, void *b, void *c, void *d)
322 LTC_ARGCHK(a != NULL);
323 LTC_ARGCHK(b != NULL);
324 LTC_ARGCHK(c != NULL);
325 LTC_ARGCHK(d != NULL);
326 return tfm_to_ltc_error(fp_addmod(a,b,c,d));
329 static int submod(void *a, void *b, void *c, void *d)
331 LTC_ARGCHK(a != NULL);
332 LTC_ARGCHK(b != NULL);
333 LTC_ARGCHK(c != NULL);
334 LTC_ARGCHK(d != NULL);
335 return tfm_to_ltc_error(fp_submod(a,b,c,d));
338 static int mulmod(void *a, void *b, void *c, void *d)
340 LTC_ARGCHK(a != NULL);
341 LTC_ARGCHK(b != NULL);
342 LTC_ARGCHK(c != NULL);
343 LTC_ARGCHK(d != NULL);
344 return tfm_to_ltc_error(fp_mulmod(a,b,c,d));
347 static int sqrmod(void *a, void *b, void *c)
349 LTC_ARGCHK(a != NULL);
350 LTC_ARGCHK(b != NULL);
351 LTC_ARGCHK(c != NULL);
352 return tfm_to_ltc_error(fp_sqrmod(a,b,c));
356 static int invmod(void *a, void *b, void *c)
358 LTC_ARGCHK(a != NULL);
359 LTC_ARGCHK(b != NULL);
360 LTC_ARGCHK(c != NULL);
361 return tfm_to_ltc_error(fp_invmod(a, b, c));
365 static int montgomery_setup(void *a, void **b)
368 LTC_ARGCHK(a != NULL);
369 LTC_ARGCHK(b != NULL);
370 *b = XCALLOC(1, sizeof(fp_digit));
374 if ((err = tfm_to_ltc_error(fp_montgomery_setup(a, (fp_digit *)*b))) != CRYPT_OK) {
380 /* get normalization value */
381 static int montgomery_normalization(void *a, void *b)
383 LTC_ARGCHK(a != NULL);
384 LTC_ARGCHK(b != NULL);
385 fp_montgomery_calc_normalization(a, b);
390 static int montgomery_reduce(void *a, void *b, void *c)
392 LTC_ARGCHK(a != NULL);
393 LTC_ARGCHK(b != NULL);
394 LTC_ARGCHK(c != NULL);
395 fp_montgomery_reduce(a, b, *((fp_digit *)c));
400 static void montgomery_deinit(void *a)
405 static int exptmod(void *a, void *b, void *c, void *d)
407 LTC_ARGCHK(a != NULL);
408 LTC_ARGCHK(b != NULL);
409 LTC_ARGCHK(c != NULL);
410 LTC_ARGCHK(d != NULL);
411 return tfm_to_ltc_error(fp_exptmod(a,b,c,d));
414 static int isprime(void *a, int b, int *c)
416 LTC_ARGCHK(a != NULL);
417 LTC_ARGCHK(c != NULL);
419 b = LTC_MILLER_RABIN_REPS;
421 *c = (fp_isprime_ex(a, b) == FP_YES) ? LTC_MP_YES : LTC_MP_NO;
425 #if defined(LTC_MECC) && defined(LTC_MECC_ACCEL)
427 static int tfm_ecc_projective_dbl_point(ecc_point *P, ecc_point *R, void *modulus, void *Mp)
432 LTC_ARGCHK(P != NULL);
433 LTC_ARGCHK(R != NULL);
434 LTC_ARGCHK(modulus != NULL);
435 LTC_ARGCHK(Mp != NULL);
437 mp = *((fp_digit*)Mp);
450 fp_montgomery_reduce(&t1, modulus, mp);
452 fp_mul(R->z, R->y, R->z);
453 fp_montgomery_reduce(R->z, modulus, mp);
455 fp_add(R->z, R->z, R->z);
456 if (fp_cmp(R->z, modulus) != FP_LT) {
457 fp_sub(R->z, modulus, R->z);
461 fp_sub(R->x, &t1, &t2);
462 if (fp_cmp_d(&t2, 0) == FP_LT) {
463 fp_add(&t2, modulus, &t2);
466 fp_add(&t1, R->x, &t1);
467 if (fp_cmp(&t1, modulus) != FP_LT) {
468 fp_sub(&t1, modulus, &t1);
471 fp_mul(&t1, &t2, &t2);
472 fp_montgomery_reduce(&t2, modulus, mp);
474 fp_add(&t2, &t2, &t1);
475 if (fp_cmp(&t1, modulus) != FP_LT) {
476 fp_sub(&t1, modulus, &t1);
479 fp_add(&t1, &t2, &t1);
480 if (fp_cmp(&t1, modulus) != FP_LT) {
481 fp_sub(&t1, modulus, &t1);
485 fp_add(R->y, R->y, R->y);
486 if (fp_cmp(R->y, modulus) != FP_LT) {
487 fp_sub(R->y, modulus, R->y);
491 fp_montgomery_reduce(R->y, modulus, mp);
494 fp_montgomery_reduce(&t2, modulus, mp);
497 fp_add(&t2, modulus, &t2);
501 fp_mul(R->y, R->x, R->y);
502 fp_montgomery_reduce(R->y, modulus, mp);
506 fp_montgomery_reduce(R->x, modulus, mp);
508 fp_sub(R->x, R->y, R->x);
509 if (fp_cmp_d(R->x, 0) == FP_LT) {
510 fp_add(R->x, modulus, R->x);
513 fp_sub(R->x, R->y, R->x);
514 if (fp_cmp_d(R->x, 0) == FP_LT) {
515 fp_add(R->x, modulus, R->x);
519 fp_sub(R->y, R->x, R->y);
520 if (fp_cmp_d(R->y, 0) == FP_LT) {
521 fp_add(R->y, modulus, R->y);
524 fp_mul(R->y, &t1, R->y);
525 fp_montgomery_reduce(R->y, modulus, mp);
527 fp_sub(R->y, &t2, R->y);
528 if (fp_cmp_d(R->y, 0) == FP_LT) {
529 fp_add(R->y, modulus, R->y);
537 @param P The point to add
538 @param Q The point to add
539 @param R [out] The destination of the double
540 @param modulus The modulus of the field the ECC curve is in
541 @param Mp The "b" value from montgomery_setup()
542 @return CRYPT_OK on success
544 static int tfm_ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R, void *modulus, void *Mp)
546 fp_int t1, t2, x, y, z;
549 LTC_ARGCHK(P != NULL);
550 LTC_ARGCHK(Q != NULL);
551 LTC_ARGCHK(R != NULL);
552 LTC_ARGCHK(modulus != NULL);
553 LTC_ARGCHK(Mp != NULL);
555 mp = *((fp_digit*)Mp);
563 /* should we dbl instead? */
564 fp_sub(modulus, Q->y, &t1);
565 if ( (fp_cmp(P->x, Q->x) == FP_EQ) &&
566 (Q->z != NULL && fp_cmp(P->z, Q->z) == FP_EQ) &&
567 (fp_cmp(P->y, Q->y) == FP_EQ || fp_cmp(P->y, &t1) == FP_EQ)) {
568 return tfm_ecc_projective_dbl_point(P, R, modulus, Mp);
575 /* if Z is one then these are no-operations */
579 fp_montgomery_reduce(&t1, modulus, mp);
582 fp_montgomery_reduce(&x, modulus, mp);
584 fp_mul(Q->z, &t1, &t1);
585 fp_montgomery_reduce(&t1, modulus, mp);
588 fp_montgomery_reduce(&y, modulus, mp);
593 fp_montgomery_reduce(&t1, modulus, mp);
595 fp_mul(Q->x, &t1, &t2);
596 fp_montgomery_reduce(&t2, modulus, mp);
598 fp_mul(&z, &t1, &t1);
599 fp_montgomery_reduce(&t1, modulus, mp);
601 fp_mul(Q->y, &t1, &t1);
602 fp_montgomery_reduce(&t1, modulus, mp);
606 if (fp_cmp_d(&y, 0) == FP_LT) {
607 fp_add(&y, modulus, &y);
610 fp_add(&t1, &t1, &t1);
611 if (fp_cmp(&t1, modulus) != FP_LT) {
612 fp_sub(&t1, modulus, &t1);
615 fp_add(&t1, &y, &t1);
616 if (fp_cmp(&t1, modulus) != FP_LT) {
617 fp_sub(&t1, modulus, &t1);
621 if (fp_cmp_d(&x, 0) == FP_LT) {
622 fp_add(&x, modulus, &x);
625 fp_add(&t2, &t2, &t2);
626 if (fp_cmp(&t2, modulus) != FP_LT) {
627 fp_sub(&t2, modulus, &t2);
630 fp_add(&t2, &x, &t2);
631 if (fp_cmp(&t2, modulus) != FP_LT) {
632 fp_sub(&t2, modulus, &t2);
638 fp_mul(&z, Q->z, &z);
639 fp_montgomery_reduce(&z, modulus, mp);
644 fp_montgomery_reduce(&z, modulus, mp);
647 fp_mul(&t1, &x, &t1);
648 fp_montgomery_reduce(&t1, modulus, mp);
651 fp_montgomery_reduce(&x, modulus, mp);
653 fp_mul(&t2, &x, &t2);
654 fp_montgomery_reduce(&t2, modulus, mp);
656 fp_mul(&t1, &x, &t1);
657 fp_montgomery_reduce(&t1, modulus, mp);
661 fp_montgomery_reduce(&x, modulus, mp);
664 if (fp_cmp_d(&x, 0) == FP_LT) {
665 fp_add(&x, modulus, &x);
669 fp_sub(&t2, &x, &t2);
670 if (fp_cmp_d(&t2, 0) == FP_LT) {
671 fp_add(&t2, modulus, &t2);
674 fp_sub(&t2, &x, &t2);
675 if (fp_cmp_d(&t2, 0) == FP_LT) {
676 fp_add(&t2, modulus, &t2);
679 fp_mul(&t2, &y, &t2);
680 fp_montgomery_reduce(&t2, modulus, mp);
682 fp_sub(&t2, &t1, &y);
683 if (fp_cmp_d(&y, 0) == FP_LT) {
684 fp_add(&y, modulus, &y);
688 fp_add(&y, modulus, &y);
702 static int set_rand(void *a, int size)
704 LTC_ARGCHK(a != NULL);
709 const ltc_math_descriptor tfm_desc = {
755 &montgomery_normalization,
767 #endif /* LTC_MECC_FP */
768 #ifdef LTC_MECC_ACCEL
769 &tfm_ecc_projective_add_point,
770 &tfm_ecc_projective_dbl_point,
772 <c_ecc_projective_add_point,
773 <c_ecc_projective_dbl_point,
774 #endif /* LTC_MECC_ACCEL */
776 #ifdef LTC_ECC_SHAMIR
781 #endif /* LTC_MECC_FP */
784 #endif /* LTC_ECC_SHAMIR */
786 NULL, NULL, NULL, NULL, NULL,
787 #endif /* LTC_MECC */
805 /* ref: $Format:%D$ */
806 /* git commit: $Format:%H$ */
807 /* commit time: $Format:%ai$ */