ecdsa.ha (10479B)
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 <pornin@bolet.org> 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 };