1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
/*
* Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
* BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
* ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
#include "inner.h"
#define I31_LEN ((BR_MAX_EC_SIZE + 61) / 31)
#define POINT_LEN (1 + (((BR_MAX_EC_SIZE + 7) >> 3) << 1))
#define ORDER_LEN ((BR_MAX_EC_SIZE + 7) >> 3)
/* see bearssl_ec.h */
size_t
br_ecdsa_i31_sign_raw(const br_ec_impl *impl,
const br_hash_class *hf, const void *hash_value,
const br_ec_private_key *sk, void *sig)
{
/*
* IMPORTANT: this code is fit only for curves with a prime
* order. This is needed so that modular reduction of the X
* coordinate of a point can be done with a simple subtraction.
* We also rely on the last byte of the curve order to be distinct
* from 0 and 1.
*/
const br_ec_curve_def *cd;
uint32_t n[I31_LEN], r[I31_LEN], s[I31_LEN], x[I31_LEN];
uint32_t m[I31_LEN], k[I31_LEN], t1[I31_LEN], t2[I31_LEN];
unsigned char tt[ORDER_LEN << 1];
unsigned char eU[POINT_LEN];
size_t hash_len, nlen, ulen;
uint32_t n0i, ctl;
br_hmac_drbg_context drbg;
/*
* If the curve is not supported, then exit with an error.
*/
if (((impl->supported_curves >> sk->curve) & 1) == 0) {
return 0;
}
/*
* Get the curve parameters (generator and order).
*/
switch (sk->curve) {
case BR_EC_secp256r1:
cd = &br_secp256r1;
break;
case BR_EC_secp384r1:
cd = &br_secp384r1;
break;
case BR_EC_secp521r1:
cd = &br_secp521r1;
break;
default:
return 0;
}
/*
* Get modulus.
*/
nlen = cd->order_len;
br_i31_decode(n, cd->order, nlen);
n0i = br_i31_ninv31(n[1]);
/*
* Get private key as an i31 integer. This also checks that the
* private key is well-defined (not zero, and less than the
* curve order).
*/
if (!br_i31_decode_mod(x, sk->x, sk->xlen, n)) {
return 0;
}
if (br_i31_iszero(x)) {
return 0;
}
/*
* Get hash length.
*/
hash_len = (hf->desc >> BR_HASHDESC_OUT_OFF) & BR_HASHDESC_OUT_MASK;
/*
* Truncate and reduce the hash value modulo the curve order.
*/
br_ecdsa_i31_bits2int(m, hash_value, hash_len, n[0]);
br_i31_sub(m, n, br_i31_sub(m, n, 0) ^ 1);
/*
* RFC 6979 generation of the "k" value.
*
* The process uses HMAC_DRBG (with the hash function used to
* process the message that is to be signed). The seed is the
* concatenation of the encodings of the private key and
* the hash value (after truncation and modular reduction).
*/
br_i31_encode(tt, nlen, x);
br_i31_encode(tt + nlen, nlen, m);
br_hmac_drbg_init(&drbg, hf, tt, nlen << 1);
for (;;) {
br_hmac_drbg_generate(&drbg, tt, nlen);
br_ecdsa_i31_bits2int(k, tt, nlen, n[0]);
if (br_i31_iszero(k)) {
continue;
}
if (br_i31_sub(k, n, 0)) {
break;
}
}
/*
* Compute k*G and extract the X coordinate, then reduce it
* modulo the curve order. Since we support only curves with
* prime order, that reduction is only a matter of computing
* a subtraction.
*/
br_i31_encode(tt, nlen, k);
ulen = impl->mulgen(eU, tt, nlen, sk->curve);
br_i31_zero(r, n[0]);
br_i31_decode(r, &eU[1], ulen >> 1);
r[0] = n[0];
br_i31_sub(r, n, br_i31_sub(r, n, 0) ^ 1);
/*
* Compute 1/k in double-Montgomery representation. We do so by
* first converting _from_ Montgomery representation (twice),
* then using a modular exponentiation.
*/
br_i31_from_monty(k, n, n0i);
br_i31_from_monty(k, n, n0i);
memcpy(tt, cd->order, nlen);
tt[nlen - 1] -= 2;
br_i31_modpow(k, tt, nlen, n, n0i, t1, t2);
/*
* Compute s = (m+xr)/k (mod n).
* The k[] array contains R^2/k (double-Montgomery representation);
* we thus can use direct Montgomery multiplications and conversions
* from Montgomery, avoiding any call to br_i31_to_monty() (which
* is slower).
*/
br_i31_from_monty(m, n, n0i);
br_i31_montymul(t1, x, r, n, n0i);
ctl = br_i31_add(t1, m, 1);
ctl |= br_i31_sub(t1, n, 0) ^ 1;
br_i31_sub(t1, n, ctl);
br_i31_montymul(s, t1, k, n, n0i);
/*
* Encode r and s in the signature.
*/
br_i31_encode(sig, nlen, r);
br_i31_encode((unsigned char *)sig + nlen, nlen, s);
return nlen << 1;
}
|
