// Copyright 2026 Leo Cheng
// SPDX-License-Identifier: Apache-2.0
// Fixed-width, constant-time modular exponentiation over a modulus of any byte
// width, for the RSA private exponentiation.
//
// The limbs are 32-bit values carried in 64-bit lanes, the same shape the
// Curve25519 field uses: a 64-bit lane holds a 32-bit limb and the carry out of
// it, so multiplying two limbs needs only the word the platform already has.
// Every operation that touches a secret runs over the same number of limbs on
// every call. The loop bound is the key's width, which is public and fixed;
// nothing here iterates over the value's significant bits, branches on an
// exponent bit, or stops early on a zero. That is the "fixed width" the timing
// claim rests on.
///|
/// How many 32-bit limbs a value of `bits` bits occupies.
fn width(bits : Int32) -> Int32 {
(bits + 31) / 32
}
///|
/// How many bits `v` takes. Used on public values only: the modulus and the
/// public exponent.
fn bit_length(v : BigInt) -> Int32 {
let mut bits = 0
let mut rest = v
while rest > 0N {
bits += 1
rest = rest >> 1
}
bits
}
///|
/// A Montgomery engine over one modulus: the modulus in 32-bit limbs (least
/// significant first), the reduction constant `n0`, `R^2 mod n` and `R mod n`
/// to convert in and out, and the scratch one product needs. Built per
/// exponentiation, so it holds nothing secret between operations.
priv struct Mont {
size : Int32
mod : FixedArray[UInt64]
n0 : UInt64
r2 : FixedArray[UInt64]
one : FixedArray[UInt64]
// The running sum of one product, and its trial subtraction of the modulus.
t : FixedArray[UInt64]
u : FixedArray[UInt64]
// A square's full-width product, and the two halves it is reduced in.
sq : FixedArray[UInt64]
lo : FixedArray[UInt64]
hi : FixedArray[UInt64]
}
///|
/// The lane width, `2^32`, as a BigInt.
let lane : BigInt = 1N << 32
///|
/// `v mod 2^32`, as a non-negative BigInt.
fn lo32(v : BigInt) -> BigInt {
let m = v % lane
if m < 0N {
m + lane
} else {
m
}
}
///|
/// The 32-bit limbs of `v`, least significant first, in `size` lanes.
fn limbs(v : BigInt, size : Int32) -> FixedArray[UInt64] {
let bytes = v.to_octets(length=size * 4)
let out = FixedArray::make(size, 0UL)
for i in 0.. BigInt {
let bytes = FixedArray::make(a.length() * 4, b'\x00')
for i in 0..> 24) & 0xFFUL).to_byte()
bytes[at + 1] = ((a[i] >> 16) & 0xFFUL).to_byte()
bytes[at + 2] = ((a[i] >> 8) & 0xFFUL).to_byte()
bytes[at + 3] = (a[i] & 0xFFUL).to_byte()
}
BigInt::from_octets(bytes.unsafe_reinterpret_as_bytes()[:])
}
///|
/// Build the engine over `n`, which must be odd.
fn Mont::new(n : BigInt) -> Mont {
let size = width(bit_length(n))
let mod = limbs(n, size)
// `n0 = -n^-1 mod 2^32`, by Newton iteration: each round doubles the correct
// bits, five rounds from one cover the lane. Only the modulus's low limb
// matters, and the modulus is public.
let nlo = lo32(n)
let mut inv = 1N
for _ in 0..<5 {
inv = lo32(inv * (2N - lo32(nlo * inv)))
}
let n0 = lo32(lane - inv).to_uint64()
// `R = 2^32*size`; `R^2 mod n` and `R mod n` convert a plain value in and out.
let r = 1N << (32 * size)
{
size,
mod,
n0,
r2: limbs(r * r % n, size),
one: limbs(r % n, size),
t: FixedArray::make(size + 2, 0UL),
u: FixedArray::make(size, 0UL),
sq: FixedArray::make(2 * size + 1, 0UL),
lo: FixedArray::make(size, 0UL),
hi: FixedArray::make(size, 0UL),
}
}
///|
/// `out = a * b * R^-1 mod n`, by CIOS: each limb of `b` is multiplied in and
/// one limb reduced away in the same pass, so the running sum stays `size + 2`
/// lanes. `out` may be `a` or `b`: both are read before `out` is written.
fn Mont::mul(
self : Mont,
out : FixedArray[UInt64],
a : FixedArray[UInt64],
b : FixedArray[UInt64],
) -> Unit {
let size = self.size
let t = self.t
let u = self.u
let n = self.mod
for i in 0..<(size + 2) {
t[i] = 0UL
}
for i in 0..> 32
}
let s = t[size] + carry
t[size] = s & 0xFFFFFFFFUL
t[size + 1] = s >> 32
// `m` makes the low lane cancel; the sum then shifts down one lane.
let m = (t[0] * self.n0) & 0xFFFFFFFFUL
let mut c = (t[0] + m * n[0]) >> 32
for j in 1..> 32
}
let s = t[size] + c
t[size - 1] = s & 0xFFFFFFFFUL
t[size] = t[size + 1] + (s >> 32)
}
// The sum is below `2n`. It is `n` or more exactly when the overflow lane is
// set or subtracting `n` does not borrow; the choice is a mask, not a branch.
let mut borrow = 0UL
for i in 0..> 63
}
let take = 0UL - ((t[size] | (borrow ^ 1UL)) & 1UL)
for i in 0.. Unit {
let size = self.size
let sq = self.sq
for i in 0..<(2 * size + 1) {
sq[i] = 0UL
}
// The upper triangle, row by row. Row `i` writes lanes `2i+1` to `i+size-1`
// and leaves its carry in lane `i+size`, which no earlier row reaches: earlier
// rows stop one lane short of it. So the carry is stored, never added.
for i in 0..> 32
}
sq[i + size] = carry
}
// Twice the cross terms. The product of two 32-bit limbs is below `2^64`, so
// the doubling runs a lane at a time with one bit of carry.
let mut carry = 0UL
for k in 0..<(2 * size) {
let v = (sq[k] << 1) | carry
sq[k] = v & 0xFFFFFFFFUL
carry = v >> 32
}
// Plus the diagonal, `a[i]^2` at lane `2i`, held as its low and high halves so
// that the pass below stays over 32-bit lanes with a single carry.
let lo = self.lo
let hi = self.hi
for i in 0..> 32
}
let mut carry = 0UL
for k in 0..<(2 * size) {
let add = if k % 2 == 0 { lo[k / 2] } else { hi[(k - 1) / 2] }
let s = sq[k] + add + carry
sq[k] = s & 0xFFFFFFFFUL
carry = s >> 32
}
// The reduction. Lane `i` takes the multiple of the modulus that cancels it;
// the row's carry out of its top lane is held in `pending` for the next row,
// whose top lane is where it belongs.
let n = self.mod
let mut pending = 0UL
for i in 0..> 32
}
let s = sq[i + size - 1] + m * n[size - 1] + c + pending
sq[i + size - 1] = s & 0xFFFFFFFFUL
pending = s >> 32
}
// The last row's carry belongs above the product's top lane, where the result
// may still hold a bit: it is below `2n`, and the top lane is where that one
// bit lands.
let top = sq[2 * size - 1] + pending
sq[2 * size - 1] = top & 0xFFFFFFFFUL
let t = self.t
let mut borrow = 0UL
for i in 0..> 63
}
let take = 0UL - (((top >> 32) | (borrow ^ 1UL)) & 1UL)
for i in 0.. FixedArray[UInt64] {
let out = FixedArray::make(a.length(), 0UL)
for i in 0.. FixedArray[UInt64] {
let size = self.size
let table = FixedArray::make(16 * size, 0UL)
let entry = copied(base)
for i in 0..= 0 {
for _ in 0..<4 {
self.sqr(r, r)
}
let nibble = (e[w / 8] >> (4 * (w % 8))) & 0xFUL
for i in 0..> 63)
for i in 0.. FixedArray[UInt64] {
let out = limbs(v, self.size)
self.mul(out, out, self.r2)
out
}
///|
/// A value in the engine's form back to the plain integer it stands for.
fn Mont::to(self : Mont, a : FixedArray[UInt64]) -> BigInt {
let unit = FixedArray::make(self.size, 0UL)
unit[0] = 1UL
let out = FixedArray::make(self.size, 0UL)
self.mul(out, a, unit)
from_limbs(out)
}
///|
/// The Chinese-remainder half of a private key: the primes, the exponents reduced
/// against each factor's own group order, and the inverses Garner recombines
/// with. Each exponentiation runs over the full width of its own prime, so each
/// is fixed width, and the number of them is the key's prime count, which is
/// public key material. The Montgomery engines are built from these on the fly;
/// only the key material is carried, so nothing secret is held between
/// operations.
priv struct Crt {
primes : Array[BigInt]
exps : Array[BigInt]
/// `coeffs[i]` is `(primes[0] * … * primes[i-1])^-1 mod primes[i]`, unused at
/// zero: the chain below starts from the first prime's own residue.
coeffs : Array[BigInt]
}
///|
/// Build the CRT half from primes the caller handed in: each exponent is `d`
/// reduced against its factor's own group order, so every half exponentiates to
/// the width of one prime rather than of the modulus. `e * d_i ≡ 1 (mod p_i - 1)`
/// holds for genuine factors; a set that fails it is `Weak`, refused here rather
/// than at a signature.
fn Crt::new(
primes : Array[BigInt],
d : BigInt,
e : BigInt,
) -> Crt raise @spec.Broken {
let crt = Crt::fitted(primes, d)
for i in 0.. Crt {
let exps : Array[BigInt] = []
let coeffs : Array[BigInt] = []
let mut prod = 1N
for i in 0.. BigInt {
let primes = self.primes
let mut x = pow_mod(c % primes[0], self.exps[0], primes[0])
let mut prod = primes[0]
for i in 1.. BigInt {
let m = Mont::new(modulus)
m.to(m.pow(m.from(base), exp))
}