Xuyi Wang / wolfSSL

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   OS

wolfcrypt/src/dsa.c@0:d92f9d21154c, 2015-06-26 (annotated)

Committer:
wolfSSL
Date:
Fri Jun 26 00:39:20 2015 +0000
Revision:
0:d92f9d21154c
wolfSSL 3.6.0

Who changed what in which revision?

UserRevisionLine numberNew contents of line
wolfSSL 0:d92f9d21154c 1 /* dsa.c
wolfSSL 0:d92f9d21154c 2 *
wolfSSL 0:d92f9d21154c 3 * Copyright (C) 2006-2015 wolfSSL Inc.
wolfSSL 0:d92f9d21154c 4 *
wolfSSL 0:d92f9d21154c 5 * This file is part of wolfSSL. (formerly known as CyaSSL)
wolfSSL 0:d92f9d21154c 6 *
wolfSSL 0:d92f9d21154c 7 * wolfSSL is free software; you can redistribute it and/or modify
wolfSSL 0:d92f9d21154c 8 * it under the terms of the GNU General Public License as published by
wolfSSL 0:d92f9d21154c 9 * the Free Software Foundation; either version 2 of the License, or
wolfSSL 0:d92f9d21154c 10 * (at your option) any later version.
wolfSSL 0:d92f9d21154c 11 *
wolfSSL 0:d92f9d21154c 12 * wolfSSL is distributed in the hope that it will be useful,
wolfSSL 0:d92f9d21154c 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
wolfSSL 0:d92f9d21154c 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
wolfSSL 0:d92f9d21154c 15 * GNU General Public License for more details.
wolfSSL 0:d92f9d21154c 16 *
wolfSSL 0:d92f9d21154c 17 * You should have received a copy of the GNU General Public License
wolfSSL 0:d92f9d21154c 18 * along with this program; if not, write to the Free Software
wolfSSL 0:d92f9d21154c 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
wolfSSL 0:d92f9d21154c 20 */
wolfSSL 0:d92f9d21154c 21
wolfSSL 0:d92f9d21154c 22 #ifdef HAVE_CONFIG_H
wolfSSL 0:d92f9d21154c 23 #include <config.h>
wolfSSL 0:d92f9d21154c 24 #endif
wolfSSL 0:d92f9d21154c 25
wolfSSL 0:d92f9d21154c 26 #include <wolfssl/wolfcrypt/settings.h>
wolfSSL 0:d92f9d21154c 27
wolfSSL 0:d92f9d21154c 28 #ifndef NO_DSA
wolfSSL 0:d92f9d21154c 29
wolfSSL 0:d92f9d21154c 30 #include <wolfssl/wolfcrypt/dsa.h>
wolfSSL 0:d92f9d21154c 31 #include <wolfssl/wolfcrypt/sha.h>
wolfSSL 0:d92f9d21154c 32 #include <wolfssl/wolfcrypt/random.h>
wolfSSL 0:d92f9d21154c 33 #include <wolfssl/wolfcrypt/error-crypt.h>
wolfSSL 0:d92f9d21154c 34
wolfSSL 0:d92f9d21154c 35
wolfSSL 0:d92f9d21154c 36 enum {
wolfSSL 0:d92f9d21154c 37 DSA_HALF_SIZE = 20, /* r and s size */
wolfSSL 0:d92f9d21154c 38 DSA_SIG_SIZE = 40 /* signature size */
wolfSSL 0:d92f9d21154c 39 };
wolfSSL 0:d92f9d21154c 40
wolfSSL 0:d92f9d21154c 41
wolfSSL 0:d92f9d21154c 42 #ifndef WOLFSSL_HAVE_MIN
wolfSSL 0:d92f9d21154c 43 #define WOLFSSL_HAVE_MIN
wolfSSL 0:d92f9d21154c 44
wolfSSL 0:d92f9d21154c 45 static INLINE word32 min(word32 a, word32 b)
wolfSSL 0:d92f9d21154c 46 {
wolfSSL 0:d92f9d21154c 47 return a > b ? b : a;
wolfSSL 0:d92f9d21154c 48 }
wolfSSL 0:d92f9d21154c 49
wolfSSL 0:d92f9d21154c 50 #endif /* WOLFSSL_HAVE_MIN */
wolfSSL 0:d92f9d21154c 51
wolfSSL 0:d92f9d21154c 52
wolfSSL 0:d92f9d21154c 53 void wc_InitDsaKey(DsaKey* key)
wolfSSL 0:d92f9d21154c 54 {
wolfSSL 0:d92f9d21154c 55 key->type = -1; /* haven't decided yet */
wolfSSL 0:d92f9d21154c 56
wolfSSL 0:d92f9d21154c 57 /* TomsFastMath doesn't use memory allocation */
wolfSSL 0:d92f9d21154c 58 #ifndef USE_FAST_MATH
wolfSSL 0:d92f9d21154c 59 key->p.dp = 0; /* public alloc parts */
wolfSSL 0:d92f9d21154c 60 key->q.dp = 0;
wolfSSL 0:d92f9d21154c 61 key->g.dp = 0;
wolfSSL 0:d92f9d21154c 62 key->y.dp = 0;
wolfSSL 0:d92f9d21154c 63
wolfSSL 0:d92f9d21154c 64 key->x.dp = 0; /* private alloc parts */
wolfSSL 0:d92f9d21154c 65 #endif
wolfSSL 0:d92f9d21154c 66 }
wolfSSL 0:d92f9d21154c 67
wolfSSL 0:d92f9d21154c 68
wolfSSL 0:d92f9d21154c 69 void wc_FreeDsaKey(DsaKey* key)
wolfSSL 0:d92f9d21154c 70 {
wolfSSL 0:d92f9d21154c 71 (void)key;
wolfSSL 0:d92f9d21154c 72 /* TomsFastMath doesn't use memory allocation */
wolfSSL 0:d92f9d21154c 73 #ifndef USE_FAST_MATH
wolfSSL 0:d92f9d21154c 74 if (key->type == DSA_PRIVATE)
wolfSSL 0:d92f9d21154c 75 mp_clear(&key->x);
wolfSSL 0:d92f9d21154c 76 mp_clear(&key->y);
wolfSSL 0:d92f9d21154c 77 mp_clear(&key->g);
wolfSSL 0:d92f9d21154c 78 mp_clear(&key->q);
wolfSSL 0:d92f9d21154c 79 mp_clear(&key->p);
wolfSSL 0:d92f9d21154c 80 #endif
wolfSSL 0:d92f9d21154c 81 }
wolfSSL 0:d92f9d21154c 82
wolfSSL 0:d92f9d21154c 83
wolfSSL 0:d92f9d21154c 84 int wc_DsaSign(const byte* digest, byte* out, DsaKey* key, RNG* rng)
wolfSSL 0:d92f9d21154c 85 {
wolfSSL 0:d92f9d21154c 86 mp_int k, kInv, r, s, H;
wolfSSL 0:d92f9d21154c 87 int ret, sz;
wolfSSL 0:d92f9d21154c 88 byte buffer[DSA_HALF_SIZE];
wolfSSL 0:d92f9d21154c 89
wolfSSL 0:d92f9d21154c 90 sz = min(sizeof(buffer), mp_unsigned_bin_size(&key->q));
wolfSSL 0:d92f9d21154c 91
wolfSSL 0:d92f9d21154c 92 /* generate k */
wolfSSL 0:d92f9d21154c 93 ret = wc_RNG_GenerateBlock(rng, buffer, sz);
wolfSSL 0:d92f9d21154c 94 if (ret != 0)
wolfSSL 0:d92f9d21154c 95 return ret;
wolfSSL 0:d92f9d21154c 96
wolfSSL 0:d92f9d21154c 97 buffer[0] |= 0x0C;
wolfSSL 0:d92f9d21154c 98
wolfSSL 0:d92f9d21154c 99 if (mp_init_multi(&k, &kInv, &r, &s, &H, 0) != MP_OKAY)
wolfSSL 0:d92f9d21154c 100 return MP_INIT_E;
wolfSSL 0:d92f9d21154c 101
wolfSSL 0:d92f9d21154c 102 if (mp_read_unsigned_bin(&k, buffer, sz) != MP_OKAY)
wolfSSL 0:d92f9d21154c 103 ret = MP_READ_E;
wolfSSL 0:d92f9d21154c 104
wolfSSL 0:d92f9d21154c 105 if (ret == 0 && mp_cmp_d(&k, 1) != MP_GT)
wolfSSL 0:d92f9d21154c 106 ret = MP_CMP_E;
wolfSSL 0:d92f9d21154c 107
wolfSSL 0:d92f9d21154c 108 /* inverse k mod q */
wolfSSL 0:d92f9d21154c 109 if (ret == 0 && mp_invmod(&k, &key->q, &kInv) != MP_OKAY)
wolfSSL 0:d92f9d21154c 110 ret = MP_INVMOD_E;
wolfSSL 0:d92f9d21154c 111
wolfSSL 0:d92f9d21154c 112 /* generate r, r = (g exp k mod p) mod q */
wolfSSL 0:d92f9d21154c 113 if (ret == 0 && mp_exptmod(&key->g, &k, &key->p, &r) != MP_OKAY)
wolfSSL 0:d92f9d21154c 114 ret = MP_EXPTMOD_E;
wolfSSL 0:d92f9d21154c 115
wolfSSL 0:d92f9d21154c 116 if (ret == 0 && mp_mod(&r, &key->q, &r) != MP_OKAY)
wolfSSL 0:d92f9d21154c 117 ret = MP_MOD_E;
wolfSSL 0:d92f9d21154c 118
wolfSSL 0:d92f9d21154c 119 /* generate H from sha digest */
wolfSSL 0:d92f9d21154c 120 if (ret == 0 && mp_read_unsigned_bin(&H, digest,SHA_DIGEST_SIZE) != MP_OKAY)
wolfSSL 0:d92f9d21154c 121 ret = MP_READ_E;
wolfSSL 0:d92f9d21154c 122
wolfSSL 0:d92f9d21154c 123 /* generate s, s = (kInv * (H + x*r)) % q */
wolfSSL 0:d92f9d21154c 124 if (ret == 0 && mp_mul(&key->x, &r, &s) != MP_OKAY)
wolfSSL 0:d92f9d21154c 125 ret = MP_MUL_E;
wolfSSL 0:d92f9d21154c 126
wolfSSL 0:d92f9d21154c 127 if (ret == 0 && mp_add(&s, &H, &s) != MP_OKAY)
wolfSSL 0:d92f9d21154c 128 ret = MP_ADD_E;
wolfSSL 0:d92f9d21154c 129
wolfSSL 0:d92f9d21154c 130 if (ret == 0 && mp_mulmod(&s, &kInv, &key->q, &s) != MP_OKAY)
wolfSSL 0:d92f9d21154c 131 ret = MP_MULMOD_E;
wolfSSL 0:d92f9d21154c 132
wolfSSL 0:d92f9d21154c 133 /* write out */
wolfSSL 0:d92f9d21154c 134 if (ret == 0) {
wolfSSL 0:d92f9d21154c 135 int rSz = mp_unsigned_bin_size(&r);
wolfSSL 0:d92f9d21154c 136 int sSz = mp_unsigned_bin_size(&s);
wolfSSL 0:d92f9d21154c 137
wolfSSL 0:d92f9d21154c 138 if (rSz == DSA_HALF_SIZE - 1) {
wolfSSL 0:d92f9d21154c 139 out[0] = 0;
wolfSSL 0:d92f9d21154c 140 out++;
wolfSSL 0:d92f9d21154c 141 }
wolfSSL 0:d92f9d21154c 142
wolfSSL 0:d92f9d21154c 143 if (mp_to_unsigned_bin(&r, out) != MP_OKAY)
wolfSSL 0:d92f9d21154c 144 ret = MP_TO_E;
wolfSSL 0:d92f9d21154c 145 else {
wolfSSL 0:d92f9d21154c 146 if (sSz == DSA_HALF_SIZE - 1) {
wolfSSL 0:d92f9d21154c 147 out[rSz] = 0;
wolfSSL 0:d92f9d21154c 148 out++;
wolfSSL 0:d92f9d21154c 149 }
wolfSSL 0:d92f9d21154c 150 ret = mp_to_unsigned_bin(&s, out + rSz);
wolfSSL 0:d92f9d21154c 151 }
wolfSSL 0:d92f9d21154c 152 }
wolfSSL 0:d92f9d21154c 153
wolfSSL 0:d92f9d21154c 154 mp_clear(&H);
wolfSSL 0:d92f9d21154c 155 mp_clear(&s);
wolfSSL 0:d92f9d21154c 156 mp_clear(&r);
wolfSSL 0:d92f9d21154c 157 mp_clear(&kInv);
wolfSSL 0:d92f9d21154c 158 mp_clear(&k);
wolfSSL 0:d92f9d21154c 159
wolfSSL 0:d92f9d21154c 160 return ret;
wolfSSL 0:d92f9d21154c 161 }
wolfSSL 0:d92f9d21154c 162
wolfSSL 0:d92f9d21154c 163
wolfSSL 0:d92f9d21154c 164 int wc_DsaVerify(const byte* digest, const byte* sig, DsaKey* key, int* answer)
wolfSSL 0:d92f9d21154c 165 {
wolfSSL 0:d92f9d21154c 166 mp_int w, u1, u2, v, r, s;
wolfSSL 0:d92f9d21154c 167 int ret = 0;
wolfSSL 0:d92f9d21154c 168
wolfSSL 0:d92f9d21154c 169 if (mp_init_multi(&w, &u1, &u2, &v, &r, &s) != MP_OKAY)
wolfSSL 0:d92f9d21154c 170 return MP_INIT_E;
wolfSSL 0:d92f9d21154c 171
wolfSSL 0:d92f9d21154c 172 /* set r and s from signature */
wolfSSL 0:d92f9d21154c 173 if (mp_read_unsigned_bin(&r, sig, DSA_HALF_SIZE) != MP_OKAY ||
wolfSSL 0:d92f9d21154c 174 mp_read_unsigned_bin(&s, sig + DSA_HALF_SIZE, DSA_HALF_SIZE) != MP_OKAY)
wolfSSL 0:d92f9d21154c 175 ret = MP_READ_E;
wolfSSL 0:d92f9d21154c 176
wolfSSL 0:d92f9d21154c 177 /* sanity checks */
wolfSSL 0:d92f9d21154c 178 if (ret == 0) {
wolfSSL 0:d92f9d21154c 179 if (mp_iszero(&r) == MP_YES || mp_iszero(&s) == MP_YES ||
wolfSSL 0:d92f9d21154c 180 mp_cmp(&r, &key->q) != MP_LT || mp_cmp(&s, &key->q) != MP_LT) {
wolfSSL 0:d92f9d21154c 181 ret = MP_ZERO_E;
wolfSSL 0:d92f9d21154c 182 }
wolfSSL 0:d92f9d21154c 183 }
wolfSSL 0:d92f9d21154c 184
wolfSSL 0:d92f9d21154c 185 /* put H into u1 from sha digest */
wolfSSL 0:d92f9d21154c 186 if (ret == 0 && mp_read_unsigned_bin(&u1,digest,SHA_DIGEST_SIZE) != MP_OKAY)
wolfSSL 0:d92f9d21154c 187 ret = MP_READ_E;
wolfSSL 0:d92f9d21154c 188
wolfSSL 0:d92f9d21154c 189 /* w = s invmod q */
wolfSSL 0:d92f9d21154c 190 if (ret == 0 && mp_invmod(&s, &key->q, &w) != MP_OKAY)
wolfSSL 0:d92f9d21154c 191 ret = MP_INVMOD_E;
wolfSSL 0:d92f9d21154c 192
wolfSSL 0:d92f9d21154c 193 /* u1 = (H * w) % q */
wolfSSL 0:d92f9d21154c 194 if (ret == 0 && mp_mulmod(&u1, &w, &key->q, &u1) != MP_OKAY)
wolfSSL 0:d92f9d21154c 195 ret = MP_MULMOD_E;
wolfSSL 0:d92f9d21154c 196
wolfSSL 0:d92f9d21154c 197 /* u2 = (r * w) % q */
wolfSSL 0:d92f9d21154c 198 if (ret == 0 && mp_mulmod(&r, &w, &key->q, &u2) != MP_OKAY)
wolfSSL 0:d92f9d21154c 199 ret = MP_MULMOD_E;
wolfSSL 0:d92f9d21154c 200
wolfSSL 0:d92f9d21154c 201 /* verify v = ((g^u1 * y^u2) mod p) mod q */
wolfSSL 0:d92f9d21154c 202 if (ret == 0 && mp_exptmod(&key->g, &u1, &key->p, &u1) != MP_OKAY)
wolfSSL 0:d92f9d21154c 203 ret = MP_EXPTMOD_E;
wolfSSL 0:d92f9d21154c 204
wolfSSL 0:d92f9d21154c 205 if (ret == 0 && mp_exptmod(&key->y, &u2, &key->p, &u2) != MP_OKAY)
wolfSSL 0:d92f9d21154c 206 ret = MP_EXPTMOD_E;
wolfSSL 0:d92f9d21154c 207
wolfSSL 0:d92f9d21154c 208 if (ret == 0 && mp_mulmod(&u1, &u2, &key->p, &v) != MP_OKAY)
wolfSSL 0:d92f9d21154c 209 ret = MP_MULMOD_E;
wolfSSL 0:d92f9d21154c 210
wolfSSL 0:d92f9d21154c 211 if (ret == 0 && mp_mod(&v, &key->q, &v) != MP_OKAY)
wolfSSL 0:d92f9d21154c 212 ret = MP_MULMOD_E;
wolfSSL 0:d92f9d21154c 213
wolfSSL 0:d92f9d21154c 214 /* do they match */
wolfSSL 0:d92f9d21154c 215 if (ret == 0 && mp_cmp(&r, &v) == MP_EQ)
wolfSSL 0:d92f9d21154c 216 *answer = 1;
wolfSSL 0:d92f9d21154c 217 else
wolfSSL 0:d92f9d21154c 218 *answer = 0;
wolfSSL 0:d92f9d21154c 219
wolfSSL 0:d92f9d21154c 220 mp_clear(&s);
wolfSSL 0:d92f9d21154c 221 mp_clear(&r);
wolfSSL 0:d92f9d21154c 222 mp_clear(&u1);
wolfSSL 0:d92f9d21154c 223 mp_clear(&u2);
wolfSSL 0:d92f9d21154c 224 mp_clear(&w);
wolfSSL 0:d92f9d21154c 225 mp_clear(&v);
wolfSSL 0:d92f9d21154c 226
wolfSSL 0:d92f9d21154c 227 return ret;
wolfSSL 0:d92f9d21154c 228 }
wolfSSL 0:d92f9d21154c 229
wolfSSL 0:d92f9d21154c 230
wolfSSL 0:d92f9d21154c 231 #endif /* NO_DSA */
wolfSSL 0:d92f9d21154c 232
wolfSSL 0:d92f9d21154c 233