Francois Berder / cyassl-lib

fork of cyassl-lib

Dependents:   TLS_cyassl TLS_cyassl

ctaocrypt/src/dsa.c@4:f377303c41be, 2013-09-16 (annotated)

Committer:
feb11
Date:
Mon Sep 16 09:53:35 2013 +0000
Revision:
4:f377303c41be
Parent:
0:714293de3836 
changed settings

Who changed what in which revision?

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