| 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) 2017 Thomas Pornin <[email protected]> |
| 7 |
// |
| 8 |
// Permission is hereby granted, free of charge, to any person obtaining a copy |
| 9 |
// of this software and associated documentation files (the "Software"), to deal |
| 10 |
// in the Software without restriction, including without limitation the rights |
| 11 |
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| 12 |
// copies of the Software, and to permit persons to whom the Software is |
| 13 |
// furnished to do so, subject to the following conditions: |
| 14 |
// |
| 15 |
// The above copyright notice and this permission notice shall be included in |
| 16 |
// all copies or substantial portions of the Software. |
| 17 |
// |
| 18 |
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 19 |
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 20 |
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| 21 |
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| 22 |
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| 23 |
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
| 24 |
// SOFTWARE. |
| 25 |
use crypto::math::*; |
| 26 |
|
| 27 |
// Adds 'b' to 'a', if 'ctl' is 1. If 'ctl' is 0, the result will be discarded. |
| 28 |
// Returns the carry, if the addition overflows. |
| 29 |
// |
| 30 |
// 'a' and 'b' must have the same effective word length. |
| 31 |
export fn add(a: []word, b: const []word, ctl: u32) u32 = { |
| 32 |
const l = ewordlen(a); |
| 33 |
assert(equ32(l, ewordlen(b)) == 1); |
| 34 |
|
| 35 |
let carry: u32 = 0; |
| 36 |
for (let i = 1z; i <= l; i += 1) { |
| 37 |
const n: u32 = a[i] + b[i] + carry; |
| 38 |
carry = n >> WORD_BITSZ; |
| 39 |
a[i] = muxu32(ctl, n & WORD_BITMASK, a[i]): word; |
| 40 |
}; |
| 41 |
return carry; |
| 42 |
}; |
| 43 |
|
| 44 |
// Subtracts 'b' from 'a', if 'ctl' is 1. If 'ctl' is 0, the result will be |
| 45 |
// discared. Returns the carry, if the subtraction overflows. |
| 46 |
// |
| 47 |
// 'a' and 'b' must be of the same effective word length. |
| 48 |
export fn sub(a: []word, b: const []word, do: u32) u32 = { |
| 49 |
const l = ewordlen(a); |
| 50 |
assert(equ32(l, ewordlen(b)) == 1); |
| 51 |
|
| 52 |
let carry: u32 = 0; |
| 53 |
for (let i = 1z; i <= l; i += 1) { |
| 54 |
let n: u32 = a[i] - b[i] - carry; |
| 55 |
carry = n >> WORD_BITSZ; |
| 56 |
a[i] = muxu32(do, n & WORD_BITMASK, a[i]): word; |
| 57 |
}; |
| 58 |
return carry; |
| 59 |
}; |
| 60 |
|
| 61 |
// Decrements 1 from an odd integer 'x'. |
| 62 |
export fn decrodd(x: []word) void = { |
| 63 |
assert(isodd(x)); |
| 64 |
x[1] ^= 1; |
| 65 |
}; |
| 66 |
|
| 67 |
// Right-shift an integer 'x' by 'count'. The shift amount must be less than |
| 68 |
// [[WORD_BITSZ]]. |
| 69 |
export fn rshift(x: []word, count: word) void = { |
| 70 |
assert(ltu32(count, WORD_BITSZ) == 1); |
| 71 |
|
| 72 |
const l = ewordlen(x); |
| 73 |
if (l == 0) { |
| 74 |
return; |
| 75 |
}; |
| 76 |
|
| 77 |
let r = x[1] >> count; |
| 78 |
for (let i = 2z; i <= l; i += 1) { |
| 79 |
const w = x[i]; |
| 80 |
x[i - 1] = (w << (WORD_BITSZ - count) | r) & WORD_BITMASK; |
| 81 |
r = w >> count; |
| 82 |
}; |
| 83 |
x[l] = r; |
| 84 |
}; |
| 85 |
|
| 86 |
// Multiply 'x' by 2^WORD_BITSZ and then add integer 'z', modulo 'm'. This |
| 87 |
// function assumes that 'x' and 'm' have the same announced bit length, and the |
| 88 |
// announced bit length of 'm' matches its true bit length. |
| 89 |
// |
| 90 |
// 'x' and 'm' may not refer to the same array. |
| 91 |
// |
| 92 |
// This function runs in constant time for a given announced bit length of 'x' |
| 93 |
// and 'm'. |
| 94 |
fn muladd_small(x: []word, z: word, m: const []word) void = { |
| 95 |
assert(&x[0] != &m[0], "'x' and 'm' may not refer to the same array"); |
| 96 |
|
| 97 |
let hi: u32 = 0; |
| 98 |
|
| 99 |
// We can test on the modulus bit length since we accept to leak that |
| 100 |
// length. |
| 101 |
const m_bitlen = m[0]; |
| 102 |
if (m_bitlen == 0) { |
| 103 |
return; |
| 104 |
}; |
| 105 |
|
| 106 |
if (m_bitlen <= WORD_BITSZ) { |
| 107 |
hi = x[1] >> 1; |
| 108 |
const lo = (x[1] << WORD_BITSZ) | z; |
| 109 |
x[1] = divu32(hi, lo, m[1]).1: word; |
| 110 |
return; |
| 111 |
}; |
| 112 |
|
| 113 |
let mlen = ewordlen(m); |
| 114 |
let mblr = m_bitlen & WORD_BITSZ: word; |
| 115 |
|
| 116 |
// Principle: we estimate the quotient (x*2^31+z)/m by |
| 117 |
// doing a 64/32 division with the high words. |
| 118 |
// |
| 119 |
// Let: |
| 120 |
// w = 2^31 |
| 121 |
// a = (w*a0 + a1) * w^N + a2 |
| 122 |
// b = b0 * w^N + b2 |
| 123 |
// such that: |
| 124 |
// 0 <= a0 < w |
| 125 |
// 0 <= a1 < w |
| 126 |
// 0 <= a2 < w^N |
| 127 |
// w/2 <= b0 < w |
| 128 |
// 0 <= b2 < w^N |
| 129 |
// a < w*b |
| 130 |
// I.e. the two top words of a are a0:a1, the top word of b is |
| 131 |
// b0, we ensured that b0 is "full" (high bit set), and a is |
| 132 |
// such that the quotient q = a/b fits on one word (0 <= q < w). |
| 133 |
// |
| 134 |
// If a = b*q + r (with 0 <= r < q), we can estimate q by |
| 135 |
// doing an Euclidean division on the top words: |
| 136 |
// a0*w+a1 = b0*u + v (with 0 <= v < b0) |
| 137 |
// Then the following holds: |
| 138 |
// 0 <= u <= w |
| 139 |
// u-2 <= q <= u |
| 140 |
|
| 141 |
let a0: u32 = 0, a1: u32 = 0, b0: u32 = 0; |
| 142 |
hi = x[mlen]; |
| 143 |
if (mblr == 0) { |
| 144 |
a0 = x[mlen]; |
| 145 |
x[2..mlen+1] = x[1..mlen]; |
| 146 |
x[1] = z; |
| 147 |
a1 = x[mlen]; |
| 148 |
b0 = m[mlen]; |
| 149 |
} else { |
| 150 |
a0 = ((x[mlen] << (WORD_BITSZ: word - mblr)) |
| 151 |
| (x[mlen - 1] >> mblr)) & WORD_BITMASK; |
| 152 |
x[2..mlen+1] = x[1..mlen]; |
| 153 |
x[1] = z; |
| 154 |
a1 = ((x[mlen] << (WORD_BITSZ: word - mblr)) |
| 155 |
| (x[mlen - 1] >> mblr)) & WORD_BITMASK; |
| 156 |
b0 = ((m[mlen] << (WORD_BITSZ: word - mblr)) |
| 157 |
| (m[mlen - 1] >> mblr)) & WORD_BITMASK; |
| 158 |
}; |
| 159 |
|
| 160 |
// We estimate a divisor q. If the quotient returned by br_div() |
| 161 |
// is g: |
| 162 |
// -- If a0 == b0 then g == 0; we want q = 0x7FFFFFFF. |
| 163 |
// -- Otherwise: |
| 164 |
// -- if g == 0 then we set q = 0; |
| 165 |
// -- otherwise, we set q = g - 1. |
| 166 |
// The properties described above then ensure that the true |
| 167 |
// quotient is q-1, q or q+1. |
| 168 |
// |
| 169 |
// Take care that a0, a1 and b0 are 31-bit words, not 32-bit. We |
| 170 |
// must adjust the parameters to br_div() accordingly. |
| 171 |
// |
| 172 |
const (g, _) = divu32(a0 >> 1, a1 | (a0 << 31), b0); |
| 173 |
const q = muxu32(equ32(a0, b0), WORD_BITMASK, |
| 174 |
muxu32(equ32(g, 0), 0, g - 1)); |
| 175 |
|
| 176 |
// We subtract q*m from x (with the extra high word of value 'hi'). |
| 177 |
// Since q may be off by 1 (in either direction), we may have to |
| 178 |
// add or subtract m afterwards. |
| 179 |
// |
| 180 |
// The 'tb' flag will be true (1) at the end of the loop if the |
| 181 |
// result is greater than or equal to the modulus (not counting |
| 182 |
// 'hi' or the carry). |
| 183 |
let cc: u32 = 0; |
| 184 |
let tb: u32 = 1; |
| 185 |
for (let u = 1z; u <= mlen; u += 1) { |
| 186 |
const mw = m[u]; |
| 187 |
const zl = mul31(mw, q) + cc; |
| 188 |
cc = (zl >> WORD_BITSZ): word; |
| 189 |
const zw = zl: word & WORD_BITMASK; |
| 190 |
const xw = x[u]; |
| 191 |
let nxw = xw - zw; |
| 192 |
cc += nxw >> WORD_BITSZ; |
| 193 |
nxw &= WORD_BITMASK; |
| 194 |
x[u] = nxw; |
| 195 |
tb = muxu32(equ32(nxw, mw), tb, gtu32(nxw, mw)); |
| 196 |
}; |
| 197 |
|
| 198 |
// If we underestimated q, then either cc < hi (one extra bit |
| 199 |
// beyond the top array word), or cc == hi and tb is true (no |
| 200 |
// extra bit, but the result is not lower than the modulus). In |
| 201 |
// these cases we must subtract m once. |
| 202 |
// |
| 203 |
// Otherwise, we may have overestimated, which will show as |
| 204 |
// cc > hi (thus a negative result). Correction is adding m once. |
| 205 |
const over = gtu32(cc, hi); |
| 206 |
const under = ~over & (tb | ltu32(cc, hi)); |
| 207 |
add(x, m, over); |
| 208 |
sub(x, m, under); |
| 209 |
}; |
| 210 |
|
| 211 |
|
| 212 |
// Multiply two 31-bit integers, with a 62-bit result. This default |
| 213 |
// implementation assumes that the basic multiplication operator |
| 214 |
// yields constant-time code. |
| 215 |
fn mul31(x: u32, y: u32) u64 = x: u64 * y: u64; |
| 216 |
fn mul31_lo(x: u32, y: u32) u32 = (x: u32 * y: u32) & 0x7FFFFFFF; |
| 217 |
|
| 218 |
// Calculate "m0i" which is equal to -(1/m0) mod 2^WORD_BITSZ, where m0 is the |
| 219 |
// least significant value word of m: []word. |
| 220 |
fn ninv31(m0: u32) u32 = { |
| 221 |
let y: u32 = 2 - m0; |
| 222 |
y *= 2 - y * m0; |
| 223 |
y *= 2 - y * m0; |
| 224 |
y *= 2 - y * m0; |
| 225 |
y *= 2 - y * m0; |
| 226 |
return muxu32(m0 & 1, -y, 0) & 0x7FFFFFFF; |
| 227 |
}; |
| 228 |
|
| 229 |
// Calculates "m0i" which is equal to -(1/'m0') mod 2^WORD_BITSZ. 'm0' is the |
| 230 |
// the first significant word of a big integer, which is the word at index 1. |
| 231 |
export fn ninv(m0: word) word = ninv31(m0); |
| 232 |
|
| 233 |
|
| 234 |
// Compute 'd' + 'a' * 'b', result in 'd'. The initial announced bit length of |
| 235 |
// 'd' MUST match that of 'a'. The 'd' array MUST be large enough to accommodate |
| 236 |
// the full result, plus (possibly) an extra word. The resulting announced bit |
| 237 |
// length of 'd' will be the sum of the announced bit lengths of 'a' and 'b' |
| 238 |
// (therefore, it may be larger than the actual bit length of the numerical |
| 239 |
// result). |
| 240 |
// |
| 241 |
// 'a' and 'b' may be the same array. 'd' must be disjoint from both 'a' and |
| 242 |
// 'b'. |
| 243 |
export fn mulacc(d: []word, a: const []word, b: const []word) void = { |
| 244 |
assert(&a[0] != &d[0] && &b[0] != &d[0]); |
| 245 |
|
| 246 |
const alen = ewordlen(a); |
| 247 |
const blen = ewordlen(b); |
| 248 |
|
| 249 |
// We want to add the two bit lengths, but these are encoded, |
| 250 |
// which requires some extra care. |
| 251 |
const dl: u32 = (a[0] & WORD_BITSZ) + (b[0] & WORD_BITSZ); |
| 252 |
const dh: u32 = (a[0] >> WORD_SHIFT) + (b[0] >> WORD_SHIFT); |
| 253 |
d[0] = (dh << WORD_SHIFT) + dl |
| 254 |
+ (~(dl - WORD_BITSZ): u32 >> 31); |
| 255 |
|
| 256 |
for (let u = 0z; u < blen; u += 1) { |
| 257 |
// Carry always fits on 31 bits; we want to keep it in a |
| 258 |
// 32-bit register on 32-bit architectures (on a 64-bit |
| 259 |
// architecture, cast down from 64 to 32 bits means |
| 260 |
// clearing the high bits, which is not free; on a 32-bit |
| 261 |
// architecture, the same operation really means ignoring |
| 262 |
// the top register, which has negative or zero cost). |
| 263 |
const f: u32 = b[1 + u]; |
| 264 |
let cc: u64 = 0; // TODO #if BR_64 u32 |
| 265 |
|
| 266 |
for (let v = 0z; v < alen; v += 1) { |
| 267 |
|
| 268 |
let z: u64 = d[1 + u + v]: u64 + mul31(f, a[1 + v]) + cc; |
| 269 |
cc = z >> WORD_BITSZ; |
| 270 |
d[1 + u + v] = z: word & WORD_BITMASK; |
| 271 |
}; |
| 272 |
d[1 + u + alen] = cc: word; |
| 273 |
}; |
| 274 |
}; |
| 275 |
|
| 276 |
// Reduce an integer 'a' modulo another 'm'. The result is written in 'x' and |
| 277 |
// its announced bit length is set to be equal to that of 'm'. |
| 278 |
// |
| 279 |
// 'x' must be distinct from 'a' and 'm'. |
| 280 |
// |
| 281 |
// This function runs in constant time for given announced bit lengths of 'a' |
| 282 |
// and 'm'. |
| 283 |
export fn reduce(x: []word, a: const []word, m: const []word) void = { |
| 284 |
assert(&x[0] != &a[0] && &x[0] != &m[0]); |
| 285 |
|
| 286 |
const m_bitlen = m[0]; |
| 287 |
const mlen = ewordlen(m); |
| 288 |
|
| 289 |
x[0] = m_bitlen; |
| 290 |
if (m_bitlen == 0) { |
| 291 |
return; |
| 292 |
}; |
| 293 |
|
| 294 |
// If the source is shorter, then simply copy all words from a[] |
| 295 |
// and zero out the upper words. |
| 296 |
const a_bitlen = a[0]; |
| 297 |
const alen = ewordlen(a); |
| 298 |
if (a_bitlen < m_bitlen) { |
| 299 |
x[1..1 + alen] = a[1..1 + alen]; |
| 300 |
for (let u = alen; u < mlen; u += 1) { |
| 301 |
x[u + 1] = 0; |
| 302 |
}; |
| 303 |
return; |
| 304 |
}; |
| 305 |
|
| 306 |
// The source length is at least equal to that of the modulus. |
| 307 |
// We must thus copy N-1 words, and input the remaining words |
| 308 |
// one by one. |
| 309 |
x[1..mlen] = a[2 + (alen - mlen).. 1 + mlen]; |
| 310 |
x[mlen] = 0; |
| 311 |
for (let u = 1 + alen - mlen; u > 0; u -= 1) { |
| 312 |
muladd_small(x, a[u], m); |
| 313 |
}; |
| 314 |
}; |
| 315 |
|
| 316 |
// Copies 'src' to 'dest' if ctl is 1. The length of 'src' must match the length |
| 317 |
// of 'dest'. |
| 318 |
fn ccopyword(ctl: u32, dest: []word, src: const []word) void = { |
| 319 |
for (let i = 0z; i < len(dest); i += 1) { |
| 320 |
const x = src[i]; |
| 321 |
const y = dest[i]; |
| 322 |
|
| 323 |
dest[i] = muxu32(ctl, x, y); |
| 324 |
}; |
| 325 |
}; |
| 326 |
|
| 327 |
// Compute a modular exponentiation. 'x' must be an integer modulo 'm' (same |
| 328 |
// announced bit length, lower value). 'm' must be odd. The exponent is in |
| 329 |
// big-endian unsigned notation, over len(e) bytes. The 'm0i' parameter is equal |
| 330 |
// to -(1/m0) mod 2^31, where m0 is the least significant value word of 'm' |
| 331 |
// (this works only if 'm' is an odd integer). See [[ninv]] on how to get this |
| 332 |
// value. The 'tmp' array is used for temporaries and MUST be large enough to |
| 333 |
// accommodate at least two temporary values with the same size as 'm' |
| 334 |
// (including the leading 'bit length' word). If there is room for more |
| 335 |
// temporaries, then this function may use the extra room for window-based |
| 336 |
// optimisation, resulting in faster computations. |
| 337 |
// |
| 338 |
// Returned value is 1 on success, 0 on error. An error is reported if the |
| 339 |
// provided 'tmp' array is too short. |
| 340 |
export fn modpow( |
| 341 |
x: []word, |
| 342 |
e: const []u8, |
| 343 |
m: const []word, |
| 344 |
m0i: u32, |
| 345 |
tmp: []word, |
| 346 |
) u32 = { |
| 347 |
assert(m[1] & 1 == 1, "'m' must be odd"); |
| 348 |
assert(equ32(x[0], m[0]) == 1); |
| 349 |
|
| 350 |
// Get modulus size. |
| 351 |
let mwlen = ewordlen(m) + 1; |
| 352 |
const tmplen = (mwlen & 1) + mwlen; |
| 353 |
let t1 = tmp[..tmplen]; |
| 354 |
let t2 = tmp[tmplen..]; |
| 355 |
|
| 356 |
const twlen = len(tmp); |
| 357 |
if (twlen < (mwlen << 1)) { |
| 358 |
return 0; |
| 359 |
}; |
| 360 |
|
| 361 |
// Compute possible window size, with a maximum of 5 bits. |
| 362 |
// When the window has size 1 bit, we use a specific code |
| 363 |
// that requires only two temporaries. Otherwise, for a |
| 364 |
// window of k bits, we need 2^k+1 temporaries. |
| 365 |
let win_len: word = 5; |
| 366 |
for (win_len > 1; win_len -= 1) { |
| 367 |
if (((1u32 << win_len: u32) + 1) * mwlen <= twlen) { |
| 368 |
break; |
| 369 |
}; |
| 370 |
}; |
| 371 |
|
| 372 |
// Everything is done in Montgomery representation. |
| 373 |
tomonty(x, m); |
| 374 |
|
| 375 |
// Compute window contents. If the window has size one bit only, |
| 376 |
// then t2 is set to x; otherwise, t2[0] is left untouched, and |
| 377 |
// t2[k] is set to x^k (for k >= 1). |
| 378 |
if (win_len == 1) { |
| 379 |
t2[..mwlen] = x[..mwlen]; |
| 380 |
} else { |
| 381 |
let base = t2[mwlen..]; |
| 382 |
base[..mwlen] = x[..mwlen]; |
| 383 |
for (let u = 2z; u < (1u << win_len: uint); u += 1) { |
| 384 |
montymul(base[mwlen..2 * mwlen], |
| 385 |
base[..mwlen], x, m, m0i); |
| 386 |
base = base[mwlen..]; |
| 387 |
}; |
| 388 |
}; |
| 389 |
|
| 390 |
// We need to set x to 1, in Montgomery representation. This can |
| 391 |
// be done efficiently by setting the high word to 1, then doing |
| 392 |
// one word-sized shift. |
| 393 |
zero(x, m[0]); |
| 394 |
x[ewordlen(m)] = 1; |
| 395 |
muladd_small(x, 0, m); |
| 396 |
|
| 397 |
let elen = len(e); |
| 398 |
let e = e[..]; |
| 399 |
|
| 400 |
// We process bits from most to least significant. At each |
| 401 |
// loop iteration, we have acc_len bits in acc. |
| 402 |
let acc: word = 0; |
| 403 |
let acc_len = 0i; |
| 404 |
for (acc_len > 0 || elen > 0) { |
| 405 |
// Get the next bits. |
| 406 |
let k = win_len; |
| 407 |
if (acc_len: u32 < win_len) { |
| 408 |
if (elen > 0) { |
| 409 |
acc = (acc << 8) | e[0]; |
| 410 |
e = e[1..]; |
| 411 |
elen -= 1; |
| 412 |
acc_len += 8; |
| 413 |
} else { |
| 414 |
k = acc_len: u32; |
| 415 |
}; |
| 416 |
}; |
| 417 |
|
| 418 |
let bits: u32 = (acc >> (acc_len: u32 - k: u32)) |
| 419 |
& ((1u32 << k: u32) - 1u32); |
| 420 |
acc_len -= k: int; |
| 421 |
|
| 422 |
// We could get exactly k bits. Compute k squarings. |
| 423 |
for (let i = 0z; i < k: size; i += 1) { |
| 424 |
montymul(t1, x, x, m, m0i); |
| 425 |
// memcpy(x, t1, mlen); |
| 426 |
x[..mwlen] = t1[..mwlen]; |
| 427 |
}; |
| 428 |
|
| 429 |
// Window lookup: we want to set t2 to the window |
| 430 |
// lookup value, assuming the bits are non-zero. If |
| 431 |
// the window length is 1 bit only, then t2 is |
| 432 |
// already set; otherwise, we do a constant-time lookup. |
| 433 |
if (win_len > 1) { |
| 434 |
zero(t2, m[0]); |
| 435 |
let base = t2[mwlen..]; |
| 436 |
for (let u = 1u32; u < (1 << k): size; u += 1) { |
| 437 |
let mask: u32 = -equ32(u, bits); |
| 438 |
for (let v = 1z; v < mwlen; v += 1) { |
| 439 |
t2[v] |= mask & base[v]; |
| 440 |
}; |
| 441 |
base = base[mwlen..]; |
| 442 |
}; |
| 443 |
}; |
| 444 |
|
| 445 |
// Multiply with the looked-up value. We keep the |
| 446 |
// product only if the exponent bits are not all-zero. |
| 447 |
montymul(t1, x, t2, m, m0i); |
| 448 |
|
| 449 |
ccopyword(nequ32(bits, 0), x[..mwlen], t1[..mwlen]); |
| 450 |
}; |
| 451 |
|
| 452 |
// Convert back from Montgomery representation, and exit. |
| 453 |
frommonty(x, m, m0i); |
| 454 |
return 1; |
| 455 |
}; |