159191Skris/* crypto/dsa/dsa_ossl.c */ 259191Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 359191Skris * All rights reserved. 459191Skris * 559191Skris * This package is an SSL implementation written 659191Skris * by Eric Young (eay@cryptsoft.com). 759191Skris * The implementation was written so as to conform with Netscapes SSL. 8296341Sdelphij * 959191Skris * This library is free for commercial and non-commercial use as long as 1059191Skris * the following conditions are aheared to. The following conditions 1159191Skris * apply to all code found in this distribution, be it the RC4, RSA, 1259191Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1359191Skris * included with this distribution is covered by the same copyright terms 1459191Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15296341Sdelphij * 1659191Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1759191Skris * the code are not to be removed. 1859191Skris * If this package is used in a product, Eric Young should be given attribution 1959191Skris * as the author of the parts of the library used. 2059191Skris * This can be in the form of a textual message at program startup or 2159191Skris * in documentation (online or textual) provided with the package. 22296341Sdelphij * 2359191Skris * Redistribution and use in source and binary forms, with or without 2459191Skris * modification, are permitted provided that the following conditions 2559191Skris * are met: 2659191Skris * 1. Redistributions of source code must retain the copyright 2759191Skris * notice, this list of conditions and the following disclaimer. 2859191Skris * 2. Redistributions in binary form must reproduce the above copyright 2959191Skris * notice, this list of conditions and the following disclaimer in the 3059191Skris * documentation and/or other materials provided with the distribution. 3159191Skris * 3. All advertising materials mentioning features or use of this software 3259191Skris * must display the following acknowledgement: 3359191Skris * "This product includes cryptographic software written by 3459191Skris * Eric Young (eay@cryptsoft.com)" 3559191Skris * The word 'cryptographic' can be left out if the rouines from the library 3659191Skris * being used are not cryptographic related :-). 37296341Sdelphij * 4. If you include any Windows specific code (or a derivative thereof) from 3859191Skris * the apps directory (application code) you must include an acknowledgement: 3959191Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40296341Sdelphij * 4159191Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4259191Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4359191Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4459191Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4559191Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4659191Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4759191Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4859191Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4959191Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5059191Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5159191Skris * SUCH DAMAGE. 52296341Sdelphij * 5359191Skris * The licence and distribution terms for any publically available version or 5459191Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5559191Skris * copied and put under another distribution licence 5659191Skris * [including the GNU Public Licence.] 5759191Skris */ 5859191Skris 5959191Skris/* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */ 6059191Skris 6159191Skris#include <stdio.h> 6259191Skris#include "cryptlib.h" 6359191Skris#include <openssl/bn.h> 64238405Sjkim#include <openssl/sha.h> 6559191Skris#include <openssl/dsa.h> 6659191Skris#include <openssl/rand.h> 6759191Skris#include <openssl/asn1.h> 6859191Skris 6959191Skrisstatic DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa); 70296341Sdelphijstatic int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, 71296341Sdelphij BIGNUM **rp); 72296341Sdelphijstatic int dsa_do_verify(const unsigned char *dgst, int dgst_len, 73296341Sdelphij DSA_SIG *sig, DSA *dsa); 7459191Skrisstatic int dsa_init(DSA *dsa); 7559191Skrisstatic int dsa_finish(DSA *dsa); 7659191Skris 7759191Skrisstatic DSA_METHOD openssl_dsa_meth = { 78296341Sdelphij "OpenSSL DSA method", 79296341Sdelphij dsa_do_sign, 80296341Sdelphij dsa_sign_setup, 81296341Sdelphij dsa_do_verify, 82296341Sdelphij NULL, /* dsa_mod_exp, */ 83296341Sdelphij NULL, /* dsa_bn_mod_exp, */ 84296341Sdelphij dsa_init, 85296341Sdelphij dsa_finish, 86296341Sdelphij 0, 87296341Sdelphij NULL, 88296341Sdelphij NULL, 89296341Sdelphij NULL 9059191Skris}; 9159191Skris 92296341Sdelphij/*- 93296341Sdelphij * These macro wrappers replace attempts to use the dsa_mod_exp() and 94160814Ssimon * bn_mod_exp() handlers in the DSA_METHOD structure. We avoid the problem of 95160814Ssimon * having a the macro work as an expression by bundling an "err_instr". So; 96296341Sdelphij * 97160814Ssimon * if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx, 98160814Ssimon * dsa->method_mont_p)) goto err; 99160814Ssimon * 100160814Ssimon * can be replaced by; 101160814Ssimon * 102160814Ssimon * DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, &k, dsa->p, ctx, 103160814Ssimon * dsa->method_mont_p); 104160814Ssimon */ 105160814Ssimon 106160814Ssimon#define DSA_MOD_EXP(err_instr,dsa,rr,a1,p1,a2,p2,m,ctx,in_mont) \ 107296341Sdelphij do { \ 108296341Sdelphij int _tmp_res53; \ 109296341Sdelphij if ((dsa)->meth->dsa_mod_exp) \ 110296341Sdelphij _tmp_res53 = (dsa)->meth->dsa_mod_exp((dsa), (rr), (a1), (p1), \ 111296341Sdelphij (a2), (p2), (m), (ctx), (in_mont)); \ 112296341Sdelphij else \ 113296341Sdelphij _tmp_res53 = BN_mod_exp2_mont((rr), (a1), (p1), (a2), (p2), \ 114296341Sdelphij (m), (ctx), (in_mont)); \ 115296341Sdelphij if (!_tmp_res53) err_instr; \ 116296341Sdelphij } while(0) 117160814Ssimon#define DSA_BN_MOD_EXP(err_instr,dsa,r,a,p,m,ctx,m_ctx) \ 118296341Sdelphij do { \ 119296341Sdelphij int _tmp_res53; \ 120296341Sdelphij if ((dsa)->meth->bn_mod_exp) \ 121296341Sdelphij _tmp_res53 = (dsa)->meth->bn_mod_exp((dsa), (r), (a), (p), \ 122296341Sdelphij (m), (ctx), (m_ctx)); \ 123296341Sdelphij else \ 124296341Sdelphij _tmp_res53 = BN_mod_exp_mont((r), (a), (p), (m), (ctx), (m_ctx)); \ 125296341Sdelphij if (!_tmp_res53) err_instr; \ 126296341Sdelphij } while(0) 127160814Ssimon 128109998Smarkmconst DSA_METHOD *DSA_OpenSSL(void) 12959191Skris{ 130296341Sdelphij return &openssl_dsa_meth; 13159191Skris} 13259191Skris 13359191Skrisstatic DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) 134296341Sdelphij{ 135296341Sdelphij BIGNUM *kinv = NULL, *r = NULL, *s = NULL; 136296341Sdelphij BIGNUM m; 137296341Sdelphij BIGNUM xr; 138296341Sdelphij BN_CTX *ctx = NULL; 139296341Sdelphij int reason = ERR_R_BN_LIB; 140296341Sdelphij DSA_SIG *ret = NULL; 141296341Sdelphij int noredo = 0; 14259191Skris 143296341Sdelphij BN_init(&m); 144296341Sdelphij BN_init(&xr); 145111147Snectar 146296341Sdelphij if (!dsa->p || !dsa->q || !dsa->g) { 147296341Sdelphij reason = DSA_R_MISSING_PARAMETERS; 148296341Sdelphij goto err; 149296341Sdelphij } 150111147Snectar 151296341Sdelphij s = BN_new(); 152296341Sdelphij if (s == NULL) 153296341Sdelphij goto err; 154296341Sdelphij ctx = BN_CTX_new(); 155296341Sdelphij if (ctx == NULL) 156296341Sdelphij goto err; 157296341Sdelphij redo: 158296341Sdelphij if ((dsa->kinv == NULL) || (dsa->r == NULL)) { 159296341Sdelphij if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) 160296341Sdelphij goto err; 161296341Sdelphij } else { 162296341Sdelphij kinv = dsa->kinv; 163296341Sdelphij dsa->kinv = NULL; 164296341Sdelphij r = dsa->r; 165296341Sdelphij dsa->r = NULL; 166296341Sdelphij noredo = 1; 167296341Sdelphij } 16859191Skris 169296341Sdelphij if (dlen > BN_num_bytes(dsa->q)) 170296341Sdelphij /* 171296341Sdelphij * if the digest length is greater than the size of q use the 172296341Sdelphij * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3, 173296341Sdelphij * 4.2 174296341Sdelphij */ 175296341Sdelphij dlen = BN_num_bytes(dsa->q); 176296341Sdelphij if (BN_bin2bn(dgst, dlen, &m) == NULL) 177296341Sdelphij goto err; 17859191Skris 179296341Sdelphij /* Compute s = inv(k) (m + xr) mod q */ 180296341Sdelphij if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) 181296341Sdelphij goto err; /* s = xr */ 182296341Sdelphij if (!BN_add(s, &xr, &m)) 183296341Sdelphij goto err; /* s = m + xr */ 184296341Sdelphij if (BN_cmp(s, dsa->q) > 0) 185296341Sdelphij if (!BN_sub(s, s, dsa->q)) 186296341Sdelphij goto err; 187296341Sdelphij if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) 188296341Sdelphij goto err; 18959191Skris 190296341Sdelphij ret = DSA_SIG_new(); 191296341Sdelphij if (ret == NULL) 192296341Sdelphij goto err; 193296341Sdelphij /* 194296341Sdelphij * Redo if r or s is zero as required by FIPS 186-3: this is very 195296341Sdelphij * unlikely. 196296341Sdelphij */ 197296341Sdelphij if (BN_is_zero(r) || BN_is_zero(s)) { 198296341Sdelphij if (noredo) { 199296341Sdelphij reason = DSA_R_NEED_NEW_SETUP_VALUES; 200296341Sdelphij goto err; 201296341Sdelphij } 202296341Sdelphij goto redo; 203296341Sdelphij } 204296341Sdelphij ret->r = r; 205296341Sdelphij ret->s = s; 20659191Skris 207296341Sdelphij err: 208296341Sdelphij if (!ret) { 209296341Sdelphij DSAerr(DSA_F_DSA_DO_SIGN, reason); 210296341Sdelphij BN_free(r); 211296341Sdelphij BN_free(s); 212296341Sdelphij } 213296341Sdelphij if (ctx != NULL) 214296341Sdelphij BN_CTX_free(ctx); 215296341Sdelphij BN_clear_free(&m); 216296341Sdelphij BN_clear_free(&xr); 217296341Sdelphij if (kinv != NULL) /* dsa->kinv is NULL now if we used it */ 218296341Sdelphij BN_clear_free(kinv); 219296341Sdelphij return (ret); 220296341Sdelphij} 22159191Skris 222296341Sdelphijstatic int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, 223296341Sdelphij BIGNUM **rp) 224296341Sdelphij{ 225296341Sdelphij BN_CTX *ctx; 226296341Sdelphij BIGNUM k, kq, *K, *kinv = NULL, *r = NULL; 227296341Sdelphij int ret = 0; 228111147Snectar 229296341Sdelphij if (!dsa->p || !dsa->q || !dsa->g) { 230296341Sdelphij DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS); 231296341Sdelphij return 0; 232296341Sdelphij } 233111147Snectar 234296341Sdelphij BN_init(&k); 235296341Sdelphij BN_init(&kq); 23659191Skris 237296341Sdelphij if (ctx_in == NULL) { 238296341Sdelphij if ((ctx = BN_CTX_new()) == NULL) 239296341Sdelphij goto err; 240296341Sdelphij } else 241296341Sdelphij ctx = ctx_in; 24259191Skris 243296341Sdelphij if ((r = BN_new()) == NULL) 244296341Sdelphij goto err; 24559191Skris 246296341Sdelphij /* Get random k */ 247296341Sdelphij do 248296341Sdelphij if (!BN_rand_range(&k, dsa->q)) 249296341Sdelphij goto err; 250306230Sdelphij while (BN_is_zero(&k)); 251306230Sdelphij 252296341Sdelphij if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) { 253296341Sdelphij BN_set_flags(&k, BN_FLG_CONSTTIME); 254296341Sdelphij } 25559191Skris 256306230Sdelphij 257296341Sdelphij if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 258296341Sdelphij if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, 259296341Sdelphij CRYPTO_LOCK_DSA, dsa->p, ctx)) 260296341Sdelphij goto err; 261296341Sdelphij } 262160814Ssimon 263296341Sdelphij /* Compute r = (g^k mod p) mod q */ 264160814Ssimon 265296341Sdelphij if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) { 266296341Sdelphij if (!BN_copy(&kq, &k)) 267296341Sdelphij goto err; 268160814Ssimon 269306230Sdelphij BN_set_flags(&kq, BN_FLG_CONSTTIME); 270306230Sdelphij 271296341Sdelphij /* 272296341Sdelphij * We do not want timing information to leak the length of k, so we 273296341Sdelphij * compute g^k using an equivalent exponent of fixed length. (This 274296341Sdelphij * is a kludge that we need because the BN_mod_exp_mont() does not 275296341Sdelphij * let us specify the desired timing behaviour.) 276296341Sdelphij */ 277160814Ssimon 278296341Sdelphij if (!BN_add(&kq, &kq, dsa->q)) 279296341Sdelphij goto err; 280296341Sdelphij if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) { 281296341Sdelphij if (!BN_add(&kq, &kq, dsa->q)) 282296341Sdelphij goto err; 283296341Sdelphij } 28459191Skris 285296341Sdelphij K = &kq; 286296341Sdelphij } else { 287296341Sdelphij K = &k; 288296341Sdelphij } 289306230Sdelphij 290296341Sdelphij DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, K, dsa->p, ctx, 291296341Sdelphij dsa->method_mont_p); 292296341Sdelphij if (!BN_mod(r, r, dsa->q, ctx)) 293296341Sdelphij goto err; 29459191Skris 295296341Sdelphij /* Compute part of 's = inv(k) (m + xr) mod q' */ 296296341Sdelphij if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL) 297296341Sdelphij goto err; 29859191Skris 299296341Sdelphij if (*kinvp != NULL) 300296341Sdelphij BN_clear_free(*kinvp); 301296341Sdelphij *kinvp = kinv; 302296341Sdelphij kinv = NULL; 303296341Sdelphij if (*rp != NULL) 304296341Sdelphij BN_clear_free(*rp); 305296341Sdelphij *rp = r; 306296341Sdelphij ret = 1; 307296341Sdelphij err: 308296341Sdelphij if (!ret) { 309296341Sdelphij DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB); 310296341Sdelphij if (r != NULL) 311296341Sdelphij BN_clear_free(r); 312296341Sdelphij } 313296341Sdelphij if (ctx_in == NULL) 314296341Sdelphij BN_CTX_free(ctx); 315296341Sdelphij BN_clear_free(&k); 316296341Sdelphij BN_clear_free(&kq); 317296341Sdelphij return (ret); 318296341Sdelphij} 31959191Skris 320296341Sdelphijstatic int dsa_do_verify(const unsigned char *dgst, int dgst_len, 321296341Sdelphij DSA_SIG *sig, DSA *dsa) 322296341Sdelphij{ 323296341Sdelphij BN_CTX *ctx; 324296341Sdelphij BIGNUM u1, u2, t1; 325296341Sdelphij BN_MONT_CTX *mont = NULL; 326296341Sdelphij int ret = -1, i; 327296341Sdelphij if (!dsa->p || !dsa->q || !dsa->g) { 328296341Sdelphij DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS); 329296341Sdelphij return -1; 330296341Sdelphij } 331162911Ssimon 332296341Sdelphij i = BN_num_bits(dsa->q); 333296341Sdelphij /* fips 186-3 allows only different sizes for q */ 334296341Sdelphij if (i != 160 && i != 224 && i != 256) { 335296341Sdelphij DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE); 336296341Sdelphij return -1; 337296341Sdelphij } 33859191Skris 339296341Sdelphij if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) { 340296341Sdelphij DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE); 341296341Sdelphij return -1; 342296341Sdelphij } 343296341Sdelphij BN_init(&u1); 344296341Sdelphij BN_init(&u2); 345296341Sdelphij BN_init(&t1); 346111147Snectar 347296341Sdelphij if ((ctx = BN_CTX_new()) == NULL) 348296341Sdelphij goto err; 34979998Skris 350296341Sdelphij if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 351296341Sdelphij BN_ucmp(sig->r, dsa->q) >= 0) { 352296341Sdelphij ret = 0; 353296341Sdelphij goto err; 354296341Sdelphij } 355296341Sdelphij if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || 356296341Sdelphij BN_ucmp(sig->s, dsa->q) >= 0) { 357296341Sdelphij ret = 0; 358296341Sdelphij goto err; 359296341Sdelphij } 36059191Skris 361296341Sdelphij /* 362296341Sdelphij * Calculate W = inv(S) mod Q save W in u2 363296341Sdelphij */ 364296341Sdelphij if ((BN_mod_inverse(&u2, sig->s, dsa->q, ctx)) == NULL) 365296341Sdelphij goto err; 36659191Skris 367296341Sdelphij /* save M in u1 */ 368296341Sdelphij if (dgst_len > (i >> 3)) 369296341Sdelphij /* 370296341Sdelphij * if the digest length is greater than the size of q use the 371296341Sdelphij * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3, 372296341Sdelphij * 4.2 373296341Sdelphij */ 374296341Sdelphij dgst_len = (i >> 3); 375296341Sdelphij if (BN_bin2bn(dgst, dgst_len, &u1) == NULL) 376296341Sdelphij goto err; 37759191Skris 378296341Sdelphij /* u1 = M * w mod q */ 379296341Sdelphij if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) 380296341Sdelphij goto err; 38159191Skris 382296341Sdelphij /* u2 = r * w mod q */ 383296341Sdelphij if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) 384296341Sdelphij goto err; 385160814Ssimon 386296341Sdelphij if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 387296341Sdelphij mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, 388296341Sdelphij CRYPTO_LOCK_DSA, dsa->p, ctx); 389296341Sdelphij if (!mont) 390296341Sdelphij goto err; 391296341Sdelphij } 39259191Skris 393296341Sdelphij DSA_MOD_EXP(goto err, dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, 394296341Sdelphij ctx, mont); 395296341Sdelphij /* BN_copy(&u1,&t1); */ 396296341Sdelphij /* let u1 = u1 mod q */ 397296341Sdelphij if (!BN_mod(&u1, &t1, dsa->q, ctx)) 398296341Sdelphij goto err; 39959191Skris 400296341Sdelphij /* 401296341Sdelphij * V is now in u1. If the signature is correct, it will be equal to R. 402296341Sdelphij */ 403296341Sdelphij ret = (BN_ucmp(&u1, sig->r) == 0); 404160814Ssimon 405296341Sdelphij err: 406296341Sdelphij /* 407296341Sdelphij * XXX: surely this is wrong - if ret is 0, it just didn't verify; there 408296341Sdelphij * is no error in BN. Test should be ret == -1 (Ben) 409296341Sdelphij */ 410296341Sdelphij if (ret != 1) 411296341Sdelphij DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB); 412296341Sdelphij if (ctx != NULL) 413296341Sdelphij BN_CTX_free(ctx); 414296341Sdelphij BN_free(&u1); 415296341Sdelphij BN_free(&u2); 416296341Sdelphij BN_free(&t1); 417296341Sdelphij return (ret); 418296341Sdelphij} 41959191Skris 42059191Skrisstatic int dsa_init(DSA *dsa) 42159191Skris{ 422296341Sdelphij dsa->flags |= DSA_FLAG_CACHE_MONT_P; 423296341Sdelphij return (1); 42459191Skris} 42559191Skris 42659191Skrisstatic int dsa_finish(DSA *dsa) 42759191Skris{ 428296341Sdelphij if (dsa->method_mont_p) 429296341Sdelphij BN_MONT_CTX_free(dsa->method_mont_p); 430296341Sdelphij return (1); 43159191Skris} 432