1 files changed, 79 insertions, 0 deletions
diff --git a/vendor/crypto-bigint/src/uint/modular/pow.rs b/vendor/crypto-bigint/src/uint/modular/pow.rs
new file mode 100644
index 000000000..5ab1fd63d
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/pow.rs
@@ -0,0 +1,79 @@
+use crate::{Limb, Uint, Word};
+
+use super::mul::{mul_montgomery_form, square_montgomery_form};
+
+/// Performs modular exponentiation using Montgomery's ladder.
+/// `exponent_bits` represents the number of bits to take into account for the exponent.
+///
+/// NOTE: this value is leaked in the time pattern.
+pub const fn pow_montgomery_form<const LIMBS: usize>(
+    x: &Uint<LIMBS>,
+    exponent: &Uint<LIMBS>,
+    exponent_bits: usize,
+    modulus: &Uint<LIMBS>,
+    r: &Uint<LIMBS>,
+    mod_neg_inv: Limb,
+) -> Uint<LIMBS> {
+    if exponent_bits == 0 {
+        return *r; // 1 in Montgomery form
+    }
+
+    const WINDOW: usize = 4;
+    const WINDOW_MASK: Word = (1 << WINDOW) - 1;
+
+    // powers[i] contains x^i
+    let mut powers = [*r; 1 << WINDOW];
+    powers[1] = *x;
+    let mut i = 2;
+    while i < powers.len() {
+        powers[i] = mul_montgomery_form(&powers[i - 1], x, modulus, mod_neg_inv);
+        i += 1;
+    }
+
+    let starting_limb = (exponent_bits - 1) / Limb::BITS;
+    let starting_bit_in_limb = (exponent_bits - 1) % Limb::BITS;
+    let starting_window = starting_bit_in_limb / WINDOW;
+    let starting_window_mask = (1 << (starting_bit_in_limb % WINDOW + 1)) - 1;
+
+    let mut z = *r; // 1 in Montgomery form
+
+    let mut limb_num = starting_limb + 1;
+    while limb_num > 0 {
+        limb_num -= 1;
+        let w = exponent.as_limbs()[limb_num].0;
+
+        let mut window_num = if limb_num == starting_limb {
+            starting_window + 1
+        } else {
+            Limb::BITS / WINDOW
+        };
+        while window_num > 0 {
+            window_num -= 1;
+
+            let mut idx = (w >> (window_num * WINDOW)) & WINDOW_MASK;
+
+            if limb_num == starting_limb && window_num == starting_window {
+                idx &= starting_window_mask;
+            } else {
+                let mut i = 0;
+                while i < WINDOW {
+                    i += 1;
+                    z = square_montgomery_form(&z, modulus, mod_neg_inv);
+                }
+            }
+
+            // Constant-time lookup in the array of powers
+            let mut power = powers[0];
+            let mut i = 1;
+            while i < 1 << WINDOW {
+                let choice = Limb::ct_eq(Limb(i as Word), Limb(idx));
+                power = Uint::<LIMBS>::ct_select(&power, &powers[i], choice);
+                i += 1;
+            }
+
+            z = mul_montgomery_form(&z, &power, modulus, mod_neg_inv);
+        }
+    }
+
+    z
+}