Elijah P / CyaSSL

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.

Fork of CyaSSL by wolf SSL

ctaocrypt/src/dsa.c@0:1239e9b70ca2, 2014-07-12 (annotated)

Committer:
wolfSSL
Date:
Sat Jul 12 07:18:23 2014 +0000
Revision:
0:1239e9b70ca2
CyaSSL 3.0.0;

Who changed what in which revision?

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