Mercurial > dropbear

comparison libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c @ 382:0cbe8f6dbf9e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 2af22fb4e878750b88f80f90d439b316d229796f) to branch 'au.asn.ucc.matt.dropbear' (head 02c413252c90e9de8e03d91e9939dde3029f5c0a)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 02:41:05 +0000
parents
children 0e1465709336
comparison
equal deleted inserted replaced
379:b66a00272a90 382:0cbe8f6dbf9e
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, [email protected], 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 */
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