Debian Codegraph @

crypto/ecdsa/ecdsa.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // Ported from BearSSL
5 //
6 // Copyright (c) 2016 Thomas Pornin <[email protected]>
7 //
8 // Permission is hereby granted, free of charge, to any person obtaining
9 // a copy of this software and associated documentation files (the
10 // "Software"), to deal in the Software without restriction, including
11 // without limitation the rights to use, copy, modify, merge, publish,
12 // distribute, sublicense, and/or sell copies of the Software, and to
13 // permit persons to whom the Software is furnished to do so, subject to
14 // the following conditions:
15 //
16 // The above copyright notice and this permission notice shall be
17 // included in all copies or substantial portions of the Software.
18 //
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
23 // BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
24 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
25 // CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 // SOFTWARE.
27
28 use crypto::ec;
29 use crypto::bigint;
30 use hash;
31 use crypto::bigint::{word};
32
33 def POINTSZ = 1 + ((ec::MAX_COORDBITSZ + bigint::WORD_BITSZ - 1)
34 / bigint::WORD_BITSZ);
35
36 // Maximum signature size of curves supported by [[crypto::ec]].
37 export def MAX_SIGSZ = ec::MAX_POINTSZ - 1;
38
39 // Returns the size of a signature created/verifiable with given key. It is
40 // [[crypto::ec::pointsz]] - 1 for the NIST curves.
41 export fn sigsz(key: (*pubkey | *privkey)) size = {
42 let c = match (key) {
43 case let k: *pubkey =>
44 yield k.curve;
45 case let k: *privkey =>
46 yield k.curve;
47 };
48 return c.pointsz - 1;
49 };
50
51 // Size of signature created with a P256 key.
52 export def P256_SIGSZ = 64;
53
54 // Size of signature created with a P384 key.
55 export def P384_SIGSZ = 96;
56
57 // Size of signature created with a P521 key.
58 export def P521_SIGSZ = 132;
59
60 // Verifies the signature 'sig' with message 'hash' using the public key 'pub'.
61 // Returns [[invalidkey]] or [[invalidsig]] in case of error. An invalid key may
62 // not be detected and causes an [[invalidsig]] in this case. Verification is
63 // done in constant time, but may return earlier if the signature format is not
64 // valid.
65 export fn verify(pub: *pubkey, hash: []u8, sig: []u8) (void | error) = {
66 // IMPORTANT: this code is fit only for curves with a prime
67 // order. This is needed so that modular reduction of the X
68 // coordinate of a point can be done with a simple subtraction.
69 assert(pub.curve == ec::p256 || pub.curve == ec::p384
70 || pub.curve == ec::p521);
71
72 let n: [POINTSZ]bigint::word = [0...];
73 let r: [POINTSZ]bigint::word = [0...];
74 let s: [POINTSZ]bigint::word = [0...];
75 let t: [POINTSZ*2]bigint::word = [0...];
76 let t1 = t[..POINTSZ];
77 let t2 = t[POINTSZ..];
78
79 let tx: [(ec::MAX_COORDBITSZ + 7) >> 3]u8 = [0...];
80 let ty: [(ec::MAX_COORDBITSZ + 7) >> 3]u8 = [0...];
81 let eu: [ec::MAX_POINTSZ]u8 = [0...];
82
83 let q = pub.get_q(pub);
84
85 // Signature length must be even.
86 if (len(sig) & 1 == 1) {
87 return invalidsig;
88 };
89 let rlen = len(sig) >> 1;
90
91 let generator = pub.curve.generator();
92 // Public key point must have the proper size for this curve.
93 if (len(q) != len(generator)) {
94 return invalidkey;
95 };
96
97 // Get modulus; then decode the r and s values. They must be
98 // lower than the modulus, and s must not be null.
99 let order = pub.curve.order();
100 const nlen = len(order);
101
102
103 bigint::encode(n, order);
104 let n0i = bigint::ninv(n[1]);
105 if (bigint::encodemod(r, sig[..rlen], n) == 0) {
106 return invalidsig;
107 };
108 if (bigint::encodemod(s, sig[rlen..2 * rlen], n) == 0) {
109 return invalidsig;
110 };
111 if (bigint::iszero(s) == 1) {
112 return invalidsig;
113 };
114
115 // Invert s. We do that with a modular exponentiation; we use
116 // the fact that for all the curves we support, the least
117 // significant byte is not 0 or 1, so we can subtract 2 without
118 // any carry to process.
119 // We also want 1/s in Montgomery representation, which can be
120 // done by converting _from_ Montgomery representation before
121 // the inversion (because (1/s)*R = 1/(s/R)).
122 bigint::frommonty(s, n, n0i);
123 tx[..nlen] = order[..];
124 tx[nlen - 1] -= 2;
125 bigint::modpow(s, tx[..nlen], n, n0i, t);
126
127
128 t1[..] = [0...];
129 // Truncate the hash to the modulus length (in bits) and reduce
130 // it modulo the curve order. The modular reduction can be done
131 // with a subtraction since the truncation already reduced the
132 // value to the modulus bit length.
133 bits2int(t1, hash, n[0]);
134 bigint::sub(t1, n, bigint::sub(t1, n, 0) ^ 1);
135
136 // Multiply the (truncated, reduced) hash value with 1/s, result in
137 // t2, encoded in ty.
138 bigint::montymul(t2, t1, s, n, n0i);
139 bigint::decode(ty[..nlen], t2);
140
141 // Multiply r with 1/s, result in t1, encoded in tx.
142 bigint::montymul(t1, r, s, n, n0i);
143 bigint::decode(tx[..nlen], t1);
144
145 // Compute the point x*Q + y*G.
146 let ulen = len(generator);
147 eu[..ulen] = q[..ulen];
148 let res = pub.curve.muladd(eu[..ulen], [], tx[..nlen], ty[..nlen]);
149
150 // Get the X coordinate, reduce modulo the curve order, and
151 // compare with the 'r' value.
152 //
153 // The modular reduction can be done with subtractions because
154 // we work with curves of prime order, so the curve order is
155 // close to the field order (Hasse's theorem).
156 bigint::zero(t1, n[0]);
157 bigint::encode(t1, eu[1..(ulen >> 1) + 1]);
158 t1[0] = n[0];
159 bigint::sub(t1, n, bigint::sub(t1, n, 0) ^ 1);
160 res &= ~bigint::sub(t1, r, 1);
161 res &= bigint::iszero(t1);
162
163 if (res != 1) {
164 return invalidsig;
165 };
166 };
167
168 def ORDER_LEN = (ec::MAX_COORDBITSZ + 7) >> 3;
169
170 // Signs hashed message 'hash' with the private key and stores it into 'sig'.
171 // Returns the number of bytes written to sig on success or [[invalidkey]]
172 // otherwise.
173 //
174 // The signature is done in a deterministic way according to RFC 6979, hence
175 // 'hashfn' and 'hashbuf' are required. 'hashfn' can be the same as the one that
176 // created 'hash', though it might not be. The overall security will be limited
177 // by the weaker of the two hash functions, according to the RFC. 'hashbuf' must
178 // be of size [[hash::sz]] of 'hashfn' * 2 + [[hash::bsz]] of 'hashfn'.
179 //
180 // For the size requirenment of 'sig' see [[sigsz]].
181 export fn sign(
182 priv: *privkey,
183 hash: []u8,
184 hashfn: *hash::hash,
185 hashbuf: []u8,
186 sig: []u8
187 ) (u32 | invalidkey) = {
188 // IMPORTANT: this code is fit only for curves with a prime
189 // order. This is needed so that modular reduction of the X
190 // coordinate of a point can be done with a simple subtraction.
191 // We also rely on the last byte of the curve order to be distinct
192 // from 0 and 1.
193 assert(priv.curve == ec::p256 || priv.curve == ec::p384
194 || priv.curve == ec::p521);
195
196 let n: [POINTSZ]bigint::word = [0...];
197 let r: [POINTSZ]bigint::word = [0...];
198 let s: [POINTSZ]bigint::word = [0...];
199 let x: [POINTSZ]bigint::word = [0...];
200 let m: [POINTSZ]bigint::word = [0...];
201 let k: [POINTSZ]bigint::word = [0...];
202 let tmp: [POINTSZ * 2]bigint::word = [0...];
203
204 let tt: [ORDER_LEN << 1]u8 = [0...];
205 let eu: [ec::MAX_POINTSZ]u8 = [0...];
206
207 // Get modulus.
208 let order = priv.curve.order();
209 const nlen = len(order);
210
211 bigint::encode(n, order);
212 const n0i = bigint::ninv(n[1]);
213
214 // Get private key as an i31 integer. This also checks that the
215 // private key is well-defined (not zero, and less than the
216 // curve order).
217 if (bigint::encodemod(x, priv.get_x(priv), n) == 0) {
218 return invalidkey;
219 };
220 if (bigint::iszero(x) == 1) {
221 return invalidkey;
222 };
223
224 // Truncate and reduce the hash value modulo the curve order.
225 bits2int(m, hash, n[0]);
226 bigint::sub(m, n, bigint::sub(m, n, 0) ^ 1);
227
228 bigint::decode(tt[..nlen], x);
229 bigint::decode(tt[nlen..nlen * 2], m);
230
231 // RFC 6979 generation of the "k" value.
232 //
233 // The process uses HMAC_DRBG (with the hash function used to
234 // process the message that is to be signed). The seed is the
235 // concatenation of the encodings of the private key and
236 // the hash value (after truncation and modular reduction).
237 hash::reset(hashfn);
238 let drbg = hmac_drbg(hashfn, tt[..nlen*2], hashbuf);
239
240 for (true) {
241 hmac_drbg_generate(&drbg, eu[..nlen]);
242 bits2int(k, eu[..nlen], n[0]);
243
244 if (bigint::iszero(k) == 1) continue;
245 if (bigint::sub(k, n, 0) > 0) {
246 break;
247 };
248 };
249
250 // Compute k*G and extract the X coordinate, then reduce it
251 // modulo the curve order. Since we support only curves with
252 // prime order, that reduction is only a matter of computing
253 // a subtraction.
254 bigint::decode(tt[..nlen], k[..]);
255
256 let ulen = priv.curve.mulgen(eu, tt[..nlen]);
257
258 bigint::zero(r, n[0]);
259 bigint::encode(r, eu[1..(ulen >> 1) + 1]);
260 r[0] = n[0];
261 bigint::sub(r, n, bigint::sub(r, n, 0) ^ 1);
262
263 // Compute 1/k in double-Montgomery representation. We do so by
264 // first converting _from_ Montgomery representation (twice),
265 // then using a modular exponentiation.
266 bigint::frommonty(k, n, n0i);
267 bigint::frommonty(k, n, n0i);
268 tt[..nlen] = order[..nlen];
269 tt[nlen - 1] -= 2;
270
271 bigint::modpow(k, tt[..nlen], n, n0i, tmp);
272
273 // Compute s = (m+xr)/k (mod n).
274 // The k[] array contains R^2/k (double-Montgomery representation);
275 // we thus can use direct Montgomery multiplications and conversions
276 // from Montgomery, avoiding any call to br_i31_to_monty() (which
277 // is slower).
278 let t1 = tmp[..POINTSZ];
279 let t2 = tmp[POINTSZ..];
280 bigint::frommonty(m, n, n0i);
281 bigint::montymul(t1, x, r, n, n0i);
282 let ctl = bigint::add(t1, m, 1);
283 ctl |= bigint::sub(t1, n, 0) ^ 1;
284 bigint::sub(t1, n, ctl);
285 bigint::montymul(s, t1, k, n, n0i);
286
287 // Encode r and s in the signature.
288 bigint::decode(sig[..nlen], r);
289 bigint::decode(sig[nlen..nlen*2], s);
290 return (nlen << 1): u32;
291 };
292
293 // Decode some bytes as an i31 integer, with truncation (corresponding
294 // to the 'bits2int' operation in RFC 6979). The target ENCODED bit
295 // length is provided as last parameter. The resulting value will have
296 // this declared bit length, and consists the big-endian unsigned decoding
297 // of exactly that many bits in the source (capped at the source length).
298 fn bits2int(x: []bigint::word, src: []u8, ebitlen: bigint::word) void = {
299 let sc: i32 = 0;
300 let l: size = len(src);
301
302 let bitlen: u32 = ebitlen - (ebitlen >> 5);
303 let hbitlen = len(src): u32 << 3;
304 if (hbitlen > bitlen) {
305 l = (bitlen + 7) >> 3;
306 sc = ((hbitlen - bitlen) & 7): i32;
307 };
308
309 bigint::zero(x, ebitlen);
310 bigint::encode(x, src[..l]);
311 bigint::rshift(x, sc: bigint::word);
312 x[0] = ebitlen;
313 };