Branch data Line data Source code
1 : : /* ec_dsa.c - TinyCrypt implementation of EC-DSA */
2 : :
3 : : /* Copyright (c) 2014, Kenneth MacKay
4 : : * All rights reserved.
5 : : *
6 : : * Redistribution and use in source and binary forms, with or without
7 : : * modification, are permitted provided that the following conditions are met:
8 : : * * Redistributions of source code must retain the above copyright notice,
9 : : * this list of conditions and the following disclaimer.
10 : : * * Redistributions in binary form must reproduce the above copyright notice,
11 : : * this list of conditions and the following disclaimer in the documentation
12 : : * and/or other materials provided with the distribution.
13 : : *
14 : : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15 : : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 : : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
18 : : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 : : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 : : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 : : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 : : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 : : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 : : * POSSIBILITY OF SUCH DAMAGE.*/
25 : :
26 : : /*
27 : : * Copyright (C) 2017 by Intel Corporation, All Rights Reserved.
28 : : *
29 : : * Redistribution and use in source and binary forms, with or without
30 : : * modification, are permitted provided that the following conditions are met:
31 : : *
32 : : * - Redistributions of source code must retain the above copyright notice,
33 : : * this list of conditions and the following disclaimer.
34 : : *
35 : : * - Redistributions in binary form must reproduce the above copyright
36 : : * notice, this list of conditions and the following disclaimer in the
37 : : * documentation and/or other materials provided with the distribution.
38 : : *
39 : : * - Neither the name of Intel Corporation nor the names of its contributors
40 : : * may be used to endorse or promote products derived from this software
41 : : * without specific prior written permission.
42 : : *
43 : : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
44 : : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
45 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
46 : : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
47 : : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
48 : : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
49 : : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
50 : : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
51 : : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
52 : : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
53 : : * POSSIBILITY OF SUCH DAMAGE.
54 : : */
55 : :
56 : : #include <tinycrypt/constants.h>
57 : : #include <tinycrypt/ecc.h>
58 : : #include <tinycrypt/ecc_dsa.h>
59 : :
60 : :
61 : 0 : static void bits2int(uECC_word_t *native, const uint8_t *bits,
62 : : unsigned bits_size, uECC_Curve curve)
63 : : {
64 : 0 : unsigned num_n_bytes = BITS_TO_BYTES(curve->num_n_bits);
65 : 0 : unsigned num_n_words = BITS_TO_WORDS(curve->num_n_bits);
66 : 0 : int shift;
67 : 0 : uECC_word_t carry;
68 : 0 : uECC_word_t *ptr;
69 : :
70 : 0 : if (bits_size > num_n_bytes) {
71 : : bits_size = num_n_bytes;
72 : : }
73 : :
74 : 0 : uECC_vli_clear(native, num_n_words);
75 : 0 : uECC_vli_bytesToNative(native, bits, bits_size);
76 [ # # ]: 0 : if (bits_size * 8 <= (unsigned)curve->num_n_bits) {
77 : : return;
78 : : }
79 : 0 : shift = bits_size * 8 - curve->num_n_bits;
80 : 0 : carry = 0;
81 : 0 : ptr = native + num_n_words;
82 [ # # ]: 0 : while (ptr-- > native) {
83 : 0 : uECC_word_t temp = *ptr;
84 : 0 : *ptr = (temp >> shift) | carry;
85 : 0 : carry = temp << (uECC_WORD_BITS - shift);
86 : : }
87 : :
88 : : /* Reduce mod curve_n */
89 [ # # ]: 0 : if (uECC_vli_cmp_unsafe(curve->n, native, num_n_words) != 1) {
90 : 0 : uECC_vli_sub(native, native, curve->n, num_n_words);
91 : : }
92 : : }
93 : :
94 : 0 : int uECC_sign_with_k(const uint8_t *private_key, const uint8_t *message_hash,
95 : : unsigned hash_size, uECC_word_t *k, uint8_t *signature,
96 : : uECC_Curve curve)
97 : : {
98 : :
99 : 0 : uECC_word_t tmp[NUM_ECC_WORDS];
100 : 0 : uECC_word_t s[NUM_ECC_WORDS];
101 : 0 : uECC_word_t *k2[2] = {tmp, s};
102 : 0 : uECC_word_t p[NUM_ECC_WORDS * 2];
103 : 0 : uECC_word_t carry;
104 : 0 : wordcount_t num_words = curve->num_words;
105 : 0 : wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits);
106 : 0 : bitcount_t num_n_bits = curve->num_n_bits;
107 : :
108 : : /* Make sure 0 < k < curve_n */
109 [ # # # # ]: 0 : if (uECC_vli_isZero(k, num_words) ||
110 : 0 : uECC_vli_cmp(curve->n, k, num_n_words) != 1) {
111 : 0 : return 0;
112 : : }
113 : :
114 : 0 : carry = regularize_k(k, tmp, s, curve);
115 : 0 : EccPoint_mult(p, curve->G, k2[!carry], 0, num_n_bits + 1, curve);
116 [ # # ]: 0 : if (uECC_vli_isZero(p, num_words)) {
117 : : return 0;
118 : : }
119 : :
120 : : /* If an RNG function was specified, get a random number
121 : : to prevent side channel analysis of k. */
122 [ # # ]: 0 : if (!uECC_get_rng()) {
123 : 0 : uECC_vli_clear(tmp, num_n_words);
124 : 0 : tmp[0] = 1;
125 : : }
126 [ # # ]: 0 : else if (!uECC_generate_random_int(tmp, curve->n, num_n_words)) {
127 : : return 0;
128 : : }
129 : :
130 : : /* Prevent side channel analysis of uECC_vli_modInv() to determine
131 : : bits of k / the private key by premultiplying by a random number */
132 : 0 : uECC_vli_modMult(k, k, tmp, curve->n, num_n_words); /* k' = rand * k */
133 : 0 : uECC_vli_modInv(k, k, curve->n, num_n_words); /* k = 1 / k' */
134 : 0 : uECC_vli_modMult(k, k, tmp, curve->n, num_n_words); /* k = 1 / k */
135 : :
136 : 0 : uECC_vli_nativeToBytes(signature, curve->num_bytes, p); /* store r */
137 : :
138 : : /* tmp = d: */
139 : 0 : uECC_vli_bytesToNative(tmp, private_key, BITS_TO_BYTES(curve->num_n_bits));
140 : :
141 : 0 : s[num_n_words - 1] = 0;
142 : 0 : uECC_vli_set(s, p, num_words);
143 : 0 : uECC_vli_modMult(s, tmp, s, curve->n, num_n_words); /* s = r*d */
144 : :
145 : 0 : bits2int(tmp, message_hash, hash_size, curve);
146 : 0 : uECC_vli_modAdd(s, tmp, s, curve->n, num_n_words); /* s = e + r*d */
147 : 0 : uECC_vli_modMult(s, s, k, curve->n, num_n_words); /* s = (e + r*d) / k */
148 [ # # ]: 0 : if (uECC_vli_numBits(s, num_n_words) > (bitcount_t)curve->num_bytes * 8) {
149 : : return 0;
150 : : }
151 : :
152 : 0 : uECC_vli_nativeToBytes(signature + curve->num_bytes, curve->num_bytes, s);
153 : 0 : return 1;
154 : : }
155 : :
156 : 0 : int uECC_sign(const uint8_t *private_key, const uint8_t *message_hash,
157 : : unsigned hash_size, uint8_t *signature, uECC_Curve curve)
158 : : {
159 : 0 : uECC_word_t _random[2*NUM_ECC_WORDS];
160 : 0 : uECC_word_t k[NUM_ECC_WORDS];
161 : 0 : uECC_word_t tries;
162 : :
163 [ # # ]: 0 : for (tries = 0; tries < uECC_RNG_MAX_TRIES; ++tries) {
164 : : /* Generating _random uniformly at random: */
165 : 0 : uECC_RNG_Function rng_function = uECC_get_rng();
166 [ # # # # ]: 0 : if (!rng_function ||
167 : 0 : !rng_function((uint8_t *)_random, 2*NUM_ECC_WORDS*uECC_WORD_SIZE)) {
168 : 0 : return 0;
169 : : }
170 : :
171 : : // computing k as modular reduction of _random (see FIPS 186.4 B.5.1):
172 : 0 : uECC_vli_mmod(k, _random, curve->n, BITS_TO_WORDS(curve->num_n_bits));
173 : :
174 [ # # ]: 0 : if (uECC_sign_with_k(private_key, message_hash, hash_size, k, signature,
175 : : curve)) {
176 : : return 1;
177 : : }
178 : : }
179 : : return 0;
180 : : }
181 : :
182 : 0 : static bitcount_t smax(bitcount_t a, bitcount_t b)
183 : : {
184 : 0 : return (a > b ? a : b);
185 : : }
186 : :
187 : 0 : int uECC_verify(const uint8_t *public_key, const uint8_t *message_hash,
188 : : unsigned hash_size, const uint8_t *signature,
189 : : uECC_Curve curve)
190 : : {
191 : :
192 : 0 : uECC_word_t u1[NUM_ECC_WORDS], u2[NUM_ECC_WORDS];
193 : 0 : uECC_word_t z[NUM_ECC_WORDS];
194 : 0 : uECC_word_t sum[NUM_ECC_WORDS * 2];
195 : 0 : uECC_word_t rx[NUM_ECC_WORDS];
196 : 0 : uECC_word_t ry[NUM_ECC_WORDS];
197 : 0 : uECC_word_t tx[NUM_ECC_WORDS];
198 : 0 : uECC_word_t ty[NUM_ECC_WORDS];
199 : 0 : uECC_word_t tz[NUM_ECC_WORDS];
200 : 0 : const uECC_word_t *points[4];
201 : 0 : const uECC_word_t *point;
202 : 0 : bitcount_t num_bits;
203 : 0 : bitcount_t i;
204 : :
205 : 0 : uECC_word_t _public[NUM_ECC_WORDS * 2];
206 : 0 : uECC_word_t r[NUM_ECC_WORDS], s[NUM_ECC_WORDS];
207 : 0 : wordcount_t num_words = curve->num_words;
208 : 0 : wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits);
209 : :
210 : 0 : rx[num_n_words - 1] = 0;
211 : 0 : r[num_n_words - 1] = 0;
212 : 0 : s[num_n_words - 1] = 0;
213 : :
214 : 0 : uECC_vli_bytesToNative(_public, public_key, curve->num_bytes);
215 : 0 : uECC_vli_bytesToNative(_public + num_words, public_key + curve->num_bytes,
216 : 0 : curve->num_bytes);
217 : 0 : uECC_vli_bytesToNative(r, signature, curve->num_bytes);
218 : 0 : uECC_vli_bytesToNative(s, signature + curve->num_bytes, curve->num_bytes);
219 : :
220 : : /* r, s must not be 0. */
221 [ # # # # ]: 0 : if (uECC_vli_isZero(r, num_words) || uECC_vli_isZero(s, num_words)) {
222 : 0 : return 0;
223 : : }
224 : :
225 : : /* r, s must be < n. */
226 [ # # # # ]: 0 : if (uECC_vli_cmp_unsafe(curve->n, r, num_n_words) != 1 ||
227 : 0 : uECC_vli_cmp_unsafe(curve->n, s, num_n_words) != 1) {
228 : 0 : return 0;
229 : : }
230 : :
231 : : /* Calculate u1 and u2. */
232 : 0 : uECC_vli_modInv(z, s, curve->n, num_n_words); /* z = 1/s */
233 : 0 : u1[num_n_words - 1] = 0;
234 : 0 : bits2int(u1, message_hash, hash_size, curve);
235 : 0 : uECC_vli_modMult(u1, u1, z, curve->n, num_n_words); /* u1 = e/s */
236 : 0 : uECC_vli_modMult(u2, r, z, curve->n, num_n_words); /* u2 = r/s */
237 : :
238 : : /* Calculate sum = G + Q. */
239 : 0 : uECC_vli_set(sum, _public, num_words);
240 : 0 : uECC_vli_set(sum + num_words, _public + num_words, num_words);
241 : 0 : uECC_vli_set(tx, curve->G, num_words);
242 : 0 : uECC_vli_set(ty, curve->G + num_words, num_words);
243 : 0 : uECC_vli_modSub(z, sum, tx, curve->p, num_words); /* z = x2 - x1 */
244 : 0 : XYcZ_add(tx, ty, sum, sum + num_words, curve);
245 : 0 : uECC_vli_modInv(z, z, curve->p, num_words); /* z = 1/z */
246 : 0 : apply_z(sum, sum + num_words, z, curve);
247 : :
248 : : /* Use Shamir's trick to calculate u1*G + u2*Q */
249 : 0 : points[0] = 0;
250 : 0 : points[1] = curve->G;
251 : 0 : points[2] = _public;
252 : 0 : points[3] = sum;
253 : 0 : num_bits = smax(uECC_vli_numBits(u1, num_n_words),
254 : 0 : uECC_vli_numBits(u2, num_n_words));
255 : :
256 : 0 : point = points[(!!uECC_vli_testBit(u1, num_bits - 1)) |
257 [ # # ]: 0 : ((!!uECC_vli_testBit(u2, num_bits - 1)) << 1)];
258 : 0 : uECC_vli_set(rx, point, num_words);
259 : 0 : uECC_vli_set(ry, point + num_words, num_words);
260 : 0 : uECC_vli_clear(z, num_words);
261 : 0 : z[0] = 1;
262 : :
263 [ # # ]: 0 : for (i = num_bits - 2; i >= 0; --i) {
264 : 0 : uECC_word_t index;
265 : 0 : curve->double_jacobian(rx, ry, z, curve);
266 : :
267 [ # # ]: 0 : index = (!!uECC_vli_testBit(u1, i)) | ((!!uECC_vli_testBit(u2, i)) << 1);
268 : 0 : point = points[index];
269 [ # # ]: 0 : if (point) {
270 : 0 : uECC_vli_set(tx, point, num_words);
271 : 0 : uECC_vli_set(ty, point + num_words, num_words);
272 : 0 : apply_z(tx, ty, z, curve);
273 : 0 : uECC_vli_modSub(tz, rx, tx, curve->p, num_words); /* Z = x2 - x1 */
274 : 0 : XYcZ_add(tx, ty, rx, ry, curve);
275 : 0 : uECC_vli_modMult_fast(z, z, tz, curve);
276 : : }
277 : : }
278 : :
279 : 0 : uECC_vli_modInv(z, z, curve->p, num_words); /* Z = 1/Z */
280 : 0 : apply_z(rx, ry, z, curve);
281 : :
282 : : /* v = x1 (mod n) */
283 [ # # ]: 0 : if (uECC_vli_cmp_unsafe(curve->n, rx, num_n_words) != 1) {
284 : 0 : uECC_vli_sub(rx, rx, curve->n, num_n_words);
285 : : }
286 : :
287 : : /* Accept only if v == r. */
288 : 0 : return (int)(uECC_vli_equal(rx, r, num_words) == 0);
289 : : }
290 : :
|
