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 (at) 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 */ 29 int 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; 125 error: 126 mp_clear_multi(key->g, key->q, key->p, key->x, key->y, NULL); 127 done: 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
