crypto_bigint/
uint.rs

1//! Stack-allocated big unsigned integers.
2
3#![allow(clippy::needless_range_loop, clippy::many_single_char_names)]
4
5use core::fmt;
6
7#[cfg(feature = "serde")]
8use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
9use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
10#[cfg(feature = "zeroize")]
11use zeroize::DefaultIsZeroes;
12
13#[cfg(feature = "extra-sizes")]
14pub use extra_sizes::*;
15
16use crate::{
17    modular::{MontyForm, SafeGcdInverter},
18    Bounded, ConstCtOption, ConstZero, Constants, Encoding, FixedInteger, Int, Integer, Limb,
19    NonZero, Odd, PrecomputeInverter, PrecomputeInverterWithAdjuster, Word,
20};
21
22#[macro_use]
23mod macros;
24
25mod add;
26mod add_mod;
27mod bit_and;
28mod bit_not;
29mod bit_or;
30mod bit_xor;
31mod bits;
32mod cmp;
33mod concat;
34mod div;
35pub(crate) mod div_limb;
36pub(crate) mod encoding;
37mod from;
38mod gcd;
39mod inv_mod;
40pub(crate) mod mul;
41mod mul_mod;
42mod neg;
43mod neg_mod;
44mod resize;
45mod shl;
46mod shr;
47mod split;
48mod sqrt;
49mod sub;
50mod sub_mod;
51
52#[cfg(feature = "hybrid-array")]
53mod array;
54#[cfg(feature = "alloc")]
55pub(crate) mod boxed;
56#[cfg(feature = "rand_core")]
57mod rand;
58
59/// Stack-allocated big unsigned integer.
60///
61/// Generic over the given number of `LIMBS`
62///
63/// # Encoding support
64/// This type supports many different types of encodings, either via the
65/// [`Encoding`][`crate::Encoding`] trait or various `const fn` decoding and
66/// encoding functions that can be used with [`Uint`] constants.
67///
68/// Optional crate features for encoding (off-by-default):
69/// - `hybrid-array`: enables [`ArrayEncoding`][`crate::ArrayEncoding`] trait which can be used to
70///   [`Uint`] as `Array<u8, N>` and a [`ArrayDecoding`][`crate::ArrayDecoding`] trait which
71///   can be used to `Array<u8, N>` as [`Uint`].
72/// - `rlp`: support for [Recursive Length Prefix (RLP)][RLP] encoding.
73///
74/// [RLP]: https://eth.wiki/fundamentals/rlp
75// TODO(tarcieri): make generic around a specified number of bits.
76// Our PartialEq impl only differs from the default one by being constant-time, so this is safe
77#[allow(clippy::derived_hash_with_manual_eq)]
78#[derive(Copy, Clone, Hash)]
79pub struct Uint<const LIMBS: usize> {
80    /// Inner limb array. Stored from least significant to most significant.
81    pub(crate) limbs: [Limb; LIMBS],
82}
83
84impl<const LIMBS: usize> Uint<LIMBS> {
85    /// The value `0`.
86    pub const ZERO: Self = Self::from_u8(0);
87
88    /// The value `1`.
89    pub const ONE: Self = Self::from_u8(1);
90
91    /// Maximum value this [`Uint`] can express.
92    pub const MAX: Self = Self {
93        limbs: [Limb::MAX; LIMBS],
94    };
95
96    /// Total size of the represented integer in bits.
97    pub const BITS: u32 = LIMBS as u32 * Limb::BITS;
98
99    /// `floor(log2(Self::BITS))`.
100    // Note: assumes the type of `BITS` is `u32`. Any way to assert that?
101    pub(crate) const LOG2_BITS: u32 = u32::BITS - Self::BITS.leading_zeros() - 1;
102
103    /// Total size of the represented integer in bytes.
104    pub const BYTES: usize = LIMBS * Limb::BYTES;
105
106    /// The number of limbs used on this platform.
107    pub const LIMBS: usize = LIMBS;
108
109    /// Const-friendly [`Uint`] constructor.
110    pub const fn new(limbs: [Limb; LIMBS]) -> Self {
111        Self { limbs }
112    }
113
114    /// Create a [`Uint`] from an array of [`Word`]s (i.e. word-sized unsigned
115    /// integers).
116    #[inline]
117    pub const fn from_words(arr: [Word; LIMBS]) -> Self {
118        let mut limbs = [Limb::ZERO; LIMBS];
119        let mut i = 0;
120
121        while i < LIMBS {
122            limbs[i] = Limb(arr[i]);
123            i += 1;
124        }
125
126        Self { limbs }
127    }
128
129    /// Create an array of [`Word`]s (i.e. word-sized unsigned integers) from
130    /// a [`Uint`].
131    #[inline]
132    pub const fn to_words(self) -> [Word; LIMBS] {
133        let mut arr = [0; LIMBS];
134        let mut i = 0;
135
136        while i < LIMBS {
137            arr[i] = self.limbs[i].0;
138            i += 1;
139        }
140
141        arr
142    }
143
144    /// Borrow the inner limbs as an array of [`Word`]s.
145    pub const fn as_words(&self) -> &[Word; LIMBS] {
146        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
147        #[allow(unsafe_code)]
148        unsafe {
149            &*self.limbs.as_ptr().cast()
150        }
151    }
152
153    /// Borrow the inner limbs as a mutable array of [`Word`]s.
154    pub fn as_words_mut(&mut self) -> &mut [Word; LIMBS] {
155        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
156        #[allow(unsafe_code)]
157        unsafe {
158            &mut *self.limbs.as_mut_ptr().cast()
159        }
160    }
161
162    /// Borrow the limbs of this [`Uint`].
163    pub const fn as_limbs(&self) -> &[Limb; LIMBS] {
164        &self.limbs
165    }
166
167    /// Borrow the limbs of this [`Uint`] mutably.
168    pub const fn as_limbs_mut(&mut self) -> &mut [Limb; LIMBS] {
169        &mut self.limbs
170    }
171
172    /// Convert this [`Uint`] into its inner limbs.
173    pub const fn to_limbs(self) -> [Limb; LIMBS] {
174        self.limbs
175    }
176
177    /// Convert to a [`NonZero<Uint<LIMBS>>`].
178    ///
179    /// Returns some if the original value is non-zero, and false otherwise.
180    pub const fn to_nz(self) -> ConstCtOption<NonZero<Self>> {
181        ConstCtOption::new(NonZero(self), self.is_nonzero())
182    }
183
184    /// Convert to a [`Odd<Uint<LIMBS>>`].
185    ///
186    /// Returns some if the original value is odd, and false otherwise.
187    pub const fn to_odd(self) -> ConstCtOption<Odd<Self>> {
188        ConstCtOption::new(Odd(self), self.is_odd())
189    }
190
191    /// Interpret the data in this type as an [`Int`] instead.
192    pub const fn as_int(&self) -> Int<LIMBS> {
193        Int::from_bits(*self)
194    }
195}
196
197impl<const LIMBS: usize> AsRef<[Word; LIMBS]> for Uint<LIMBS> {
198    fn as_ref(&self) -> &[Word; LIMBS] {
199        self.as_words()
200    }
201}
202
203impl<const LIMBS: usize> AsMut<[Word; LIMBS]> for Uint<LIMBS> {
204    fn as_mut(&mut self) -> &mut [Word; LIMBS] {
205        self.as_words_mut()
206    }
207}
208
209impl<const LIMBS: usize> AsRef<[Limb]> for Uint<LIMBS> {
210    fn as_ref(&self) -> &[Limb] {
211        self.as_limbs()
212    }
213}
214
215impl<const LIMBS: usize> AsMut<[Limb]> for Uint<LIMBS> {
216    fn as_mut(&mut self) -> &mut [Limb] {
217        self.as_limbs_mut()
218    }
219}
220
221impl<const LIMBS: usize> ConditionallySelectable for Uint<LIMBS> {
222    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
223        let mut limbs = [Limb::ZERO; LIMBS];
224
225        for i in 0..LIMBS {
226            limbs[i] = Limb::conditional_select(&a.limbs[i], &b.limbs[i], choice);
227        }
228
229        Self { limbs }
230    }
231}
232
233impl<const LIMBS: usize> Bounded for Uint<LIMBS> {
234    const BITS: u32 = Self::BITS;
235    const BYTES: usize = Self::BYTES;
236}
237
238impl<const LIMBS: usize> Constants for Uint<LIMBS> {
239    const ONE: Self = Self::ONE;
240    const MAX: Self = Self::MAX;
241}
242
243impl<const LIMBS: usize> Default for Uint<LIMBS> {
244    fn default() -> Self {
245        Self::ZERO
246    }
247}
248
249impl<const LIMBS: usize> FixedInteger for Uint<LIMBS> {
250    const LIMBS: usize = LIMBS;
251}
252
253impl<const LIMBS: usize> Integer for Uint<LIMBS> {
254    type Monty = MontyForm<LIMBS>;
255
256    fn one() -> Self {
257        Self::ONE
258    }
259
260    fn from_limb_like(limb: Limb, _other: &Self) -> Self {
261        Self::from(limb)
262    }
263
264    fn nlimbs(&self) -> usize {
265        Self::LIMBS
266    }
267}
268
269impl<const LIMBS: usize> num_traits::Num for Uint<LIMBS> {
270    type FromStrRadixErr = crate::DecodeError;
271
272    /// ⚠️ WARNING: `from_str_radix` impl operates in variable-time with respect to the input.
273    fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
274        Self::from_str_radix_vartime(str, radix)
275    }
276}
277
278impl<const LIMBS: usize> ConstZero for Uint<LIMBS> {
279    const ZERO: Self = Self::ZERO;
280}
281
282impl<const LIMBS: usize> num_traits::Zero for Uint<LIMBS> {
283    fn zero() -> Self {
284        Self::ZERO
285    }
286
287    fn is_zero(&self) -> bool {
288        self.ct_eq(&Self::ZERO).into()
289    }
290}
291
292impl<const LIMBS: usize> num_traits::One for Uint<LIMBS> {
293    fn one() -> Self {
294        Self::ONE
295    }
296
297    fn is_one(&self) -> bool {
298        self.ct_eq(&Self::ONE).into()
299    }
300}
301
302impl<const LIMBS: usize> fmt::Debug for Uint<LIMBS> {
303    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
304        write!(f, "Uint(0x{self:X})")
305    }
306}
307
308impl<const LIMBS: usize> fmt::Binary for Uint<LIMBS> {
309    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
310        for limb in self.limbs.iter().rev() {
311            fmt::Binary::fmt(limb, f)?;
312        }
313        Ok(())
314    }
315}
316
317impl<const LIMBS: usize> fmt::Display for Uint<LIMBS> {
318    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
319        fmt::UpperHex::fmt(self, f)
320    }
321}
322
323impl<const LIMBS: usize> fmt::LowerHex for Uint<LIMBS> {
324    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
325        for limb in self.limbs.iter().rev() {
326            fmt::LowerHex::fmt(limb, f)?;
327        }
328        Ok(())
329    }
330}
331
332impl<const LIMBS: usize> fmt::UpperHex for Uint<LIMBS> {
333    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
334        for limb in self.limbs.iter().rev() {
335            fmt::UpperHex::fmt(limb, f)?;
336        }
337        Ok(())
338    }
339}
340
341#[cfg(feature = "serde")]
342impl<'de, const LIMBS: usize> Deserialize<'de> for Uint<LIMBS>
343where
344    Uint<LIMBS>: Encoding,
345{
346    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
347    where
348        D: Deserializer<'de>,
349    {
350        let mut buffer = Self::ZERO.to_le_bytes();
351        serdect::array::deserialize_hex_or_bin(buffer.as_mut(), deserializer)?;
352
353        Ok(Self::from_le_bytes(buffer))
354    }
355}
356
357#[cfg(feature = "serde")]
358impl<const LIMBS: usize> Serialize for Uint<LIMBS>
359where
360    Uint<LIMBS>: Encoding,
361{
362    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
363    where
364        S: Serializer,
365    {
366        serdect::array::serialize_hex_lower_or_bin(&Encoding::to_le_bytes(self), serializer)
367    }
368}
369
370#[cfg(feature = "zeroize")]
371impl<const LIMBS: usize> DefaultIsZeroes for Uint<LIMBS> {}
372
373// TODO(tarcieri): use `generic_const_exprs` when stable to make generic around bits.
374impl_uint_aliases! {
375    (U64, 64, "64-bit"),
376    (U128, 128, "128-bit"),
377    (U192, 192, "192-bit"),
378    (U256, 256, "256-bit"),
379    (U320, 320, "320-bit"),
380    (U384, 384, "384-bit"),
381    (U448, 448, "448-bit"),
382    (U512, 512, "512-bit"),
383    (U576, 576, "576-bit"),
384    (U640, 640, "640-bit"),
385    (U704, 704, "704-bit"),
386    (U768, 768, "768-bit"),
387    (U832, 832, "832-bit"),
388    (U896, 896, "896-bit"),
389    (U960, 960, "960-bit"),
390    (U1024, 1024, "1024-bit"),
391    (U1280, 1280, "1280-bit"),
392    (U1536, 1536, "1536-bit"),
393    (U1792, 1792, "1792-bit"),
394    (U2048, 2048, "2048-bit"),
395    (U3072, 3072, "3072-bit"),
396    (U3584, 3584, "3584-bit"),
397    (U4096, 4096, "4096-bit"),
398    (U4224, 4224, "4224-bit"),
399    (U4352, 4352, "4352-bit"),
400    (U6144, 6144, "6144-bit"),
401    (U8192, 8192, "8192-bit"),
402    (U16384, 16384, "16384-bit"),
403    (U32768, 32768, "32768-bit")
404}
405
406#[cfg(target_pointer_width = "32")]
407impl_uint_aliases! {
408    (U224, 224, "224-bit"), // For NIST P-224
409    (U544, 544, "544-bit")  // For NIST P-521
410}
411
412#[cfg(target_pointer_width = "32")]
413impl_uint_concat_split_even! {
414    U64,
415}
416
417// Implement concat and split for double-width Uint sizes: these should be
418// multiples of 128 bits.
419impl_uint_concat_split_even! {
420    U128,
421    U256,
422    U384,
423    U512,
424    U640,
425    U768,
426    U896,
427    U1024,
428    U1280,
429    U1536,
430    U1792,
431    U2048,
432    U3072,
433    U3584,
434    U4096,
435    U4224,
436    U4352,
437    U6144,
438    U8192,
439    U16384,
440}
441
442// Implement mixed concat, split and reduce for combinations not implemented by
443// impl_uint_concat_split_even. The numbers represent the size of each
444// component Uint in multiple of 64 bits. For example,
445// (U256, [1, 3]) will allow splitting U256 into (U64, U192) as well as
446// (U192, U64), while the (U128, U128) combination is already covered.
447impl_uint_concat_split_mixed! {
448    (U192, [1, 2]),
449    (U256, [1, 3]),
450    (U320, [1, 2, 3, 4]),
451    (U384, [1, 2, 4, 5]),
452    (U448, [1, 2, 3, 4, 5, 6]),
453    (U512, [1, 2, 3, 5, 6, 7]),
454    (U576, [1, 2, 3, 4, 5, 6, 7, 8]),
455    (U640, [1, 2, 3, 4, 6, 7, 8, 9]),
456    (U704, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]),
457    (U768, [1, 2, 3, 4, 5, 7, 8, 9, 10, 11]),
458    (U832, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]),
459    (U896, [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]),
460    (U960, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]),
461    (U1024, [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]),
462}
463
464#[cfg(feature = "extra-sizes")]
465mod extra_sizes;
466
467#[cfg(test)]
468#[allow(clippy::unwrap_used)]
469mod tests {
470    #[cfg(feature = "alloc")]
471    use alloc::format;
472
473    use subtle::ConditionallySelectable;
474
475    #[cfg(feature = "serde")]
476    use crate::U64;
477    use crate::{Encoding, U128};
478
479    #[cfg(target_pointer_width = "64")]
480    #[test]
481    fn as_words() {
482        let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
483        assert_eq!(n.as_words(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
484    }
485
486    #[cfg(target_pointer_width = "64")]
487    #[test]
488    fn as_words_mut() {
489        let mut n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
490        assert_eq!(n.as_words_mut(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
491    }
492
493    #[cfg(feature = "alloc")]
494    #[test]
495    fn debug() {
496        let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
497
498        assert_eq!(
499            format!("{:?}", n),
500            "Uint(0xAAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD)"
501        );
502    }
503
504    #[cfg(feature = "alloc")]
505    #[test]
506    fn display() {
507        let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
508        let n = U128::from_be_hex(hex);
509
510        use alloc::string::ToString;
511        assert_eq!(hex, n.to_string());
512
513        let hex = "AAAAAAAABBBBBBBB0000000000000000";
514        let n = U128::from_be_hex(hex);
515        assert_eq!(hex, n.to_string());
516
517        let hex = "AAAAAAAABBBBBBBB00000000DDDDDDDD";
518        let n = U128::from_be_hex(hex);
519        assert_eq!(hex, n.to_string());
520
521        let hex = "AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD";
522        let n = U128::from_be_hex(hex);
523        assert_eq!(hex, n.to_string());
524    }
525
526    #[test]
527    fn from_bytes() {
528        let a = U128::from_be_hex("AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD");
529
530        let be_bytes = a.to_be_bytes();
531        let le_bytes = a.to_le_bytes();
532        for i in 0..16 {
533            assert_eq!(le_bytes[i], be_bytes[15 - i]);
534        }
535
536        let a_from_be = U128::from_be_bytes(be_bytes);
537        let a_from_le = U128::from_le_bytes(le_bytes);
538        assert_eq!(a_from_be, a_from_le);
539        assert_eq!(a_from_be, a);
540    }
541
542    #[test]
543    fn conditional_select() {
544        let a = U128::from_be_hex("00002222444466668888AAAACCCCEEEE");
545        let b = U128::from_be_hex("11113333555577779999BBBBDDDDFFFF");
546
547        let select_0 = U128::conditional_select(&a, &b, 0.into());
548        assert_eq!(a, select_0);
549
550        let select_1 = U128::conditional_select(&a, &b, 1.into());
551        assert_eq!(b, select_1);
552    }
553
554    #[cfg(feature = "serde")]
555    #[test]
556    fn serde() {
557        const TEST: U64 = U64::from_u64(0x0011223344556677);
558
559        let serialized = bincode::serialize(&TEST).unwrap();
560        let deserialized: U64 = bincode::deserialize(&serialized).unwrap();
561
562        assert_eq!(TEST, deserialized);
563    }
564
565    #[cfg(feature = "serde")]
566    #[test]
567    fn serde_owned() {
568        const TEST: U64 = U64::from_u64(0x0011223344556677);
569
570        let serialized = bincode::serialize(&TEST).unwrap();
571        let deserialized: U64 = bincode::deserialize_from(serialized.as_slice()).unwrap();
572
573        assert_eq!(TEST, deserialized);
574    }
575}
crypto_bigint/uint.rs

crypto_bigint/
uint.rs
