1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis */
2 /* SPDX-License-Identifier: Unlicense */
3
4 #include "tomcrypt_private.h"
5
6 /**
7 @file ltc_ecc_mulmod_timing.c
8 ECC Crypto, Tom St Denis
9 */
10
11 #ifdef LTC_MECC
12
13 #ifdef LTC_ECC_TIMING_RESISTANT
14
15 /**
16 Perform a point multiplication (timing resistant)
17 @param k The scalar to multiply by
18 @param G The base point
19 @param R [out] Destination for kG
20 @param a ECC curve parameter a
21 @param modulus The modulus of the field the ECC curve is in
22 @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
23 @return CRYPT_OK on success
24 */
ltc_ecc_mulmod(void * k,const ecc_point * G,ecc_point * R,void * a,void * modulus,int map)25 int ltc_ecc_mulmod(void *k, const ecc_point *G, ecc_point *R, void *a, void *modulus, int map)
26 {
27 ecc_point *tG, *M[3];
28 int i, j, err, inf;
29 void *mp = NULL, *mu = NULL, *ma = NULL, *a_plus3 = NULL;
30 ltc_mp_digit buf;
31 int bitcnt, mode, digidx;
32
33 LTC_ARGCHK(k != NULL);
34 LTC_ARGCHK(G != NULL);
35 LTC_ARGCHK(R != NULL);
36 LTC_ARGCHK(modulus != NULL);
37
38 if ((err = ltc_ecc_is_point_at_infinity(G, modulus, &inf)) != CRYPT_OK) return err;
39 if (inf) {
40 /* return the point at infinity */
41 return ltc_ecc_set_point_xyz(1, 1, 0, R);
42 }
43
44 /* init montgomery reduction */
45 if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { goto error; }
46 if ((err = mp_init(&mu)) != CRYPT_OK) { goto error; }
47 if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { goto error; }
48
49 /* for curves with a == -3 keep ma == NULL */
50 if ((err = mp_init(&a_plus3)) != CRYPT_OK) { goto error; }
51 if ((err = mp_add_d(a, 3, a_plus3)) != CRYPT_OK) { goto error; }
52 if (mp_cmp(a_plus3, modulus) != LTC_MP_EQ) {
53 if ((err = mp_init(&ma)) != CRYPT_OK) { goto error; }
54 if ((err = mp_mulmod(a, mu, modulus, ma)) != CRYPT_OK) { goto error; }
55 }
56
57 /* alloc ram for window temps */
58 for (i = 0; i < 3; i++) {
59 M[i] = ltc_ecc_new_point();
60 if (M[i] == NULL) {
61 for (j = 0; j < i; j++) {
62 ltc_ecc_del_point(M[j]);
63 }
64 mp_clear(mu);
65 mp_montgomery_free(mp);
66 return CRYPT_MEM;
67 }
68 }
69
70 /* make a copy of G incase R==G */
71 tG = ltc_ecc_new_point();
72 if (tG == NULL) { err = CRYPT_MEM; goto done; }
73
74 /* tG = G and convert to montgomery */
75 if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; }
76 if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; }
77 if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; }
78 mp_clear(mu);
79 mu = NULL;
80
81 /* calc the M tab */
82 /* M[0] == G */
83 if ((err = ltc_ecc_copy_point(tG, M[0])) != CRYPT_OK) { goto done; }
84 /* M[1] == 2G */
85 if ((err = ltc_mp.ecc_ptdbl(tG, M[1], ma, modulus, mp)) != CRYPT_OK) { goto done; }
86
87 /* setup sliding window */
88 mode = 0;
89 bitcnt = 1;
90 buf = 0;
91 digidx = mp_get_digit_count(k) - 1;
92
93 /* perform ops */
94 for (;;) {
95 /* grab next digit as required */
96 if (--bitcnt == 0) {
97 if (digidx == -1) {
98 break;
99 }
100 buf = mp_get_digit(k, digidx);
101 bitcnt = (int) MP_DIGIT_BIT;
102 --digidx;
103 }
104
105 /* grab the next msb from the ltiplicand */
106 i = (int)((buf >> (MP_DIGIT_BIT - 1)) & 1);
107 buf <<= 1;
108
109 if (mode == 0 && i == 0) {
110 /* dummy operations */
111 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; }
112 if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; }
113 continue;
114 }
115
116 if (mode == 0 && i == 1) {
117 mode = 1;
118 /* dummy operations */
119 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; }
120 if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; }
121 continue;
122 }
123
124 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[i^1], ma, modulus, mp)) != CRYPT_OK) { goto done; }
125 if ((err = ltc_mp.ecc_ptdbl(M[i], M[i], ma, modulus, mp)) != CRYPT_OK) { goto done; }
126 }
127
128 /* copy result out */
129 if ((err = ltc_ecc_copy_point(M[0], R)) != CRYPT_OK) { goto done; }
130
131 /* map R back from projective space */
132 if (map) {
133 err = ltc_ecc_map(R, modulus, mp);
134 } else {
135 err = CRYPT_OK;
136 }
137 done:
138 ltc_ecc_del_point(tG);
139 for (i = 0; i < 3; i++) {
140 ltc_ecc_del_point(M[i]);
141 }
142 error:
143 if (ma != NULL) mp_clear(ma);
144 if (a_plus3 != NULL) mp_clear(a_plus3);
145 if (mu != NULL) mp_clear(mu);
146 if (mp != NULL) mp_montgomery_free(mp);
147 return err;
148 }
149
150 #endif
151 #endif
152