dsa.c

00001 /* dsa.c
00002  *
00003  * Copyright (C) 2006-2012 Sawtooth Consulting Ltd.
00004  *
00005  * This file is part of CyaSSL.
00006  *
00007  * CyaSSL 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  * CyaSSL 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
00020  */
00021 
00022 #ifdef HAVE_CONFIG_H
00023     #include <config.h>
00024 #endif
00025 
00026 #ifndef NO_DSA
00027 
00028 #include <cyassl/ctaocrypt/dsa.h>
00029 #include <cyassl/ctaocrypt/sha.h>
00030 #include <cyassl/ctaocrypt/random.h>
00031 #include <cyassl/ctaocrypt/error.h>
00032 
00033 
00034 enum {
00035     DSA_HALF_SIZE = 20,   /* r and s size  */
00036     DSA_SIG_SIZE  = 40    /* signature size */
00037 };
00038 
00039 
00040 #ifndef min
00041 
00042     static INLINE word32 min(word32 a, word32 b)
00043     {
00044         return a > b ? b : a;
00045     }
00046 
00047 #endif /* min */
00048 
00049 
00050 void InitDsaKey(DsaKey* key)
00051 {
00052     key->type = -1;  /* haven't decided yet */
00053 
00054 /* TomsFastMath doesn't use memory allocation */
00055 #ifndef USE_FAST_MATH
00056     key->p.dp = 0;   /* public  alloc parts */
00057     key->q.dp = 0;    
00058     key->g.dp = 0;    
00059     key->y.dp = 0;    
00060 
00061     key->x.dp = 0;   /* private alloc parts */
00062 #endif
00063 }
00064 
00065 
00066 void FreeDsaKey(DsaKey* key)
00067 {
00068     (void)key;
00069 /* TomsFastMath doesn't use memory allocation */
00070 #ifndef USE_FAST_MATH
00071     if (key->type == DSA_PRIVATE)
00072         mp_clear(&key->x);
00073     mp_clear(&key->y);
00074     mp_clear(&key->g);
00075     mp_clear(&key->q);
00076     mp_clear(&key->p);
00077 #endif
00078 }
00079 
00080 
00081 int DsaSign(const byte* digest, byte* out, DsaKey* key, RNG* rng)
00082 {
00083     mp_int k, kInv, r, s, H;
00084     int    ret = 0, sz;
00085     byte   buffer[DSA_HALF_SIZE];
00086 
00087     if (mp_init_multi(&k, &kInv, &r, &s, &H, 0) != MP_OKAY)
00088         return MP_INIT_E;
00089 
00090     sz = min(sizeof(buffer), mp_unsigned_bin_size(&key->q)); 
00091 
00092     /* generate k */
00093     RNG_GenerateBlock(rng, buffer, sz);
00094     buffer[0] |= 0x0C;
00095 
00096     if (mp_read_unsigned_bin(&k, buffer, sz) != MP_OKAY)
00097         ret = MP_READ_E;
00098 
00099     if (mp_cmp_d(&k, 1) != MP_GT)
00100         ret = MP_CMP_E;
00101 
00102     /* inverse k mod q */
00103     if (ret == 0 && mp_invmod(&k, &key->q, &kInv) != MP_OKAY)
00104         ret = MP_INVMOD_E;
00105 
00106     /* generate r, r = (g exp k mod p) mod q */
00107     if (ret == 0 && mp_exptmod(&key->g, &k, &key->p, &r) != MP_OKAY)
00108         ret = MP_EXPTMOD_E;
00109 
00110     if (ret == 0 && mp_mod(&r, &key->q, &r) != MP_OKAY)
00111         ret = MP_MOD_E;
00112 
00113     /* generate H from sha digest */
00114     if (ret == 0 && mp_read_unsigned_bin(&H, digest,SHA_DIGEST_SIZE) != MP_OKAY)
00115         ret = MP_READ_E;
00116 
00117     /* generate s, s = (kInv * (H + x*r)) % q */
00118     if (ret == 0 && mp_mul(&key->x, &r, &s) != MP_OKAY)
00119         ret = MP_MUL_E;
00120 
00121     if (ret == 0 && mp_add(&s, &H, &s) != MP_OKAY)
00122         ret = MP_ADD_E;
00123 
00124     if (ret == 0 && mp_mulmod(&s, &kInv, &key->q, &s) != MP_OKAY)
00125         ret = MP_MULMOD_E;
00126 
00127     /* write out */
00128     if (ret == 0)  {
00129         int rSz = mp_unsigned_bin_size(&r);
00130         int sSz = mp_unsigned_bin_size(&s);
00131 
00132         if (rSz == DSA_HALF_SIZE - 1) {
00133             out[0] = 0;
00134             out++;
00135         }
00136 
00137         if (mp_to_unsigned_bin(&r, out) != MP_OKAY)
00138             ret = MP_TO_E;
00139         else {
00140             if (sSz == DSA_HALF_SIZE - 1) {
00141                 out[rSz] = 0;
00142                 out++;
00143             }    
00144             ret = mp_to_unsigned_bin(&s, out + rSz);
00145         }
00146     }
00147 
00148     mp_clear(&H);
00149     mp_clear(&s);
00150     mp_clear(&r);
00151     mp_clear(&kInv);
00152     mp_clear(&k);
00153 
00154     return ret;
00155 }
00156 
00157 
00158 int DsaVerify(const byte* digest, const byte* sig, DsaKey* key, int* answer)
00159 {
00160     mp_int w, u1, u2, v, r, s;
00161     int    ret = 0;
00162 
00163     if (mp_init_multi(&w, &u1, &u2, &v, &r, &s) != MP_OKAY)
00164         return MP_INIT_E;
00165 
00166     /* set r and s from signature */
00167     if (mp_read_unsigned_bin(&r, sig, DSA_HALF_SIZE) != MP_OKAY ||
00168         mp_read_unsigned_bin(&s, sig + DSA_HALF_SIZE, DSA_HALF_SIZE) != MP_OKAY)
00169         ret = MP_READ_E;
00170 
00171     /* sanity checks */
00172 
00173 
00174     /* put H into u1 from sha digest */
00175     if (ret == 0 && mp_read_unsigned_bin(&u1,digest,SHA_DIGEST_SIZE) != MP_OKAY)
00176         ret = MP_READ_E;
00177 
00178     /* w = s invmod q */
00179     if (ret == 0 && mp_invmod(&s, &key->q, &w) != MP_OKAY)
00180         ret = MP_INVMOD_E;
00181 
00182     /* u1 = (H * w) % q */
00183     if (ret == 0 && mp_mulmod(&u1, &w, &key->q, &u1) != MP_OKAY)
00184         ret = MP_MULMOD_E;
00185 
00186     /* u2 = (r * w) % q */
00187     if (ret == 0 && mp_mulmod(&r, &w, &key->q, &u2) != MP_OKAY)
00188         ret = MP_MULMOD_E;
00189 
00190     /* verify v = ((g^u1 * y^u2) mod p) mod q */
00191     if (ret == 0 && mp_exptmod(&key->g, &u1, &key->p, &u1) != MP_OKAY)
00192         ret = MP_EXPTMOD_E;
00193 
00194     if (ret == 0 && mp_exptmod(&key->y, &u2, &key->p, &u2) != MP_OKAY)
00195         ret = MP_EXPTMOD_E;
00196 
00197     if (ret == 0 && mp_mulmod(&u1, &u2, &key->p, &v) != MP_OKAY)
00198         ret = MP_MULMOD_E;
00199 
00200     if (ret == 0 && mp_mod(&v, &key->q, &v) != MP_OKAY)
00201         ret = MP_MULMOD_E;
00202 
00203     /* do they match */
00204     if (ret == 0 && mp_cmp(&r, &v) == MP_EQ)
00205         *answer = 1;
00206     else
00207         *answer = 0;
00208 
00209     mp_clear(&s);
00210     mp_clear(&r);
00211     mp_clear(&u1);
00212     mp_clear(&u2);
00213     mp_clear(&w);
00214     mp_clear(&v);
00215 
00216     return ret;
00217 }
00218 
00219 
00220 #endif /* NO_DSA */
00221