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 <openssl/bn.h>
63#include <openssl/dsa.h>
64#include <openssl/rand.h>
65#include <openssl/asn1.h>
66#ifndef OPENSSL_NO_ENGINE
67#include <openssl/engine.h>
68#endif
69#include <openssl/fips.h>
70
71#ifdef OPENSSL_FIPS
72
73static DSA_SIG *dsa_do_sign(const unsigned char *dgst, FIPS_DSA_SIZE_T dlen, DSA *dsa);
74static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
75static int dsa_do_verify(const unsigned char *dgst, FIPS_DSA_SIZE_T dgst_len, DSA_SIG *sig,
76		  DSA *dsa);
77static int dsa_init(DSA *dsa);
78static int dsa_finish(DSA *dsa);
79static int dsa_mod_exp(DSA *dsa, BIGNUM *rr, BIGNUM *a1, BIGNUM *p1,
80		BIGNUM *a2, BIGNUM *p2, BIGNUM *m, BN_CTX *ctx,
81		BN_MONT_CTX *in_mont);
82static int dsa_bn_mod_exp(DSA *dsa, BIGNUM *r, BIGNUM *a, const BIGNUM *p,
83				const BIGNUM *m, BN_CTX *ctx,
84				BN_MONT_CTX *m_ctx);
85
86static DSA_METHOD openssl_dsa_meth = {
87"OpenSSL FIPS DSA method",
88dsa_do_sign,
89dsa_sign_setup,
90dsa_do_verify,
91dsa_mod_exp,
92dsa_bn_mod_exp,
93dsa_init,
94dsa_finish,
950,
96NULL
97};
98
99int FIPS_dsa_check(struct dsa_st *dsa)
100    {
101    if(dsa->meth != &openssl_dsa_meth || dsa->meth->dsa_do_sign != dsa_do_sign
102       || dsa->meth->dsa_sign_setup != dsa_sign_setup
103       || dsa->meth->dsa_mod_exp != dsa_mod_exp
104       || dsa->meth->bn_mod_exp != dsa_bn_mod_exp
105       || dsa->meth->init != dsa_init
106       || dsa->meth->finish != dsa_finish)
107	{
108	FIPSerr(FIPS_F_FIPS_DSA_CHECK,FIPS_R_NON_FIPS_METHOD);
109	return 0;
110	}
111    return 1;
112    }
113
114const DSA_METHOD *DSA_OpenSSL(void)
115{
116	return &openssl_dsa_meth;
117}
118
119static DSA_SIG *dsa_do_sign(const unsigned char *dgst, FIPS_DSA_SIZE_T dlen, DSA *dsa)
120	{
121	BIGNUM *kinv=NULL,*r=NULL,*s=NULL;
122	BIGNUM m;
123	BIGNUM xr;
124	BN_CTX *ctx=NULL;
125	int i,reason=ERR_R_BN_LIB;
126	DSA_SIG *ret=NULL;
127
128	if(FIPS_selftest_failed())
129	    {
130	    FIPSerr(FIPS_F_DSA_DO_SIGN,FIPS_R_FIPS_SELFTEST_FAILED);
131	    return NULL;
132	    }
133
134	BN_init(&m);
135	BN_init(&xr);
136
137	if (!dsa->p || !dsa->q || !dsa->g)
138		{
139		reason=DSA_R_MISSING_PARAMETERS;
140		goto err;
141		}
142
143	s=BN_new();
144	if (s == NULL) goto err;
145
146	i=BN_num_bytes(dsa->q); /* should be 20 */
147	if ((dlen > i) || (dlen > 50))
148		{
149		reason=DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE;
150		goto err;
151		}
152
153	ctx=BN_CTX_new();
154	if (ctx == NULL) goto err;
155
156	if ((dsa->kinv == NULL) || (dsa->r == NULL))
157		{
158		if (!DSA_sign_setup(dsa,ctx,&kinv,&r)) goto err;
159		}
160	else
161		{
162		kinv=dsa->kinv;
163		dsa->kinv=NULL;
164		r=dsa->r;
165		dsa->r=NULL;
166		}
167
168	if (BN_bin2bn(dgst,dlen,&m) == NULL) goto err;
169
170	/* Compute  s = inv(k) (m + xr) mod q */
171	if (!BN_mod_mul(&xr,dsa->priv_key,r,dsa->q,ctx)) goto err;/* s = xr */
172	if (!BN_add(s, &xr, &m)) goto err;		/* s = m + xr */
173	if (BN_cmp(s,dsa->q) > 0)
174		BN_sub(s,s,dsa->q);
175	if (!BN_mod_mul(s,s,kinv,dsa->q,ctx)) goto err;
176
177	ret=DSA_SIG_new();
178	if (ret == NULL) goto err;
179	ret->r = r;
180	ret->s = s;
181
182err:
183	if (!ret)
184		{
185		DSAerr(DSA_F_DSA_DO_SIGN,reason);
186		BN_free(r);
187		BN_free(s);
188		}
189	if (ctx != NULL) BN_CTX_free(ctx);
190	BN_clear_free(&m);
191	BN_clear_free(&xr);
192	if (kinv != NULL) /* dsa->kinv is NULL now if we used it */
193	    BN_clear_free(kinv);
194	return(ret);
195	}
196
197static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
198	{
199	BN_CTX *ctx;
200	BIGNUM k,*kinv=NULL,*r=NULL;
201	int ret=0;
202
203	if (!dsa->p || !dsa->q || !dsa->g)
204		{
205		DSAerr(DSA_F_DSA_SIGN_SETUP,DSA_R_MISSING_PARAMETERS);
206		return 0;
207		}
208
209	BN_init(&k);
210
211	if (ctx_in == NULL)
212		{
213		if ((ctx=BN_CTX_new()) == NULL) goto err;
214		}
215	else
216		ctx=ctx_in;
217
218	if ((r=BN_new()) == NULL) goto err;
219	kinv=NULL;
220
221	/* Get random k */
222	do
223		if (!BN_rand_range(&k, dsa->q)) goto err;
224	while (BN_is_zero(&k));
225
226	if ((dsa->method_mont_p == NULL) && (dsa->flags & DSA_FLAG_CACHE_MONT_P))
227		{
228		if ((dsa->method_mont_p=(char *)BN_MONT_CTX_new()) != NULL)
229			if (!BN_MONT_CTX_set((BN_MONT_CTX *)dsa->method_mont_p,
230				dsa->p,ctx)) goto err;
231		}
232
233	/* Compute r = (g^k mod p) mod q */
234	if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx,
235		(BN_MONT_CTX *)dsa->method_mont_p)) goto err;
236	if (!BN_mod(r,r,dsa->q,ctx)) goto err;
237
238	/* Compute  part of 's = inv(k) (m + xr) mod q' */
239	if ((kinv=BN_mod_inverse(NULL,&k,dsa->q,ctx)) == NULL) goto err;
240
241	if (*kinvp != NULL) BN_clear_free(*kinvp);
242	*kinvp=kinv;
243	kinv=NULL;
244	if (*rp != NULL) BN_clear_free(*rp);
245	*rp=r;
246	ret=1;
247err:
248	if (!ret)
249		{
250		DSAerr(DSA_F_DSA_SIGN_SETUP,ERR_R_BN_LIB);
251		if (kinv != NULL) BN_clear_free(kinv);
252		if (r != NULL) BN_clear_free(r);
253		}
254	if (ctx_in == NULL) BN_CTX_free(ctx);
255	if (kinv != NULL) BN_clear_free(kinv);
256	BN_clear_free(&k);
257	return(ret);
258	}
259
260static int dsa_do_verify(const unsigned char *dgst, FIPS_DSA_SIZE_T dgst_len, DSA_SIG *sig,
261		  DSA *dsa)
262	{
263	BN_CTX *ctx;
264	BIGNUM u1,u2,t1;
265	BN_MONT_CTX *mont=NULL;
266	int ret = -1;
267
268	if (!dsa->p || !dsa->q || !dsa->g)
269		{
270		DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MISSING_PARAMETERS);
271		return -1;
272		}
273
274	if(FIPS_selftest_failed())
275	    {
276	    FIPSerr(FIPS_F_DSA_DO_VERIFY,FIPS_R_FIPS_SELFTEST_FAILED);
277	    return -1;
278	    }
279
280	BN_init(&u1);
281	BN_init(&u2);
282	BN_init(&t1);
283
284	if ((ctx=BN_CTX_new()) == NULL) goto err;
285
286	if (BN_is_zero(sig->r) || sig->r->neg || BN_ucmp(sig->r, dsa->q) >= 0)
287		{
288		ret = 0;
289		goto err;
290		}
291	if (BN_is_zero(sig->s) || sig->s->neg || BN_ucmp(sig->s, dsa->q) >= 0)
292		{
293		ret = 0;
294		goto err;
295		}
296
297	/* Calculate W = inv(S) mod Q
298	 * save W in u2 */
299	if ((BN_mod_inverse(&u2,sig->s,dsa->q,ctx)) == NULL) goto err;
300
301	/* save M in u1 */
302	if (BN_bin2bn(dgst,dgst_len,&u1) == NULL) goto err;
303
304	/* u1 = M * w mod q */
305	if (!BN_mod_mul(&u1,&u1,&u2,dsa->q,ctx)) goto err;
306
307	/* u2 = r * w mod q */
308	if (!BN_mod_mul(&u2,sig->r,&u2,dsa->q,ctx)) goto err;
309
310	if ((dsa->method_mont_p == NULL) && (dsa->flags & DSA_FLAG_CACHE_MONT_P))
311		{
312		if ((dsa->method_mont_p=(char *)BN_MONT_CTX_new()) != NULL)
313			if (!BN_MONT_CTX_set((BN_MONT_CTX *)dsa->method_mont_p,
314				dsa->p,ctx)) goto err;
315		}
316	mont=(BN_MONT_CTX *)dsa->method_mont_p;
317
318#if 0
319	{
320	BIGNUM t2;
321
322	BN_init(&t2);
323	/* v = ( g^u1 * y^u2 mod p ) mod q */
324	/* let t1 = g ^ u1 mod p */
325	if (!BN_mod_exp_mont(&t1,dsa->g,&u1,dsa->p,ctx,mont)) goto err;
326	/* let t2 = y ^ u2 mod p */
327	if (!BN_mod_exp_mont(&t2,dsa->pub_key,&u2,dsa->p,ctx,mont)) goto err;
328	/* let u1 = t1 * t2 mod p */
329	if (!BN_mod_mul(&u1,&t1,&t2,dsa->p,ctx)) goto err_bn;
330	BN_free(&t2);
331	}
332	/* let u1 = u1 mod q */
333	if (!BN_mod(&u1,&u1,dsa->q,ctx)) goto err;
334#else
335	{
336	if (!dsa->meth->dsa_mod_exp(dsa, &t1,dsa->g,&u1,dsa->pub_key,&u2,
337						dsa->p,ctx,mont)) goto err;
338	/* BN_copy(&u1,&t1); */
339	/* let u1 = u1 mod q */
340	if (!BN_mod(&u1,&t1,dsa->q,ctx)) goto err;
341	}
342#endif
343	/* V is now in u1.  If the signature is correct, it will be
344	 * equal to R. */
345	ret=(BN_ucmp(&u1, sig->r) == 0);
346
347	err:
348	if (ret != 1) DSAerr(DSA_F_DSA_DO_VERIFY,ERR_R_BN_LIB);
349	if (ctx != NULL) BN_CTX_free(ctx);
350	BN_free(&u1);
351	BN_free(&u2);
352	BN_free(&t1);
353	return(ret);
354	}
355
356static int dsa_init(DSA *dsa)
357{
358	dsa->flags|=DSA_FLAG_CACHE_MONT_P;
359	return(1);
360}
361
362static int dsa_finish(DSA *dsa)
363{
364	if(dsa->method_mont_p)
365		BN_MONT_CTX_free((BN_MONT_CTX *)dsa->method_mont_p);
366	return(1);
367}
368
369static int dsa_mod_exp(DSA *dsa, BIGNUM *rr, BIGNUM *a1, BIGNUM *p1,
370		BIGNUM *a2, BIGNUM *p2, BIGNUM *m, BN_CTX *ctx,
371		BN_MONT_CTX *in_mont)
372{
373	return BN_mod_exp2_mont(rr, a1, p1, a2, p2, m, ctx, in_mont);
374}
375
376static int dsa_bn_mod_exp(DSA *dsa, BIGNUM *r, BIGNUM *a, const BIGNUM *p,
377				const BIGNUM *m, BN_CTX *ctx,
378				BN_MONT_CTX *m_ctx)
379{
380	return BN_mod_exp_mont(r, a, p, m, ctx, m_ctx);
381}
382
383#else /* ndef OPENSSL_FIPS */
384
385static void *dummy=&dummy;
386
387#endif /* ndef OPENSSL_FIPS */
388