// 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))
}