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 
00039 enum {
00040     DSA_HALF_SIZE = 20,   /* r and s size  */
00041     DSA_SIG_SIZE  = 40    /* signature size */
00042 };
00043 
00044 
00045 #ifndef WOLFSSL_HAVE_MIN
00046 #define WOLFSSL_HAVE_MIN
00047 
00048     static INLINE word32 min(word32 a, word32 b)
00049     {
00050         return a > b ? b : a;
00051     }
00052 
00053 #endif /* WOLFSSL_HAVE_MIN */
00054 
00055 
00056 void wc_InitDsaKey(DsaKey* key)
00057 {
00058     key->type = -1;  /* haven't decided yet */
00059 
00060 /* TomsFastMath doesn't use memory allocation */
00061 #ifndef USE_FAST_MATH
00062     key->p.dp = 0;   /* public  alloc parts */
00063     key->q.dp = 0;    
00064     key->g.dp = 0;    
00065     key->y.dp = 0;    
00066 
00067     key->x.dp = 0;   /* private alloc parts */
00068 #endif
00069 }
00070 
00071 
00072 void wc_FreeDsaKey(DsaKey* key)
00073 {
00074     (void)key;
00075 /* TomsFastMath doesn't use memory allocation */
00076 #ifndef USE_FAST_MATH
00077     if (key->type == DSA_PRIVATE)
00078         mp_clear(&key->x);
00079     mp_clear(&key->y);
00080     mp_clear(&key->g);
00081     mp_clear(&key->q);
00082     mp_clear(&key->p);
00083 #endif
00084 }
00085 
00086 #ifdef WOLFSSL_KEY_GEN
00087 
00088 int wc_MakeDsaKey(WC_RNG *rng, DsaKey *dsa)
00089 {
00090     unsigned char *buf;
00091     int qsize, err;
00092 
00093     if (rng == NULL || dsa == NULL)
00094         return BAD_FUNC_ARG;
00095 
00096     qsize = mp_unsigned_bin_size(&dsa->q);
00097     if (qsize == 0)
00098         return BAD_FUNC_ARG;
00099 
00100     /* allocate ram */
00101     buf = (unsigned char *)XMALLOC(qsize, NULL,
00102                                    DYNAMIC_TYPE_TMP_BUFFER);
00103     if (buf == NULL)
00104         return MEMORY_E;
00105 
00106     if (mp_init(&dsa->x) != MP_OKAY) {
00107         XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00108         return MP_INIT_E;
00109     }
00110 
00111     do {
00112         /* make a random exponent mod q */
00113         err = wc_RNG_GenerateBlock(rng, buf, qsize);
00114         if (err != MP_OKAY) {
00115             mp_clear(&dsa->x);
00116             XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00117             return err;
00118         }
00119 
00120         err = mp_read_unsigned_bin(&dsa->x, buf, qsize);
00121         if (err != MP_OKAY) {
00122             mp_clear(&dsa->x);
00123             XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00124             return err;
00125         }
00126     } while (mp_cmp_d(&dsa->x, 1) != MP_GT);
00127 
00128     XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00129 
00130     if (mp_init(&dsa->y) != MP_OKAY) {
00131         mp_clear(&dsa->x);
00132         return MP_INIT_E;
00133     }
00134 
00135     /* public key : y = g^x mod p */
00136     err = mp_exptmod(&dsa->g, &dsa->x, &dsa->p, &dsa->y);
00137     if (err != MP_OKAY) {
00138         mp_clear(&dsa->x);
00139         mp_clear(&dsa->y);
00140         return err;
00141     }
00142 
00143     dsa->type = DSA_PRIVATE;
00144     
00145     return MP_OKAY;
00146 }
00147 
00148 /* modulus_size in bits */
00149 int wc_MakeDsaParameters(WC_RNG *rng, int modulus_size, DsaKey *dsa)
00150 {
00151     mp_int  tmp, tmp2;
00152     int     err, msize, qsize,
00153             loop_check_prime = 0,
00154             check_prime = MP_NO;
00155     unsigned char   *buf;
00156 
00157     if (rng == NULL || dsa == NULL)
00158         return BAD_FUNC_ARG;
00159 
00160     /* set group size in bytes from modulus size
00161      * FIPS 186-4 defines valid values (1024, 160) (2048, 256) (3072, 256)
00162      */
00163     switch (modulus_size) {
00164         case 1024:
00165             qsize = 20;
00166             break;
00167         case 2048:
00168         case 3072:
00169             qsize = 32;
00170             break;
00171         default:
00172             return BAD_FUNC_ARG;
00173             break;
00174     }
00175 
00176     /* modulus size in bytes */
00177     msize = modulus_size / 8;
00178 
00179     /* allocate ram */
00180     buf = (unsigned char *)XMALLOC(msize - qsize,
00181                                    NULL, DYNAMIC_TYPE_TMP_BUFFER);
00182     if (buf == NULL) {
00183         return MEMORY_E;
00184     }
00185 
00186     /* make a random string that will be multplied against q */
00187     err = wc_RNG_GenerateBlock(rng, buf, msize - qsize);
00188     if (err != MP_OKAY) {
00189         XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00190         return err;
00191     }
00192 
00193     /* force magnitude */
00194     buf[0] |= 0xC0;
00195 
00196     /* force even */
00197     buf[msize - qsize - 1] &= ~1;
00198 
00199     if (mp_init_multi(&tmp2, &dsa->p, &dsa->q, 0, 0, 0) != MP_OKAY) {
00200         mp_clear(&dsa->q);
00201         XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00202         return MP_INIT_E;
00203     }
00204 
00205     err = mp_read_unsigned_bin(&tmp2, buf, msize - qsize);
00206     if (err != MP_OKAY) {
00207         mp_clear(&dsa->q);
00208         mp_clear(&dsa->p);
00209         mp_clear(&tmp2);
00210         XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00211         return err;
00212     }
00213     XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
00214 
00215     /* make our prime q */
00216     err = mp_rand_prime(&dsa->q, qsize, rng, NULL);
00217     if (err != MP_OKAY) {
00218         mp_clear(&dsa->q);
00219         mp_clear(&dsa->p);
00220         mp_clear(&tmp2);
00221         return err;
00222     }
00223 
00224     /* p = random * q */
00225     err = mp_mul(&dsa->q, &tmp2, &dsa->p);
00226     if (err != MP_OKAY) {
00227         mp_clear(&dsa->q);
00228         mp_clear(&dsa->p);
00229         mp_clear(&tmp2);
00230         return err;
00231     }
00232 
00233     /* p = random * q + 1, so q is a prime divisor of p-1 */
00234     err = mp_add_d(&dsa->p, 1, &dsa->p);
00235     if (err != MP_OKAY) {
00236         mp_clear(&dsa->q);
00237         mp_clear(&dsa->p);
00238         mp_clear(&tmp2);
00239         return err;
00240     }
00241 
00242     if (mp_init(&tmp) != MP_OKAY) {
00243         mp_clear(&dsa->q);
00244         mp_clear(&dsa->p);
00245         mp_clear(&tmp2);
00246         return MP_INIT_E;
00247     }
00248 
00249     /* tmp = 2q  */
00250     err = mp_add(&dsa->q, &dsa->q, &tmp);
00251     if (err != MP_OKAY) {
00252         mp_clear(&dsa->q);
00253         mp_clear(&dsa->p);
00254         mp_clear(&tmp);
00255         mp_clear(&tmp2);
00256         return err;
00257     }
00258 
00259     /* loop until p is prime */
00260     while (check_prime == MP_NO) {
00261         err = mp_prime_is_prime(&dsa->p, 8, &check_prime);
00262         if (err != MP_OKAY) {
00263             mp_clear(&dsa->q);
00264             mp_clear(&dsa->p);
00265             mp_clear(&tmp);
00266             mp_clear(&tmp2);
00267             return err;
00268         }
00269 
00270         if (check_prime != MP_YES) {
00271             /* p += 2q */
00272             err = mp_add(&tmp, &dsa->p, &dsa->p);
00273             if (err != MP_OKAY) {
00274                 mp_clear(&dsa->q);
00275                 mp_clear(&dsa->p);
00276                 mp_clear(&tmp);
00277                 mp_clear(&tmp2);
00278                 return err;
00279             }
00280 
00281             loop_check_prime++;
00282         }
00283     }
00284 
00285     /* tmp2 += (2*loop_check_prime)
00286      * to have p = (q * tmp2) + 1 prime
00287      */
00288     if (loop_check_prime) {
00289         err = mp_add_d(&tmp2, 2*loop_check_prime, &tmp2);
00290         if (err != MP_OKAY) {
00291             mp_clear(&dsa->q);
00292             mp_clear(&dsa->p);
00293             mp_clear(&tmp);
00294             mp_clear(&tmp2);
00295             return err;
00296         }
00297     }
00298 
00299     if (mp_init(&dsa->g) != MP_OKAY) {
00300         mp_clear(&dsa->q);
00301         mp_clear(&dsa->p);
00302         mp_clear(&tmp);
00303         mp_clear(&tmp2);
00304         return MP_INIT_E;
00305     }
00306 
00307     /* find a value g for which g^tmp2 != 1 */
00308     mp_set(&dsa->g, 1);
00309 
00310     do {
00311         err = mp_add_d(&dsa->g, 1, &dsa->g);
00312         if (err != MP_OKAY) {
00313             mp_clear(&dsa->q);
00314             mp_clear(&dsa->p);
00315             mp_clear(&dsa->g);
00316             mp_clear(&tmp);
00317             mp_clear(&tmp2);
00318             return err;
00319         }
00320 
00321         err = mp_exptmod(&dsa->g, &tmp2, &dsa->p, &tmp);
00322         if (err != MP_OKAY) {
00323             mp_clear(&dsa->q);
00324             mp_clear(&dsa->p);
00325             mp_clear(&dsa->g);
00326             mp_clear(&tmp);
00327             mp_clear(&tmp2);
00328             return err;
00329         }
00330 
00331     } while (mp_cmp_d(&tmp, 1) == MP_EQ);
00332 
00333     /* at this point tmp generates a group of order q mod p */
00334     mp_exch(&tmp, &dsa->g);
00335 
00336     mp_clear(&tmp);
00337     mp_clear(&tmp2);
00338 
00339     return MP_OKAY;
00340 }
00341 #endif /* WOLFSSL_KEY_GEN */
00342 
00343 
00344 int wc_DsaSign(const byte* digest, byte* out, DsaKey* key, WC_RNG* rng)
00345 {
00346     mp_int k, kInv, r, s, H;
00347     int    ret, sz;
00348     byte   buffer[DSA_HALF_SIZE];
00349 
00350     sz = min(sizeof(buffer), mp_unsigned_bin_size(&key->q));
00351 
00352     /* generate k */
00353     ret = wc_RNG_GenerateBlock(rng, buffer, sz);
00354     if (ret != 0)
00355         return ret;
00356 
00357     buffer[0] |= 0x0C;
00358 
00359     if (mp_init_multi(&k, &kInv, &r, &s, &H, 0) != MP_OKAY)
00360         return MP_INIT_E;
00361 
00362     if (mp_read_unsigned_bin(&k, buffer, sz) != MP_OKAY)
00363         ret = MP_READ_E;
00364 
00365     if (ret == 0 && mp_cmp_d(&k, 1) != MP_GT)
00366         ret = MP_CMP_E;
00367 
00368     /* inverse k mod q */
00369     if (ret == 0 && mp_invmod(&k, &key->q, &kInv) != MP_OKAY)
00370         ret = MP_INVMOD_E;
00371 
00372     /* generate r, r = (g exp k mod p) mod q */
00373     if (ret == 0 && mp_exptmod(&key->g, &k, &key->p, &r) != MP_OKAY)
00374         ret = MP_EXPTMOD_E;
00375 
00376     if (ret == 0 && mp_mod(&r, &key->q, &r) != MP_OKAY)
00377         ret = MP_MOD_E;
00378 
00379     /* generate H from sha digest */
00380     if (ret == 0 && mp_read_unsigned_bin(&H, digest,SHA_DIGEST_SIZE) != MP_OKAY)
00381         ret = MP_READ_E;
00382 
00383     /* generate s, s = (kInv * (H + x*r)) % q */
00384     if (ret == 0 && mp_mul(&key->x, &r, &s) != MP_OKAY)
00385         ret = MP_MUL_E;
00386 
00387     if (ret == 0 && mp_add(&s, &H, &s) != MP_OKAY)
00388         ret = MP_ADD_E;
00389 
00390     if (ret == 0 && mp_mulmod(&s, &kInv, &key->q, &s) != MP_OKAY)
00391         ret = MP_MULMOD_E;
00392 
00393     /* write out */
00394     if (ret == 0)  {
00395         int rSz = mp_unsigned_bin_size(&r);
00396         int sSz = mp_unsigned_bin_size(&s);
00397 
00398         if (rSz == DSA_HALF_SIZE - 1) {
00399             out[0] = 0;
00400             out++;
00401         }
00402 
00403         if (mp_to_unsigned_bin(&r, out) != MP_OKAY)
00404             ret = MP_TO_E;
00405         else {
00406             if (sSz == DSA_HALF_SIZE - 1) {
00407                 out[rSz] = 0;
00408                 out++;
00409             }    
00410             ret = mp_to_unsigned_bin(&s, out + rSz);
00411         }
00412     }
00413 
00414     mp_clear(&H);
00415     mp_clear(&s);
00416     mp_clear(&r);
00417     mp_clear(&kInv);
00418     mp_clear(&k);
00419 
00420     return ret;
00421 }
00422 
00423 
00424 int wc_DsaVerify(const byte* digest, const byte* sig, DsaKey* key, int* answer)
00425 {
00426     mp_int w, u1, u2, v, r, s;
00427     int    ret = 0;
00428 
00429     if (mp_init_multi(&w, &u1, &u2, &v, &r, &s) != MP_OKAY)
00430         return MP_INIT_E;
00431 
00432     /* set r and s from signature */
00433     if (mp_read_unsigned_bin(&r, sig, DSA_HALF_SIZE) != MP_OKAY ||
00434         mp_read_unsigned_bin(&s, sig + DSA_HALF_SIZE, DSA_HALF_SIZE) != MP_OKAY)
00435         ret = MP_READ_E;
00436 
00437     /* sanity checks */
00438     if (ret == 0) {
00439         if (mp_iszero(&r) == MP_YES || mp_iszero(&s) == MP_YES ||
00440                 mp_cmp(&r, &key->q) != MP_LT || mp_cmp(&s, &key->q) != MP_LT) {
00441             ret = MP_ZERO_E;
00442         }
00443     }
00444 
00445     /* put H into u1 from sha digest */
00446     if (ret == 0 && mp_read_unsigned_bin(&u1,digest,SHA_DIGEST_SIZE) != MP_OKAY)
00447         ret = MP_READ_E;
00448 
00449     /* w = s invmod q */
00450     if (ret == 0 && mp_invmod(&s, &key->q, &w) != MP_OKAY)
00451         ret = MP_INVMOD_E;
00452 
00453     /* u1 = (H * w) % q */
00454     if (ret == 0 && mp_mulmod(&u1, &w, &key->q, &u1) != MP_OKAY)
00455         ret = MP_MULMOD_E;
00456 
00457     /* u2 = (r * w) % q */
00458     if (ret == 0 && mp_mulmod(&r, &w, &key->q, &u2) != MP_OKAY)
00459         ret = MP_MULMOD_E;
00460 
00461     /* verify v = ((g^u1 * y^u2) mod p) mod q */
00462     if (ret == 0 && mp_exptmod(&key->g, &u1, &key->p, &u1) != MP_OKAY)
00463         ret = MP_EXPTMOD_E;
00464 
00465     if (ret == 0 && mp_exptmod(&key->y, &u2, &key->p, &u2) != MP_OKAY)
00466         ret = MP_EXPTMOD_E;
00467 
00468     if (ret == 0 && mp_mulmod(&u1, &u2, &key->p, &v) != MP_OKAY)
00469         ret = MP_MULMOD_E;
00470 
00471     if (ret == 0 && mp_mod(&v, &key->q, &v) != MP_OKAY)
00472         ret = MP_MULMOD_E;
00473 
00474     /* do they match */
00475     if (ret == 0 && mp_cmp(&r, &v) == MP_EQ)
00476         *answer = 1;
00477     else
00478         *answer = 0;
00479 
00480     mp_clear(&s);
00481     mp_clear(&r);
00482     mp_clear(&u1);
00483     mp_clear(&u2);
00484     mp_clear(&w);
00485     mp_clear(&v);
00486 
00487     return ret;
00488 }
00489 
00490 
00491 #endif /* NO_DSA */
00492 
00493