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