crypto_bigint/
uint.rs

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

crypto_bigint/
uint.rs
