1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
/* LibTomCrypt, modular cryptographic library -- Tom St Denis
*
* LibTomCrypt is a library that provides various cryptographic
* algorithms in a highly modular and flexible manner.
*
* The library is free for all purposes without any express
* guarantee it works.
*
* Tom St Denis, tomstdenis@gmail.com, http://libtom.org
*/
#include "tomcrypt.h"
/**
@file dsa_make_key.c
DSA implementation, generate a DSA key, Tom St Denis
*/
#ifdef LTC_MDSA
/**
Create a DSA key
@param group_size Size of the multiplicative group (octets)
@param modulus_size Size of the modulus (octets)
@param key [out] Where to store the created key
@return CRYPT_OK if successful, upon error this function will free all allocated memory
*/
int dsa_make_key(int group_size, int modulus_size, dsa_key * key)
{
mp_int tmp, tmp2;
int err, res;
unsigned char *buf;
LTC_ARGCHK(key != NULL);
/* check size */
if (group_size >= LTC_MDSA_MAX_GROUP || group_size <= 15 ||
group_size >= modulus_size
|| (modulus_size - group_size) >= LTC_MDSA_DELTA) {
return CRYPT_INVALID_ARG;
}
/* allocate ram */
buf = XMALLOC(LTC_MDSA_DELTA);
if (buf == NULL) {
return CRYPT_MEM;
}
/* init mp_ints */
if ((err =
mp_init_multi(&tmp, &tmp2, &key->g, &key->q, &key->p, &key->x,
&key->y, NULL)) != CRYPT_OK) {
XFREE(buf);
return err;
}
/* make our prime q */
if ((err = rand_prime(&key->q, group_size)) != CRYPT_OK) {
goto error;
}
/* double q */
if ((err = mp_add(&key->q, &key->q, &tmp)) != CRYPT_OK) {
goto error;
}
/* now make a random string and multply it against q */
get_random_bytes(buf + 1, modulus_size - group_size);
/* force magnitude */
buf[0] |= 0xC0;
/* force even */
buf[modulus_size - group_size - 1] &= ~1;
if ((err =
mp_read_unsigned_bin(&tmp2, buf,
modulus_size - group_size)) != CRYPT_OK) {
goto error;
}
if ((err = mp_mul(&key->q, &tmp2, &key->p)) != CRYPT_OK) {
goto error;
}
if ((err = mp_add_d(&key->p, 1, &key->p)) != CRYPT_OK) {
goto error;
}
/* now loop until p is prime */
for (;;) {
if ((err = mp_prime_is_prime(&key->p, 8, &res)) != CRYPT_OK) {
goto error;
}
if (res == LTC_MP_YES)
break;
/* add 2q to p and 2 to tmp2 */
if ((err = mp_add(&tmp, &key->p, &key->p)) != CRYPT_OK) {
goto error;
}
if ((err = mp_add_d(&tmp2, 2, &tmp2)) != CRYPT_OK) {
goto error;
}
}
/* now p = (q * tmp2) + 1 is prime, find a value g for which g^tmp2 != 1 */
mp_set(&key->g, 1);
do {
if ((err = mp_add_d(&key->g, 1, &key->g)) != CRYPT_OK) {
goto error;
}
if ((err =
mp_exptmod(&key->g, &tmp2, &key->p, &tmp)) != CRYPT_OK) {
goto error;
}
} while (mp_cmp_d(&tmp, 1) == LTC_MP_EQ);
/* at this point tmp generates a group of order q mod p */
mp_exch(&tmp, &key->g);
/* so now we have our DH structure, generator g, order q, modulus p
Now we need a random exponent [mod q] and it's power g^x mod p
*/
do {
get_random_bytes(buf, group_size);
if ((err =
mp_read_unsigned_bin(&key->x, buf,
group_size)) != CRYPT_OK) {
goto error;
}
} while (mp_cmp_d(&key->x, 1) != LTC_MP_GT);
if ((err = mp_exptmod(&key->g, &key->x, &key->p, &key->y)) != CRYPT_OK) {
goto error;
}
key->type = PK_PRIVATE;
key->qord = group_size;
#ifdef LTC_CLEAN_STACK
zeromem(buf, LTC_MDSA_DELTA);
#endif
err = CRYPT_OK;
goto done;
error:
mp_clear_multi(&key->g, &key->q, &key->p, &key->x, &key->y, NULL);
done:
mp_clear_multi(&tmp, &tmp2, NULL);
XFREE(buf);
return err;
}
#endif
/* $Source: /cvs/libtom/libtomcrypt/src/pk/dsa/dsa_make_key.c,v $ */
/* $Revision: 1.12 $ */
/* $Date: 2007/05/12 14:32:35 $ */
|
