crypto_bigint/
odd.rs

1//! Wrapper type for non-zero integers.
2
3use crate::{
4    Bounded, Choice, ConstOne, CtAssign, CtEq, CtOption, CtSelect, Int, Integer, Limb, Mul,
5    NonZero, One, Uint, UintRef,
6};
7use core::{cmp::Ordering, fmt, ops::Deref, ptr};
8use ctutils::{CtAssignSlice, CtEqSlice};
9
10#[cfg(feature = "alloc")]
11use crate::{BoxedUint, Resize};
12
13#[cfg(feature = "rand_core")]
14use crate::{Random, rand_core::TryRng};
15
16#[cfg(all(feature = "alloc", feature = "rand_core"))]
17use crate::RandomBits;
18
19#[cfg(feature = "serde")]
20use crate::Zero;
21#[cfg(feature = "serde")]
22use serdect::serde::{
23    Deserialize, Deserializer, Serialize, Serializer,
24    de::{Error, Unexpected},
25};
26
27/// Odd unsigned integer.
28pub type OddUint<const LIMBS: usize> = Odd<Uint<LIMBS>>;
29
30/// Odd unsigned integer reference.
31pub type OddUintRef = Odd<UintRef>;
32
33/// Odd signed integer.
34pub type OddInt<const LIMBS: usize> = Odd<Int<LIMBS>>;
35
36/// Odd boxed unsigned integer.
37#[cfg(feature = "alloc")]
38pub type OddBoxedUint = Odd<BoxedUint>;
39
40/// Wrapper type for odd integers.
41///
42/// These are frequently used in cryptography, e.g. as a modulus.
43#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, PartialOrd, Ord)]
44#[repr(transparent)]
45pub struct Odd<T: ?Sized>(T);
46
47impl<T> Odd<T> {
48    /// Create a new odd integer.
49    #[inline]
50    pub fn new(mut n: T) -> CtOption<Self>
51    where
52        T: Integer,
53    {
54        let is_odd = n.is_odd();
55
56        // Use one as a placeholder in the event an even number is provided, so functions that
57        // operate on `NonZero` values really can expect the value to never be zero, even in the
58        // case `CtOption::is_some` is false.
59        n.ct_assign(&T::one_like(&n), !is_odd);
60        CtOption::new(Self(n), is_odd)
61    }
62
63    /// Create a new [`Odd<T>`] without first checking that the contained value is odd.
64    ///
65    /// Use with care! This method bypasses invariant checks.
66    ///
67    /// # Warning: Panics
68    /// We don't explicitly flag this function as `unsafe` because it doesn't have a memory safety
69    /// impact, however functions called with `Odd` arguments assume this value is odd
70    /// and may panic if given an even value.
71    #[inline]
72    #[must_use]
73    pub(crate) const fn new_unchecked(n: T) -> Odd<T> {
74        Self(n)
75    }
76
77    /// Returns the inner value.
78    #[inline]
79    pub fn get(self) -> T {
80        self.0
81    }
82
83    /// Returns a copy of the inner value for `Copy` types.
84    ///
85    /// This allows the function to be `const fn`, since `Copy` is implicitly `!Drop`, which avoids
86    /// problems around `const fn` destructors.
87    #[inline]
88    pub const fn get_copy(self) -> T
89    where
90        T: Copy,
91    {
92        self.0
93    }
94
95    /// All odd integers are definitionally non-zero, so we can convert into
96    /// the equivalent [`NonZero`] type.
97    pub fn into_nz(self) -> NonZero<T> {
98        NonZero::new_unchecked(self.0)
99    }
100}
101
102impl<T: ?Sized> Odd<T> {
103    /// Provides access to the contents of [`Odd`] in a `const` context.
104    #[inline]
105    pub const fn as_ref(&self) -> &T {
106        &self.0
107    }
108
109    /// All odd integers are definitionally non-zero, so we can also obtain a reference to
110    /// the equivalent [`NonZero`] type.
111    #[inline]
112    pub const fn as_nz_ref(&self) -> &NonZero<T> {
113        // All `Odd` numbers are definitionally non-zero because zero is an even number
114        NonZero::new_ref_unchecked(&self.0)
115    }
116
117    /// Cast a reference to [`Odd`] without first checking that the referenced value is odd.
118    ///
119    /// Use with care! This method bypasses invariant checks.
120    ///
121    /// # Warning: Panics
122    /// We don't explicitly flag this function as `unsafe` because it doesn't have a memory safety
123    /// impact, however functions called with `Odd` arguments assume this value is odd
124    /// and may panic if given an even value.
125    #[inline]
126    #[must_use]
127    #[allow(unsafe_code)]
128    pub(crate) const fn new_ref_unchecked(refval: &T) -> &Odd<T> {
129        // SAFETY: `Odd` is a `repr(transparent)` newtype
130        unsafe { &*(ptr::from_ref(refval) as *const Odd<T>) }
131    }
132}
133
134impl<T> Odd<T>
135where
136    T: Bounded + ?Sized,
137{
138    /// Total size of the represented integer in bits.
139    pub const BITS: u32 = T::BITS;
140
141    /// Total size of the represented integer in bytes.
142    pub const BYTES: usize = T::BYTES;
143}
144
145impl<const LIMBS: usize> OddUint<LIMBS> {
146    /// Create a new [`OddUint`] from the provided big endian hex string.
147    ///
148    /// # Panics
149    /// - if the hex is malformed or not zero-padded accordingly for the size.
150    /// - if the value is even.
151    #[must_use]
152    #[track_caller]
153    pub const fn from_be_hex(hex: &str) -> Self {
154        let uint = Uint::<LIMBS>::from_be_hex(hex);
155        assert!(uint.is_odd().to_bool_vartime(), "number must be odd");
156        Odd(uint)
157    }
158
159    /// Create a new [`Odd<Uint<LIMBS>>`] from the provided little endian hex string.
160    ///
161    /// # Panics
162    /// - if the hex is malformed or not zero-padded accordingly for the size.
163    /// - if the value is even.
164    #[must_use]
165    #[track_caller]
166    pub const fn from_le_hex(hex: &str) -> Self {
167        let uint = Uint::<LIMBS>::from_le_hex(hex);
168        assert!(uint.is_odd().to_bool_vartime(), "number must be odd");
169        Odd(uint)
170    }
171
172    /// Borrow this `OddUint` as a `&OddUintRef`.
173    #[inline]
174    #[must_use]
175    pub const fn as_uint_ref(&self) -> &OddUintRef {
176        Odd::new_ref_unchecked(self.0.as_uint_ref())
177    }
178
179    /// Construct an [`Odd<Uint<T>>`] from the unsigned integer value,
180    /// truncating the upper bits if the value is too large to be
181    /// represented.
182    #[must_use]
183    pub const fn resize<const T: usize>(&self) -> Odd<Uint<T>> {
184        Odd(self.0.resize())
185    }
186}
187
188impl<const LIMBS: usize> AsRef<OddUintRef> for OddUint<LIMBS> {
189    fn as_ref(&self) -> &OddUintRef {
190        self.as_uint_ref()
191    }
192}
193
194impl<const LIMBS: usize> Odd<Int<LIMBS>> {
195    /// The sign and magnitude of this [`Odd<Int<{LIMBS}>>`].
196    #[must_use]
197    pub const fn abs_sign(&self) -> (Odd<Uint<LIMBS>>, Choice) {
198        // Absolute value of an odd value is odd
199        let (abs, sgn) = Int::abs_sign(self.as_ref());
200        (Odd(abs), sgn)
201    }
202
203    /// The magnitude of this [`Odd<Int<{LIMBS}>>`].
204    #[must_use]
205    pub const fn abs(&self) -> Odd<Uint<LIMBS>> {
206        self.abs_sign().0
207    }
208}
209
210impl<T: ?Sized> AsRef<T> for Odd<T> {
211    fn as_ref(&self) -> &T {
212        &self.0
213    }
214}
215
216impl<T> AsRef<[Limb]> for Odd<T>
217where
218    T: AsRef<[Limb]>,
219{
220    fn as_ref(&self) -> &[Limb] {
221        self.0.as_ref()
222    }
223}
224
225impl<T: ?Sized> AsRef<NonZero<T>> for Odd<T> {
226    fn as_ref(&self) -> &NonZero<T> {
227        self.as_nz_ref()
228    }
229}
230
231impl<T> CtAssign for Odd<T>
232where
233    T: CtAssign,
234{
235    #[inline]
236    fn ct_assign(&mut self, other: &Self, choice: Choice) {
237        self.0.ct_assign(&other.0, choice);
238    }
239}
240impl<T> CtAssignSlice for Odd<T> where T: CtAssignSlice {}
241
242impl<T> CtEq for Odd<T>
243where
244    T: CtEq + ?Sized,
245{
246    #[inline]
247    fn ct_eq(&self, other: &Self) -> Choice {
248        CtEq::ct_eq(&self.0, &other.0)
249    }
250}
251impl<T> CtEqSlice for Odd<T> where T: CtEq {}
252
253impl<T> CtSelect for Odd<T>
254where
255    T: CtSelect,
256{
257    #[inline]
258    fn ct_select(&self, other: &Self, choice: Choice) -> Self {
259        Self(self.0.ct_select(&other.0, choice))
260    }
261}
262
263impl<T> Default for Odd<T>
264where
265    T: One,
266{
267    #[inline]
268    fn default() -> Self {
269        Odd(T::one())
270    }
271}
272
273impl<T: ?Sized> Deref for Odd<T> {
274    type Target = T;
275
276    fn deref(&self) -> &T {
277        &self.0
278    }
279}
280
281impl<T> ConstOne for Odd<T>
282where
283    T: ConstOne + One,
284{
285    const ONE: Self = Self(T::ONE);
286}
287
288impl<T> One for Odd<T>
289where
290    T: One,
291{
292    #[inline]
293    fn one() -> Self {
294        Self(T::one())
295    }
296}
297
298impl<T> num_traits::One for Odd<T>
299where
300    T: One + Mul<T, Output = T>,
301{
302    #[inline]
303    fn one() -> Self {
304        Self(T::one())
305    }
306
307    fn is_one(&self) -> bool {
308        self.0.is_one().into()
309    }
310}
311
312/// Any odd integer multiplied by another odd integer is definitionally odd.
313impl<T> Mul<Self> for Odd<T>
314where
315    T: Mul<T, Output = T>,
316{
317    type Output = Self;
318
319    fn mul(self, rhs: Self) -> Self {
320        Self(self.0 * rhs.0)
321    }
322}
323
324impl<const LIMBS: usize> PartialEq<Odd<Uint<LIMBS>>> for Uint<LIMBS> {
325    fn eq(&self, other: &Odd<Uint<LIMBS>>) -> bool {
326        self.eq(&other.0)
327    }
328}
329
330impl<const LIMBS: usize> PartialOrd<Odd<Uint<LIMBS>>> for Uint<LIMBS> {
331    fn partial_cmp(&self, other: &Odd<Uint<LIMBS>>) -> Option<Ordering> {
332        Some(self.cmp(&other.0))
333    }
334}
335
336impl OddUintRef {
337    /// Construct an [`Odd<Uint<T>>`] from the unsigned integer value,
338    /// truncating the upper bits if the value is too large to be
339    /// represented.
340    #[must_use]
341    pub const fn to_uint_resize<const T: usize>(&self) -> Odd<Uint<T>> {
342        Odd(self.0.to_uint_resize())
343    }
344}
345
346#[cfg(feature = "alloc")]
347impl OddBoxedUint {
348    /// Borrow this `OddBoxedUint` as a `&OddUintRef`.
349    #[inline]
350    #[must_use]
351    pub const fn as_uint_ref(&self) -> &OddUintRef {
352        Odd::new_ref_unchecked(self.0.as_uint_ref())
353    }
354
355    /// Generate a random `Odd<Uint<T>>`.
356    #[cfg(feature = "rand_core")]
357    pub fn random<R: TryRng + ?Sized>(rng: &mut R, bit_length: u32) -> Self {
358        let mut ret = BoxedUint::random_bits(rng, bit_length);
359        ret.limbs[0] |= Limb::ONE;
360        Odd(ret)
361    }
362}
363
364#[cfg(feature = "alloc")]
365impl AsRef<OddUintRef> for OddBoxedUint {
366    fn as_ref(&self) -> &OddUintRef {
367        self.as_uint_ref()
368    }
369}
370
371#[cfg(feature = "alloc")]
372impl PartialEq<OddBoxedUint> for BoxedUint {
373    fn eq(&self, other: &OddBoxedUint) -> bool {
374        self.eq(&other.0)
375    }
376}
377
378#[cfg(feature = "alloc")]
379impl PartialOrd<OddBoxedUint> for BoxedUint {
380    fn partial_cmp(&self, other: &OddBoxedUint) -> Option<Ordering> {
381        Some(self.cmp(&other.0))
382    }
383}
384
385#[cfg(feature = "alloc")]
386impl Resize for OddBoxedUint {
387    type Output = Self;
388
389    fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
390        Odd(self.0.resize_unchecked(at_least_bits_precision))
391    }
392
393    fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
394        self.0.try_resize(at_least_bits_precision).map(Odd)
395    }
396}
397
398#[cfg(feature = "alloc")]
399impl Resize for &OddBoxedUint {
400    type Output = OddBoxedUint;
401
402    fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
403        Odd((&self.0).resize_unchecked(at_least_bits_precision))
404    }
405
406    fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
407        (&self.0).try_resize(at_least_bits_precision).map(Odd)
408    }
409}
410
411#[cfg(feature = "rand_core")]
412impl<const LIMBS: usize> Random for Odd<Uint<LIMBS>> {
413    /// Generate a random `Odd<Uint<T>>`.
414    fn try_random_from_rng<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
415        let mut ret = Uint::try_random_from_rng(rng)?;
416        ret.limbs[0] |= Limb::ONE;
417        Ok(Odd(ret))
418    }
419}
420
421impl<T> fmt::Display for Odd<T>
422where
423    T: fmt::Display + ?Sized,
424{
425    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
426        fmt::Display::fmt(&self.0, f)
427    }
428}
429
430impl<T> fmt::Binary for Odd<T>
431where
432    T: fmt::Binary + ?Sized,
433{
434    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
435        fmt::Binary::fmt(&self.0, f)
436    }
437}
438
439impl<T> fmt::Octal for Odd<T>
440where
441    T: fmt::Octal + ?Sized,
442{
443    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
444        fmt::Octal::fmt(&self.0, f)
445    }
446}
447
448impl<T> fmt::LowerHex for Odd<T>
449where
450    T: fmt::LowerHex + ?Sized,
451{
452    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
453        fmt::LowerHex::fmt(&self.0, f)
454    }
455}
456
457impl<T> fmt::UpperHex for Odd<T>
458where
459    T: fmt::UpperHex + ?Sized,
460{
461    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
462        fmt::UpperHex::fmt(&self.0, f)
463    }
464}
465
466#[cfg(feature = "serde")]
467impl<'de, T: Deserialize<'de> + Integer + Zero> Deserialize<'de> for Odd<T> {
468    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
469    where
470        D: Deserializer<'de>,
471    {
472        let value: T = T::deserialize(deserializer)?;
473        Option::<Self>::from(Self::new(value)).ok_or(D::Error::invalid_value(
474            Unexpected::Other("even"),
475            &"a non-zero odd value",
476        ))
477    }
478}
479
480#[cfg(feature = "serde")]
481impl<T: Serialize + Zero> Serialize for Odd<T> {
482    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
483    where
484        S: Serializer,
485    {
486        self.0.serialize(serializer)
487    }
488}
489
490#[cfg(feature = "subtle")]
491impl<T> subtle::ConditionallySelectable for Odd<T>
492where
493    T: Copy,
494    Self: CtSelect,
495{
496    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
497        a.ct_select(b, choice.into())
498    }
499}
500
501#[cfg(feature = "subtle")]
502impl<T> subtle::ConstantTimeEq for Odd<T>
503where
504    T: ?Sized,
505    Self: CtEq,
506{
507    fn ct_eq(&self, other: &Self) -> subtle::Choice {
508        CtEq::ct_eq(self, other).into()
509    }
510}
511
512#[cfg(feature = "zeroize")]
513impl<T: zeroize::Zeroize + One> zeroize::Zeroize for Odd<T> {
514    fn zeroize(&mut self) {
515        self.0.zeroize();
516        self.0 = T::one_like(&self.0);
517    }
518}
519
520#[cfg(test)]
521mod tests {
522    use super::Odd;
523    use crate::{ConstOne, U128, Uint};
524
525    #[cfg(feature = "alloc")]
526    use crate::BoxedUint;
527
528    #[cfg(feature = "zeroize")]
529    use zeroize::Zeroize;
530
531    #[test]
532    fn default() {
533        assert!(Odd::<U128>::default().is_odd().to_bool());
534    }
535
536    #[test]
537    fn from_be_hex_when_odd() {
538        assert_eq!(
539            Odd::<U128>::from_be_hex("00000000000000000000000000000001"),
540            Odd::<U128>::ONE
541        );
542    }
543
544    #[test]
545    #[should_panic]
546    fn from_be_hex_when_even() {
547        let _ = Odd::<U128>::from_be_hex("00000000000000000000000000000002");
548    }
549
550    #[test]
551    fn from_le_hex_when_odd() {
552        assert_eq!(
553            Odd::<U128>::from_le_hex("01000000000000000000000000000000"),
554            Odd::<U128>::ONE
555        );
556    }
557
558    #[test]
559    #[should_panic]
560    fn from_le_hex_when_even() {
561        let _ = Odd::<U128>::from_le_hex("20000000000000000000000000000000");
562    }
563
564    #[test]
565    fn not_odd_numbers() {
566        let zero = Odd::new(Uint::<4>::ZERO);
567        assert!(bool::from(zero.is_none()));
568        let two = Odd::new(Uint::<4>::from(2u8));
569        assert!(bool::from(two.is_none()));
570    }
571
572    #[cfg(feature = "alloc")]
573    #[test]
574    fn not_odd_numbers_boxed() {
575        let zero = Odd::new(BoxedUint::zero());
576        assert!(bool::from(zero.is_none()));
577        let two = Odd::new(BoxedUint::from(2u8));
578        assert!(bool::from(two.is_none()));
579    }
580    #[cfg(feature = "zeroize")]
581    #[test]
582    fn zeroize_preserves_invariant() {
583        let mut value = Odd::new(U128::from(0x1235u64)).unwrap();
584
585        value.zeroize();
586
587        assert_eq!(*value.as_ref(), U128::ONE);
588    }
589
590    #[cfg(all(feature = "alloc", feature = "zeroize"))]
591    #[test]
592    fn boxed_zeroize_preserves_invariant_and_precision() {
593        let mut value = Odd::new(BoxedUint::from_be_slice(&[0x12, 0x35], 128).unwrap()).unwrap();
594
595        value.zeroize();
596
597        assert_eq!(value.as_ref(), &BoxedUint::one_with_precision(128));
598        assert_eq!(value.bits_precision(), 128);
599    }
600}
crypto_bigint/odd.rs

crypto_bigint/
odd.rs
