tecdsa_core/arith/
fixed_base.rs

1//! Fixed-window precomputation for repeated exponentiations of one base.
2use alloc::vec::Vec;
3use crypto_bigint::{Choice, ctutils::CtSelect};
4
5use super::{
6    monty::{Modulus, Residue},
7    sbig::SBig,
8};
9use crate::error::Result;
10
11/// Table `T[i][d] = base^{d · 2^{w·i}}` for `d ∈ [0, 2^w)`.
12pub struct FixedBase {
13    modulus: Modulus,
14    window: u32,
15    table: Vec<Vec<Residue>>,
16    max_bits: u32,
17}
18
19impl FixedBase {
20    /// Builds the table for exponent magnitudes below `2^max_bits`.
21    pub fn new(modulus: &Modulus, base: &Residue, max_bits: u32, window: u32) -> Self {
22        let window = window.clamp(1, 8);
23        let windows = max_bits.div_ceil(window);
24        let mut table = Vec::with_capacity(windows as usize);
25        let mut g = base.clone();
26        for _ in 0..windows {
27            let mut row = Vec::with_capacity(1 << window);
28            row.push(modulus.one());
29            for d in 1..(1usize << window) {
30                row.push(row[d - 1].mul(&g));
31            }
32            // g ← g^{2^w}
33            g = row[(1 << window) - 1].mul(&g);
34            table.push(row);
35        }
36        Self {
37            modulus: modulus.clone(),
38            window,
39            table,
40            max_bits,
41        }
42    }
43
44    pub fn max_bits(&self) -> u32 {
45        self.max_bits
46    }
47
48    /// Approximate memory held by the table, in bytes.
49    pub fn size_bytes(&self) -> usize {
50        self.table.len() * (1usize << self.window) * (self.modulus.bits_precision() as usize / 8)
51    }
52
53    fn digit(mag: &crypto_bigint::BoxedUint, i: u32, w: u32) -> usize {
54        let mut d = 0usize;
55        for b in 0..w {
56            d |= usize::from(mag.bit_vartime(i * w + b)) << b;
57        }
58        d
59    }
60
61    /// Public exponent.
62    pub fn pow_vartime(&self, exp: &SBig) -> Result<Residue> {
63        let mut acc = self.modulus.one();
64        for i in 0..self.table.len() as u32 {
65            let d = Self::digit(exp.mag(), i, self.window);
66            if d != 0 {
67                acc = acc.mul(&self.table[i as usize][d]);
68            }
69        }
70        if bool::from(exp.is_neg()) {
71            acc = self.modulus.invert(&acc)?;
72        }
73        Ok(acc)
74    }
75
76    /// Secret exponent: every window is processed, entries are picked by a full scan.
77    pub fn pow_ct(&self, exp: &SBig) -> Result<Residue> {
78        let mut acc = self.modulus.one();
79        for i in 0..self.table.len() {
80            let mut d = 0u32;
81            for b in 0..self.window {
82                d |= u32::from(bool::from(exp.mag().bit(i as u32 * self.window + b))) << b;
83            }
84            let mut pick = self.table[i][0].as_montgomery().clone();
85            for (j, e) in self.table[i].iter().enumerate().skip(1) {
86                let hit = Choice::from_u32_eq(d, j as u32);
87                pick = pick.ct_select(e.as_montgomery(), hit);
88            }
89            acc = acc.mul(&Residue::from_montgomery(pick, acc.params()));
90        }
91        let inv = self.modulus.invert(&acc)?;
92        Ok(Residue::from_montgomery(
93            acc.as_montgomery()
94                .ct_select(inv.as_montgomery(), exp.is_neg()),
95            acc.params(),
96        ))
97    }
98}
tecdsa_core/arith/fixed_base.rs

tecdsa_core/arith/
fixed_base.rs
