1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
2 *
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
5 *
6 * The library is free for all purposes without any express
7 * guarantee it works.
8 *
9 * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com
10 */
11
12 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
13 *
14 * All curves taken from NIST recommendation paper of July 1999
15 * Available at http://csrc.nist.gov/cryptval/dss.htm
16 */
17 #include "tomcrypt.h"
18
19 /**
20 @file ltc_ecc_mulmod_timing.c
21 ECC Crypto, Tom St Denis
22 */
23
24 #ifdef MECC
25
26 #ifdef LTC_ECC_TIMING_RESISTANT
27
28 /**
29 Perform a point multiplication (timing resistant)
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
36 */
ltc_ecc_mulmod(void * k,ecc_point * G,ecc_point * R,void * modulus,int map)37 int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map)
38 {
39 ecc_point *tG, *M[3];
40 int i, j, err;
41 void *mu, *mp;
42 unsigned long buf;
43 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
44
45 LTC_ARGCHK(k != NULL);
46 LTC_ARGCHK(G != NULL);
47 LTC_ARGCHK(R != NULL);
48 LTC_ARGCHK(modulus != NULL);
49
50 /* init montgomery reduction */
51 if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
52 return err;
53 }
54 if ((err = mp_init(&mu)) != CRYPT_OK) {
55 mp_montgomery_free(mp);
56 return err;
57 }
58 if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
59 mp_clear(mu);
60 mp_montgomery_free(mp);
61 return err;
62 }
63
64 /* alloc ram for window temps */
65 for (i = 0; i < 3; i++) {
66 M[i] = ltc_ecc_new_point();
67 if (M[i] == NULL) {
68 for (j = 0; j < i; j++) {
69 ltc_ecc_del_point(M[j]);
70 }
71 mp_clear(mu);
72 mp_montgomery_free(mp);
73 return CRYPT_MEM;
74 }
75 }
76
77 /* make a copy of G incase R==G */
78 tG = ltc_ecc_new_point();
79 if (tG == NULL) { err = CRYPT_MEM; goto done; }
80
81 /* tG = G and convert to montgomery */
82 if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; }
83 if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; }
84 if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; }
85 mp_clear(mu);
86 mu = NULL;
87
88 /* calc the M tab */
89 /* M[0] == G */
90 if ((err = mp_copy(tG->x, M[0]->x)) != CRYPT_OK) { goto done; }
91 if ((err = mp_copy(tG->y, M[0]->y)) != CRYPT_OK) { goto done; }
92 if ((err = mp_copy(tG->z, M[0]->z)) != CRYPT_OK) { goto done; }
93 /* M[1] == 2G */
94 if ((err = ltc_mp.ecc_ptdbl(tG, M[1], modulus, mp)) != CRYPT_OK) { goto done; }
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) MP_DIGIT_BIT;
113 --digidx;
114 }
115
116 /* grab the next msb from the ltiplicand */
117 i = (buf >> (MP_DIGIT_BIT - 1)) & 1;
118 buf <<= 1;
119
120 if (mode == 0 && i == 0) {
121 /* dummy operations */
122 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; }
123 if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; }
124 continue;
125 }
126
127 if (mode == 0 && i == 1) {
128 mode = 1;
129 /* dummy operations */
130 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; }
131 if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; }
132 continue;
133 }
134
135 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[i^1], modulus, mp)) != CRYPT_OK) { goto done; }
136 if ((err = ltc_mp.ecc_ptdbl(M[i], M[i], modulus, mp)) != CRYPT_OK) { goto done; }
137 }
138
139 /* copy result out */
140 if ((err = mp_copy(M[0]->x, R->x)) != CRYPT_OK) { goto done; }
141 if ((err = mp_copy(M[0]->y, R->y)) != CRYPT_OK) { goto done; }
142 if ((err = mp_copy(M[0]->z, R->z)) != CRYPT_OK) { goto done; }
143
144 /* map R back from projective space */
145 if (map) {
146 err = ltc_ecc_map(R, modulus, mp);
147 } else {
148 err = CRYPT_OK;
149 }
150 done:
151 if (mu != NULL) {
152 mp_clear(mu);
153 }
154 mp_montgomery_free(mp);
155 ltc_ecc_del_point(tG);
156 for (i = 0; i < 3; i++) {
157 ltc_ecc_del_point(M[i]);
158 }
159 return err;
160 }
161
162 #endif
163 #endif
164 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c,v $ */
165 /* $Revision: 1.11 $ */
166 /* $Date: 2006/12/04 22:17:46 $ */
167
168