// SPDX-License-Identifier: MPL-2.0 // (c) Hare authors // The following code was initially 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 bytes; use crypto::bigint::*; use crypto::math::{divu32}; use errors; use types; // Maximum factor size of a key of [[BITSZ]]. def MAXFACTOR: size = ((BITSZ + 64) >> 1); // Required buf size for the [[pubexp]] operation. def PUBEXP_BUFSZ: size = size(word) * (1 + (4 * (2 + ((BITSZ + WORD_BITSZ - 1) / WORD_BITSZ)))); // Requried buf size for the [[privexp]] operation. def PRIVEXP_BUFSZ: size = size(word) * (1 + (8 * (2 + ((MAXFACTOR + WORD_BITSZ - 1) / WORD_BITSZ)))); // Performs the modular exponentiation of 'x' with the public exponent of 'pub'. // 'x' is modified in place. 'x' must be the same length as the actual length // of 'pub.n'. // // For the size of 'buf' see [[PUBEXP_BUFSZ]]. If the buffer is not large // enough, [[errors::overflow]] will be returned. In case of 'x' being not of // required length or if 'x' is not modulo 'pub.n' [[errors::invalid]] is // returned and 'x' will be zeroed. fn pubexp(pub: *pubparams, x: []u8, buf: []u8) (void | error) = { // supported key length leaks. But that is not a problem. const wbuflen = len(buf) / size(word); let wbuf: []word = (buf: *[*]word)[..wbuflen]; let n = pub.n; // get the maximal allowed key size for given buffer. Reverse of the // [[PUBEXP_BUFSZ]] equation. const maxkeybits = (((wbuflen - 1) / 4) - 2) * WORD_BITSZ; if (len(n) == 0 || len(n) > (maxkeybits >> 3)) { return errors::overflow; }; if (len(x) != len(n)) { bytes::zero(x); return errors::invalid; }; // add word size - 1 to ceil required words in the division that follows const maxnbitlen = (len(n) << 3) + WORD_BITSZ: size - 1; assert(maxnbitlen <= types::U32_MAX); let bwordlen = 1 + divu32(0, maxnbitlen: u32, WORD_BITSZ).0; // make it even bwordlen += bwordlen & 1; let nenc = wbuf[..bwordlen]; let xenc = wbuf[bwordlen..2 * bwordlen]; let t = wbuf[2 * bwordlen..]; // From now on, buf will be indirectly used via slices borrowed from // wbuf. Therefore make sure it gets cleared in the end. defer bytes::zero(buf); encode(nenc, n); const n0i = ninv(nenc[1]); // if m is odd, n0i is also. let result: word = n0i & 1; result &= encodemod(xenc, x, nenc); modpow(xenc, pub.e, nenc, n0i, t); decode(x, xenc); if (result == 0: word) { bytes::zero(x); return errors::invalid; }; }; // Performs modular exponentiation of 'x' with the private exponent of 'priv'. // 'x' is modified in place. 'x' must be the same length as the actual length // of the modulus n (see [[privkey_nsize]]). // // For size of 'buf' see [[PRIVEXP_BUFSZ]]. If the buffer is not large enough // [[errors::overflow]] will be returned. In case of an invalid size of 'x' or // an invalid key, [[errors::invalid]] will be returned and 'x' will be zeroed. fn privexp(priv: *privparams, x: []u8, buf: []u8) (void | error) = { // supported key length leaks. But that is not a problem. const wbuflen = len(buf) / size(word); let wbuf: []word = (buf: *[*]word)[..wbuflen]; let p = priv.p; let q = priv.q; const maxflen = if (len(p) > len(q)) len(p) else len(q); // add word size - 1 to ceil required words in the division that follows const maxfbitlen = (maxflen << 3) + WORD_BITSZ: size - 1; assert(maxfbitlen <= types::U32_MAX); let bwordlen = 1 + divu32(0, maxfbitlen: u32, WORD_BITSZ).0; // make it even bwordlen += bwordlen & 1; // We need at least 6 big integers for the following calculations if (6 * bwordlen > len(wbuf)) { return errors::overflow; }; // From now on, buf will be indirectly used via wbuf. Therefore make // sure it gets cleared in the end. defer bytes::zero(buf); let mq = wbuf[..bwordlen]; encode(mq, q); let t1 = wbuf[bwordlen..2 * bwordlen]; encode(t1, p); // compute modulus n let t2 = wbuf[2 * bwordlen..4 * bwordlen]; zero(t2, mq[0]); mulacc(t2, mq, t1); // ceiled modulus length in bytes const nlen = (priv.nbitlen + 7) >> 3; if(len(x) != nlen) { bytes::zero(x); return errors::invalid; }; let t3 = wbuf[4 * bwordlen..6 * bwordlen]; let t3 = (t3: *[*]u8)[..nlen]; decode(t3, t2); let r: u32 = 0; // Check if x is mod n. // // We encode the modulus into bytes, to perform the comparison with // bytes. We know that the product length, in bytes, is exactly nlen. // // The comparison actually computes the carry when subtracting the // modulus from the source value; that carry must be 1 for a value in // the correct range. We keep it in r, which is our accumulator for the // error code. for (let u = nlen; u > 0) { u -= 1; r = ((x[u] - (t3[u] + r)) >> 8) & 1; }; // Move the decoded p to another temporary buffer. let mp = wbuf[2 * bwordlen..3 * bwordlen]; mp[..] = t1[..]; // Compute s2 = x^dq mod q. const q0i = ninv(mq[1]); let s2 = wbuf[bwordlen..bwordlen * 3]; encodereduce(s2, x, mq); r &= modpow(s2, priv.dq, mq, q0i, wbuf[3 * bwordlen..]); // Compute s1 = x^dp mod p. const p0i = ninv(mp[1]); let s1 = wbuf[bwordlen * 3..]; encodereduce(s1, x, mp); r &= modpow(s1, priv.dp, mp, p0i, wbuf[4 * bwordlen..]); // Compute: // h = (s1 - s2)*(1/q) mod p // s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is // unclear about whether p may be lower than q (some existing, // widely deployed implementations of RSA don't tolerate p < q), // but we want to support that occurrence, so we need to use the // reduction function. // // Since we use br_i31_decode_reduce() for iq (purportedly, the // inverse of q modulo p), we also tolerate improperly large // values for this parameter. let t1 = wbuf[4 * bwordlen..5 * bwordlen]; let t2 = wbuf[5 * bwordlen..]; reduce(t2, s2, mp); add(s1, mp, sub(s1, t2, 1)); tomonty(s1, mp); encodereduce(t1, priv.iq, mp); montymul(t2, s1, t1, mp, p0i); // h is now in t2. We compute the final result: // s = s2 + q*h // All these operations are non-modular. // // We need mq, s2 and t2. We use the t3 buffer as destination. // The buffers mp, s1 and t1 are no longer needed, so we can // reuse them for t3. Moreover, the first step of the computation // is to copy s2 into t3, after which s2 is not needed. Right // now, mq is in slot 0, s2 is in slot 1, and t2 is in slot 5. // Therefore, we have ample room for t3 by simply using s2. let t3 = s2; mulacc(t3, mq, t2); // Encode the result. Since we already checked the value of xlen, // we can just use it right away. decode(x, t3); if ((p0i & q0i & r) != 1) { bytes::zero(x); return errors::invalid; }; };