comparison libtomcrypt/src/pk/dsa/dsa_make_key.c @ 285:1b9e69c058d2

propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 20dccfc09627970a312d77fb41dc2970b62689c3) to branch 'au.asn.ucc.matt.dropbear' (head fdf4a7a3b97ae5046139915de7e40399cceb2c01)
author Matt Johnston <matt@ucc.asn.au>
date Wed, 08 Mar 2006 13:23:58 +0000
parents
children 0cbe8f6dbf9e
comparison
equal deleted inserted replaced
281:997e6f7dc01e 285:1b9e69c058d2
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.org
10 */
11 #include "tomcrypt.h"
12
13 /**
14 @file dsa_make_key.c
15 DSA implementation, generate a DSA key, Tom St Denis
16 */
17
18 #ifdef MDSA
19
20 /**
21 Create a DSA key
22 @param prng An active PRNG state
23 @param wprng The index of the PRNG desired
24 @param group_size Size of the multiplicative group (octets)
25 @param modulus_size Size of the modulus (octets)
26 @param key [out] Where to store the created key
27 @return CRYPT_OK if successful, upon error this function will free all allocated memory
28 */
29 int dsa_make_key(prng_state *prng, int wprng, int group_size, int modulus_size, dsa_key *key)
30 {
31 mp_int tmp, tmp2;
32 int err, res;
33 unsigned char *buf;
34
35 LTC_ARGCHK(key != NULL);
36
37 /* check prng */
38 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
39 return err;
40 }
41
42 /* check size */
43 if (group_size >= MDSA_MAX_GROUP || group_size <= 15 ||
44 group_size >= modulus_size || (modulus_size - group_size) >= MDSA_DELTA) {
45 return CRYPT_INVALID_ARG;
46 }
47
48 /* allocate ram */
49 buf = XMALLOC(MDSA_DELTA);
50 if (buf == NULL) {
51 return CRYPT_MEM;
52 }
53
54 /* init mp_ints */
55 if ((err = mp_init_multi(&tmp, &tmp2, &key->g, &key->q, &key->p, &key->x, &key->y, NULL)) != MP_OKAY) {
56 err = mpi_to_ltc_error(err);
57 goto LBL_ERR;
58 }
59
60 /* make our prime q */
61 if ((err = rand_prime(&key->q, group_size*8, prng, wprng)) != CRYPT_OK) { goto LBL_ERR; }
62
63 /* double q */
64 if ((err = mp_mul_2(&key->q, &tmp)) != MP_OKAY) { goto error; }
65
66 /* now make a random string and multply it against q */
67 if (prng_descriptor[wprng].read(buf+1, modulus_size - group_size, prng) != (unsigned long)(modulus_size - group_size)) {
68 err = CRYPT_ERROR_READPRNG;
69 goto LBL_ERR;
70 }
71
72 /* force magnitude */
73 buf[0] |= 0xC0;
74
75 /* force even */
76 buf[modulus_size - group_size - 1] &= ~1;
77
78 if ((err = mp_read_unsigned_bin(&tmp2, buf, modulus_size - group_size)) != MP_OKAY) { goto error; }
79 if ((err = mp_mul(&key->q, &tmp2, &key->p)) != MP_OKAY) { goto error; }
80 if ((err = mp_add_d(&key->p, 1, &key->p)) != MP_OKAY) { goto error; }
81
82 /* now loop until p is prime */
83 for (;;) {
84 if ((err = is_prime(&key->p, &res)) != CRYPT_OK) { goto LBL_ERR; }
85 if (res == MP_YES) break;
86
87 /* add 2q to p and 2 to tmp2 */
88 if ((err = mp_add(&tmp, &key->p, &key->p)) != MP_OKAY) { goto error; }
89 if ((err = mp_add_d(&tmp2, 2, &tmp2)) != MP_OKAY) { goto error; }
90 }
91
92 /* now p = (q * tmp2) + 1 is prime, find a value g for which g^tmp2 != 1 */
93 mp_set(&key->g, 1);
94
95 do {
96 if ((err = mp_add_d(&key->g, 1, &key->g)) != MP_OKAY) { goto error; }
97 if ((err = mp_exptmod(&key->g, &tmp2, &key->p, &tmp)) != MP_OKAY) { goto error; }
98 } while (mp_cmp_d(&tmp, 1) == MP_EQ);
99
100 /* at this point tmp generates a group of order q mod p */
101 mp_exch(&tmp, &key->g);
102
103 /* so now we have our DH structure, generator g, order q, modulus p
104 Now we need a random exponent [mod q] and it's power g^x mod p
105 */
106 do {
107 if (prng_descriptor[wprng].read(buf, group_size, prng) != (unsigned long)group_size) {
108 err = CRYPT_ERROR_READPRNG;
109 goto LBL_ERR;
110 }
111 if ((err = mp_read_unsigned_bin(&key->x, buf, group_size)) != MP_OKAY) { goto error; }
112 } while (mp_cmp_d(&key->x, 1) != MP_GT);
113 if ((err = mp_exptmod(&key->g, &key->x, &key->p, &key->y)) != MP_OKAY) { goto error; }
114
115 key->type = PK_PRIVATE;
116 key->qord = group_size;
117
118 /* shrink the ram required */
119 if ((err = mp_shrink(&key->g)) != MP_OKAY) { goto error; }
120 if ((err = mp_shrink(&key->p)) != MP_OKAY) { goto error; }
121 if ((err = mp_shrink(&key->q)) != MP_OKAY) { goto error; }
122 if ((err = mp_shrink(&key->x)) != MP_OKAY) { goto error; }
123 if ((err = mp_shrink(&key->y)) != MP_OKAY) { goto error; }
124
125 #ifdef LTC_CLEAN_STACK
126 zeromem(buf, MDSA_DELTA);
127 #endif
128
129 err = CRYPT_OK;
130 goto done;
131 error:
132 err = mpi_to_ltc_error(err);
133 LBL_ERR:
134 mp_clear_multi(&key->g, &key->q, &key->p, &key->x, &key->y, NULL);
135 done:
136 mp_clear_multi(&tmp, &tmp2, NULL);
137
138 XFREE(buf);
139 return err;
140 }
141
142 #endif
143
144 /* $Source: /cvs/libtom/libtomcrypt/src/pk/dsa/dsa_make_key.c,v $ */
145 /* $Revision: 1.4 $ */
146 /* $Date: 2005/06/11 05:45:35 $ */