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.c
8 ECC Crypto, Tom St Denis
9 */
10
11 #ifdef LTC_MECC
12 #ifndef LTC_ECC_TIMING_RESISTANT
13
14 /* size of sliding window, don't change this! */
15 #define WINSIZE 4
16
17 /**
18 Perform a point multiplication
19 @param k The scalar to multiply by
20 @param G The base point
21 @param R [out] Destination for kG
22 @param modulus The modulus of the field the ECC curve is in
23 @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
24 @return CRYPT_OK on success
25 */
ltc_ecc_mulmod(void * k,const ecc_point * G,ecc_point * R,void * a,void * modulus,int map)26 int ltc_ecc_mulmod(void *k, const ecc_point *G, ecc_point *R, void *a, void *modulus, int map)
27 {
28 ecc_point *tG, *M[8];
29 int i, j, err, inf;
30 void *mp = NULL, *mu = NULL, *ma = NULL, *a_plus3 = NULL;
31 ltc_mp_digit buf;
32 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
33
34 LTC_ARGCHK(k != NULL);
35 LTC_ARGCHK(G != NULL);
36 LTC_ARGCHK(R != NULL);
37 LTC_ARGCHK(modulus != NULL);
38
39 if ((err = ltc_ecc_is_point_at_infinity(G, modulus, &inf)) != CRYPT_OK) return err;
40 if (inf) {
41 /* return the point at infinity */
42 return ltc_ecc_set_point_xyz(1, 1, 0, R);
43 }
44
45 /* init montgomery reduction */
46 if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { goto error; }
47 if ((err = mp_init(&mu)) != CRYPT_OK) { goto error; }
48 if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { goto error; }
49
50 /* for curves with a == -3 keep ma == NULL */
51 if ((err = mp_init(&a_plus3)) != CRYPT_OK) { goto error; }
52 if ((err = mp_add_d(a, 3, a_plus3)) != CRYPT_OK) { goto error; }
53 if (mp_cmp(a_plus3, modulus) != LTC_MP_EQ) {
54 if ((err = mp_init(&ma)) != CRYPT_OK) { goto error; }
55 if ((err = mp_mulmod(a, mu, modulus, ma)) != CRYPT_OK) { goto error; }
56 }
57
58 /* alloc ram for window temps */
59 for (i = 0; i < 8; i++) {
60 M[i] = ltc_ecc_new_point();
61 if (M[i] == NULL) {
62 for (j = 0; j < i; j++) {
63 ltc_ecc_del_point(M[j]);
64 }
65 err = CRYPT_MEM;
66 goto error;
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 (mp_cmp_d(mu, 1) == LTC_MP_EQ) {
76 if ((err = ltc_ecc_copy_point(G, tG)) != CRYPT_OK) { goto done; }
77 } else {
78 if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; }
79 if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; }
80 if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; }
81 }
82 mp_clear(mu);
83 mu = NULL;
84
85 /* calc the M tab, which holds kG for k==8..15 */
86 /* M[0] == 8G */
87 if ((err = ltc_mp.ecc_ptdbl(tG, M[0], ma, modulus, mp)) != CRYPT_OK) { goto done; }
88 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], ma, modulus, mp)) != CRYPT_OK) { goto done; }
89 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], ma, modulus, mp)) != CRYPT_OK) { goto done; }
90
91 /* now find (8+k)G for k=1..7 */
92 for (j = 9; j < 16; j++) {
93 if ((err = ltc_mp.ecc_ptadd(M[j-9], tG, M[j-8], ma, modulus, mp)) != CRYPT_OK) { goto done; }
94 }
95
96 /* setup sliding window */
97 mode = 0;
98 bitcnt = 1;
99 buf = 0;
100 digidx = mp_get_digit_count(k) - 1;
101 bitcpy = bitbuf = 0;
102 first = 1;
103
104 /* perform ops */
105 for (;;) {
106 /* grab next digit as required */
107 if (--bitcnt == 0) {
108 if (digidx == -1) {
109 break;
110 }
111 buf = mp_get_digit(k, digidx);
112 bitcnt = (int) ltc_mp.bits_per_digit;
113 --digidx;
114 }
115
116 /* grab the next msb from the ltiplicand */
117 i = (buf >> (ltc_mp.bits_per_digit - 1)) & 1;
118 buf <<= 1;
119
120 /* skip leading zero bits */
121 if (mode == 0 && i == 0) {
122 continue;
123 }
124
125 /* if the bit is zero and mode == 1 then we double */
126 if (mode == 1 && i == 0) {
127 if ((err = ltc_mp.ecc_ptdbl(R, R, ma, modulus, mp)) != CRYPT_OK) { goto done; }
128 continue;
129 }
130
131 /* else we add it to the window */
132 bitbuf |= (i << (WINSIZE - ++bitcpy));
133 mode = 2;
134
135 if (bitcpy == WINSIZE) {
136 /* if this is the first window we do a simple copy */
137 if (first == 1) {
138 /* R = kG [k = first window] */
139 if ((err = ltc_ecc_copy_point(M[bitbuf-8], R)) != CRYPT_OK) { goto done; }
140 first = 0;
141 } else {
142 /* normal window */
143 /* ok window is filled so double as required and add */
144 /* double first */
145 for (j = 0; j < WINSIZE; j++) {
146 if ((err = ltc_mp.ecc_ptdbl(R, R, ma, modulus, mp)) != CRYPT_OK) { goto done; }
147 }
148
149 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
150 if ((err = ltc_mp.ecc_ptadd(R, M[bitbuf-8], R, ma, modulus, mp)) != CRYPT_OK) { goto done; }
151 }
152 /* empty window and reset */
153 bitcpy = bitbuf = 0;
154 mode = 1;
155 }
156 }
157
158 /* if bits remain then double/add */
159 if (mode == 2 && bitcpy > 0) {
160 /* double then add */
161 for (j = 0; j < bitcpy; j++) {
162 /* only double if we have had at least one add first */
163 if (first == 0) {
164 if ((err = ltc_mp.ecc_ptdbl(R, R, ma, modulus, mp)) != CRYPT_OK) { goto done; }
165 }
166
167 bitbuf <<= 1;
168 if ((bitbuf & (1 << WINSIZE)) != 0) {
169 if (first == 1){
170 /* first add, so copy */
171 if ((err = ltc_ecc_copy_point(tG, R)) != CRYPT_OK) { goto done; }
172 first = 0;
173 } else {
174 /* then add */
175 if ((err = ltc_mp.ecc_ptadd(R, tG, R, ma, modulus, mp)) != CRYPT_OK) { goto done; }
176 }
177 }
178 }
179 }
180
181 /* map R back from projective space */
182 if (map) {
183 err = ltc_ecc_map(R, modulus, mp);
184 } else {
185 err = CRYPT_OK;
186 }
187 done:
188 ltc_ecc_del_point(tG);
189 for (i = 0; i < 8; i++) {
190 ltc_ecc_del_point(M[i]);
191 }
192 error:
193 if (ma != NULL) mp_clear(ma);
194 if (a_plus3 != NULL) mp_clear(a_plus3);
195 if (mu != NULL) mp_clear(mu);
196 if (mp != NULL) mp_montgomery_free(mp);
197 return err;
198 }
199
200 #endif
201
202 #undef WINSIZE
203
204 #endif
205