structured_dstu4145/
validation.rs

1//! Explicit-domain validation, without hidden randomness or factoring services.
2
3use crate::{
4    Error, domains,
5    field::{Arithmetic, Polynomial},
6    multiplication::Kernel,
7    words::Words,
8};
9use core::fmt;
10use crypto_bigint::{
11    NonZero, Odd, U512,
12    modular::{FixedMontyForm, FixedMontyParams},
13};
14use rand_core::TryCryptoRng;
15
16type Monty = FixedMontyForm<{ U512::LIMBS }>;
17
18/// Original entropy failure or a mathematical/representation refusal.
19#[derive(Debug)]
20pub enum ValidationError<E> {
21    /// Invalid or unsupported supplied validation inputs.
22    Input(Error),
23    /// The original caller-provided entropy-source failure.
24    Entropy(E),
25}
26
27impl<E: fmt::Display> fmt::Display for ValidationError<E> {
28    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
29        match self {
30            Self::Input(error) => error.fmt(f),
31            Self::Entropy(error) => error.fmt(f),
32        }
33    }
34}
35
36impl<E: core::error::Error + 'static> core::error::Error for ValidationError<E> {
37    fn source(&self) -> Option<&(dyn core::error::Error + 'static)> {
38        Some(match self {
39            Self::Input(error) => error,
40            Self::Entropy(error) => error,
41        })
42    }
43}
44
45impl<E> From<Error> for ValidationError<E> {
46    fn from(value: Error) -> Self {
47        Self::Input(value)
48    }
49}
50
51/// One prime factor of 2^m-1 and its positive multiplicity.
52/// Factors are unsigned big-endian, distinct and strictly increasing.
53#[derive(Debug, Clone, Copy)]
54pub struct Factor<'a> {
55    /// Unsigned factor, at most64 octets.
56    pub prime: &'a [u8],
57    /// Multiplicity in the complete factorization.
58    pub multiplicity: u16,
59}
60
61pub(crate) trait Validator {
62    type Error: From<Error>;
63    fn polynomial<K: Kernel>(
64        &mut self,
65        field: &Polynomial<K>,
66        terms: &[usize],
67    ) -> Result<(), Self::Error>;
68    fn order(&mut self, value: Words, degree: usize) -> Result<(), Self::Error>;
69}
70
71pub(crate) struct Known;
72
73pub(crate) fn standard_polynomial(degree: usize, terms: &[usize]) -> bool {
74    for row in domains::POLYNOMIALS {
75        if row[0] == degree {
76            let count = if row[2] == 0 { 1 } else { 3 };
77            return terms == &row[1..=count];
78        }
79    }
80    false
81}
82
83fn known_order(value: Words, degree: usize) -> bool {
84    domains::PB
85        .iter()
86        .any(|spec| spec.m == degree && spec.order == value)
87}
88
89impl Validator for Known {
90    type Error = Error;
91    fn polynomial<K: Kernel>(
92        &mut self,
93        field: &Polynomial<K>,
94        terms: &[usize],
95    ) -> Result<(), Error> {
96        if standard_polynomial(field.degree(), terms) {
97            Ok(())
98        } else {
99            Err(Error::ValidationEvidenceRequired)
100        }
101    }
102    fn order(&mut self, value: Words, degree: usize) -> Result<(), Error> {
103        if known_order(value, degree) {
104            Ok(())
105        } else {
106            Err(Error::ValidationEvidenceRequired)
107        }
108    }
109}
110
111pub(crate) struct Custom<'a, R> {
112    pub(crate) factors: &'a [Factor<'a>],
113    pub(crate) random: &'a mut R,
114}
115
116impl<R: TryCryptoRng> Validator for Custom<'_, R> {
117    type Error = ValidationError<R::Error>;
118
119    fn polynomial<K: Kernel>(
120        &mut self,
121        field: &Polynomial<K>,
122        terms: &[usize],
123    ) -> Result<(), Self::Error> {
124        let degree = field.degree();
125        if standard_polynomial(degree, terms) {
126            return Ok(());
127        }
128        if !domains::POLYNOMIALS.iter().any(|row| row[0] == degree) {
129            return Err(Error::UnsupportedDomain.into());
130        }
131        let mut polynomial_t = Words::ZERO;
132        polynomial_t.flip(1);
133        // Every allowed m is prime and f(0)=f(1)=1. Rabin's criterion
134        // therefore reduces irreducibility to t^(2^m)=t modulo f.
135        if field.square_times(polynomial_t, degree) != polynomial_t {
136            return Err(Error::InvalidField.into());
137        }
138        if self.factors.is_empty() || self.factors.len() > degree {
139            return Err(Error::ValidationEvidenceRequired.into());
140        }
141        let mut all_ones = Words([u64::MAX; 8]);
142        all_ones.clear_above(degree);
143        let mersenne = integer(all_ones);
144        let mut remaining = mersenne;
145        let mut previous = U512::ONE;
146        let mut multiplicities = 0;
147        for factor in self.factors {
148            multiplicities += usize::from(factor.multiplicity);
149            if factor.multiplicity == 0 || multiplicities > degree {
150                return Err(Error::InvalidField.into());
151            }
152            let prime = integer(Words::read(factor.prime, crate::ByteOrder::BigEndian)?);
153            if prime <= previous || !probable_prime(prime, self.random)? {
154                return Err(Error::InvalidField.into());
155            }
156            previous = prime;
157            let divisor =
158                Option::<NonZero<U512>>::from(NonZero::new(prime)).ok_or(Error::InvalidField)?;
159            for _ in 0..factor.multiplicity {
160                let (quotient, remainder) = remaining.div_rem_vartime(&divisor);
161                if remainder != U512::ZERO {
162                    return Err(Error::InvalidField.into());
163                }
164                remaining = quotient;
165            }
166            let exponent = mersenne.div_rem_vartime(&divisor).0;
167            if power(field, polynomial_t, exponent) == Words::ONE {
168                return Err(Error::InvalidField.into());
169            }
170        }
171        if remaining != U512::ONE {
172            return Err(Error::ValidationEvidenceRequired.into());
173        }
174        Ok(())
175    }
176
177    fn order(&mut self, value: Words, degree: usize) -> Result<(), Self::Error> {
178        if known_order(value, degree) {
179            return Ok(());
180        }
181        let candidate = integer(value);
182        if !probable_prime(candidate, self.random)? {
183            return Err(Error::InvalidDomain.into());
184        }
185        let odd = Option::<Odd<U512>>::from(Odd::new(candidate)).ok_or(Error::InvalidDomain)?;
186        let params = FixedMontyParams::new_vartime(odd);
187        let two = Monty::new(&U512::from_u32(2), &params);
188        let degree = u32::try_from(degree).map_err(|_| Error::UnsupportedDomain)?;
189        let step = two.pow_vartime(&U512::from_u32(degree));
190        let mut product = Monty::one(&params);
191        for _ in 0..32 {
192            product *= step;
193            if product.retrieve() == U512::ONE {
194                return Err(Error::InvalidDomain.into());
195            }
196        }
197        Ok(())
198    }
199}
200
201pub(crate) fn integer(value: Words) -> U512 {
202    let mut bytes = [0; 64];
203    for (chunk, limb) in bytes.as_chunks_mut::<8>().0.iter_mut().zip(value.0) {
204        chunk.copy_from_slice(&limb.to_le_bytes());
205    }
206    U512::from_le_slice(&bytes)
207}
208
209pub(crate) fn order_bounds(value: Words, degree: usize) -> Result<(), Error> {
210    if !value.bit(0) || value.bits() < 161 || value.bits() > degree + 1 {
211        return Err(Error::InvalidDomain);
212    }
213    // Section8.2(5): n >= max(2^160, 4*(floor(sqrt(2^m))+1)).
214    let power = U512::ONE.shl_vartime(u32::try_from(degree).map_err(|_| Error::UnsupportedDomain)?);
215    let bound = power
216        .floor_sqrt_vartime()
217        .wrapping_add(&U512::ONE)
218        .shl_vartime(2);
219    if integer(value) < bound {
220        return Err(Error::InvalidDomain);
221    }
222    Ok(())
223}
224
225fn probable_prime<R: TryCryptoRng>(
226    candidate: U512,
227    random: &mut R,
228) -> Result<bool, ValidationError<R::Error>> {
229    for small in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] {
230        let prime = U512::from_u32(small);
231        if candidate == prime {
232            return Ok(true);
233        }
234        if candidate < prime {
235            return Ok(false);
236        }
237        let divisor =
238            Option::<NonZero<U512>>::from(NonZero::new(prime)).ok_or(Error::InvalidDomain)?;
239        if candidate.rem_vartime(&divisor) == U512::ZERO {
240            return Ok(false);
241        }
242    }
243    let odd = Option::<Odd<U512>>::from(Odd::new(candidate)).ok_or(Error::InvalidDomain)?;
244    let params = FixedMontyParams::new_vartime(odd);
245    let minus_one = candidate.wrapping_sub(&U512::ONE);
246    let twos = minus_one.trailing_zeros_vartime();
247    let exponent = minus_one.shr_vartime(twos);
248    let bits = candidate.bit_width_vartime();
249    let bytes = usize::try_from(bits.div_ceil(8)).map_err(|_| Error::InvalidDomain)?;
250    // DSTU6.12 prescribes50 independent random bases. Rejection sampling
251    // is bounded, uses caller entropy, and never reduces biased bytes mod n.
252    for _ in 0..50 {
253        let mut selected = None;
254        for _ in 0..128 {
255            let mut sample = [0; 64];
256            random
257                .try_fill_bytes(&mut sample[..bytes])
258                .map_err(ValidationError::Entropy)?;
259            if !bits.is_multiple_of(8) {
260                sample[bytes - 1] &= (1 << (bits % 8)) - 1;
261            }
262            let base = U512::from_le_slice(&sample);
263            if base > U512::ONE && base < candidate {
264                selected = Some(base);
265                break;
266            }
267        }
268        let base = selected.ok_or(Error::RandomSampleRefused)?;
269        let mut witness = Monty::new(&base, &params).pow_vartime(&exponent);
270        let answer = witness.retrieve();
271        if answer == U512::ONE || answer == minus_one {
272            continue;
273        }
274        let mut passed = false;
275        for _ in 1..twos {
276            witness *= witness;
277            let answer = witness.retrieve();
278            if answer == minus_one {
279                passed = true;
280                break;
281            }
282            if answer == U512::ONE {
283                return Ok(false);
284            }
285        }
286        if !passed {
287            return Ok(false);
288        }
289    }
290    Ok(true)
291}
292
293fn power<F: Arithmetic>(field: &F, value: Words, exponent: U512) -> Words {
294    let bytes = exponent.to_le_bytes();
295    let mut result = field.one();
296    for bit in (0..exponent.bit_width_vartime()).rev() {
297        result = field.square(result);
298        let index = bit as usize;
299        if bytes[index / 8] & (1 << (index % 8)) != 0 {
300            result = field.multiply(result, value);
301        }
302    }
303    result
304}
structured_dstu4145/validation.rs

structured_dstu4145/
validation.rs
