1#![allow(missing_docs)]
3
4use core::borrow::Borrow;
5
6#[cfg(feature = "alloc")]
7use alloc::boxed::Box;
8#[cfg(not(feature = "modmath"))]
9use const_num_traits::PrimInt;
10use const_num_traits::{BitWidth, BitsPrecision, FromByteSlice, WithPrecision};
11use const_num_traits::{FromBytes as NumFromBytes, ToBytes as NumToBytes};
12#[cfg(feature = "alloc")]
13use crypto_bigint::{
14 modular::{BoxedMontyForm, BoxedMontyParams},
15 BoxedUint, Resize as CryptoResize,
16};
17#[cfg(feature = "alloc")]
18use crypto_bigint::{NonZero as CryptoNonZero, Odd as CryptoOdd};
19use zeroize::Zeroize;
20
21use crate::errors::{Error, Result};
22
23pub trait NumBytes: Borrow<[u8]> + AsRef<[u8]> {}
24
25impl<T> NumBytes for T where T: Borrow<[u8]> + AsRef<[u8]> {}
26
27#[repr(transparent)]
28#[derive(Clone, Debug, Eq, PartialEq)]
29pub struct NonZero<T>(T);
30
31#[repr(transparent)]
32#[derive(Clone, Debug, Eq, PartialEq)]
33pub struct Odd<T>(T);
34
35pub trait IntegerResize: Sized {
36 type Output;
37
38 fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output;
39 fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output>;
40}
41
42pub trait FixedWidthUnsignedInt:
56 Zeroize + Clone + Copy + BitsPrecision + BitWidth + WithPrecision + FromByteSlice
57{
58 type Bytes: NumBytes + Default + AsMut<[u8]>;
59
60 fn leading_zeros(&self) -> u32;
61 fn bit_length(&self) -> u32;
66 fn to_be_bytes(&self) -> Self::Bytes;
67 fn try_from_be_bytes_vartime(bytes: &[u8]) -> Result<Self>;
68 fn bits_precision(&self) -> u32;
69}
70
71#[cfg(feature = "modmath")]
72impl<T> FixedWidthUnsignedInt for T
73where
74 T: Zeroize
75 + Clone
76 + Copy
77 + BitsPrecision
78 + BitWidth
79 + WithPrecision
80 + FromByteSlice
81 + NumToBytes
82 + NumFromBytes,
83 T: NumToBytes<Bytes = <T as NumFromBytes>::Bytes>,
84 <T as NumToBytes>::Bytes: NumBytes + Default + AsMut<[u8]>,
85{
86 type Bytes = <T as NumToBytes>::Bytes;
87
88 fn leading_zeros(&self) -> u32 {
89 BitsPrecision::bits_precision(self) - BitWidth::bit_width(*self)
92 }
93
94 fn bit_length(&self) -> u32 {
95 BitWidth::bit_width(*self)
96 }
97
98 fn to_be_bytes(&self) -> Self::Bytes {
99 NumToBytes::to_be_bytes(*self)
100 }
101
102 fn try_from_be_bytes_vartime(bytes: &[u8]) -> Result<Self> {
103 let mut repr = <T as NumFromBytes>::Bytes::default();
104 let out = repr.as_mut();
105 let out_len = out.len();
106 if bytes.len() > out_len {
107 return Err(Error::InvalidArguments);
108 }
109 let dst = out
113 .get_mut(out_len - bytes.len()..)
114 .ok_or(Error::InvalidArguments)?;
115 for (d, s) in dst.iter_mut().zip(bytes.iter()) {
116 *d = *s;
117 }
118 Ok(NumFromBytes::from_be_bytes(&repr))
119 }
120
121 fn bits_precision(&self) -> u32 {
122 BitsPrecision::bits_precision(self)
123 }
124}
125
126#[cfg(not(feature = "modmath"))]
127impl<T> FixedWidthUnsignedInt for T
128where
129 T: Zeroize
130 + Clone
131 + Copy
132 + PrimInt
133 + BitsPrecision
134 + BitWidth
135 + WithPrecision
136 + FromByteSlice
137 + NumToBytes
138 + NumFromBytes,
139 T: NumToBytes<Bytes = <T as NumFromBytes>::Bytes>,
140 <T as NumToBytes>::Bytes: NumBytes + Default + AsMut<[u8]>,
141{
142 type Bytes = <T as NumToBytes>::Bytes;
143
144 fn leading_zeros(&self) -> u32 {
145 BitsPrecision::bits_precision(self) - BitWidth::bit_width(*self)
148 }
149
150 fn bit_length(&self) -> u32 {
151 BitWidth::bit_width(*self)
152 }
153
154 fn to_be_bytes(&self) -> Self::Bytes {
155 NumToBytes::to_be_bytes(*self)
156 }
157
158 fn try_from_be_bytes_vartime(bytes: &[u8]) -> Result<Self> {
159 let mut repr = <T as NumFromBytes>::Bytes::default();
160 let out = repr.as_mut();
161 let out_len = out.len();
162 if bytes.len() > out_len {
163 return Err(Error::InvalidArguments);
164 }
165 let dst = out
169 .get_mut(out_len - bytes.len()..)
170 .ok_or(Error::InvalidArguments)?;
171 for (d, s) in dst.iter_mut().zip(bytes.iter()) {
172 *d = *s;
173 }
174 Ok(NumFromBytes::from_be_bytes(&repr))
175 }
176
177 fn bits_precision(&self) -> u32 {
178 BitsPrecision::bits_precision(self)
179 }
180}
181
182#[cfg(not(feature = "alloc"))]
183impl<T> IntegerResize for T
184where
185 T: FixedWidthUnsignedInt,
186{
187 type Output = Self;
188
189 fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
190 WithPrecision::widen_to_precision(self, at_least_bits_precision)
194 }
195
196 fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
197 let value_bits = self.bit_length();
202 if value_bits <= at_least_bits_precision {
203 Some(WithPrecision::widen_to_precision(
204 self,
205 at_least_bits_precision,
206 ))
207 } else {
208 None
209 }
210 }
211}
212
213#[cfg(not(feature = "alloc"))]
214impl<T> UnsignedModularInt for T
215where
216 T: FixedWidthUnsignedInt + PartialOrd,
217{
218 type Bytes = <T as FixedWidthUnsignedInt>::Bytes;
219
220 fn to_be_bytes(&self) -> Self::Bytes {
221 FixedWidthUnsignedInt::to_be_bytes(self)
222 }
223
224 fn as_nz_ref(&self) -> NonZero<Self> {
225 NonZero::new(*self).expect("value is non-zero")
226 }
227
228 fn bits(&self) -> u32 {
229 FixedWidthUnsignedInt::bit_length(self)
230 }
231
232 fn bits_precision(&self) -> u32 {
233 FixedWidthUnsignedInt::bits_precision(self)
234 }
235
236 #[cfg(feature = "alloc")]
237 fn to_be_bytes_trimmed_vartime(&self) -> Box<[u8]> {
238 unreachable!("alloc-gated")
239 }
240}
241
242#[cfg(not(feature = "alloc"))]
243impl<T> TryFromBeBytes for T
244where
245 T: FixedWidthUnsignedInt,
246{
247 fn try_from_be_bytes_vartime(bytes: &[u8]) -> Result<Self> {
248 FixedWidthUnsignedInt::try_from_be_bytes_vartime(bytes)
249 }
250}
251
252pub trait TryFromBeBytes: Sized {
253 fn try_from_be_bytes_vartime(bytes: &[u8]) -> Result<Self>;
254}
255
256pub trait UnsignedModularInt:
257 Zeroize + Clone + PartialOrd + IntegerResize<Output = Self> + TryFromBeBytes
258{
259 type Bytes: NumBytes + AsMut<[u8]>;
260 fn to_be_bytes(&self) -> Self::Bytes;
261 fn as_nz_ref(&self) -> NonZero<Self>;
262 fn bits(&self) -> u32;
268 fn bits_precision(&self) -> u32;
269 #[cfg(feature = "alloc")]
270 fn to_be_bytes_trimmed_vartime(&self) -> Box<[u8]>;
271}
272
273impl<T> NonZero<T>
274where
275 T: UnsignedModularInt,
276{
277 pub fn new(value: T) -> Option<Self> {
278 if value.bits() == 0 {
279 None
280 } else {
281 Some(Self(value))
282 }
283 }
284
285 pub fn get(self) -> T {
286 self.0
287 }
288
289 #[allow(clippy::should_implement_trait)]
290 pub fn as_ref(&self) -> &T {
291 &self.0
292 }
293
294 pub fn bits(&self) -> u32 {
295 self.0.bits()
296 }
297
298 pub fn bits_precision(&self) -> u32 {
299 self.0.bits_precision()
300 }
301
302 pub fn to_be_bytes(&self) -> T::Bytes {
303 self.0.to_be_bytes()
304 }
305
306 #[cfg(feature = "alloc")]
307 pub fn to_be_bytes_trimmed_vartime(&self) -> Box<[u8]> {
308 self.0.to_be_bytes_trimmed_vartime()
309 }
310}
311
312impl<T> Odd<T>
313where
314 T: UnsignedModularInt,
315{
316 pub fn new(value: T) -> Option<Self> {
317 let non_zero = NonZero::new(value)?;
318 let bytes = non_zero.as_ref().to_be_bytes();
319 let bytes = bytes.as_ref();
320 let is_odd = bytes.last().map(|byte| byte & 1 == 1).unwrap_or(false);
321 if is_odd {
322 Some(Self(non_zero.get()))
323 } else {
324 None
325 }
326 }
327
328 pub fn get(self) -> T {
329 self.0
330 }
331
332 #[allow(clippy::should_implement_trait)]
333 pub fn as_ref(&self) -> &T {
334 &self.0
335 }
336
337 pub fn as_nz_ref(&self) -> NonZero<T> {
338 NonZero::new(self.0.clone()).expect("odd values are non-zero")
339 }
340
341 pub fn bits_precision(&self) -> u32 {
342 self.0.bits_precision()
343 }
344}
345
346pub trait IntoMontyForm<P: ModulusParams>: Sized {
363 fn from_reduced(integer: P::Modulus, params: &P) -> Self;
365
366 fn from_value(integer: P::Modulus, params: &P) -> Self;
369}
370
371#[cfg(feature = "alloc")]
372impl IntoMontyForm<BoxedMontyParams> for BoxedMontyForm {
373 fn from_reduced(integer: BoxedUint, params: &BoxedMontyParams) -> Self {
374 BoxedMontyForm::new(integer, params)
375 }
376
377 fn from_value(integer: BoxedUint, params: &BoxedMontyParams) -> Self {
378 let modulus =
379 CryptoNonZero::new(params.modulus().as_ref().clone()).expect("modulus is non-zero");
380 let reduced = integer.rem_vartime(&modulus);
381 Self::from_reduced(reduced, params)
382 }
383}
384
385pub trait PowBoundedExp<M: ModulusParams>: Sized {
386 fn pow_bounded_exp(&self, exp: &M::Modulus, exp_bits: u32) -> Self;
387 fn retrieve(&self) -> M::Modulus;
388}
389
390#[cfg(feature = "alloc")]
391impl PowBoundedExp<BoxedMontyParams> for BoxedMontyForm {
392 fn pow_bounded_exp(&self, exp: &BoxedUint, exp_bits: u32) -> Self {
393 self.clone().pow_bounded_exp(exp, exp_bits)
394 }
395
396 fn retrieve(&self) -> BoxedUint {
397 self.clone().retrieve()
398 }
399}
400
401pub trait Pow<M: ModulusParams>: Sized {
402 fn pow(&self, exp: &M::Modulus) -> Self;
403}
404
405#[cfg(feature = "alloc")]
406impl Pow<BoxedMontyParams> for BoxedMontyForm {
407 fn pow(&self, exp: &BoxedUint) -> Self {
408 self.clone().pow(exp)
409 }
410}
411
412pub trait InvertCt<M: ModulusParams>: Sized {
425 fn invert_ct(&self) -> Option<Self>;
426}
427
428#[cfg(feature = "alloc")]
429impl InvertCt<BoxedMontyParams> for BoxedMontyForm {
430 fn invert_ct(&self) -> Option<Self> {
431 self.invert().into_option()
432 }
433}
434
435pub trait MulCt<M: ModulusParams>: Sized {
445 fn mul_ct(&self, rhs: &Self) -> Self;
446}
447
448#[cfg(feature = "alloc")]
449impl MulCt<BoxedMontyParams> for BoxedMontyForm {
450 fn mul_ct(&self, rhs: &Self) -> Self {
451 self * rhs
452 }
453}
454
455pub trait TryRandomMod: Sized {
465 fn try_random_mod<R>(rng: &mut R, modulus: &Self) -> Result<Self>
466 where
467 R: rand_core::TryCryptoRng + ?Sized;
468}
469
470#[cfg(feature = "alloc")]
471impl TryRandomMod for BoxedUint {
472 fn try_random_mod<R>(rng: &mut R, modulus: &Self) -> Result<Self>
473 where
474 R: rand_core::TryCryptoRng + ?Sized,
475 {
476 let nz = CryptoNonZero::new(modulus.clone())
477 .into_option()
478 .ok_or(Error::InvalidModulus)?;
479 <Self as crypto_bigint::RandomMod>::try_random_mod_vartime(rng, &nz).map_err(|_| Error::Rng)
480 }
481}
482
483pub trait ModulusParams: Sized {
484 type Modulus: UnsignedModularInt;
485 type MontgomeryForm: IntoMontyForm<Self> + PowBoundedExp<Self>;
486 fn modulus(&self) -> &Odd<Self::Modulus>;
487 fn bits_precision(&self) -> u32;
488}
489
490pub(crate) mod sealed {
491 pub trait CtModulusParamsSealed {}
495}
496
497pub trait CtModulusParams: ModulusParams + sealed::CtModulusParamsSealed {}
529
530#[cfg(feature = "alloc")]
531impl sealed::CtModulusParamsSealed for BoxedMontyParams {}
532#[cfg(feature = "alloc")]
533impl CtModulusParams for BoxedMontyParams {}
534
535#[cfg(feature = "alloc")]
536impl ModulusParams for BoxedMontyParams {
537 type Modulus = BoxedUint;
538 type MontgomeryForm = BoxedMontyForm;
539 fn modulus(&self) -> &Odd<Self::Modulus> {
540 const _: () = assert!(
546 core::mem::size_of::<CryptoOdd<BoxedUint>>() == core::mem::size_of::<Odd<BoxedUint>>()
547 );
548 const _: () = assert!(
549 core::mem::align_of::<CryptoOdd<BoxedUint>>()
550 == core::mem::align_of::<Odd<BoxedUint>>()
551 );
552 unsafe {
553 &*(self.modulus() as *const CryptoOdd<Self::Modulus> as *const Odd<Self::Modulus>)
554 }
555 }
556 fn bits_precision(&self) -> u32 {
557 self.bits_precision()
558 }
559}
560
561#[cfg(feature = "alloc")]
562impl IntegerResize for BoxedUint {
563 type Output = Self;
564
565 fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
566 CryptoResize::resize_unchecked(self, at_least_bits_precision)
567 }
568
569 fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
570 CryptoResize::try_resize(self, at_least_bits_precision)
571 }
572}
573
574#[cfg(feature = "alloc")]
575impl UnsignedModularInt for BoxedUint {
576 type Bytes = alloc::boxed::Box<[u8]>;
577
578 fn to_be_bytes(&self) -> Self::Bytes {
579 self.to_be_bytes()
580 }
581 #[cfg(feature = "alloc")]
582 fn to_be_bytes_trimmed_vartime(&self) -> Box<[u8]> {
583 self.to_be_bytes_trimmed_vartime()
584 }
585 fn as_nz_ref(&self) -> NonZero<Self> {
586 NonZero::new(self.clone()).expect("Value is non-zero")
587 }
588 fn bits(&self) -> u32 {
589 self.bits()
590 }
591 fn bits_precision(&self) -> u32 {
592 self.bits_precision()
593 }
594}
595
596#[cfg(feature = "alloc")]
597impl TryFromBeBytes for BoxedUint {
598 fn try_from_be_bytes_vartime(bytes: &[u8]) -> Result<Self> {
599 Ok(BoxedUint::from_be_slice_vartime(bytes))
600 }
601}
602
603#[cfg(all(test, feature = "modmath"))]
615mod ct_type_guarantees {
616 use super::{CtModulusParams, InvertCt, MulCt};
617 use crate::modmath_support::{ModMathForm, ModMathParams};
618 use const_num_traits::{Ct, Nct};
619 use fixed_bigint::FixedUInt;
620 use static_assertions::{assert_impl_all, assert_not_impl_any};
621 use zeroize::ZeroizeOnDrop;
622
623 assert_impl_all!(ModMathParams<FixedUInt<u8, 64, Ct>, Ct>: CtModulusParams);
632 assert_not_impl_any!(ModMathParams<FixedUInt<u8, 64, Nct>, Nct>: CtModulusParams);
633
634 assert_impl_all!(
638 ModMathForm<FixedUInt<u8, 64, Ct>, Ct>:
639 InvertCt<ModMathParams<FixedUInt<u8, 64, Ct>, Ct>>,
640 MulCt<ModMathParams<FixedUInt<u8, 64, Ct>, Ct>>
641 );
642 assert_not_impl_any!(
643 ModMathForm<FixedUInt<u8, 64, Nct>, Nct>:
644 InvertCt<ModMathParams<FixedUInt<u8, 64, Nct>, Nct>>,
645 MulCt<ModMathParams<FixedUInt<u8, 64, Nct>, Nct>>
646 );
647
648 assert_impl_all!(ModMathForm<FixedUInt<u8, 64, Ct>, Ct>: ZeroizeOnDrop);
653 assert_impl_all!(ModMathForm<FixedUInt<u8, 64, Nct>, Nct>: ZeroizeOnDrop);
654}