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, tomstdenis@gmail.com, http://libtomcrypt.com
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*/
29int dsa_make_key(prng_state *prng, int wprng, int group_size, int modulus_size, dsa_key *key)
30{
31   void           *tmp, *tmp2;
32   int            err, res;
33   unsigned char *buf;
34
35   LTC_ARGCHK(key  != NULL);
36   LTC_ARGCHK(ltc_mp.name != NULL);
37
38   /* check prng */
39   if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
40      return err;
41   }
42
43   /* check size */
44   if (group_size >= MDSA_MAX_GROUP || group_size <= 15 ||
45       group_size >= modulus_size || (modulus_size - group_size) >= MDSA_DELTA) {
46      return CRYPT_INVALID_ARG;
47   }
48
49   /* allocate ram */
50   buf = XMALLOC(MDSA_DELTA);
51   if (buf == NULL) {
52      return CRYPT_MEM;
53   }
54
55   /* init mp_ints  */
56   if ((err = mp_init_multi(&tmp, &tmp2, &key->g, &key->q, &key->p, &key->x, &key->y, NULL)) != CRYPT_OK) {
57      XFREE(buf);
58      return err;
59   }
60
61   /* make our prime q */
62   if ((err = rand_prime(key->q, group_size, prng, wprng)) != CRYPT_OK)                { goto error; }
63
64   /* double q  */
65   if ((err = mp_add(key->q, key->q, tmp)) != CRYPT_OK)                                { goto error; }
66
67   /* now make a random string and multply it against q */
68   if (prng_descriptor[wprng].read(buf+1, modulus_size - group_size, prng) != (unsigned long)(modulus_size - group_size)) {
69      err = CRYPT_ERROR_READPRNG;
70      goto error;
71   }
72
73   /* force magnitude */
74   buf[0] |= 0xC0;
75
76   /* force even */
77   buf[modulus_size - group_size - 1] &= ~1;
78
79   if ((err = mp_read_unsigned_bin(tmp2, buf, modulus_size - group_size)) != CRYPT_OK) { goto error; }
80   if ((err = mp_mul(key->q, tmp2, key->p)) != CRYPT_OK)                               { goto error; }
81   if ((err = mp_add_d(key->p, 1, key->p)) != CRYPT_OK)                                { goto error; }
82
83   /* now loop until p is prime */
84   for (;;) {
85       if ((err = mp_prime_is_prime(key->p, 8, &res)) != CRYPT_OK)                     { goto error; }
86       if (res == LTC_MP_YES) break;
87
88       /* add 2q to p and 2 to tmp2 */
89       if ((err = mp_add(tmp, key->p, key->p)) != CRYPT_OK)                            { goto error; }
90       if ((err = mp_add_d(tmp2, 2, tmp2)) != CRYPT_OK)                                { goto error; }
91   }
92
93   /* now p = (q * tmp2) + 1 is prime, find a value g for which g^tmp2 != 1 */
94   mp_set(key->g, 1);
95
96   do {
97      if ((err = mp_add_d(key->g, 1, key->g)) != CRYPT_OK)                             { goto error; }
98      if ((err = mp_exptmod(key->g, tmp2, key->p, tmp)) != CRYPT_OK)                   { goto error; }
99   } while (mp_cmp_d(tmp, 1) == LTC_MP_EQ);
100
101   /* at this point tmp generates a group of order q mod p */
102   mp_exch(tmp, key->g);
103
104   /* so now we have our DH structure, generator g, order q, modulus p
105      Now we need a random exponent [mod q] and it's power g^x mod p
106    */
107   do {
108      if (prng_descriptor[wprng].read(buf, group_size, prng) != (unsigned long)group_size) {
109         err = CRYPT_ERROR_READPRNG;
110         goto error;
111      }
112      if ((err = mp_read_unsigned_bin(key->x, buf, group_size)) != CRYPT_OK)           { goto error; }
113   } while (mp_cmp_d(key->x, 1) != LTC_MP_GT);
114   if ((err = mp_exptmod(key->g, key->x, key->p, key->y)) != CRYPT_OK)                 { goto error; }
115
116   key->type = PK_PRIVATE;
117   key->qord = group_size;
118
119#ifdef LTC_CLEAN_STACK
120   zeromem(buf, MDSA_DELTA);
121#endif
122
123   err = CRYPT_OK;
124   goto done;
125error:
126    mp_clear_multi(key->g, key->q, key->p, key->x, key->y, NULL);
127done:
128    mp_clear_multi(tmp, tmp2, NULL);
129    XFREE(buf);
130    return err;
131}
132
133#endif
134
135/* $Source: /cvs/libtom/libtomcrypt/src/pk/dsa/dsa_make_key.c,v $ */
136/* $Revision: 1.10 $ */
137/* $Date: 2006/12/04 03:18:43 $ */
138