dsa.c

00001 /* dsa.c
00002  *
00003  * Copyright (C) 2006-2016 wolfSSL Inc.
00004  *
00005  * This file is part of wolfSSL.
00006  *
00007  * wolfSSL is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 2 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * wolfSSL is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
00020  */
00021 
00022 
00023 #ifdef HAVE_CONFIG_H
00024     #include <config.h>
00025 #endif
00026 
00027 #include <wolfssl/wolfcrypt/settings.h>
00028 
00029 #ifndef NO_DSA
00030 
00031 #include <wolfssl/wolfcrypt/random.h>
00032 #include <wolfssl/wolfcrypt/integer.h>
00033 #include <wolfssl/wolfcrypt/error-crypt.h>
00034 #include <wolfssl/wolfcrypt/logging.h>
00035 #include <wolfssl/wolfcrypt/sha.h>
00036 #include <wolfssl/wolfcrypt/dsa.h>
00037 
00038 #ifdef NO_INLINE
00039     #include <wolfssl/wolfcrypt/misc.h>
00040 #else
00041     #define WOLFSSL_MISC_INCLUDED
00042     #include <wolfcrypt/src/misc.c>
00043 #endif
00044 
00045 
00046 enum {
00047     DSA_HALF_SIZE = 20,   /* r and s size  */
00048     DSA_SIG_SIZE  = 40    /* signature size */
00049 };
00050 
00051 
00052 
00053 int wc_InitDsaKey(DsaKey* key)
00054 {
00055     if (key == NULL)
00056         return BAD_FUNC_ARG;
00057 
00058     key->type = -1;  /* haven't decided yet */
00059     key->heap = NULL;
00060 
00061     return mp_init_multi(
00062         /* public  alloc parts */
00063         &key->p,
00064         &key->q,
00065         &key->g,
00066         &key->y,
00067 
00068         /* private alloc parts */
00069         &key->x,
00070         NULL
00071     );
00072 }
00073 
00074 
00075 int wc_InitDsaKey_h(DsaKey* key, void* h)
00076 {
00077     int ret = wc_InitDsaKey(key);
00078     if (ret == 0)
00079         key->heap = h;
00080 
00081     return ret;
00082 }
00083 
00084 
00085 void wc_FreeDsaKey(DsaKey* key)
00086 {
00087     if (key == NULL)
00088         return;
00089 
00090     if (key->type == DSA_PRIVATE)
00091         mp_forcezero(&key->x);
00092 
00093 #ifndef USE_FAST_MATH
00094     mp_clear(&key->x);
00095     mp_clear(&key->y);
00096     mp_clear(&key->g);
00097     mp_clear(&key->q);
00098     mp_clear(&key->p);
00099 #endif
00100 }
00101 
00102 #ifdef WOLFSSL_KEY_GEN
00103 
00104 int wc_MakeDsaKey(WC_RNG *rng, DsaKey *dsa)
00105 {
00106     unsigned char *buf;
00107     int qsize, err;
00108 
00109     if (rng == NULL || dsa == NULL)
00110         return BAD_FUNC_ARG;
00111 
00112     qsize = mp_unsigned_bin_size(&dsa->q);
00113     if (qsize == 0)
00114         return BAD_FUNC_ARG;
00115 
00116     /* allocate ram */
00117     buf = (unsigned char *)XMALLOC(qsize, dsa->heap,
00118                                    DYNAMIC_TYPE_TMP_BUFFER);
00119     if (buf == NULL)
00120         return MEMORY_E;
00121 
00122     if (mp_init(&dsa->x) != MP_OKAY) {
00123         XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00124         return MP_INIT_E;
00125     }
00126 
00127     do {
00128         /* make a random exponent mod q */
00129         err = wc_RNG_GenerateBlock(rng, buf, qsize);
00130         if (err != MP_OKAY) {
00131             mp_clear(&dsa->x);
00132             XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00133             return err;
00134         }
00135 
00136         err = mp_read_unsigned_bin(&dsa->x, buf, qsize);
00137         if (err != MP_OKAY) {
00138             mp_clear(&dsa->x);
00139             XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00140             return err;
00141         }
00142     } while (mp_cmp_d(&dsa->x, 1) != MP_GT);
00143 
00144     XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00145 
00146     if (mp_init(&dsa->y) != MP_OKAY) {
00147         mp_clear(&dsa->x);
00148         return MP_INIT_E;
00149     }
00150 
00151     /* public key : y = g^x mod p */
00152     err = mp_exptmod(&dsa->g, &dsa->x, &dsa->p, &dsa->y);
00153     if (err != MP_OKAY) {
00154         mp_clear(&dsa->x);
00155         mp_clear(&dsa->y);
00156         return err;
00157     }
00158 
00159     dsa->type = DSA_PRIVATE;
00160 
00161     return MP_OKAY;
00162 }
00163 
00164 /* modulus_size in bits */
00165 int wc_MakeDsaParameters(WC_RNG *rng, int modulus_size, DsaKey *dsa)
00166 {
00167     mp_int  tmp, tmp2;
00168     int     err, msize, qsize,
00169             loop_check_prime = 0,
00170             check_prime = MP_NO;
00171     unsigned char   *buf;
00172 
00173     if (rng == NULL || dsa == NULL)
00174         return BAD_FUNC_ARG;
00175 
00176     /* set group size in bytes from modulus size
00177      * FIPS 186-4 defines valid values (1024, 160) (2048, 256) (3072, 256)
00178      */
00179     switch (modulus_size) {
00180         case 1024:
00181             qsize = 20;
00182             break;
00183         case 2048:
00184         case 3072:
00185             qsize = 32;
00186             break;
00187         default:
00188             return BAD_FUNC_ARG;
00189             break;
00190     }
00191 
00192     /* modulus size in bytes */
00193     msize = modulus_size / 8;
00194 
00195     /* allocate ram */
00196     buf = (unsigned char *)XMALLOC(msize - qsize,
00197                                    dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00198     if (buf == NULL) {
00199         return MEMORY_E;
00200     }
00201 
00202     /* make a random string that will be multplied against q */
00203     err = wc_RNG_GenerateBlock(rng, buf, msize - qsize);
00204     if (err != MP_OKAY) {
00205         XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00206         return err;
00207     }
00208 
00209     /* force magnitude */
00210     buf[0] |= 0xC0;
00211 
00212     /* force even */
00213     buf[msize - qsize - 1] &= ~1;
00214 
00215     if (mp_init_multi(&tmp2, &dsa->p, &dsa->q, 0, 0, 0) != MP_OKAY) {
00216         mp_clear(&dsa->q);
00217         XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00218         return MP_INIT_E;
00219     }
00220 
00221     err = mp_read_unsigned_bin(&tmp2, buf, msize - qsize);
00222     if (err != MP_OKAY) {
00223         mp_clear(&dsa->q);
00224         mp_clear(&dsa->p);
00225         mp_clear(&tmp2);
00226         XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00227         return err;
00228     }
00229     XFREE(buf, dsa->heap, DYNAMIC_TYPE_TMP_BUFFER);
00230 
00231     /* make our prime q */
00232     err = mp_rand_prime(&dsa->q, qsize, rng, NULL);
00233     if (err != MP_OKAY) {
00234         mp_clear(&dsa->q);
00235         mp_clear(&dsa->p);
00236         mp_clear(&tmp2);
00237         return err;
00238     }
00239 
00240     /* p = random * q */
00241     err = mp_mul(&dsa->q, &tmp2, &dsa->p);
00242     if (err != MP_OKAY) {
00243         mp_clear(&dsa->q);
00244         mp_clear(&dsa->p);
00245         mp_clear(&tmp2);
00246         return err;
00247     }
00248 
00249     /* p = random * q + 1, so q is a prime divisor of p-1 */
00250     err = mp_add_d(&dsa->p, 1, &dsa->p);
00251     if (err != MP_OKAY) {
00252         mp_clear(&dsa->q);
00253         mp_clear(&dsa->p);
00254         mp_clear(&tmp2);
00255         return err;
00256     }
00257 
00258     if (mp_init(&tmp) != MP_OKAY) {
00259         mp_clear(&dsa->q);
00260         mp_clear(&dsa->p);
00261         mp_clear(&tmp2);
00262         return MP_INIT_E;
00263     }
00264 
00265     /* tmp = 2q  */
00266     err = mp_add(&dsa->q, &dsa->q, &tmp);
00267     if (err != MP_OKAY) {
00268         mp_clear(&dsa->q);
00269         mp_clear(&dsa->p);
00270         mp_clear(&tmp);
00271         mp_clear(&tmp2);
00272         return err;
00273     }
00274 
00275     /* loop until p is prime */
00276     while (check_prime == MP_NO) {
00277         err = mp_prime_is_prime(&dsa->p, 8, &check_prime);
00278         if (err != MP_OKAY) {
00279             mp_clear(&dsa->q);
00280             mp_clear(&dsa->p);
00281             mp_clear(&tmp);
00282             mp_clear(&tmp2);
00283             return err;
00284         }
00285 
00286         if (check_prime != MP_YES) {
00287             /* p += 2q */
00288             err = mp_add(&tmp, &dsa->p, &dsa->p);
00289             if (err != MP_OKAY) {
00290                 mp_clear(&dsa->q);
00291                 mp_clear(&dsa->p);
00292                 mp_clear(&tmp);
00293                 mp_clear(&tmp2);
00294                 return err;
00295             }
00296 
00297             loop_check_prime++;
00298         }
00299     }
00300 
00301     /* tmp2 += (2*loop_check_prime)
00302      * to have p = (q * tmp2) + 1 prime
00303      */
00304     if (loop_check_prime) {
00305         err = mp_add_d(&tmp2, 2*loop_check_prime, &tmp2);
00306         if (err != MP_OKAY) {
00307             mp_clear(&dsa->q);
00308             mp_clear(&dsa->p);
00309             mp_clear(&tmp);
00310             mp_clear(&tmp2);
00311             return err;
00312         }
00313     }
00314 
00315     if (mp_init(&dsa->g) != MP_OKAY) {
00316         mp_clear(&dsa->q);
00317         mp_clear(&dsa->p);
00318         mp_clear(&tmp);
00319         mp_clear(&tmp2);
00320         return MP_INIT_E;
00321     }
00322 
00323     /* find a value g for which g^tmp2 != 1 */
00324     if (mp_set(&dsa->g, 1) != MP_OKAY) {
00325         mp_clear(&dsa->q);
00326         mp_clear(&dsa->p);
00327         mp_clear(&tmp);
00328         mp_clear(&tmp2);
00329         return MP_INIT_E;
00330     }
00331 
00332     do {
00333         err = mp_add_d(&dsa->g, 1, &dsa->g);
00334         if (err != MP_OKAY) {
00335             mp_clear(&dsa->q);
00336             mp_clear(&dsa->p);
00337             mp_clear(&dsa->g);
00338             mp_clear(&tmp);
00339             mp_clear(&tmp2);
00340             return err;
00341         }
00342 
00343         err = mp_exptmod(&dsa->g, &tmp2, &dsa->p, &tmp);
00344         if (err != MP_OKAY) {
00345             mp_clear(&dsa->q);
00346             mp_clear(&dsa->p);
00347             mp_clear(&dsa->g);
00348             mp_clear(&tmp);
00349             mp_clear(&tmp2);
00350             return err;
00351         }
00352 
00353     } while (mp_cmp_d(&tmp, 1) == MP_EQ);
00354 
00355     /* at this point tmp generates a group of order q mod p */
00356     mp_exch(&tmp, &dsa->g);
00357 
00358     mp_clear(&tmp);
00359     mp_clear(&tmp2);
00360 
00361     return MP_OKAY;
00362 }
00363 #endif /* WOLFSSL_KEY_GEN */
00364 
00365 
00366 int wc_DsaSign(const byte* digest, byte* out, DsaKey* key, WC_RNG* rng)
00367 {
00368     mp_int k, kInv, r, s, H;
00369     int    ret, sz;
00370     byte   buffer[DSA_HALF_SIZE];
00371     byte*  tmp = out;  /* initial output pointer */
00372 
00373     sz = min((int)sizeof(buffer), mp_unsigned_bin_size(&key->q));
00374 
00375     if (mp_init_multi(&k, &kInv, &r, &s, &H, 0) != MP_OKAY)
00376         return MP_INIT_E;
00377 
00378     do {
00379         /* generate k */
00380         ret = wc_RNG_GenerateBlock(rng, buffer, sz);
00381         if (ret != 0)
00382             return ret;
00383 
00384         buffer[0] |= 0x0C;
00385 
00386         if (mp_read_unsigned_bin(&k, buffer, sz) != MP_OKAY)
00387             ret = MP_READ_E;
00388 
00389         /* k is a random numnber and it should be less than q
00390          * if k greater than repeat
00391          */
00392     } while (mp_cmp(&k, &key->q) != MP_LT);
00393 
00394     if (ret == 0 && mp_cmp_d(&k, 1) != MP_GT)
00395         ret = MP_CMP_E;
00396 
00397     /* inverse k mod q */
00398     if (ret == 0 && mp_invmod(&k, &key->q, &kInv) != MP_OKAY)
00399         ret = MP_INVMOD_E;
00400 
00401     /* generate r, r = (g exp k mod p) mod q */
00402     if (ret == 0 && mp_exptmod(&key->g, &k, &key->p, &r) != MP_OKAY)
00403         ret = MP_EXPTMOD_E;
00404 
00405     if (ret == 0 && mp_mod(&r, &key->q, &r) != MP_OKAY)
00406         ret = MP_MOD_E;
00407 
00408     /* generate H from sha digest */
00409     if (ret == 0 && mp_read_unsigned_bin(&H, digest,SHA_DIGEST_SIZE) != MP_OKAY)
00410         ret = MP_READ_E;
00411 
00412     /* generate s, s = (kInv * (H + x*r)) % q */
00413     if (ret == 0 && mp_mul(&key->x, &r, &s) != MP_OKAY)
00414         ret = MP_MUL_E;
00415 
00416     if (ret == 0 && mp_add(&s, &H, &s) != MP_OKAY)
00417         ret = MP_ADD_E;
00418 
00419     if (ret == 0 && mp_mulmod(&s, &kInv, &key->q, &s) != MP_OKAY)
00420         ret = MP_MULMOD_E;
00421 
00422     /* detect zero r or s */
00423     if (ret == 0 && (mp_iszero(&r) == MP_YES || mp_iszero(&s) == MP_YES))
00424         ret = MP_ZERO_E;
00425 
00426     /* write out */
00427     if (ret == 0)  {
00428         int rSz = mp_unsigned_bin_size(&r);
00429         int sSz = mp_unsigned_bin_size(&s);
00430 
00431         while (rSz++ < DSA_HALF_SIZE) {
00432             *out++ = 0x00;  /* pad front with zeros */
00433         }
00434 
00435         if (mp_to_unsigned_bin(&r, out) != MP_OKAY)
00436             ret = MP_TO_E;
00437         else {
00438             out = tmp + DSA_HALF_SIZE;  /* advance to s in output */
00439             while (sSz++ < DSA_HALF_SIZE) {
00440                 *out++ = 0x00;  /* pad front with zeros */
00441             }
00442             ret = mp_to_unsigned_bin(&s, out);
00443         }
00444     }
00445 
00446     mp_clear(&H);
00447     mp_clear(&s);
00448     mp_clear(&r);
00449     mp_clear(&kInv);
00450     mp_clear(&k);
00451 
00452     return ret;
00453 }
00454 
00455 
00456 int wc_DsaVerify(const byte* digest, const byte* sig, DsaKey* key, int* answer)
00457 {
00458     mp_int w, u1, u2, v, r, s;
00459     int    ret = 0;
00460 
00461     if (mp_init_multi(&w, &u1, &u2, &v, &r, &s) != MP_OKAY)
00462         return MP_INIT_E;
00463 
00464     /* set r and s from signature */
00465     if (mp_read_unsigned_bin(&r, sig, DSA_HALF_SIZE) != MP_OKAY ||
00466         mp_read_unsigned_bin(&s, sig + DSA_HALF_SIZE, DSA_HALF_SIZE) != MP_OKAY)
00467         ret = MP_READ_E;
00468 
00469     /* sanity checks */
00470     if (ret == 0) {
00471         if (mp_iszero(&r) == MP_YES || mp_iszero(&s) == MP_YES ||
00472                 mp_cmp(&r, &key->q) != MP_LT || mp_cmp(&s, &key->q) != MP_LT) {
00473             ret = MP_ZERO_E;
00474         }
00475     }
00476 
00477     /* put H into u1 from sha digest */
00478     if (ret == 0 && mp_read_unsigned_bin(&u1,digest,SHA_DIGEST_SIZE) != MP_OKAY)
00479         ret = MP_READ_E;
00480 
00481     /* w = s invmod q */
00482     if (ret == 0 && mp_invmod(&s, &key->q, &w) != MP_OKAY)
00483         ret = MP_INVMOD_E;
00484 
00485     /* u1 = (H * w) % q */
00486     if (ret == 0 && mp_mulmod(&u1, &w, &key->q, &u1) != MP_OKAY)
00487         ret = MP_MULMOD_E;
00488 
00489     /* u2 = (r * w) % q */
00490     if (ret == 0 && mp_mulmod(&r, &w, &key->q, &u2) != MP_OKAY)
00491         ret = MP_MULMOD_E;
00492 
00493     /* verify v = ((g^u1 * y^u2) mod p) mod q */
00494     if (ret == 0 && mp_exptmod(&key->g, &u1, &key->p, &u1) != MP_OKAY)
00495         ret = MP_EXPTMOD_E;
00496 
00497     if (ret == 0 && mp_exptmod(&key->y, &u2, &key->p, &u2) != MP_OKAY)
00498         ret = MP_EXPTMOD_E;
00499 
00500     if (ret == 0 && mp_mulmod(&u1, &u2, &key->p, &v) != MP_OKAY)
00501         ret = MP_MULMOD_E;
00502 
00503     if (ret == 0 && mp_mod(&v, &key->q, &v) != MP_OKAY)
00504         ret = MP_MULMOD_E;
00505 
00506     /* do they match */
00507     if (ret == 0 && mp_cmp(&r, &v) == MP_EQ)
00508         *answer = 1;
00509     else
00510         *answer = 0;
00511 
00512     mp_clear(&s);
00513     mp_clear(&r);
00514     mp_clear(&u1);
00515     mp_clear(&u2);
00516     mp_clear(&w);
00517     mp_clear(&v);
00518 
00519     return ret;
00520 }
00521 
00522 
00523 #endif /* NO_DSA */
00524 
00525