| 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 <[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 |
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 |
}; |