Line data Source code
1 : /* crypto/dsa/dsa_ossl.c */
2 : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 : * All rights reserved.
4 : *
5 : * This package is an SSL implementation written
6 : * by Eric Young (eay@cryptsoft.com).
7 : * The implementation was written so as to conform with Netscapes SSL.
8 : *
9 : * This library is free for commercial and non-commercial use as long as
10 : * the following conditions are aheared to. The following conditions
11 : * apply to all code found in this distribution, be it the RC4, RSA,
12 : * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 : * included with this distribution is covered by the same copyright terms
14 : * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 : *
16 : * Copyright remains Eric Young's, and as such any Copyright notices in
17 : * the code are not to be removed.
18 : * If this package is used in a product, Eric Young should be given attribution
19 : * as the author of the parts of the library used.
20 : * This can be in the form of a textual message at program startup or
21 : * in documentation (online or textual) provided with the package.
22 : *
23 : * Redistribution and use in source and binary forms, with or without
24 : * modification, are permitted provided that the following conditions
25 : * are met:
26 : * 1. Redistributions of source code must retain the copyright
27 : * notice, this list of conditions and the following disclaimer.
28 : * 2. Redistributions in binary form must reproduce the above copyright
29 : * notice, this list of conditions and the following disclaimer in the
30 : * documentation and/or other materials provided with the distribution.
31 : * 3. All advertising materials mentioning features or use of this software
32 : * must display the following acknowledgement:
33 : * "This product includes cryptographic software written by
34 : * Eric Young (eay@cryptsoft.com)"
35 : * The word 'cryptographic' can be left out if the rouines from the library
36 : * being used are not cryptographic related :-).
37 : * 4. If you include any Windows specific code (or a derivative thereof) from
38 : * the apps directory (application code) you must include an acknowledgement:
39 : * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 : *
41 : * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 : * SUCH DAMAGE.
52 : *
53 : * The licence and distribution terms for any publically available version or
54 : * derivative of this code cannot be changed. i.e. this code cannot simply be
55 : * copied and put under another distribution licence
56 : * [including the GNU Public Licence.]
57 : */
58 :
59 : /* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */
60 :
61 : #include <stdio.h>
62 : #include "cryptlib.h"
63 : #include <openssl/bn.h>
64 : #include <openssl/sha.h>
65 : #include <openssl/dsa.h>
66 : #include <openssl/rand.h>
67 : #include <openssl/asn1.h>
68 :
69 : static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
70 : static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
71 : BIGNUM **rp);
72 : static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
73 : DSA_SIG *sig, DSA *dsa);
74 : static int dsa_init(DSA *dsa);
75 : static int dsa_finish(DSA *dsa);
76 :
77 : static DSA_METHOD openssl_dsa_meth = {
78 : "OpenSSL DSA method",
79 : dsa_do_sign,
80 : dsa_sign_setup,
81 : dsa_do_verify,
82 : NULL, /* dsa_mod_exp, */
83 : NULL, /* dsa_bn_mod_exp, */
84 : dsa_init,
85 : dsa_finish,
86 : 0,
87 : NULL,
88 : NULL,
89 : NULL
90 : };
91 :
92 : /*-
93 : * These macro wrappers replace attempts to use the dsa_mod_exp() and
94 : * bn_mod_exp() handlers in the DSA_METHOD structure. We avoid the problem of
95 : * having a the macro work as an expression by bundling an "err_instr". So;
96 : *
97 : * if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx,
98 : * dsa->method_mont_p)) goto err;
99 : *
100 : * can be replaced by;
101 : *
102 : * DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, &k, dsa->p, ctx,
103 : * dsa->method_mont_p);
104 : */
105 :
106 : #define DSA_MOD_EXP(err_instr,dsa,rr,a1,p1,a2,p2,m,ctx,in_mont) \
107 : do { \
108 : int _tmp_res53; \
109 : if ((dsa)->meth->dsa_mod_exp) \
110 : _tmp_res53 = (dsa)->meth->dsa_mod_exp((dsa), (rr), (a1), (p1), \
111 : (a2), (p2), (m), (ctx), (in_mont)); \
112 : else \
113 : _tmp_res53 = BN_mod_exp2_mont((rr), (a1), (p1), (a2), (p2), \
114 : (m), (ctx), (in_mont)); \
115 : if (!_tmp_res53) err_instr; \
116 : } while(0)
117 : #define DSA_BN_MOD_EXP(err_instr,dsa,r,a,p,m,ctx,m_ctx) \
118 : do { \
119 : int _tmp_res53; \
120 : if ((dsa)->meth->bn_mod_exp) \
121 : _tmp_res53 = (dsa)->meth->bn_mod_exp((dsa), (r), (a), (p), \
122 : (m), (ctx), (m_ctx)); \
123 : else \
124 : _tmp_res53 = BN_mod_exp_mont((r), (a), (p), (m), (ctx), (m_ctx)); \
125 : if (!_tmp_res53) err_instr; \
126 : } while(0)
127 :
128 0 : const DSA_METHOD *DSA_OpenSSL(void)
129 : {
130 0 : return &openssl_dsa_meth;
131 : }
132 :
133 0 : static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
134 : {
135 0 : BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
136 : BIGNUM m;
137 : BIGNUM xr;
138 : BN_CTX *ctx = NULL;
139 : int reason = ERR_R_BN_LIB;
140 : DSA_SIG *ret = NULL;
141 : int noredo = 0;
142 :
143 0 : BN_init(&m);
144 0 : BN_init(&xr);
145 :
146 0 : if (!dsa->p || !dsa->q || !dsa->g) {
147 : reason = DSA_R_MISSING_PARAMETERS;
148 : goto err;
149 : }
150 :
151 0 : s = BN_new();
152 0 : if (s == NULL)
153 : goto err;
154 0 : ctx = BN_CTX_new();
155 0 : if (ctx == NULL)
156 : goto err;
157 : redo:
158 0 : if ((dsa->kinv == NULL) || (dsa->r == NULL)) {
159 0 : if (!DSA_sign_setup(dsa, ctx, &kinv, &r))
160 : goto err;
161 : } else {
162 0 : kinv = dsa->kinv;
163 0 : dsa->kinv = NULL;
164 0 : r = dsa->r;
165 0 : dsa->r = NULL;
166 : noredo = 1;
167 : }
168 :
169 0 : if (dlen > BN_num_bytes(dsa->q))
170 : /*
171 : * if the digest length is greater than the size of q use the
172 : * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
173 : * 4.2
174 : */
175 0 : dlen = BN_num_bytes(dsa->q);
176 0 : if (BN_bin2bn(dgst, dlen, &m) == NULL)
177 : goto err;
178 :
179 : /* Compute s = inv(k) (m + xr) mod q */
180 0 : if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx))
181 : goto err; /* s = xr */
182 0 : if (!BN_add(s, &xr, &m))
183 : goto err; /* s = m + xr */
184 0 : if (BN_cmp(s, dsa->q) > 0)
185 0 : if (!BN_sub(s, s, dsa->q))
186 : goto err;
187 0 : if (!BN_mod_mul(s, s, kinv, dsa->q, ctx))
188 : goto err;
189 :
190 0 : ret = DSA_SIG_new();
191 0 : if (ret == NULL)
192 : goto err;
193 : /*
194 : * Redo if r or s is zero as required by FIPS 186-3: this is very
195 : * unlikely.
196 : */
197 0 : if (BN_is_zero(r) || BN_is_zero(s)) {
198 0 : if (noredo) {
199 : reason = DSA_R_NEED_NEW_SETUP_VALUES;
200 : goto err;
201 : }
202 : goto redo;
203 : }
204 0 : ret->r = r;
205 0 : ret->s = s;
206 :
207 : err:
208 0 : if (!ret) {
209 0 : DSAerr(DSA_F_DSA_DO_SIGN, reason);
210 0 : BN_free(r);
211 0 : BN_free(s);
212 : }
213 0 : if (ctx != NULL)
214 0 : BN_CTX_free(ctx);
215 0 : BN_clear_free(&m);
216 0 : BN_clear_free(&xr);
217 0 : if (kinv != NULL) /* dsa->kinv is NULL now if we used it */
218 0 : BN_clear_free(kinv);
219 0 : return (ret);
220 : }
221 :
222 0 : static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
223 : BIGNUM **rp)
224 : {
225 : BN_CTX *ctx;
226 : BIGNUM k, kq, *K, *kinv = NULL, *r = NULL;
227 : int ret = 0;
228 :
229 0 : if (!dsa->p || !dsa->q || !dsa->g) {
230 0 : DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS);
231 0 : return 0;
232 : }
233 :
234 0 : BN_init(&k);
235 0 : BN_init(&kq);
236 :
237 0 : if (ctx_in == NULL) {
238 0 : if ((ctx = BN_CTX_new()) == NULL)
239 : goto err;
240 : } else
241 : ctx = ctx_in;
242 :
243 0 : if ((r = BN_new()) == NULL)
244 : goto err;
245 :
246 : /* Get random k */
247 : do
248 0 : if (!BN_rand_range(&k, dsa->q))
249 : goto err;
250 0 : while (BN_is_zero(&k)) ;
251 0 : if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) {
252 0 : BN_set_flags(&k, BN_FLG_CONSTTIME);
253 : }
254 :
255 0 : if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
256 0 : if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
257 0 : CRYPTO_LOCK_DSA, dsa->p, ctx))
258 : goto err;
259 : }
260 :
261 : /* Compute r = (g^k mod p) mod q */
262 :
263 0 : if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) {
264 0 : if (!BN_copy(&kq, &k))
265 : goto err;
266 :
267 : /*
268 : * We do not want timing information to leak the length of k, so we
269 : * compute g^k using an equivalent exponent of fixed length. (This
270 : * is a kludge that we need because the BN_mod_exp_mont() does not
271 : * let us specify the desired timing behaviour.)
272 : */
273 :
274 0 : if (!BN_add(&kq, &kq, dsa->q))
275 : goto err;
276 0 : if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) {
277 0 : if (!BN_add(&kq, &kq, dsa->q))
278 : goto err;
279 : }
280 :
281 : K = &kq;
282 : } else {
283 : K = &k;
284 : }
285 0 : DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, K, dsa->p, ctx,
286 : dsa->method_mont_p);
287 0 : if (!BN_mod(r, r, dsa->q, ctx))
288 : goto err;
289 :
290 : /* Compute part of 's = inv(k) (m + xr) mod q' */
291 0 : if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL)
292 : goto err;
293 :
294 0 : if (*kinvp != NULL)
295 0 : BN_clear_free(*kinvp);
296 0 : *kinvp = kinv;
297 : kinv = NULL;
298 0 : if (*rp != NULL)
299 0 : BN_clear_free(*rp);
300 0 : *rp = r;
301 : ret = 1;
302 : err:
303 0 : if (!ret) {
304 0 : DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB);
305 0 : if (r != NULL)
306 0 : BN_clear_free(r);
307 : }
308 0 : if (ctx_in == NULL)
309 0 : BN_CTX_free(ctx);
310 0 : BN_clear_free(&k);
311 0 : BN_clear_free(&kq);
312 0 : return (ret);
313 : }
314 :
315 0 : static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
316 : DSA_SIG *sig, DSA *dsa)
317 : {
318 : BN_CTX *ctx;
319 : BIGNUM u1, u2, t1;
320 : BN_MONT_CTX *mont = NULL;
321 : int ret = -1, i;
322 0 : if (!dsa->p || !dsa->q || !dsa->g) {
323 0 : DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS);
324 0 : return -1;
325 : }
326 :
327 0 : i = BN_num_bits(dsa->q);
328 : /* fips 186-3 allows only different sizes for q */
329 0 : if (i != 160 && i != 224 && i != 256) {
330 0 : DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE);
331 0 : return -1;
332 : }
333 :
334 0 : if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
335 0 : DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE);
336 0 : return -1;
337 : }
338 0 : BN_init(&u1);
339 0 : BN_init(&u2);
340 0 : BN_init(&t1);
341 :
342 0 : if ((ctx = BN_CTX_new()) == NULL)
343 : goto err;
344 :
345 0 : if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
346 0 : BN_ucmp(sig->r, dsa->q) >= 0) {
347 : ret = 0;
348 : goto err;
349 : }
350 0 : if (BN_is_zero(sig->s) || BN_is_negative(sig->s) ||
351 0 : BN_ucmp(sig->s, dsa->q) >= 0) {
352 : ret = 0;
353 : goto err;
354 : }
355 :
356 : /*
357 : * Calculate W = inv(S) mod Q save W in u2
358 : */
359 0 : if ((BN_mod_inverse(&u2, sig->s, dsa->q, ctx)) == NULL)
360 : goto err;
361 :
362 : /* save M in u1 */
363 0 : if (dgst_len > (i >> 3))
364 : /*
365 : * if the digest length is greater than the size of q use the
366 : * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
367 : * 4.2
368 : */
369 : dgst_len = (i >> 3);
370 0 : if (BN_bin2bn(dgst, dgst_len, &u1) == NULL)
371 : goto err;
372 :
373 : /* u1 = M * w mod q */
374 0 : if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx))
375 : goto err;
376 :
377 : /* u2 = r * w mod q */
378 0 : if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx))
379 : goto err;
380 :
381 0 : if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
382 0 : mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
383 0 : CRYPTO_LOCK_DSA, dsa->p, ctx);
384 0 : if (!mont)
385 : goto err;
386 : }
387 :
388 0 : DSA_MOD_EXP(goto err, dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p,
389 : ctx, mont);
390 : /* BN_copy(&u1,&t1); */
391 : /* let u1 = u1 mod q */
392 0 : if (!BN_mod(&u1, &t1, dsa->q, ctx))
393 : goto err;
394 :
395 : /*
396 : * V is now in u1. If the signature is correct, it will be equal to R.
397 : */
398 0 : ret = (BN_ucmp(&u1, sig->r) == 0);
399 :
400 : err:
401 0 : if (ret < 0)
402 0 : DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB);
403 0 : if (ctx != NULL)
404 0 : BN_CTX_free(ctx);
405 0 : BN_free(&u1);
406 0 : BN_free(&u2);
407 0 : BN_free(&t1);
408 0 : return (ret);
409 : }
410 :
411 0 : static int dsa_init(DSA *dsa)
412 : {
413 0 : dsa->flags |= DSA_FLAG_CACHE_MONT_P;
414 0 : return (1);
415 : }
416 :
417 0 : static int dsa_finish(DSA *dsa)
418 : {
419 0 : if (dsa->method_mont_p)
420 0 : BN_MONT_CTX_free(dsa->method_mont_p);
421 0 : return (1);
422 : }
|
