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
10 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
12 * All curves taken from NIST recommendation paper of July 1999
13 * Available at http://csrc.nist.gov/cryptval/dss.htm
18 @file ltc_ecc_mulmod.c
19 ECC Crypto, Tom St Denis
23 #ifndef LTC_ECC_TIMING_RESISTANT
25 /* size of sliding window, don't change this! */
29 Perform a point multiplication
30 @param k The scalar to multiply by
31 @param G The base point
32 @param R [out] Destination for kG
33 @param modulus The modulus of the field the ECC curve is in
34 @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
35 @return CRYPT_OK on success
37 int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map)
43 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
45 LTC_ARGCHK(k != NULL);
46 LTC_ARGCHK(G != NULL);
47 LTC_ARGCHK(R != NULL);
48 LTC_ARGCHK(modulus != NULL);
50 /* init montgomery reduction */
51 if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
54 if ((err = mp_init(&mu)) != CRYPT_OK) {
55 mp_montgomery_free(mp);
58 if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
59 mp_montgomery_free(mp);
64 /* alloc ram for window temps */
65 for (i = 0; i < 8; i++) {
66 M[i] = ltc_ecc_new_point();
68 for (j = 0; j < i; j++) {
69 ltc_ecc_del_point(M[j]);
71 mp_montgomery_free(mp);
77 /* make a copy of G incase R==G */
78 tG = ltc_ecc_new_point();
79 if (tG == NULL) { err = CRYPT_MEM; goto done; }
81 /* tG = G and convert to montgomery */
82 if (mp_cmp_d(mu, 1) == LTC_MP_EQ) {
83 if ((err = mp_copy(G->x, tG->x)) != CRYPT_OK) { goto done; }
84 if ((err = mp_copy(G->y, tG->y)) != CRYPT_OK) { goto done; }
85 if ((err = mp_copy(G->z, tG->z)) != CRYPT_OK) { goto done; }
87 if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; }
88 if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; }
89 if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; }
94 /* calc the M tab, which holds kG for k==8..15 */
96 if ((err = ltc_mp.ecc_ptdbl(tG, M[0], modulus, mp)) != CRYPT_OK) { goto done; }
97 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
98 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
100 /* now find (8+k)G for k=1..7 */
101 for (j = 9; j < 16; j++) {
102 if ((err = ltc_mp.ecc_ptadd(M[j-9], tG, M[j-8], modulus, mp)) != CRYPT_OK) { goto done; }
105 /* setup sliding window */
109 digidx = mp_get_digit_count(k) - 1;
115 /* grab next digit as required */
120 buf = mp_get_digit(k, digidx);
121 bitcnt = (int) ltc_mp.bits_per_digit;
125 /* grab the next msb from the ltiplicand */
126 i = (buf >> (ltc_mp.bits_per_digit - 1)) & 1;
129 /* skip leading zero bits */
130 if (mode == 0 && i == 0) {
134 /* if the bit is zero and mode == 1 then we double */
135 if (mode == 1 && i == 0) {
136 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
140 /* else we add it to the window */
141 bitbuf |= (i << (WINSIZE - ++bitcpy));
144 if (bitcpy == WINSIZE) {
145 /* if this is the first window we do a simple copy */
147 /* R = kG [k = first window] */
148 if ((err = mp_copy(M[bitbuf-8]->x, R->x)) != CRYPT_OK) { goto done; }
149 if ((err = mp_copy(M[bitbuf-8]->y, R->y)) != CRYPT_OK) { goto done; }
150 if ((err = mp_copy(M[bitbuf-8]->z, R->z)) != CRYPT_OK) { goto done; }
154 /* ok window is filled so double as required and add */
156 for (j = 0; j < WINSIZE; j++) {
157 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
160 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
161 if ((err = ltc_mp.ecc_ptadd(R, M[bitbuf-8], R, modulus, mp)) != CRYPT_OK) { goto done; }
163 /* empty window and reset */
169 /* if bits remain then double/add */
170 if (mode == 2 && bitcpy > 0) {
171 /* double then add */
172 for (j = 0; j < bitcpy; j++) {
173 /* only double if we have had at least one add first */
175 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
179 if ((bitbuf & (1 << WINSIZE)) != 0) {
181 /* first add, so copy */
182 if ((err = mp_copy(tG->x, R->x)) != CRYPT_OK) { goto done; }
183 if ((err = mp_copy(tG->y, R->y)) != CRYPT_OK) { goto done; }
184 if ((err = mp_copy(tG->z, R->z)) != CRYPT_OK) { goto done; }
188 if ((err = ltc_mp.ecc_ptadd(R, tG, R, modulus, mp)) != CRYPT_OK) { goto done; }
194 /* map R back from projective space */
196 err = ltc_ecc_map(R, modulus, mp);
204 mp_montgomery_free(mp);
205 ltc_ecc_del_point(tG);
206 for (i = 0; i < 8; i++) {
207 ltc_ecc_del_point(M[i]);
218 /* ref: $Format:%D$ */
219 /* git commit: $Format:%H$ */
220 /* commit time: $Format:%ai$ */