2 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the OpenSSL license (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
11 #include "internal/cryptlib.h"
12 #include <openssl/bn.h>
13 #include <openssl/sha.h>
15 #include <openssl/asn1.h>
17 static DSA_SIG
*dsa_do_sign(const unsigned char *dgst
, int dlen
, DSA
*dsa
);
18 static int dsa_sign_setup_no_digest(DSA
*dsa
, BN_CTX
*ctx_in
, BIGNUM
**kinvp
,
20 static int dsa_sign_setup(DSA
*dsa
, BN_CTX
*ctx_in
, BIGNUM
**kinvp
,
21 BIGNUM
**rp
, const unsigned char *dgst
, int dlen
);
22 static int dsa_do_verify(const unsigned char *dgst
, int dgst_len
,
23 DSA_SIG
*sig
, DSA
*dsa
);
24 static int dsa_init(DSA
*dsa
);
25 static int dsa_finish(DSA
*dsa
);
27 static DSA_METHOD openssl_dsa_meth
= {
30 dsa_sign_setup_no_digest
,
32 NULL
, /* dsa_mod_exp, */
33 NULL
, /* dsa_bn_mod_exp, */
42 static const DSA_METHOD
*default_DSA_method
= &openssl_dsa_meth
;
44 void DSA_set_default_method(const DSA_METHOD
*meth
)
46 default_DSA_method
= meth
;
49 const DSA_METHOD
*DSA_get_default_method(void)
51 return default_DSA_method
;
54 const DSA_METHOD
*DSA_OpenSSL(void)
56 return &openssl_dsa_meth
;
59 static DSA_SIG
*dsa_do_sign(const unsigned char *dgst
, int dlen
, DSA
*dsa
)
62 BIGNUM
*m
, *blind
, *blindm
, *tmp
;
64 int reason
= ERR_R_BN_LIB
;
68 if (dsa
->p
== NULL
|| dsa
->q
== NULL
|| dsa
->g
== NULL
) {
69 reason
= DSA_R_MISSING_PARAMETERS
;
78 if (ret
->r
== NULL
|| ret
->s
== NULL
)
85 blind
= BN_CTX_get(ctx
);
86 blindm
= BN_CTX_get(ctx
);
87 tmp
= BN_CTX_get(ctx
);
92 if (!dsa_sign_setup(dsa
, ctx
, &kinv
, &ret
->r
, dgst
, dlen
))
95 if (dlen
> BN_num_bytes(dsa
->q
))
97 * if the digest length is greater than the size of q use the
98 * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
101 dlen
= BN_num_bytes(dsa
->q
);
102 if (BN_bin2bn(dgst
, dlen
, m
) == NULL
)
106 * The normal signature calculation is:
108 * s := k^-1 * (m + r * priv_key) mod q
110 * We will blind this to protect against side channel attacks
112 * s := blind^-1 * k^-1 * (blind * m + blind * r * priv_key) mod q
115 /* Generate a blinding value */
117 if (!BN_priv_rand(blind
, BN_num_bits(dsa
->q
) - 1,
118 BN_RAND_TOP_ANY
, BN_RAND_BOTTOM_ANY
))
120 } while (BN_is_zero(blind
));
121 BN_set_flags(blind
, BN_FLG_CONSTTIME
);
122 BN_set_flags(blindm
, BN_FLG_CONSTTIME
);
123 BN_set_flags(tmp
, BN_FLG_CONSTTIME
);
125 /* tmp := blind * priv_key * r mod q */
126 if (!BN_mod_mul(tmp
, blind
, dsa
->priv_key
, dsa
->q
, ctx
))
128 if (!BN_mod_mul(tmp
, tmp
, ret
->r
, dsa
->q
, ctx
))
131 /* blindm := blind * m mod q */
132 if (!BN_mod_mul(blindm
, blind
, m
, dsa
->q
, ctx
))
135 /* s : = (blind * priv_key * r) + (blind * m) mod q */
136 if (!BN_mod_add_quick(ret
->s
, tmp
, blindm
, dsa
->q
))
139 /* s := s * k^-1 mod q */
140 if (!BN_mod_mul(ret
->s
, ret
->s
, kinv
, dsa
->q
, ctx
))
143 /* s:= s * blind^-1 mod q */
144 if (BN_mod_inverse(blind
, blind
, dsa
->q
, ctx
) == NULL
)
146 if (!BN_mod_mul(ret
->s
, ret
->s
, blind
, dsa
->q
, ctx
))
150 * Redo if r or s is zero as required by FIPS 186-3: this is very
153 if (BN_is_zero(ret
->r
) || BN_is_zero(ret
->s
))
160 DSAerr(DSA_F_DSA_DO_SIGN
, reason
);
169 static int dsa_sign_setup_no_digest(DSA
*dsa
, BN_CTX
*ctx_in
,
170 BIGNUM
**kinvp
, BIGNUM
**rp
)
172 return dsa_sign_setup(dsa
, ctx_in
, kinvp
, rp
, NULL
, 0);
175 static int dsa_sign_setup(DSA
*dsa
, BN_CTX
*ctx_in
,
176 BIGNUM
**kinvp
, BIGNUM
**rp
,
177 const unsigned char *dgst
, int dlen
)
180 BIGNUM
*k
, *kinv
= NULL
, *r
= *rp
;
185 if (!dsa
->p
|| !dsa
->q
|| !dsa
->g
) {
186 DSAerr(DSA_F_DSA_SIGN_SETUP
, DSA_R_MISSING_PARAMETERS
);
193 if (k
== NULL
|| l
== NULL
|| m
== NULL
)
196 if (ctx_in
== NULL
) {
197 if ((ctx
= BN_CTX_new()) == NULL
)
202 /* Preallocate space */
203 q_bits
= BN_num_bits(dsa
->q
);
204 if (!BN_set_bit(k
, q_bits
)
205 || !BN_set_bit(l
, q_bits
)
206 || !BN_set_bit(m
, q_bits
))
213 * We calculate k from SHA512(private_key + H(message) + random).
214 * This protects the private key from a weak PRNG.
216 if (!BN_generate_dsa_nonce(k
, dsa
->q
, dsa
->priv_key
, dgst
,
219 } else if (!BN_priv_rand_range(k
, dsa
->q
))
221 } while (BN_is_zero(k
));
223 BN_set_flags(k
, BN_FLG_CONSTTIME
);
225 if (dsa
->flags
& DSA_FLAG_CACHE_MONT_P
) {
226 if (!BN_MONT_CTX_set_locked(&dsa
->method_mont_p
,
227 dsa
->lock
, dsa
->p
, ctx
))
231 /* Compute r = (g^k mod p) mod q */
234 * We do not want timing information to leak the length of k, so we
235 * compute G^k using an equivalent scalar of fixed bit-length.
237 * We unconditionally perform both of these additions to prevent a
238 * small timing information leakage. We then choose the sum that is
239 * one bit longer than the modulus.
241 * TODO: revisit the BN_copy aiming for a memory access agnostic
244 if (!BN_add(l
, k
, dsa
->q
)
245 || !BN_add(m
, l
, dsa
->q
)
246 || !BN_copy(k
, BN_num_bits(l
) > q_bits
? l
: m
))
249 if ((dsa
)->meth
->bn_mod_exp
!= NULL
) {
250 if (!dsa
->meth
->bn_mod_exp(dsa
, r
, dsa
->g
, k
, dsa
->p
, ctx
,
254 if (!BN_mod_exp_mont(r
, dsa
->g
, k
, dsa
->p
, ctx
, dsa
->method_mont_p
))
258 if (!BN_mod(r
, r
, dsa
->q
, ctx
))
261 /* Compute part of 's = inv(k) (m + xr) mod q' */
262 if ((kinv
= BN_mod_inverse(NULL
, k
, dsa
->q
, ctx
)) == NULL
)
265 BN_clear_free(*kinvp
);
271 DSAerr(DSA_F_DSA_SIGN_SETUP
, ERR_R_BN_LIB
);
280 static int dsa_do_verify(const unsigned char *dgst
, int dgst_len
,
281 DSA_SIG
*sig
, DSA
*dsa
)
284 BIGNUM
*u1
, *u2
, *t1
;
285 BN_MONT_CTX
*mont
= NULL
;
288 if (!dsa
->p
|| !dsa
->q
|| !dsa
->g
) {
289 DSAerr(DSA_F_DSA_DO_VERIFY
, DSA_R_MISSING_PARAMETERS
);
293 i
= BN_num_bits(dsa
->q
);
294 /* fips 186-3 allows only different sizes for q */
295 if (i
!= 160 && i
!= 224 && i
!= 256) {
296 DSAerr(DSA_F_DSA_DO_VERIFY
, DSA_R_BAD_Q_VALUE
);
300 if (BN_num_bits(dsa
->p
) > OPENSSL_DSA_MAX_MODULUS_BITS
) {
301 DSAerr(DSA_F_DSA_DO_VERIFY
, DSA_R_MODULUS_TOO_LARGE
);
308 if (u1
== NULL
|| u2
== NULL
|| t1
== NULL
|| ctx
== NULL
)
311 DSA_SIG_get0(sig
, &r
, &s
);
313 if (BN_is_zero(r
) || BN_is_negative(r
) ||
314 BN_ucmp(r
, dsa
->q
) >= 0) {
318 if (BN_is_zero(s
) || BN_is_negative(s
) ||
319 BN_ucmp(s
, dsa
->q
) >= 0) {
325 * Calculate W = inv(S) mod Q save W in u2
327 if ((BN_mod_inverse(u2
, s
, dsa
->q
, ctx
)) == NULL
)
331 if (dgst_len
> (i
>> 3))
333 * if the digest length is greater than the size of q use the
334 * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
338 if (BN_bin2bn(dgst
, dgst_len
, u1
) == NULL
)
341 /* u1 = M * w mod q */
342 if (!BN_mod_mul(u1
, u1
, u2
, dsa
->q
, ctx
))
345 /* u2 = r * w mod q */
346 if (!BN_mod_mul(u2
, r
, u2
, dsa
->q
, ctx
))
349 if (dsa
->flags
& DSA_FLAG_CACHE_MONT_P
) {
350 mont
= BN_MONT_CTX_set_locked(&dsa
->method_mont_p
,
351 dsa
->lock
, dsa
->p
, ctx
);
356 if (dsa
->meth
->dsa_mod_exp
!= NULL
) {
357 if (!dsa
->meth
->dsa_mod_exp(dsa
, t1
, dsa
->g
, u1
, dsa
->pub_key
, u2
,
361 if (!BN_mod_exp2_mont(t1
, dsa
->g
, u1
, dsa
->pub_key
, u2
, dsa
->p
, ctx
,
366 /* let u1 = u1 mod q */
367 if (!BN_mod(u1
, t1
, dsa
->q
, ctx
))
371 * V is now in u1. If the signature is correct, it will be equal to R.
373 ret
= (BN_ucmp(u1
, r
) == 0);
377 DSAerr(DSA_F_DSA_DO_VERIFY
, ERR_R_BN_LIB
);
385 static int dsa_init(DSA
*dsa
)
387 dsa
->flags
|= DSA_FLAG_CACHE_MONT_P
;
391 static int dsa_finish(DSA
*dsa
)
393 BN_MONT_CTX_free(dsa
->method_mont_p
);