source: UsbWattMeter/trunk/wolfssl-3.7.0/wolfcrypt/src/dsa.c@ 167

Last change on this file since 167 was 167, checked in by coas-nagasima, 8 years ago

MIMEにSJISを設定
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
  • Property svn:mime-type set to text/x-csrc; charset=SHIFT_JIS
File size: 12.0 KB
Line 
1/* dsa.c
2 *
3 * Copyright (C) 2006-2015 wolfSSL Inc.
4 *
5 * This file is part of wolfSSL. (formerly known as CyaSSL)
6 *
7 * wolfSSL is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * wolfSSL is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
20 */
21
22#ifdef HAVE_CONFIG_H
23 #include <config.h>
24#endif
25
26#include <wolfssl/wolfcrypt/settings.h>
27
28#ifndef NO_DSA
29
30#include <wolfssl/wolfcrypt/random.h>
31#include <wolfssl/wolfcrypt/integer.h>
32#include <wolfssl/wolfcrypt/error-crypt.h>
33#include <wolfssl/wolfcrypt/logging.h>
34#include <wolfssl/wolfcrypt/sha.h>
35#include <wolfssl/wolfcrypt/dsa.h>
36
37
38enum {
39 DSA_HALF_SIZE = 20, /* r and s size */
40 DSA_SIG_SIZE = 40 /* signature size */
41};
42
43
44#ifdef min
45#define WOLFSSL_HAVE_MIN
46#endif
47#ifndef WOLFSSL_HAVE_MIN
48#define WOLFSSL_HAVE_MIN
49
50 static INLINE word32 min(word32 a, word32 b)
51 {
52 return a > b ? b : a;
53 }
54
55#endif /* WOLFSSL_HAVE_MIN */
56
57
58void wc_InitDsaKey(DsaKey* key)
59{
60 key->type = -1; /* haven't decided yet */
61
62/* TomsFastMath doesn't use memory allocation */
63#ifndef USE_FAST_MATH
64 key->p.dp = 0; /* public alloc parts */
65 key->q.dp = 0;
66 key->g.dp = 0;
67 key->y.dp = 0;
68
69 key->x.dp = 0; /* private alloc parts */
70#endif
71}
72
73
74void wc_FreeDsaKey(DsaKey* key)
75{
76 (void)key;
77/* TomsFastMath doesn't use memory allocation */
78#ifndef USE_FAST_MATH
79 if (key->type == DSA_PRIVATE)
80 mp_clear(&key->x);
81 mp_clear(&key->y);
82 mp_clear(&key->g);
83 mp_clear(&key->q);
84 mp_clear(&key->p);
85#endif
86}
87
88#ifdef WOLFSSL_KEY_GEN
89
90int wc_MakeDsaKey(WC_RNG *rng, DsaKey *dsa)
91{
92 unsigned char *buf;
93 int qsize, err;
94
95 if (rng == NULL || dsa == NULL)
96 return BAD_FUNC_ARG;
97
98 qsize = mp_unsigned_bin_size(&dsa->q);
99 if (qsize == 0)
100 return BAD_FUNC_ARG;
101
102 /* allocate ram */
103 buf = (unsigned char *)XMALLOC(qsize, NULL,
104 DYNAMIC_TYPE_TMP_BUFFER);
105 if (buf == NULL)
106 return MEMORY_E;
107
108 if (mp_init(&dsa->x) != MP_OKAY) {
109 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
110 return MP_INIT_E;
111 }
112
113 do {
114 /* make a random exponent mod q */
115 err = wc_RNG_GenerateBlock(rng, buf, qsize);
116 if (err != MP_OKAY) {
117 mp_clear(&dsa->x);
118 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
119 return err;
120 }
121
122 err = mp_read_unsigned_bin(&dsa->x, buf, qsize);
123 if (err != MP_OKAY) {
124 mp_clear(&dsa->x);
125 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
126 return err;
127 }
128 } while (mp_cmp_d(&dsa->x, 1) != MP_GT);
129
130 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
131
132 if (mp_init(&dsa->y) != MP_OKAY) {
133 mp_clear(&dsa->x);
134 return MP_INIT_E;
135 }
136
137 /* public key : y = g^x mod p */
138 err = mp_exptmod(&dsa->g, &dsa->x, &dsa->p, &dsa->y);
139 if (err != MP_OKAY) {
140 mp_clear(&dsa->x);
141 mp_clear(&dsa->y);
142 return err;
143 }
144
145 dsa->type = DSA_PRIVATE;
146
147 return MP_OKAY;
148}
149
150/* modulus_size in bits */
151int wc_MakeDsaParameters(WC_RNG *rng, int modulus_size, DsaKey *dsa)
152{
153 mp_int tmp, tmp2;
154 int err, msize, qsize,
155 loop_check_prime = 0,
156 check_prime = MP_NO;
157 unsigned char *buf;
158
159 if (rng == NULL || dsa == NULL)
160 return BAD_FUNC_ARG;
161
162 /* set group size in bytes from modulus size
163 * FIPS 186-4 defines valid values (1024, 160) (2048, 256) (3072, 256)
164 */
165 switch (modulus_size) {
166 case 1024:
167 qsize = 20;
168 break;
169 case 2048:
170 case 3072:
171 qsize = 32;
172 break;
173 default:
174 return BAD_FUNC_ARG;
175 break;
176 }
177
178 /* modulus size in bytes */
179 msize = modulus_size / 8;
180
181 /* allocate ram */
182 buf = (unsigned char *)XMALLOC(msize - qsize,
183 NULL, DYNAMIC_TYPE_TMP_BUFFER);
184 if (buf == NULL) {
185 return MEMORY_E;
186 }
187
188 /* make a random string that will be multplied against q */
189 err = wc_RNG_GenerateBlock(rng, buf, msize - qsize);
190 if (err != MP_OKAY) {
191 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
192 return err;
193 }
194
195 /* force magnitude */
196 buf[0] |= 0xC0;
197
198 /* force even */
199 buf[msize - qsize - 1] &= ~1;
200
201 if (mp_init_multi(&tmp2, &dsa->p, &dsa->q, 0, 0, 0) != MP_OKAY) {
202 mp_clear(&dsa->q);
203 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
204 return MP_INIT_E;
205 }
206
207 err = mp_read_unsigned_bin(&tmp2, buf, msize - qsize);
208 if (err != MP_OKAY) {
209 mp_clear(&dsa->q);
210 mp_clear(&dsa->p);
211 mp_clear(&tmp2);
212 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
213 return err;
214 }
215 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
216
217 /* make our prime q */
218 err = mp_rand_prime(&dsa->q, qsize, rng, NULL);
219 if (err != MP_OKAY) {
220 mp_clear(&dsa->q);
221 mp_clear(&dsa->p);
222 mp_clear(&tmp2);
223 return err;
224 }
225
226 /* p = random * q */
227 err = mp_mul(&dsa->q, &tmp2, &dsa->p);
228 if (err != MP_OKAY) {
229 mp_clear(&dsa->q);
230 mp_clear(&dsa->p);
231 mp_clear(&tmp2);
232 return err;
233 }
234
235 /* p = random * q + 1, so q is a prime divisor of p-1 */
236 err = mp_add_d(&dsa->p, 1, &dsa->p);
237 if (err != MP_OKAY) {
238 mp_clear(&dsa->q);
239 mp_clear(&dsa->p);
240 mp_clear(&tmp2);
241 return err;
242 }
243
244 if (mp_init(&tmp) != MP_OKAY) {
245 mp_clear(&dsa->q);
246 mp_clear(&dsa->p);
247 mp_clear(&tmp2);
248 return MP_INIT_E;
249 }
250
251 /* tmp = 2q */
252 err = mp_add(&dsa->q, &dsa->q, &tmp);
253 if (err != MP_OKAY) {
254 mp_clear(&dsa->q);
255 mp_clear(&dsa->p);
256 mp_clear(&tmp);
257 mp_clear(&tmp2);
258 return err;
259 }
260
261 /* loop until p is prime */
262 while (check_prime == MP_NO) {
263 err = mp_prime_is_prime(&dsa->p, 8, &check_prime);
264 if (err != MP_OKAY) {
265 mp_clear(&dsa->q);
266 mp_clear(&dsa->p);
267 mp_clear(&tmp);
268 mp_clear(&tmp2);
269 return err;
270 }
271
272 if (check_prime != MP_YES) {
273 /* p += 2q */
274 err = mp_add(&tmp, &dsa->p, &dsa->p);
275 if (err != MP_OKAY) {
276 mp_clear(&dsa->q);
277 mp_clear(&dsa->p);
278 mp_clear(&tmp);
279 mp_clear(&tmp2);
280 return err;
281 }
282
283 loop_check_prime++;
284 }
285 }
286
287 /* tmp2 += (2*loop_check_prime)
288 * to have p = (q * tmp2) + 1 prime
289 */
290 if (loop_check_prime) {
291 err = mp_add_d(&tmp2, 2*loop_check_prime, &tmp2);
292 if (err != MP_OKAY) {
293 mp_clear(&dsa->q);
294 mp_clear(&dsa->p);
295 mp_clear(&tmp);
296 mp_clear(&tmp2);
297 return err;
298 }
299 }
300
301 if (mp_init(&dsa->g) != MP_OKAY) {
302 mp_clear(&dsa->q);
303 mp_clear(&dsa->p);
304 mp_clear(&tmp);
305 mp_clear(&tmp2);
306 return MP_INIT_E;
307 }
308
309 /* find a value g for which g^tmp2 != 1 */
310 mp_set(&dsa->g, 1);
311
312 do {
313 err = mp_add_d(&dsa->g, 1, &dsa->g);
314 if (err != MP_OKAY) {
315 mp_clear(&dsa->q);
316 mp_clear(&dsa->p);
317 mp_clear(&dsa->g);
318 mp_clear(&tmp);
319 mp_clear(&tmp2);
320 return err;
321 }
322
323 err = mp_exptmod(&dsa->g, &tmp2, &dsa->p, &tmp);
324 if (err != MP_OKAY) {
325 mp_clear(&dsa->q);
326 mp_clear(&dsa->p);
327 mp_clear(&dsa->g);
328 mp_clear(&tmp);
329 mp_clear(&tmp2);
330 return err;
331 }
332
333 } while (mp_cmp_d(&tmp, 1) == MP_EQ);
334
335 /* at this point tmp generates a group of order q mod p */
336 mp_exch(&tmp, &dsa->g);
337
338 mp_clear(&tmp);
339 mp_clear(&tmp2);
340
341 return MP_OKAY;
342}
343#endif /* WOLFSSL_KEY_GEN */
344
345
346int wc_DsaSign(const byte* digest, byte* out, DsaKey* key, WC_RNG* rng)
347{
348 mp_int k, kInv, r, s, H;
349 int ret, sz;
350 byte buffer[DSA_HALF_SIZE];
351
352 sz = min(sizeof(buffer), mp_unsigned_bin_size(&key->q));
353
354 /* generate k */
355 ret = wc_RNG_GenerateBlock(rng, buffer, sz);
356 if (ret != 0)
357 return ret;
358
359 buffer[0] |= 0x0C;
360
361 if (mp_init_multi(&k, &kInv, &r, &s, &H, 0) != MP_OKAY)
362 return MP_INIT_E;
363
364 if (mp_read_unsigned_bin(&k, buffer, sz) != MP_OKAY)
365 ret = MP_READ_E;
366
367 if (ret == 0 && mp_cmp_d(&k, 1) != MP_GT)
368 ret = MP_CMP_E;
369
370 /* inverse k mod q */
371 if (ret == 0 && mp_invmod(&k, &key->q, &kInv) != MP_OKAY)
372 ret = MP_INVMOD_E;
373
374 /* generate r, r = (g exp k mod p) mod q */
375 if (ret == 0 && mp_exptmod(&key->g, &k, &key->p, &r) != MP_OKAY)
376 ret = MP_EXPTMOD_E;
377
378 if (ret == 0 && mp_mod(&r, &key->q, &r) != MP_OKAY)
379 ret = MP_MOD_E;
380
381 /* generate H from sha digest */
382 if (ret == 0 && mp_read_unsigned_bin(&H, digest,SHA_DIGEST_SIZE) != MP_OKAY)
383 ret = MP_READ_E;
384
385 /* generate s, s = (kInv * (H + x*r)) % q */
386 if (ret == 0 && mp_mul(&key->x, &r, &s) != MP_OKAY)
387 ret = MP_MUL_E;
388
389 if (ret == 0 && mp_add(&s, &H, &s) != MP_OKAY)
390 ret = MP_ADD_E;
391
392 if (ret == 0 && mp_mulmod(&s, &kInv, &key->q, &s) != MP_OKAY)
393 ret = MP_MULMOD_E;
394
395 /* write out */
396 if (ret == 0) {
397 int rSz = mp_unsigned_bin_size(&r);
398 int sSz = mp_unsigned_bin_size(&s);
399
400 if (rSz == DSA_HALF_SIZE - 1) {
401 out[0] = 0;
402 out++;
403 }
404
405 if (mp_to_unsigned_bin(&r, out) != MP_OKAY)
406 ret = MP_TO_E;
407 else {
408 if (sSz == DSA_HALF_SIZE - 1) {
409 out[rSz] = 0;
410 out++;
411 }
412 ret = mp_to_unsigned_bin(&s, out + rSz);
413 }
414 }
415
416 mp_clear(&H);
417 mp_clear(&s);
418 mp_clear(&r);
419 mp_clear(&kInv);
420 mp_clear(&k);
421
422 return ret;
423}
424
425
426int wc_DsaVerify(const byte* digest, const byte* sig, DsaKey* key, int* answer)
427{
428 mp_int w, u1, u2, v, r, s;
429 int ret = 0;
430
431 if (mp_init_multi(&w, &u1, &u2, &v, &r, &s) != MP_OKAY)
432 return MP_INIT_E;
433
434 /* set r and s from signature */
435 if (mp_read_unsigned_bin(&r, sig, DSA_HALF_SIZE) != MP_OKAY ||
436 mp_read_unsigned_bin(&s, sig + DSA_HALF_SIZE, DSA_HALF_SIZE) != MP_OKAY)
437 ret = MP_READ_E;
438
439 /* sanity checks */
440 if (ret == 0) {
441 if (mp_iszero(&r) == MP_YES || mp_iszero(&s) == MP_YES ||
442 mp_cmp(&r, &key->q) != MP_LT || mp_cmp(&s, &key->q) != MP_LT) {
443 ret = MP_ZERO_E;
444 }
445 }
446
447 /* put H into u1 from sha digest */
448 if (ret == 0 && mp_read_unsigned_bin(&u1,digest,SHA_DIGEST_SIZE) != MP_OKAY)
449 ret = MP_READ_E;
450
451 /* w = s invmod q */
452 if (ret == 0 && mp_invmod(&s, &key->q, &w) != MP_OKAY)
453 ret = MP_INVMOD_E;
454
455 /* u1 = (H * w) % q */
456 if (ret == 0 && mp_mulmod(&u1, &w, &key->q, &u1) != MP_OKAY)
457 ret = MP_MULMOD_E;
458
459 /* u2 = (r * w) % q */
460 if (ret == 0 && mp_mulmod(&r, &w, &key->q, &u2) != MP_OKAY)
461 ret = MP_MULMOD_E;
462
463 /* verify v = ((g^u1 * y^u2) mod p) mod q */
464 if (ret == 0 && mp_exptmod(&key->g, &u1, &key->p, &u1) != MP_OKAY)
465 ret = MP_EXPTMOD_E;
466
467 if (ret == 0 && mp_exptmod(&key->y, &u2, &key->p, &u2) != MP_OKAY)
468 ret = MP_EXPTMOD_E;
469
470 if (ret == 0 && mp_mulmod(&u1, &u2, &key->p, &v) != MP_OKAY)
471 ret = MP_MULMOD_E;
472
473 if (ret == 0 && mp_mod(&v, &key->q, &v) != MP_OKAY)
474 ret = MP_MULMOD_E;
475
476 /* do they match */
477 if (ret == 0 && mp_cmp(&r, &v) == MP_EQ)
478 *answer = 1;
479 else
480 *answer = 0;
481
482 mp_clear(&s);
483 mp_clear(&r);
484 mp_clear(&u1);
485 mp_clear(&u2);
486 mp_clear(&w);
487 mp_clear(&v);
488
489 return ret;
490}
491
492
493#endif /* NO_DSA */
494
Note: See TracBrowser for help on using the repository browser.