1/*
2 * Copyright (c) 2000-2001,2011,2014 Apple Inc. All Rights Reserved.
3 *
4 * The contents of this file constitute Original Code as defined in and are
5 * subject to the Apple Public Source License Version 1.2 (the 'License').
6 * You may not use this file except in compliance with the License. Please obtain
7 * a copy of the License at http://www.apple.com/publicsource and read it before
8 * using this file.
9 *
10 * This Original Code and all software distributed under the License are
11 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
12 * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
13 * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
14 * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
15 * specific language governing rights and limitations under the License.
16 */
17
18
19/* crypto/dsa/dsa_ossl.c */
20/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
21 * All rights reserved.
22 *
23 * This package is an SSL implementation written
24 * by Eric Young (eay@cryptsoft.com).
25 * The implementation was written so as to conform with Netscapes SSL.
26 *
27 * This library is free for commercial and non-commercial use as long as
28 * the following conditions are aheared to.  The following conditions
29 * apply to all code found in this distribution, be it the RC4, RSA,
30 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
31 * included with this distribution is covered by the same copyright terms
32 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
33 *
34 * Copyright remains Eric Young's, and as such any Copyright notices in
35 * the code are not to be removed.
36 * If this package is used in a product, Eric Young should be given attribution
37 * as the author of the parts of the library used.
38 * This can be in the form of a textual message at program startup or
39 * in documentation (online or textual) provided with the package.
40 *
41 * Redistribution and use in source and binary forms, with or without
42 * modification, are permitted provided that the following conditions
43 * are met:
44 * 1. Redistributions of source code must retain the copyright
45 *    notice, this list of conditions and the following disclaimer.
46 * 2. Redistributions in binary form must reproduce the above copyright
47 *    notice, this list of conditions and the following disclaimer in the
48 *    documentation and/or other materials provided with the distribution.
49 * 3. All advertising materials mentioning features or use of this software
50 *    must display the following acknowledgement:
51 *    "This product includes cryptographic software written by
52 *     Eric Young (eay@cryptsoft.com)"
53 *    The word 'cryptographic' can be left out if the rouines from the library
54 *    being used are not cryptographic related :-).
55 * 4. If you include any Windows specific code (or a derivative thereof) from
56 *    the apps directory (application code) you must include an acknowledgement:
57 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
58 *
59 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
60 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
61 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
62 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
63 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
64 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
65 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
66 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
67 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69 * SUCH DAMAGE.
70 *
71 * The licence and distribution terms for any publically available version or
72 * derivative of this code cannot be changed.  i.e. this code cannot simply be
73 * copied and put under another distribution licence
74 * [including the GNU Public Licence.]
75 */
76
77/* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */
78
79#include <stdio.h>
80#include "cryptlib.h"
81#include <openssl/bn.h>
82#include <openssl/dsa.h>
83#include <openssl/rand.h>
84#include <openssl/asn1.h>
85
86static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
87static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
88static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
89		  DSA *dsa);
90static int dsa_init(DSA *dsa);
91static int dsa_finish(DSA *dsa);
92static int dsa_mod_exp(DSA *dsa, BIGNUM *rr, BIGNUM *a1, BIGNUM *p1,
93		BIGNUM *a2, BIGNUM *p2, BIGNUM *m, BN_CTX *ctx,
94		BN_MONT_CTX *in_mont);
95static int dsa_bn_mod_exp(DSA *dsa, BIGNUM *r, BIGNUM *a, const BIGNUM *p,
96				const BIGNUM *m, BN_CTX *ctx,
97				BN_MONT_CTX *m_ctx);
98
99static const DSA_METHOD openssl_dsa_meth = {
100"OpenSSL DSA method",
101dsa_do_sign,
102dsa_sign_setup,
103dsa_do_verify,
104dsa_mod_exp,
105dsa_bn_mod_exp,
106dsa_init,
107dsa_finish,
1080,
109NULL
110};
111
112const DSA_METHOD *DSA_OpenSSL(void)
113{
114	return &openssl_dsa_meth;
115}
116
117static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
118	{
119	BIGNUM *kinv=NULL,*r=NULL,*s=NULL;
120	BIGNUM m;
121	BIGNUM xr;
122	BN_CTX *ctx=NULL;
123	int i,reason=ERR_R_BN_LIB;
124	DSA_SIG *ret=NULL;
125
126	BN_init(&m);
127	BN_init(&xr);
128	s=BN_new();
129	if (s == NULL) goto err;
130
131	i=BN_num_bytes(dsa->q); /* should be 20 */
132	if ((dlen > i) || (dlen > 50))
133		{
134		reason=DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE;
135		goto err;
136		}
137
138	ctx=BN_CTX_new();
139	if (ctx == NULL) goto err;
140
141	if ((dsa->kinv == NULL) || (dsa->r == NULL))
142		{
143		if (!DSA_sign_setup(dsa,ctx,&kinv,&r)) goto err;
144		}
145	else
146		{
147		kinv=dsa->kinv;
148		dsa->kinv=NULL;
149		r=dsa->r;
150		dsa->r=NULL;
151		}
152
153	if (BN_bin2bn(dgst,dlen,&m) == NULL) goto err;
154
155	/* Compute  s = inv(k) (m + xr) mod q */
156	if (!BN_mod_mul(&xr,dsa->priv_key,r,dsa->q,ctx)) goto err;/* s = xr */
157	if (!BN_add(s, &xr, &m)) goto err;		/* s = m + xr */
158	if (BN_cmp(s,dsa->q) > 0)
159		BN_sub(s,s,dsa->q);
160	if (!BN_mod_mul(s,s,kinv,dsa->q,ctx)) goto err;
161
162	ret=DSA_SIG_new();
163	if (ret == NULL) goto err;
164	ret->r = r;
165	ret->s = s;
166
167err:
168	if (!ret)
169		{
170		DSAerr(DSA_F_DSA_DO_SIGN,reason);
171		BN_free(r);
172		BN_free(s);
173		}
174	if (ctx != NULL) BN_CTX_free(ctx);
175	BN_clear_free(&m);
176	BN_clear_free(&xr);
177	if (kinv != NULL) /* dsa->kinv is NULL now if we used it */
178	    BN_clear_free(kinv);
179	return(ret);
180	}
181
182static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
183	{
184	BN_CTX *ctx;
185	BIGNUM k,*kinv=NULL,*r=NULL;
186	int ret=0;
187
188	if (ctx_in == NULL)
189		{
190		if ((ctx=BN_CTX_new()) == NULL) goto err;
191		}
192	else
193		ctx=ctx_in;
194
195	BN_init(&k);
196	if ((r=BN_new()) == NULL) goto err;
197	kinv=NULL;
198
199	/* Get random k */
200	for (;;)
201		{
202		if (!BN_rand(&k, BN_num_bits(dsa->q), 1, 0)) goto err;
203		if (BN_cmp(&k,dsa->q) >= 0)
204			BN_sub(&k,&k,dsa->q);
205		if (!BN_is_zero(&k)) break;
206		}
207
208	if ((dsa->method_mont_p == NULL) && (dsa->flags & DSA_FLAG_CACHE_MONT_P))
209		{
210		if ((dsa->method_mont_p=(char *)BN_MONT_CTX_new()) != NULL)
211			if (!BN_MONT_CTX_set((BN_MONT_CTX *)dsa->method_mont_p,
212				dsa->p,ctx)) goto err;
213		}
214
215	/* Compute r = (g^k mod p) mod q */
216	if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx,
217		(BN_MONT_CTX *)dsa->method_mont_p)) goto err;
218	if (!BN_mod(r,r,dsa->q,ctx)) goto err;
219
220	/* Compute  part of 's = inv(k) (m + xr) mod q' */
221	if ((kinv=BN_mod_inverse(NULL,&k,dsa->q,ctx)) == NULL) goto err;
222
223	if (*kinvp != NULL) BN_clear_free(*kinvp);
224	*kinvp=kinv;
225	kinv=NULL;
226	if (*rp != NULL) BN_clear_free(*rp);
227	*rp=r;
228	ret=1;
229err:
230	if (!ret)
231		{
232		DSAerr(DSA_F_DSA_SIGN_SETUP,ERR_R_BN_LIB);
233		if (kinv != NULL) BN_clear_free(kinv);
234		if (r != NULL) BN_clear_free(r);
235		}
236	if (ctx_in == NULL) BN_CTX_free(ctx);
237	if (kinv != NULL) BN_clear_free(kinv);
238	BN_clear_free(&k);
239	return(ret);
240	}
241
242static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
243		  DSA *dsa)
244	{
245	BN_CTX *ctx;
246	BIGNUM u1,u2,t1;
247	BN_MONT_CTX *mont=NULL;
248	int ret = -1;
249
250	if ((ctx=BN_CTX_new()) == NULL) goto err;
251	BN_init(&u1);
252	BN_init(&u2);
253	BN_init(&t1);
254
255	/* Calculate W = inv(S) mod Q
256	 * save W in u2 */
257	if ((BN_mod_inverse(&u2,sig->s,dsa->q,ctx)) == NULL) goto err;
258
259	/* save M in u1 */
260	if (BN_bin2bn(dgst,dgst_len,&u1) == NULL) goto err;
261
262	/* u1 = M * w mod q */
263	if (!BN_mod_mul(&u1,&u1,&u2,dsa->q,ctx)) goto err;
264
265	/* u2 = r * w mod q */
266	if (!BN_mod_mul(&u2,sig->r,&u2,dsa->q,ctx)) goto err;
267
268	if ((dsa->method_mont_p == NULL) && (dsa->flags & DSA_FLAG_CACHE_MONT_P))
269		{
270		if ((dsa->method_mont_p=(char *)BN_MONT_CTX_new()) != NULL)
271			if (!BN_MONT_CTX_set((BN_MONT_CTX *)dsa->method_mont_p,
272				dsa->p,ctx)) goto err;
273		}
274	mont=(BN_MONT_CTX *)dsa->method_mont_p;
275
276#if 0
277	{
278	BIGNUM t2;
279
280	BN_init(&t2);
281	/* v = ( g^u1 * y^u2 mod p ) mod q */
282	/* let t1 = g ^ u1 mod p */
283	if (!BN_mod_exp_mont(&t1,dsa->g,&u1,dsa->p,ctx,mont)) goto err;
284	/* let t2 = y ^ u2 mod p */
285	if (!BN_mod_exp_mont(&t2,dsa->pub_key,&u2,dsa->p,ctx,mont)) goto err;
286	/* let u1 = t1 * t2 mod p */
287	if (!BN_mod_mul(&u1,&t1,&t2,dsa->p,ctx)) goto err_bn;
288	BN_free(&t2);
289	}
290	/* let u1 = u1 mod q */
291	if (!BN_mod(&u1,&u1,dsa->q,ctx)) goto err;
292#else
293	{
294	if (!dsa->meth->dsa_mod_exp(dsa, &t1,dsa->g,&u1,dsa->pub_key,&u2,
295						dsa->p,ctx,mont)) goto err;
296	/* BN_copy(&u1,&t1); */
297	/* let u1 = u1 mod q */
298	if (!BN_mod(&u1,&t1,dsa->q,ctx)) goto err;
299	}
300#endif
301	/* V is now in u1.  If the signature is correct, it will be
302	 * equal to R. */
303	ret=(BN_ucmp(&u1, sig->r) == 0);
304
305	err:
306	if (ret != 1) DSAerr(DSA_F_DSA_DO_VERIFY,ERR_R_BN_LIB);
307	if (ctx != NULL) BN_CTX_free(ctx);
308	BN_free(&u1);
309	BN_free(&u2);
310	BN_free(&t1);
311	return(ret);
312	}
313
314static int dsa_init(DSA *dsa)
315{
316	dsa->flags|=DSA_FLAG_CACHE_MONT_P;
317	return(1);
318}
319
320static int dsa_finish(DSA *dsa)
321{
322	if(dsa->method_mont_p)
323		BN_MONT_CTX_free((BN_MONT_CTX *)dsa->method_mont_p);
324	return(1);
325}
326
327static int dsa_mod_exp(DSA *dsa, BIGNUM *rr, BIGNUM *a1, BIGNUM *p1,
328		BIGNUM *a2, BIGNUM *p2, BIGNUM *m, BN_CTX *ctx,
329		BN_MONT_CTX *in_mont)
330{
331	return BN_mod_exp2_mont(rr, a1, p1, a2, p2, m, ctx, in_mont);
332}
333
334static int dsa_bn_mod_exp(DSA *dsa, BIGNUM *r, BIGNUM *a, const BIGNUM *p,
335				const BIGNUM *m, BN_CTX *ctx,
336				BN_MONT_CTX *m_ctx)
337{
338	return BN_mod_exp_mont(r, a, p, m, ctx, m_ctx);
339}
340