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 TFM_DESC
8
9 #include <tfm.h>
10
11 static const struct {
12 int tfm_code, ltc_code;
13 } tfm_to_ltc_codes[] = {
14 { FP_OKAY , CRYPT_OK},
15 { FP_MEM , CRYPT_MEM},
16 { FP_VAL , CRYPT_INVALID_ARG},
17 };
18
19 /**
20 Convert a tfm error to a LTC error (Possibly the most powerful function ever! Oh wait... no)
21 @param err The error to convert
22 @return The equivalent LTC error code or CRYPT_ERROR if none found
23 */
tfm_to_ltc_error(int err)24 static int tfm_to_ltc_error(int err)
25 {
26 int x;
27
28 for (x = 0; x < (int)(sizeof(tfm_to_ltc_codes)/sizeof(tfm_to_ltc_codes[0])); x++) {
29 if (err == tfm_to_ltc_codes[x].tfm_code) {
30 return tfm_to_ltc_codes[x].ltc_code;
31 }
32 }
33 return CRYPT_ERROR;
34 }
35
init(void ** a)36 static int init(void **a)
37 {
38 LTC_ARGCHK(a != NULL);
39
40 *a = XCALLOC(1, sizeof(fp_int));
41 if (*a == NULL) {
42 return CRYPT_MEM;
43 }
44 fp_init(*a);
45 return CRYPT_OK;
46 }
47
deinit(void * a)48 static void deinit(void *a)
49 {
50 LTC_ARGCHKVD(a != NULL);
51 XFREE(a);
52 }
53
neg(void * a,void * b)54 static int neg(void *a, void *b)
55 {
56 LTC_ARGCHK(a != NULL);
57 LTC_ARGCHK(b != NULL);
58 fp_neg(((fp_int*)a), ((fp_int*)b));
59 return CRYPT_OK;
60 }
61
copy(void * a,void * b)62 static int copy(void *a, void *b)
63 {
64 LTC_ARGCHK(a != NULL);
65 LTC_ARGCHK(b != NULL);
66 fp_copy(a, b);
67 return CRYPT_OK;
68 }
69
init_copy(void ** a,void * b)70 static int init_copy(void **a, void *b)
71 {
72 if (init(a) != CRYPT_OK) {
73 return CRYPT_MEM;
74 }
75 return copy(b, *a);
76 }
77
78 /* ---- trivial ---- */
set_int(void * a,ltc_mp_digit b)79 static int set_int(void *a, ltc_mp_digit b)
80 {
81 LTC_ARGCHK(a != NULL);
82 fp_set(a, b);
83 return CRYPT_OK;
84 }
85
get_int(void * a)86 static unsigned long get_int(void *a)
87 {
88 fp_int *A;
89 LTC_ARGCHK(a != NULL);
90 A = a;
91 return A->used > 0 ? A->dp[0] : 0;
92 }
93
get_digit(void * a,int n)94 static ltc_mp_digit get_digit(void *a, int n)
95 {
96 fp_int *A;
97 LTC_ARGCHK(a != NULL);
98 A = a;
99 return (n >= A->used || n < 0) ? 0 : A->dp[n];
100 }
101
get_digit_count(void * a)102 static int get_digit_count(void *a)
103 {
104 fp_int *A;
105 LTC_ARGCHK(a != NULL);
106 A = a;
107 return A->used;
108 }
109
compare(void * a,void * b)110 static int compare(void *a, void *b)
111 {
112 int ret;
113 LTC_ARGCHK(a != NULL);
114 LTC_ARGCHK(b != NULL);
115 ret = fp_cmp(a, b);
116 switch (ret) {
117 case FP_LT: return LTC_MP_LT;
118 case FP_EQ: return LTC_MP_EQ;
119 case FP_GT: return LTC_MP_GT;
120 }
121 return 0;
122 }
123
compare_d(void * a,ltc_mp_digit b)124 static int compare_d(void *a, ltc_mp_digit b)
125 {
126 int ret;
127 LTC_ARGCHK(a != NULL);
128 ret = fp_cmp_d(a, b);
129 switch (ret) {
130 case FP_LT: return LTC_MP_LT;
131 case FP_EQ: return LTC_MP_EQ;
132 case FP_GT: return LTC_MP_GT;
133 }
134 return 0;
135 }
136
count_bits(void * a)137 static int count_bits(void *a)
138 {
139 LTC_ARGCHK(a != NULL);
140 return fp_count_bits(a);
141 }
142
count_lsb_bits(void * a)143 static int count_lsb_bits(void *a)
144 {
145 LTC_ARGCHK(a != NULL);
146 return fp_cnt_lsb(a);
147 }
148
twoexpt(void * a,int n)149 static int twoexpt(void *a, int n)
150 {
151 LTC_ARGCHK(a != NULL);
152 fp_2expt(a, n);
153 return CRYPT_OK;
154 }
155
156 /* ---- conversions ---- */
157
158 /* read ascii string */
read_radix(void * a,const char * b,int radix)159 static int read_radix(void *a, const char *b, int radix)
160 {
161 LTC_ARGCHK(a != NULL);
162 LTC_ARGCHK(b != NULL);
163 return tfm_to_ltc_error(fp_read_radix(a, (char *)b, radix));
164 }
165
166 /* write one */
write_radix(void * a,char * b,int radix)167 static int write_radix(void *a, char *b, int radix)
168 {
169 LTC_ARGCHK(a != NULL);
170 LTC_ARGCHK(b != NULL);
171 return tfm_to_ltc_error(fp_toradix(a, b, radix));
172 }
173
174 /* get size as unsigned char string */
unsigned_size(void * a)175 static unsigned long unsigned_size(void *a)
176 {
177 LTC_ARGCHK(a != NULL);
178 return fp_unsigned_bin_size(a);
179 }
180
181 /* store */
unsigned_write(void * a,unsigned char * b)182 static int unsigned_write(void *a, unsigned char *b)
183 {
184 LTC_ARGCHK(a != NULL);
185 LTC_ARGCHK(b != NULL);
186 fp_to_unsigned_bin(a, b);
187 return CRYPT_OK;
188 }
189
190 /* read */
unsigned_read(void * a,unsigned char * b,unsigned long len)191 static int unsigned_read(void *a, unsigned char *b, unsigned long len)
192 {
193 LTC_ARGCHK(a != NULL);
194 LTC_ARGCHK(b != NULL);
195 fp_read_unsigned_bin(a, b, len);
196 return CRYPT_OK;
197 }
198
199 /* add */
add(void * a,void * b,void * c)200 static int add(void *a, void *b, void *c)
201 {
202 LTC_ARGCHK(a != NULL);
203 LTC_ARGCHK(b != NULL);
204 LTC_ARGCHK(c != NULL);
205 fp_add(a, b, c);
206 return CRYPT_OK;
207 }
208
addi(void * a,ltc_mp_digit b,void * c)209 static int addi(void *a, ltc_mp_digit b, void *c)
210 {
211 LTC_ARGCHK(a != NULL);
212 LTC_ARGCHK(c != NULL);
213 fp_add_d(a, b, c);
214 return CRYPT_OK;
215 }
216
217 /* sub */
sub(void * a,void * b,void * c)218 static int sub(void *a, void *b, void *c)
219 {
220 LTC_ARGCHK(a != NULL);
221 LTC_ARGCHK(b != NULL);
222 LTC_ARGCHK(c != NULL);
223 fp_sub(a, b, c);
224 return CRYPT_OK;
225 }
226
subi(void * a,ltc_mp_digit b,void * c)227 static int subi(void *a, ltc_mp_digit b, void *c)
228 {
229 LTC_ARGCHK(a != NULL);
230 LTC_ARGCHK(c != NULL);
231 fp_sub_d(a, b, c);
232 return CRYPT_OK;
233 }
234
235 /* mul */
mul(void * a,void * b,void * c)236 static int mul(void *a, void *b, void *c)
237 {
238 LTC_ARGCHK(a != NULL);
239 LTC_ARGCHK(b != NULL);
240 LTC_ARGCHK(c != NULL);
241 fp_mul(a, b, c);
242 return CRYPT_OK;
243 }
244
muli(void * a,ltc_mp_digit b,void * c)245 static int muli(void *a, ltc_mp_digit b, void *c)
246 {
247 LTC_ARGCHK(a != NULL);
248 LTC_ARGCHK(c != NULL);
249 fp_mul_d(a, b, c);
250 return CRYPT_OK;
251 }
252
253 /* sqr */
sqr(void * a,void * b)254 static int sqr(void *a, void *b)
255 {
256 LTC_ARGCHK(a != NULL);
257 LTC_ARGCHK(b != NULL);
258 fp_sqr(a, b);
259 return CRYPT_OK;
260 }
261
262 /* sqrtmod_prime - NOT SUPPORTED */
263
264 /* div */
divide(void * a,void * b,void * c,void * d)265 static int divide(void *a, void *b, void *c, void *d)
266 {
267 LTC_ARGCHK(a != NULL);
268 LTC_ARGCHK(b != NULL);
269 return tfm_to_ltc_error(fp_div(a, b, c, d));
270 }
271
div_2(void * a,void * b)272 static int div_2(void *a, void *b)
273 {
274 LTC_ARGCHK(a != NULL);
275 LTC_ARGCHK(b != NULL);
276 fp_div_2(a, b);
277 return CRYPT_OK;
278 }
279
280 /* modi */
modi(void * a,ltc_mp_digit b,ltc_mp_digit * c)281 static int modi(void *a, ltc_mp_digit b, ltc_mp_digit *c)
282 {
283 fp_digit tmp;
284 int err;
285
286 LTC_ARGCHK(a != NULL);
287 LTC_ARGCHK(c != NULL);
288
289 if ((err = tfm_to_ltc_error(fp_mod_d(a, b, &tmp))) != CRYPT_OK) {
290 return err;
291 }
292 *c = tmp;
293 return CRYPT_OK;
294 }
295
296 /* gcd */
gcd(void * a,void * b,void * c)297 static int gcd(void *a, void *b, void *c)
298 {
299 LTC_ARGCHK(a != NULL);
300 LTC_ARGCHK(b != NULL);
301 LTC_ARGCHK(c != NULL);
302 fp_gcd(a, b, c);
303 return CRYPT_OK;
304 }
305
306 /* lcm */
lcm(void * a,void * b,void * c)307 static int lcm(void *a, void *b, void *c)
308 {
309 LTC_ARGCHK(a != NULL);
310 LTC_ARGCHK(b != NULL);
311 LTC_ARGCHK(c != NULL);
312 fp_lcm(a, b, c);
313 return CRYPT_OK;
314 }
315
addmod(void * a,void * b,void * c,void * d)316 static int addmod(void *a, void *b, void *c, void *d)
317 {
318 LTC_ARGCHK(a != NULL);
319 LTC_ARGCHK(b != NULL);
320 LTC_ARGCHK(c != NULL);
321 LTC_ARGCHK(d != NULL);
322 return tfm_to_ltc_error(fp_addmod(a,b,c,d));
323 }
324
submod(void * a,void * b,void * c,void * d)325 static int submod(void *a, void *b, void *c, void *d)
326 {
327 LTC_ARGCHK(a != NULL);
328 LTC_ARGCHK(b != NULL);
329 LTC_ARGCHK(c != NULL);
330 LTC_ARGCHK(d != NULL);
331 return tfm_to_ltc_error(fp_submod(a,b,c,d));
332 }
333
mulmod(void * a,void * b,void * c,void * d)334 static int mulmod(void *a, void *b, void *c, void *d)
335 {
336 LTC_ARGCHK(a != NULL);
337 LTC_ARGCHK(b != NULL);
338 LTC_ARGCHK(c != NULL);
339 LTC_ARGCHK(d != NULL);
340 return tfm_to_ltc_error(fp_mulmod(a,b,c,d));
341 }
342
sqrmod(void * a,void * b,void * c)343 static int sqrmod(void *a, void *b, void *c)
344 {
345 LTC_ARGCHK(a != NULL);
346 LTC_ARGCHK(b != NULL);
347 LTC_ARGCHK(c != NULL);
348 return tfm_to_ltc_error(fp_sqrmod(a,b,c));
349 }
350
351 /* invmod */
invmod(void * a,void * b,void * c)352 static int invmod(void *a, void *b, void *c)
353 {
354 LTC_ARGCHK(a != NULL);
355 LTC_ARGCHK(b != NULL);
356 LTC_ARGCHK(c != NULL);
357 return tfm_to_ltc_error(fp_invmod(a, b, c));
358 }
359
360 /* setup */
montgomery_setup(void * a,void ** b)361 static int montgomery_setup(void *a, void **b)
362 {
363 int err;
364 LTC_ARGCHK(a != NULL);
365 LTC_ARGCHK(b != NULL);
366 *b = XCALLOC(1, sizeof(fp_digit));
367 if (*b == NULL) {
368 return CRYPT_MEM;
369 }
370 if ((err = tfm_to_ltc_error(fp_montgomery_setup(a, (fp_digit *)*b))) != CRYPT_OK) {
371 XFREE(*b);
372 }
373 return err;
374 }
375
376 /* get normalization value */
montgomery_normalization(void * a,void * b)377 static int montgomery_normalization(void *a, void *b)
378 {
379 LTC_ARGCHK(a != NULL);
380 LTC_ARGCHK(b != NULL);
381 fp_montgomery_calc_normalization(a, b);
382 return CRYPT_OK;
383 }
384
385 /* reduce */
montgomery_reduce(void * a,void * b,void * c)386 static int montgomery_reduce(void *a, void *b, void *c)
387 {
388 LTC_ARGCHK(a != NULL);
389 LTC_ARGCHK(b != NULL);
390 LTC_ARGCHK(c != NULL);
391 fp_montgomery_reduce(a, b, *((fp_digit *)c));
392 return CRYPT_OK;
393 }
394
395 /* clean up */
montgomery_deinit(void * a)396 static void montgomery_deinit(void *a)
397 {
398 XFREE(a);
399 }
400
exptmod(void * a,void * b,void * c,void * d)401 static int exptmod(void *a, void *b, void *c, void *d)
402 {
403 LTC_ARGCHK(a != NULL);
404 LTC_ARGCHK(b != NULL);
405 LTC_ARGCHK(c != NULL);
406 LTC_ARGCHK(d != NULL);
407 return tfm_to_ltc_error(fp_exptmod(a,b,c,d));
408 }
409
isprime(void * a,int b,int * c)410 static int isprime(void *a, int b, int *c)
411 {
412 LTC_ARGCHK(a != NULL);
413 LTC_ARGCHK(c != NULL);
414 if (b == 0) {
415 b = LTC_MILLER_RABIN_REPS;
416 } /* if */
417 *c = (fp_isprime_ex(a, b) == FP_YES) ? LTC_MP_YES : LTC_MP_NO;
418 return CRYPT_OK;
419 }
420
421 #if defined(LTC_MECC) && defined(LTC_MECC_ACCEL)
422
tfm_ecc_projective_dbl_point(const ecc_point * P,ecc_point * R,void * ma,void * modulus,void * Mp)423 static int tfm_ecc_projective_dbl_point(const ecc_point *P, ecc_point *R, void *ma, void *modulus, void *Mp)
424 {
425 fp_int t1, t2;
426 fp_digit mp;
427 int err, inf;
428
429 LTC_ARGCHK(P != NULL);
430 LTC_ARGCHK(R != NULL);
431 LTC_ARGCHK(modulus != NULL);
432 LTC_ARGCHK(Mp != NULL);
433
434 mp = *((fp_digit*)Mp);
435
436 fp_init(&t1);
437 fp_init(&t2);
438
439 if (P != R) {
440 fp_copy(P->x, R->x);
441 fp_copy(P->y, R->y);
442 fp_copy(P->z, R->z);
443 }
444
445 if ((err = ltc_ecc_is_point_at_infinity(P, modulus, &inf)) != CRYPT_OK) return err;
446 if (inf) {
447 /* if P is point at infinity >> Result = point at infinity */
448 ltc_mp.set_int(R->x, 1);
449 ltc_mp.set_int(R->y, 1);
450 ltc_mp.set_int(R->z, 0);
451 return CRYPT_OK;
452 }
453
454 /* t1 = Z * Z */
455 fp_sqr(R->z, &t1);
456 fp_montgomery_reduce(&t1, modulus, mp);
457 /* Z = Y * Z */
458 fp_mul(R->z, R->y, R->z);
459 fp_montgomery_reduce(R->z, modulus, mp);
460 /* Z = 2Z */
461 fp_add(R->z, R->z, R->z);
462 if (fp_cmp(R->z, modulus) != FP_LT) {
463 fp_sub(R->z, modulus, R->z);
464 }
465
466 if (ma == NULL) { /* special case for curves with a == -3 (10% faster than general case) */
467 /* T2 = X - T1 */
468 fp_sub(R->x, &t1, &t2);
469 if (fp_cmp_d(&t2, 0) == LTC_MP_LT) {
470 fp_add(&t2, modulus, &t2);
471 }
472 /* T1 = X + T1 */
473 fp_add(&t1, R->x, &t1);
474 if (fp_cmp(&t1, modulus) != FP_LT) {
475 fp_sub(&t1, modulus, &t1);
476 }
477 /* T2 = T1 * T2 */
478 fp_mul(&t1, &t2, &t2);
479 fp_montgomery_reduce(&t2, modulus, mp);
480 /* T1 = 2T2 */
481 fp_add(&t2, &t2, &t1);
482 if (fp_cmp(&t1, modulus) != FP_LT) {
483 fp_sub(&t1, modulus, &t1);
484 }
485 /* T1 = T1 + T2 */
486 fp_add(&t1, &t2, &t1);
487 if (fp_cmp(&t1, modulus) != FP_LT) {
488 fp_sub(&t1, modulus, &t1);
489 }
490 }
491 else {
492 /* T2 = T1 * T1 */
493 fp_sqr(&t1, &t2);
494 fp_montgomery_reduce(&t2, modulus, mp);
495 /* T1 = T2 * a */
496 fp_mul(&t2, ma, &t1);
497 fp_montgomery_reduce(&t1, modulus, mp);
498 /* T2 = X * X */
499 fp_sqr(R->x, &t2);
500 fp_montgomery_reduce(&t2, modulus, mp);
501 /* T1 = T1 + T2 */
502 fp_add(&t1, &t2, &t1);
503 if (fp_cmp(&t1, modulus) != FP_LT) {
504 fp_sub(&t1, modulus, &t1);
505 }
506 /* T1 = T1 + T2 */
507 fp_add(&t1, &t2, &t1);
508 if (fp_cmp(&t1, modulus) != FP_LT) {
509 fp_sub(&t1, modulus, &t1);
510 }
511 /* T1 = T1 + T2 */
512 fp_add(&t1, &t2, &t1);
513 if (fp_cmp(&t1, modulus) != FP_LT) {
514 fp_sub(&t1, modulus, &t1);
515 }
516 }
517
518 /* Y = 2Y */
519 fp_add(R->y, R->y, R->y);
520 if (fp_cmp(R->y, modulus) != FP_LT) {
521 fp_sub(R->y, modulus, R->y);
522 }
523 /* Y = Y * Y */
524 fp_sqr(R->y, R->y);
525 fp_montgomery_reduce(R->y, modulus, mp);
526 /* T2 = Y * Y */
527 fp_sqr(R->y, &t2);
528 fp_montgomery_reduce(&t2, modulus, mp);
529 /* T2 = T2/2 */
530 if (fp_isodd(&t2)) {
531 fp_add(&t2, modulus, &t2);
532 }
533 fp_div_2(&t2, &t2);
534 /* Y = Y * X */
535 fp_mul(R->y, R->x, R->y);
536 fp_montgomery_reduce(R->y, modulus, mp);
537
538 /* X = T1 * T1 */
539 fp_sqr(&t1, R->x);
540 fp_montgomery_reduce(R->x, modulus, mp);
541 /* X = X - Y */
542 fp_sub(R->x, R->y, R->x);
543 if (fp_cmp_d(R->x, 0) == FP_LT) {
544 fp_add(R->x, modulus, R->x);
545 }
546 /* X = X - Y */
547 fp_sub(R->x, R->y, R->x);
548 if (fp_cmp_d(R->x, 0) == FP_LT) {
549 fp_add(R->x, modulus, R->x);
550 }
551
552 /* Y = Y - X */
553 fp_sub(R->y, R->x, R->y);
554 if (fp_cmp_d(R->y, 0) == FP_LT) {
555 fp_add(R->y, modulus, R->y);
556 }
557 /* Y = Y * T1 */
558 fp_mul(R->y, &t1, R->y);
559 fp_montgomery_reduce(R->y, modulus, mp);
560 /* Y = Y - T2 */
561 fp_sub(R->y, &t2, R->y);
562 if (fp_cmp_d(R->y, 0) == FP_LT) {
563 fp_add(R->y, modulus, R->y);
564 }
565
566 return CRYPT_OK;
567 }
568
569 /**
570 Add two ECC points
571 @param P The point to add
572 @param Q The point to add
573 @param R [out] The destination of the double
574 @param modulus The modulus of the field the ECC curve is in
575 @param Mp The "b" value from montgomery_setup()
576 @return CRYPT_OK on success
577 */
tfm_ecc_projective_add_point(const ecc_point * P,const ecc_point * Q,ecc_point * R,void * ma,void * modulus,void * Mp)578 static int tfm_ecc_projective_add_point(const ecc_point *P, const ecc_point *Q, ecc_point *R, void *ma, void *modulus, void *Mp)
579 {
580 fp_int t1, t2, x, y, z;
581 fp_digit mp;
582 int err, inf;
583
584 LTC_ARGCHK(P != NULL);
585 LTC_ARGCHK(Q != NULL);
586 LTC_ARGCHK(R != NULL);
587 LTC_ARGCHK(modulus != NULL);
588 LTC_ARGCHK(Mp != NULL);
589
590 mp = *((fp_digit*)Mp);
591
592 fp_init(&t1);
593 fp_init(&t2);
594 fp_init(&x);
595 fp_init(&y);
596 fp_init(&z);
597
598 if ((err = ltc_ecc_is_point_at_infinity(P, modulus, &inf)) != CRYPT_OK) return err;
599 if (inf) {
600 /* P is point at infinity >> Result = Q */
601 ltc_mp.copy(Q->x, R->x);
602 ltc_mp.copy(Q->y, R->y);
603 ltc_mp.copy(Q->z, R->z);
604 return CRYPT_OK;
605 }
606
607 if ((err = ltc_ecc_is_point_at_infinity(Q, modulus, &inf)) != CRYPT_OK) return err;
608 if (inf) {
609 /* Q is point at infinity >> Result = P */
610 ltc_mp.copy(P->x, R->x);
611 ltc_mp.copy(P->y, R->y);
612 ltc_mp.copy(P->z, R->z);
613 return CRYPT_OK;
614 }
615
616 /* should we dbl instead? */
617 fp_sub(modulus, Q->y, &t1);
618 if ( (fp_cmp(P->x, Q->x) == FP_EQ) &&
619 (Q->z != NULL && fp_cmp(P->z, Q->z) == FP_EQ) &&
620 (fp_cmp(P->y, Q->y) == FP_EQ || fp_cmp(P->y, &t1) == FP_EQ)) {
621 return tfm_ecc_projective_dbl_point(P, R, ma, modulus, Mp);
622 }
623
624 fp_copy(P->x, &x);
625 fp_copy(P->y, &y);
626 fp_copy(P->z, &z);
627
628 /* if Z is one then these are no-operations */
629 if (Q->z != NULL) {
630 /* T1 = Z' * Z' */
631 fp_sqr(Q->z, &t1);
632 fp_montgomery_reduce(&t1, modulus, mp);
633 /* X = X * T1 */
634 fp_mul(&t1, &x, &x);
635 fp_montgomery_reduce(&x, modulus, mp);
636 /* T1 = Z' * T1 */
637 fp_mul(Q->z, &t1, &t1);
638 fp_montgomery_reduce(&t1, modulus, mp);
639 /* Y = Y * T1 */
640 fp_mul(&t1, &y, &y);
641 fp_montgomery_reduce(&y, modulus, mp);
642 }
643
644 /* T1 = Z*Z */
645 fp_sqr(&z, &t1);
646 fp_montgomery_reduce(&t1, modulus, mp);
647 /* T2 = X' * T1 */
648 fp_mul(Q->x, &t1, &t2);
649 fp_montgomery_reduce(&t2, modulus, mp);
650 /* T1 = Z * T1 */
651 fp_mul(&z, &t1, &t1);
652 fp_montgomery_reduce(&t1, modulus, mp);
653 /* T1 = Y' * T1 */
654 fp_mul(Q->y, &t1, &t1);
655 fp_montgomery_reduce(&t1, modulus, mp);
656
657 /* Y = Y - T1 */
658 fp_sub(&y, &t1, &y);
659 if (fp_cmp_d(&y, 0) == FP_LT) {
660 fp_add(&y, modulus, &y);
661 }
662 /* T1 = 2T1 */
663 fp_add(&t1, &t1, &t1);
664 if (fp_cmp(&t1, modulus) != FP_LT) {
665 fp_sub(&t1, modulus, &t1);
666 }
667 /* T1 = Y + T1 */
668 fp_add(&t1, &y, &t1);
669 if (fp_cmp(&t1, modulus) != FP_LT) {
670 fp_sub(&t1, modulus, &t1);
671 }
672 /* X = X - T2 */
673 fp_sub(&x, &t2, &x);
674 if (fp_cmp_d(&x, 0) == FP_LT) {
675 fp_add(&x, modulus, &x);
676 }
677 /* T2 = 2T2 */
678 fp_add(&t2, &t2, &t2);
679 if (fp_cmp(&t2, modulus) != FP_LT) {
680 fp_sub(&t2, modulus, &t2);
681 }
682 /* T2 = X + T2 */
683 fp_add(&t2, &x, &t2);
684 if (fp_cmp(&t2, modulus) != FP_LT) {
685 fp_sub(&t2, modulus, &t2);
686 }
687
688 /* if Z' != 1 */
689 if (Q->z != NULL) {
690 /* Z = Z * Z' */
691 fp_mul(&z, Q->z, &z);
692 fp_montgomery_reduce(&z, modulus, mp);
693 }
694
695 /* Z = Z * X */
696 fp_mul(&z, &x, &z);
697 fp_montgomery_reduce(&z, modulus, mp);
698
699 /* T1 = T1 * X */
700 fp_mul(&t1, &x, &t1);
701 fp_montgomery_reduce(&t1, modulus, mp);
702 /* X = X * X */
703 fp_sqr(&x, &x);
704 fp_montgomery_reduce(&x, modulus, mp);
705 /* T2 = T2 * x */
706 fp_mul(&t2, &x, &t2);
707 fp_montgomery_reduce(&t2, modulus, mp);
708 /* T1 = T1 * X */
709 fp_mul(&t1, &x, &t1);
710 fp_montgomery_reduce(&t1, modulus, mp);
711
712 /* X = Y*Y */
713 fp_sqr(&y, &x);
714 fp_montgomery_reduce(&x, modulus, mp);
715 /* X = X - T2 */
716 fp_sub(&x, &t2, &x);
717 if (fp_cmp_d(&x, 0) == FP_LT) {
718 fp_add(&x, modulus, &x);
719 }
720
721 /* T2 = T2 - X */
722 fp_sub(&t2, &x, &t2);
723 if (fp_cmp_d(&t2, 0) == FP_LT) {
724 fp_add(&t2, modulus, &t2);
725 }
726 /* T2 = T2 - X */
727 fp_sub(&t2, &x, &t2);
728 if (fp_cmp_d(&t2, 0) == FP_LT) {
729 fp_add(&t2, modulus, &t2);
730 }
731 /* T2 = T2 * Y */
732 fp_mul(&t2, &y, &t2);
733 fp_montgomery_reduce(&t2, modulus, mp);
734 /* Y = T2 - T1 */
735 fp_sub(&t2, &t1, &y);
736 if (fp_cmp_d(&y, 0) == FP_LT) {
737 fp_add(&y, modulus, &y);
738 }
739 /* Y = Y/2 */
740 if (fp_isodd(&y)) {
741 fp_add(&y, modulus, &y);
742 }
743 fp_div_2(&y, &y);
744
745 fp_copy(&x, R->x);
746 fp_copy(&y, R->y);
747 fp_copy(&z, R->z);
748
749 return CRYPT_OK;
750 }
751
752
753 #endif
754
set_rand(void * a,int size)755 static int set_rand(void *a, int size)
756 {
757 LTC_ARGCHK(a != NULL);
758 fp_rand(a, size);
759 return CRYPT_OK;
760 }
761
762 const ltc_math_descriptor tfm_desc = {
763
764 "TomsFastMath",
765 (int)DIGIT_BIT,
766
767 &init,
768 &init_copy,
769 &deinit,
770
771 &neg,
772 ©,
773
774 &set_int,
775 &get_int,
776 &get_digit,
777 &get_digit_count,
778 &compare,
779 &compare_d,
780 &count_bits,
781 &count_lsb_bits,
782 &twoexpt,
783
784 &read_radix,
785 &write_radix,
786 &unsigned_size,
787 &unsigned_write,
788 &unsigned_read,
789
790 &add,
791 &addi,
792 &sub,
793 &subi,
794 &mul,
795 &muli,
796 &sqr,
797 NULL, /* TODO: &sqrtmod_prime */
798 ÷,
799 &div_2,
800 &modi,
801 &gcd,
802 &lcm,
803
804 &mulmod,
805 &sqrmod,
806 &invmod,
807
808 &montgomery_setup,
809 &montgomery_normalization,
810 &montgomery_reduce,
811 &montgomery_deinit,
812
813 &exptmod,
814 &isprime,
815
816 #ifdef LTC_MECC
817 #ifdef LTC_MECC_FP
818 <c_ecc_fp_mulmod,
819 #else
820 <c_ecc_mulmod,
821 #endif /* LTC_MECC_FP */
822 #ifdef LTC_MECC_ACCEL
823 &tfm_ecc_projective_add_point,
824 &tfm_ecc_projective_dbl_point,
825 #else
826 <c_ecc_projective_add_point,
827 <c_ecc_projective_dbl_point,
828 #endif /* LTC_MECC_ACCEL */
829 <c_ecc_map,
830 #ifdef LTC_ECC_SHAMIR
831 #ifdef LTC_MECC_FP
832 <c_ecc_fp_mul2add,
833 #else
834 <c_ecc_mul2add,
835 #endif /* LTC_MECC_FP */
836 #else
837 NULL,
838 #endif /* LTC_ECC_SHAMIR */
839 #else
840 NULL, NULL, NULL, NULL, NULL,
841 #endif /* LTC_MECC */
842
843 #ifdef LTC_MRSA
844 &rsa_make_key,
845 &rsa_exptmod,
846 #else
847 NULL, NULL,
848 #endif
849 &addmod,
850 &submod,
851
852 set_rand,
853
854 };
855
856
857 #endif
858