hare

[hare] The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

core.ha (7704B)


      1 // SPDX-License-Identifier: MPL-2.0
      2 // (c) Hare authors <https://harelang.org>
      3 
      4 // The following code was initially 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 use bytes;
     28 use crypto::bigint::*;
     29 use crypto::math::{divu32};
     30 use errors;
     31 use types;
     32 
     33 // Maximum factor size of a key of [[BITSZ]].
     34 def MAXFACTOR: size = ((BITSZ + 64) >> 1);
     35 
     36 // Required buf size for the [[pubexp]] operation.
     37 def PUBEXP_BUFSZ: size = size(word) * (1 + (4 * (2
     38 		+ ((BITSZ + WORD_BITSZ - 1) / WORD_BITSZ))));
     39 
     40 // Requried buf size for the [[privexp]] operation.
     41 def PRIVEXP_BUFSZ: size = size(word) * (1 + (8 * (2
     42 		+ ((MAXFACTOR + WORD_BITSZ - 1) / WORD_BITSZ))));
     43 
     44 // Performs the modular exponentiation of 'x' with the public exponent of 'pub'.
     45 // 'x' is modified in place. 'x' must be the same length as the actual length
     46 // of 'pub.n'.
     47 //
     48 // For the size of 'buf' see [[PUBEXP_BUFSZ]]. If the buffer is not large
     49 // enough, [[errors::overflow]] will be returned. In case of 'x' being not of
     50 // required length or if 'x' is not modulo 'pub.n' [[errors::invalid]] is
     51 // returned and 'x' will be zeroed.
     52 fn pubexp(pub: *pubparams, x: []u8, buf: []u8) (void | error) = {
     53 	// supported key length leaks. But that is not a problem.
     54 	const wbuflen = len(buf) / size(word);
     55 	let wbuf: []word = (buf: *[*]word)[..wbuflen];
     56 	let n = pub.n;
     57 
     58 	// get the maximal allowed key size for given buffer. Reverse of the
     59 	// [[PUBEXP_BUFSZ]] equation.
     60 	const maxkeybits = (((wbuflen - 1) / 4) - 2) * WORD_BITSZ;
     61 
     62 	if (len(n) == 0 || len(n) > (maxkeybits >> 3)) {
     63 		return errors::overflow;
     64 	};
     65 
     66 	if (len(x) != len(n)) {
     67 		bytes::zero(x);
     68 		return errors::invalid;
     69 	};
     70 
     71 	// add word size - 1 to ceil required words in the division that follows
     72 	const maxnbitlen = (len(n) << 3) + WORD_BITSZ: size - 1;
     73 	assert(maxnbitlen <= types::U32_MAX);
     74 	let bwordlen = 1 + divu32(0, maxnbitlen: u32, WORD_BITSZ).0;
     75 
     76 	// make it even
     77 	bwordlen += bwordlen & 1;
     78 
     79 	let nenc = wbuf[..bwordlen];
     80 	let xenc = wbuf[bwordlen..2 * bwordlen];
     81 	let t = wbuf[2 * bwordlen..];
     82 
     83 	// From now on, buf will be indirectly used via slices borrowed from
     84 	// wbuf. Therefore make sure it gets cleared in the end.
     85 	defer bytes::zero(buf);
     86 
     87 	encode(nenc, n);
     88 	const n0i = ninv(nenc[1]);
     89 
     90 	// if m is odd, n0i is also.
     91 	let result: word = n0i & 1;
     92 	result &= encodemod(xenc, x, nenc);
     93 
     94 	modpow(xenc, pub.e, nenc, n0i, t);
     95 
     96 	decode(x, xenc);
     97 
     98 	if (result == 0: word) {
     99 		bytes::zero(x);
    100 		return errors::invalid;
    101 	};
    102 };
    103 
    104 // Performs modular exponentiation of 'x' with the private exponent of 'priv'.
    105 // 'x' is modified in place. 'x' must be the same length as the actual length
    106 // of the modulus n (see [[privkey_nsize]]).
    107 //
    108 // For size of 'buf' see [[PRIVEXP_BUFSZ]]. If the buffer is not large enough
    109 // [[errors::overflow]] will be returned. In case of an invalid size of 'x' or
    110 // an invalid key, [[errors::invalid]] will be returned and 'x' will be zeroed.
    111 fn privexp(priv: *privparams, x: []u8, buf: []u8) (void | error) = {
    112 	// supported key length leaks. But that is not a problem.
    113 	const wbuflen = len(buf) / size(word);
    114 	let wbuf: []word = (buf: *[*]word)[..wbuflen];
    115 
    116 	let p = priv.p;
    117 	let q = priv.q;
    118 
    119 	const maxflen = if (len(p) > len(q)) len(p) else len(q);
    120 
    121 	// add word size - 1 to ceil required words in the division that follows
    122 	const maxfbitlen = (maxflen << 3) + WORD_BITSZ: size - 1;
    123 	assert(maxfbitlen <= types::U32_MAX);
    124 	let bwordlen = 1 + divu32(0, maxfbitlen: u32, WORD_BITSZ).0;
    125 
    126 	// make it even
    127 	bwordlen += bwordlen & 1;
    128 
    129 	// We need at least 6 big integers for the following calculations
    130 	if (6 * bwordlen > len(wbuf)) {
    131 		return errors::overflow;
    132 	};
    133 
    134 	// From now on, buf will be indirectly used via wbuf. Therefore make
    135 	// sure it gets cleared in the end.
    136 	defer bytes::zero(buf);
    137 
    138 	let mq = wbuf[..bwordlen];
    139 	encode(mq, q);
    140 
    141 	let t1 = wbuf[bwordlen..2 * bwordlen];
    142 	encode(t1, p);
    143 
    144 	// compute modulus n
    145 	let t2 = wbuf[2 * bwordlen..4 * bwordlen];
    146 	zero(t2, mq[0]);
    147 	mulacc(t2, mq, t1);
    148 
    149 	// ceiled modulus length in bytes
    150 	const nlen = (priv.nbitlen + 7) >> 3;
    151 	if(len(x) != nlen) {
    152 		bytes::zero(x);
    153 		return errors::invalid;
    154 	};
    155 
    156 	let t3 = wbuf[4 * bwordlen..6 * bwordlen];
    157 	let t3 = (t3: *[*]u8)[..nlen];
    158 	decode(t3, t2);
    159 	let r: u32 = 0;
    160 
    161 	// Check if x is mod n.
    162 	//
    163 	// We encode the modulus into bytes, to perform the comparison with
    164 	// bytes. We know that the product length, in bytes, is exactly nlen.
    165 	//
    166 	// The comparison actually computes the carry when subtracting the
    167 	// modulus from the source value; that carry must be 1 for a value in
    168 	// the correct range. We keep it in r, which is our accumulator for the
    169 	// error code.
    170 	for (let u = nlen; u > 0) {
    171 		u -= 1;
    172 		r = ((x[u] - (t3[u] + r)) >> 8) & 1;
    173 	};
    174 
    175 	// Move the decoded p to another temporary buffer.
    176 	let mp = wbuf[2 * bwordlen..3 * bwordlen];
    177 	mp[..] = t1[..];
    178 
    179 	// Compute s2 = x^dq mod q.
    180 	const q0i = ninv(mq[1]);
    181 	let s2 = wbuf[bwordlen..bwordlen * 3];
    182 	encodereduce(s2, x, mq);
    183 	r &= modpow(s2, priv.dq, mq, q0i, wbuf[3 * bwordlen..]);
    184 
    185 	// Compute s1 = x^dp mod p.
    186 	const p0i = ninv(mp[1]);
    187 	let s1 = wbuf[bwordlen * 3..];
    188 	encodereduce(s1, x, mp);
    189 	r &= modpow(s1, priv.dp, mp, p0i, wbuf[4 * bwordlen..]);
    190 
    191 	// Compute:
    192 	//   h = (s1 - s2)*(1/q) mod p
    193 	// s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is
    194 	// unclear about whether p may be lower than q (some existing,
    195 	// widely deployed implementations of RSA don't tolerate p < q),
    196 	// but we want to support that occurrence, so we need to use the
    197 	// reduction function.
    198 	//
    199 	// Since we use br_i31_decode_reduce() for iq (purportedly, the
    200 	// inverse of q modulo p), we also tolerate improperly large
    201 	// values for this parameter.
    202 	let t1 = wbuf[4 * bwordlen..5 * bwordlen];
    203 	let t2 = wbuf[5 * bwordlen..];
    204 
    205 	reduce(t2, s2, mp);
    206 	add(s1, mp, sub(s1, t2, 1));
    207 	tomonty(s1, mp);
    208 	encodereduce(t1, priv.iq, mp);
    209 	montymul(t2, s1, t1, mp, p0i);
    210 
    211 	// h is now in t2. We compute the final result:
    212 	//   s = s2 + q*h
    213 	// All these operations are non-modular.
    214 	//
    215 	// We need mq, s2 and t2. We use the t3 buffer as destination.
    216 	// The buffers mp, s1 and t1 are no longer needed, so we can
    217 	// reuse them for t3. Moreover, the first step of the computation
    218 	// is to copy s2 into t3, after which s2 is not needed. Right
    219 	// now, mq is in slot 0, s2 is in slot 1, and t2 is in slot 5.
    220 	// Therefore, we have ample room for t3 by simply using s2.
    221 	let t3 = s2;
    222 	mulacc(t3, mq, t2);
    223 
    224 	// Encode the result. Since we already checked the value of xlen,
    225 	// we can just use it right away.
    226 	decode(x, t3);
    227 
    228 	if ((p0i & q0i & r) != 1) {
    229 		bytes::zero(x);
    230 		return errors::invalid;
    231 	};
    232 };