// SPDX-License-Identifier: MPL-2.0 // (c) Hare authors // Ported from BearSSL // // Copyright (c) 2016 Thomas Pornin // // 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. use crypto::ec; use crypto::bigint; use hash; use crypto::bigint::{word}; def POINTSZ = 1 + ((ec::MAX_COORDBITSZ + bigint::WORD_BITSZ - 1) / bigint::WORD_BITSZ); // Maximum signature size of curves supported by [[crypto::ec]]. export def MAX_SIGSZ = ec::MAX_POINTSZ - 1; // Returns the size of a signature created/verifiable with given key. It is // [[crypto::ec::pointsz]] - 1 for the NIST curves. export fn sigsz(key: (*pubkey | *privkey)) size = { let c = match (key) { case let k: *pubkey => yield k.curve; case let k: *privkey => yield k.curve; }; return c.pointsz - 1; }; // Size of signature created with a P256 key. export def P256_SIGSZ = 64; // Size of signature created with a P384 key. export def P384_SIGSZ = 96; // Size of signature created with a P521 key. export def P521_SIGSZ = 132; // Verifies the signature 'sig' with message 'hash' using the public key 'pub'. // Returns [[invalidkey]] or [[invalidsig]] in case of error. An invalid key may // not be detected and causes an [[invalidsig]] in this case. Verification is // done in constant time, but may return earlier if the signature format is not // valid. export fn verify(pub: *pubkey, hash: []u8, sig: []u8) (void | error) = { // 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. assert(pub.curve == ec::p256 || pub.curve == ec::p384 || pub.curve == ec::p521); let n: [POINTSZ]bigint::word = [0...]; let r: [POINTSZ]bigint::word = [0...]; let s: [POINTSZ]bigint::word = [0...]; let t: [POINTSZ*2]bigint::word = [0...]; let t1 = t[..POINTSZ]; let t2 = t[POINTSZ..]; let tx: [(ec::MAX_COORDBITSZ + 7) >> 3]u8 = [0...]; let ty: [(ec::MAX_COORDBITSZ + 7) >> 3]u8 = [0...]; let eu: [ec::MAX_POINTSZ]u8 = [0...]; let q = pub.get_q(pub); // Signature length must be even. if (len(sig) & 1 == 1) { return invalidsig; }; let rlen = len(sig) >> 1; let generator = pub.curve.generator(); // Public key point must have the proper size for this curve. if (len(q) != len(generator)) { return invalidkey; }; // Get modulus; then decode the r and s values. They must be // lower than the modulus, and s must not be null. let order = pub.curve.order(); const nlen = len(order); bigint::encode(n, order); let n0i = bigint::ninv(n[1]); if (bigint::encodemod(r, sig[..rlen], n) == 0) { return invalidsig; }; if (bigint::encodemod(s, sig[rlen..2 * rlen], n) == 0) { return invalidsig; }; if (bigint::iszero(s) == 1) { return invalidsig; }; // Invert s. We do that with a modular exponentiation; we use // the fact that for all the curves we support, the least // significant byte is not 0 or 1, so we can subtract 2 without // any carry to process. // We also want 1/s in Montgomery representation, which can be // done by converting _from_ Montgomery representation before // the inversion (because (1/s)*R = 1/(s/R)). bigint::frommonty(s, n, n0i); tx[..nlen] = order[..]; tx[nlen - 1] -= 2; bigint::modpow(s, tx[..nlen], n, n0i, t); t1[..] = [0...]; // Truncate the hash to the modulus length (in bits) and reduce // it modulo the curve order. The modular reduction can be done // with a subtraction since the truncation already reduced the // value to the modulus bit length. bits2int(t1, hash, n[0]); bigint::sub(t1, n, bigint::sub(t1, n, 0) ^ 1); // Multiply the (truncated, reduced) hash value with 1/s, result in // t2, encoded in ty. bigint::montymul(t2, t1, s, n, n0i); bigint::decode(ty[..nlen], t2); // Multiply r with 1/s, result in t1, encoded in tx. bigint::montymul(t1, r, s, n, n0i); bigint::decode(tx[..nlen], t1); // Compute the point x*Q + y*G. let ulen = len(generator); eu[..ulen] = q[..ulen]; let res = pub.curve.muladd(eu[..ulen], [], tx[..nlen], ty[..nlen]); // Get the X coordinate, reduce modulo the curve order, and // compare with the 'r' value. // // The modular reduction can be done with subtractions because // we work with curves of prime order, so the curve order is // close to the field order (Hasse's theorem). bigint::zero(t1, n[0]); bigint::encode(t1, eu[1..(ulen >> 1) + 1]); t1[0] = n[0]; bigint::sub(t1, n, bigint::sub(t1, n, 0) ^ 1); res &= ~bigint::sub(t1, r, 1); res &= bigint::iszero(t1); if (res != 1) { return invalidsig; }; }; def ORDER_LEN = (ec::MAX_COORDBITSZ + 7) >> 3; // Signs hashed message 'hash' with the private key and stores it into 'sig'. // Returns the number of bytes written to sig on success or [[invalidkey]] // otherwise. // // The signature is done in a deterministic way according to RFC 6979, hence // 'hashfn' and 'hashbuf' are required. 'hashfn' can be the same as the one that // created 'hash', though it might not be. The overall security will be limited // by the weaker of the two hash functions, according to the RFC. 'hashbuf' must // be of size [[hash::sz]] of 'hashfn' * 2 + [[hash::bsz]] of 'hashfn'. // // For the size requirenment of 'sig' see [[sigsz]]. export fn sign( priv: *privkey, hash: []u8, hashfn: *hash::hash, hashbuf: []u8, sig: []u8 ) (u32 | invalidkey) = { // 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. assert(priv.curve == ec::p256 || priv.curve == ec::p384 || priv.curve == ec::p521); let n: [POINTSZ]bigint::word = [0...]; let r: [POINTSZ]bigint::word = [0...]; let s: [POINTSZ]bigint::word = [0...]; let x: [POINTSZ]bigint::word = [0...]; let m: [POINTSZ]bigint::word = [0...]; let k: [POINTSZ]bigint::word = [0...]; let tmp: [POINTSZ * 2]bigint::word = [0...]; let tt: [ORDER_LEN << 1]u8 = [0...]; let eu: [ec::MAX_POINTSZ]u8 = [0...]; // Get modulus. let order = priv.curve.order(); const nlen = len(order); bigint::encode(n, order); const n0i = bigint::ninv(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 (bigint::encodemod(x, priv.get_x(priv), n) == 0) { return invalidkey; }; if (bigint::iszero(x) == 1) { return invalidkey; }; // Truncate and reduce the hash value modulo the curve order. bits2int(m, hash, n[0]); bigint::sub(m, n, bigint::sub(m, n, 0) ^ 1); bigint::decode(tt[..nlen], x); bigint::decode(tt[nlen..nlen * 2], m); // 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). hash::reset(hashfn); let drbg = hmac_drbg(hashfn, tt[..nlen*2], hashbuf); for (true) { hmac_drbg_generate(&drbg, eu[..nlen]); bits2int(k, eu[..nlen], n[0]); if (bigint::iszero(k) == 1) continue; if (bigint::sub(k, n, 0) > 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. bigint::decode(tt[..nlen], k[..]); let ulen = priv.curve.mulgen(eu, tt[..nlen]); bigint::zero(r, n[0]); bigint::encode(r, eu[1..(ulen >> 1) + 1]); r[0] = n[0]; bigint::sub(r, n, bigint::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. bigint::frommonty(k, n, n0i); bigint::frommonty(k, n, n0i); tt[..nlen] = order[..nlen]; tt[nlen - 1] -= 2; bigint::modpow(k, tt[..nlen], n, n0i, tmp); // 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). let t1 = tmp[..POINTSZ]; let t2 = tmp[POINTSZ..]; bigint::frommonty(m, n, n0i); bigint::montymul(t1, x, r, n, n0i); let ctl = bigint::add(t1, m, 1); ctl |= bigint::sub(t1, n, 0) ^ 1; bigint::sub(t1, n, ctl); bigint::montymul(s, t1, k, n, n0i); // Encode r and s in the signature. bigint::decode(sig[..nlen], r); bigint::decode(sig[nlen..nlen*2], s); return (nlen << 1): u32; }; // Decode some bytes as an i31 integer, with truncation (corresponding // to the 'bits2int' operation in RFC 6979). The target ENCODED bit // length is provided as last parameter. The resulting value will have // this declared bit length, and consists the big-endian unsigned decoding // of exactly that many bits in the source (capped at the source length). fn bits2int(x: []bigint::word, src: []u8, ebitlen: bigint::word) void = { let sc: i32 = 0; let l: size = len(src); let bitlen: u32 = ebitlen - (ebitlen >> 5); let hbitlen = len(src): u32 << 3; if (hbitlen > bitlen) { l = (bitlen + 7) >> 3; sc = ((hbitlen - bitlen) & 7): i32; }; bigint::zero(x, ebitlen); bigint::encode(x, src[..l]); bigint::rshift(x, sc: bigint::word); x[0] = ebitlen; };