dsa_make_key.c revision f7fc46c63fdc8f39234fea409b8dbe116d73ebf8
119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* LibTomCrypt, modular cryptographic library -- Tom St Denis 219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * 319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * LibTomCrypt is a library that provides various cryptographic 419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * algorithms in a highly modular and flexible manner. 519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * 619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * The library is free for all purposes without any express 719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * guarantee it works. 819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * 919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com 1019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 1119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "tomcrypt.h" 1219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 1319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/** 1419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project @file dsa_make_key.c 1519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project DSA implementation, generate a DSA key, Tom St Denis 1619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project*/ 1719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 1819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#ifdef MDSA 1919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 2019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/** 2119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project Create a DSA key 2219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project @param prng An active PRNG state 2319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project @param wprng The index of the PRNG desired 2419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project @param group_size Size of the multiplicative group (octets) 2519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project @param modulus_size Size of the modulus (octets) 2619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project @param key [out] Where to store the created key 2719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project @return CRYPT_OK if successful, upon error this function will free all allocated memory 2819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project*/ 2919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectint dsa_make_key(prng_state *prng, int wprng, int group_size, int modulus_size, dsa_key *key) 3019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 3119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project void *tmp, *tmp2; 3219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project int err, res; 3319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project unsigned char *buf; 3419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 3519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project LTC_ARGCHK(key != NULL); 3619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project LTC_ARGCHK(ltc_mp.name != NULL); 3719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 3819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* check prng */ 3919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = prng_is_valid(wprng)) != CRYPT_OK) { 4019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return err; 4119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 4219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 4319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* check size */ 4419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (group_size >= MDSA_MAX_GROUP || group_size <= 15 || 4519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project group_size >= modulus_size || (modulus_size - group_size) >= MDSA_DELTA) { 4619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return CRYPT_INVALID_ARG; 4719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 4819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 4919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* allocate ram */ 5019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project buf = XMALLOC(MDSA_DELTA); 5119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (buf == NULL) { 5219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return CRYPT_MEM; 5319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 5419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 5519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* init mp_ints */ 5619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_init_multi(&tmp, &tmp2, &key->g, &key->q, &key->p, &key->x, &key->y, NULL)) != CRYPT_OK) { 5719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project XFREE(buf); 5819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return err; 5919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 6019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 6119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* make our prime q */ 6219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = rand_prime(key->q, group_size, prng, wprng)) != CRYPT_OK) { goto error; } 6319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 6419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* double q */ 6519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_add(key->q, key->q, tmp)) != CRYPT_OK) { goto error; } 6619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 6719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* now make a random string and multply it against q */ 6819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (prng_descriptor[wprng].read(buf+1, modulus_size - group_size, prng) != (unsigned long)(modulus_size - group_size)) { 6919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project err = CRYPT_ERROR_READPRNG; 7019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project goto error; 7119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 7219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 7319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* force magnitude */ 7419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project buf[0] |= 0xC0; 7519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 7619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* force even */ 7719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project buf[modulus_size - group_size - 1] &= ~1; 7819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 7919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_read_unsigned_bin(tmp2, buf, modulus_size - group_size)) != CRYPT_OK) { goto error; } 8019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_mul(key->q, tmp2, key->p)) != CRYPT_OK) { goto error; } 8119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_add_d(key->p, 1, key->p)) != CRYPT_OK) { goto error; } 8219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 8319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* now loop until p is prime */ 8419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project for (;;) { 8519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_prime_is_prime(key->p, 8, &res)) != CRYPT_OK) { goto error; } 8619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (res == LTC_MP_YES) break; 8719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 8819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* add 2q to p and 2 to tmp2 */ 8919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_add(tmp, key->p, key->p)) != CRYPT_OK) { goto error; } 9019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_add_d(tmp2, 2, tmp2)) != CRYPT_OK) { goto error; } 9119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 9219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 9319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* now p = (q * tmp2) + 1 is prime, find a value g for which g^tmp2 != 1 */ 9419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project mp_set(key->g, 1); 9519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 9619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project do { 9719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_add_d(key->g, 1, key->g)) != CRYPT_OK) { goto error; } 9819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_exptmod(key->g, tmp2, key->p, tmp)) != CRYPT_OK) { goto error; } 9919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } while (mp_cmp_d(tmp, 1) == LTC_MP_EQ); 10019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 10119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* at this point tmp generates a group of order q mod p */ 10219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project mp_exch(tmp, key->g); 10319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 10419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* so now we have our DH structure, generator g, order q, modulus p 10519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project Now we need a random exponent [mod q] and it's power g^x mod p 10619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 10719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project do { 10819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (prng_descriptor[wprng].read(buf, group_size, prng) != (unsigned long)group_size) { 10919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project err = CRYPT_ERROR_READPRNG; 11019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project goto error; 11119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 11219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_read_unsigned_bin(key->x, buf, group_size)) != CRYPT_OK) { goto error; } 11319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } while (mp_cmp_d(key->x, 1) != LTC_MP_GT); 11419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if ((err = mp_exptmod(key->g, key->x, key->p, key->y)) != CRYPT_OK) { goto error; } 11519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 11619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project key->type = PK_PRIVATE; 11719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project key->qord = group_size; 11819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 11919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#ifdef LTC_CLEAN_STACK 12019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project zeromem(buf, MDSA_DELTA); 12119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#endif 12219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 12319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project err = CRYPT_OK; 12419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project goto done; 12519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projecterror: 12619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project mp_clear_multi(key->g, key->q, key->p, key->x, key->y, NULL); 12719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectdone: 12819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project mp_clear_multi(tmp, tmp2, NULL); 12919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project XFREE(buf); 13019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return err; 13119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 13219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 13319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#endif 13419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 13519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* $Source: /cvs/libtom/libtomcrypt/src/pk/dsa/dsa_make_key.c,v $ */ 13619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* $Revision: 1.10 $ */ 13719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* $Date: 2006/12/04 03:18:43 $ */ 13819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project