crypto_bigint/uint/boxed/
encoding.rs

1//! Const-friendly decoding operations for [`BoxedUint`].
2
3use super::BoxedUint;
4use crate::{CtEq, CtOption, DecodeError, Encoding, Limb, Word, bitlen, uint::encoding};
5use alloc::{boxed::Box, string::String, vec::Vec};
6
7#[cfg(feature = "serde")]
8mod serde;
9
10impl BoxedUint {
11    /// Create a new [`BoxedUint`] from the provided big endian bytes.
12    ///
13    /// The `bits_precision` argument represents the precision of the resulting integer, which is
14    /// fixed as this type is not arbitrary-precision.
15    ///
16    /// The new [`BoxedUint`] will be created with `bits_precision`
17    /// rounded up to a multiple of [`Limb::BITS`].
18    ///
19    /// # Errors
20    /// - Returns [`DecodeError::InputSize`] if the length of `bytes` is larger than
21    ///   `bits_precision` (rounded up to a multiple of 8).
22    /// - Returns [`DecodeError::Precision`] if the size of the decoded integer is larger than
23    ///   `bits_precision`.
24    pub fn from_be_slice(bytes: &[u8], bits_precision: u32) -> Result<Self, DecodeError> {
25        if bytes.len() > bitlen::to_bytes(bits_precision) {
26            return Err(DecodeError::InputSize);
27        }
28
29        let mut ret = Self::zero_with_precision(bits_precision);
30
31        for (chunk, limb) in bytes.rchunks(Limb::BYTES).zip(ret.limbs.iter_mut()) {
32            *limb = Limb::from_be_slice(chunk);
33        }
34
35        if bits_precision < ret.bits() {
36            return Err(DecodeError::Precision);
37        }
38
39        Ok(ret)
40    }
41
42    /// Create a new [`BoxedUint`] from the provided big endian bytes, automatically selecting its
43    /// precision based on the size of the input.
44    ///
45    /// This method is variable-time with respect to all subsequent operations since it chooses the
46    /// limb count based on the input size, and is therefore only suitable for public inputs.
47    ///
48    /// When working with secret values, use [`BoxedUint::from_be_slice`].
49    #[must_use]
50    #[allow(clippy::cast_possible_truncation, clippy::missing_panics_doc)]
51    pub fn from_be_slice_vartime(bytes: &[u8]) -> Self {
52        let bits_precision = bitlen::from_bytes(bytes.len());
53
54        // TODO(tarcieri): avoid panic
55        Self::from_be_slice(bytes, bits_precision).expect("precision should be large enough")
56    }
57
58    /// Create a new [`BoxedUint`] from the provided little endian bytes.
59    ///
60    /// The `bits_precision` argument represents the precision of the resulting integer, which is
61    /// fixed as this type is not arbitrary-precision.
62    ///
63    /// The new [`BoxedUint`] will be created with `bits_precision`
64    /// rounded up to a multiple of [`Limb::BITS`].
65    ///
66    /// # Errors
67    /// - Returns [`DecodeError::InputSize`] if the length of `bytes` is larger than
68    ///   `bits_precision` (rounded up to a multiple of 8).
69    /// - Returns [`DecodeError::Precision`] if the size of the decoded integer is larger than
70    ///   `bits_precision`.
71    pub fn from_le_slice(bytes: &[u8], bits_precision: u32) -> Result<Self, DecodeError> {
72        if bytes.len() > bitlen::to_bytes(bits_precision) {
73            return Err(DecodeError::InputSize);
74        }
75
76        let mut ret = Self::zero_with_precision(bits_precision);
77
78        for (chunk, limb) in bytes.chunks(Limb::BYTES).zip(ret.limbs.iter_mut()) {
79            *limb = Limb::from_le_slice(chunk);
80        }
81
82        if bits_precision < ret.bits() {
83            return Err(DecodeError::Precision);
84        }
85
86        Ok(ret)
87    }
88
89    /// Create a new [`BoxedUint`] from the provided little endian bytes, automatically selecting
90    /// its precision based on the size of the input.
91    ///
92    /// This method is variable-time with respect to all subsequent operations since it chooses the
93    /// limb count based on the input size, and is therefore only suitable for public inputs.
94    ///
95    /// When working with secret values, use [`BoxedUint::from_le_slice`].
96    #[must_use]
97    #[allow(clippy::cast_possible_truncation, clippy::missing_panics_doc)]
98    pub fn from_le_slice_vartime(bytes: &[u8]) -> Self {
99        let bits_precision = bitlen::from_bytes(bytes.len());
100
101        // TODO(tarcieri): avoid panic
102        Self::from_le_slice(bytes, bits_precision).expect("precision should be large enough")
103    }
104
105    /// Serialize this [`BoxedUint`] as big-endian.
106    #[inline]
107    #[must_use]
108    pub fn to_be_bytes(&self) -> Box<[u8]> {
109        let mut out = vec![0u8; self.limbs.len() * Limb::BYTES];
110
111        for (src, dst) in self
112            .limbs
113            .iter()
114            .rev()
115            .cloned()
116            .zip(out.chunks_exact_mut(Limb::BYTES))
117        {
118            dst.copy_from_slice(&src.0.to_be_bytes());
119        }
120
121        out.into()
122    }
123
124    /// Serialize this [`BoxedUint`] as big-endian without leading zeroes.
125    #[inline]
126    #[must_use]
127    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
128    pub fn to_be_bytes_trimmed_vartime(&self) -> Box<[u8]> {
129        let zeroes = self.leading_zeros() as usize / 8;
130        (&self.to_be_bytes()[zeroes..]).into()
131    }
132
133    /// Serialize this [`BoxedUint`] as little-endian.
134    #[inline]
135    #[must_use]
136    pub fn to_le_bytes(&self) -> Box<[u8]> {
137        let mut out = vec![0u8; self.limbs.len() * Limb::BYTES];
138
139        for (src, dst) in self
140            .limbs
141            .iter()
142            .cloned()
143            .zip(out.chunks_exact_mut(Limb::BYTES))
144        {
145            dst.copy_from_slice(&src.0.to_le_bytes());
146        }
147
148        out.into()
149    }
150
151    /// Serialize this [`BoxedUint`] as little-endian without trailing zeroes.
152    #[inline]
153    #[must_use]
154    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
155    pub fn to_le_bytes_trimmed_vartime(&self) -> Box<[u8]> {
156        let zeroes = self.leading_zeros() as usize / 8;
157        let bytes = self.to_le_bytes();
158        (&bytes[..bytes.len() - zeroes]).into()
159    }
160
161    /// Create a new [`BoxedUint`] from the provided big endian hex string.
162    ///
163    /// # Panics
164    /// - if hex string is not the expected size
165    #[must_use]
166    pub fn from_be_hex(hex: &str, bits_precision: u32) -> CtOption<Self> {
167        let nlimbs = bitlen::to_limbs(bits_precision);
168        let bytes = hex.as_bytes();
169
170        assert_eq!(
171            bytes.len(),
172            Limb::BYTES * nlimbs * 2,
173            "hex string is not the expected size"
174        );
175
176        let mut res = vec![Limb::ZERO; nlimbs];
177        let mut buf = [0u8; Limb::BYTES];
178        let mut i = 0;
179        let mut err = 0;
180
181        while i < nlimbs {
182            let mut j = 0;
183            while j < Limb::BYTES {
184                let offset = (i * Limb::BYTES + j) * 2;
185                let (result, byte_err) =
186                    encoding::decode_hex_byte([bytes[offset], bytes[offset + 1]]);
187                err |= byte_err;
188                buf[j] = result;
189                j += 1;
190            }
191            res[nlimbs - i - 1] = Limb(Word::from_be_bytes(buf));
192            i += 1;
193        }
194
195        CtOption::new(Self { limbs: res.into() }, err.ct_eq(&0))
196    }
197
198    /// Create a new [`BoxedUint`] from a big-endian string in a given base.
199    ///
200    /// The string may begin with a `+` character, and may use underscore
201    /// characters to separate digits.
202    ///
203    /// # Errors
204    /// - Returns [`DecodeError::InvalidDigit`] if the input value contains non-digit characters or
205    ///   digits outside of the range `0..radix`.
206    ///
207    /// # Panics
208    /// - if `radix` is not in the range from 2 to 36.
209    pub fn from_str_radix_vartime(src: &str, radix: u32) -> Result<Self, DecodeError> {
210        let mut dec = VecDecodeByLimb::default();
211        encoding::radix_decode_str(src, radix, &mut dec)?;
212        Ok(Self {
213            limbs: dec.limbs.into(),
214        })
215    }
216
217    /// Create a new [`BoxedUint`] from a big-endian string in a given base,
218    /// with a given precision.
219    ///
220    /// The string may begin with a `+` character, and may use underscore
221    /// characters to separate digits.
222    ///
223    /// The `bits_precision` argument represents the precision of the resulting integer, which is
224    /// fixed as this type is not arbitrary-precision.
225    ///
226    /// The new [`BoxedUint`] will be created with `bits_precision` rounded up to a multiple
227    /// of [`Limb::BITS`].
228    ///
229    /// # Errors
230    /// - Returns [`DecodeError::InputSize`] if the length of `bytes` is larger than
231    ///   `bits_precision` (rounded up to a multiple of 8).
232    /// - Returns [`DecodeError::InvalidDigit`] if the input value contains non-digit characters or
233    ///   digits are outside the range `0..radix`.
234    /// - Returns [`DecodeError::Precision`] if the size of the decoded integer is larger than
235    ///   `bits_precision`.
236    ///
237    /// # Panics
238    /// - if `radix` is not in the range from 2 to 36.
239    pub fn from_str_radix_with_precision_vartime(
240        src: &str,
241        radix: u32,
242        bits_precision: u32,
243    ) -> Result<Self, DecodeError> {
244        let mut ret = Self::zero_with_precision(bits_precision);
245        encoding::radix_decode_str(
246            src,
247            radix,
248            &mut encoding::SliceDecodeByLimb::new(&mut ret.limbs),
249        )?;
250        if bits_precision < ret.bits() {
251            return Err(DecodeError::Precision);
252        }
253        Ok(ret)
254    }
255
256    /// Format a [`BoxedUint`] as a string in a given base.
257    ///
258    /// # Panics
259    /// - if `radix` is not in the range from 2 to 36.
260    #[must_use]
261    pub fn to_string_radix_vartime(&self, radix: u32) -> String {
262        encoding::radix_encode_limbs_to_string(radix, &self.limbs)
263    }
264}
265
266impl Encoding for BoxedUint {
267    type Repr = Box<[u8]>;
268
269    fn to_be_bytes(&self) -> Self::Repr {
270        BoxedUint::to_be_bytes(self)
271    }
272
273    fn to_le_bytes(&self) -> Self::Repr {
274        BoxedUint::to_le_bytes(self)
275    }
276
277    fn from_be_bytes(bytes: Self::Repr) -> Self {
278        BoxedUint::from_be_slice_vartime(&bytes)
279    }
280
281    fn from_le_bytes(bytes: Self::Repr) -> Self {
282        BoxedUint::from_le_slice_vartime(&bytes)
283    }
284}
285
286/// Decoder target producing a Vec<Limb>
287#[derive(Default)]
288struct VecDecodeByLimb {
289    limbs: Vec<Limb>,
290}
291
292impl encoding::DecodeByLimb for VecDecodeByLimb {
293    #[inline]
294    fn limbs_mut(&mut self) -> &mut [Limb] {
295        self.limbs.as_mut_slice()
296    }
297
298    #[inline]
299    fn push_limb(&mut self, limb: Limb) -> bool {
300        self.limbs.push(limb);
301        true
302    }
303}
304
305#[cfg(test)]
306mod tests {
307    use super::{BoxedUint, DecodeError};
308    use crate::Limb;
309    use hex_literal::hex;
310
311    cpubits::cpubits! {
312        32 => {
313            #[test]
314            fn from_be_slice_eq() {
315                let bytes = hex!("0011223344556677");
316                let n = BoxedUint::from_be_slice(&bytes, 64).unwrap();
317                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
318            }
319
320            #[test]
321            fn from_be_slice_short() {
322                let bytes = hex!("0011223344556677");
323                let n = BoxedUint::from_be_slice(&bytes, 128).unwrap();
324                assert_eq!(
325                    n.as_limbs(),
326                    &[Limb(0x44556677), Limb(0x00112233), Limb::ZERO, Limb::ZERO]
327                );
328            }
329
330            #[test]
331            fn from_be_slice_not_word_sized() {
332                let bytes = hex!("112233445566778899aabbccddeeff");
333                let n = BoxedUint::from_be_slice(&bytes, 127).unwrap();
334                assert_eq!(
335                    n.as_limbs(),
336                    &[
337                        Limb(0xccddeeff),
338                        Limb(0x8899aabb),
339                        Limb(0x44556677),
340                        Limb(0x00112233)
341                    ]
342                );
343                assert_eq!(n.bits_precision(), 128);
344            }
345
346            #[test]
347            fn from_le_slice_eq() {
348                let bytes = hex!("7766554433221100");
349                let n = BoxedUint::from_le_slice(&bytes, 64).unwrap();
350                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
351            }
352
353            #[test]
354            fn from_le_slice_short() {
355                let bytes = hex!("7766554433221100");
356                let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
357                assert_eq!(
358                    n.as_limbs(),
359                    &[Limb(0x44556677), Limb(0x00112233), Limb::ZERO, Limb::ZERO]
360                );
361            }
362
363            #[test]
364            fn from_le_slice_not_word_sized() {
365                let bytes = hex!("ffeeddccbbaa998877665544332211");
366                let n = BoxedUint::from_le_slice(&bytes, 127).unwrap();
367                assert_eq!(
368                    n.as_limbs(),
369                    &[
370                        Limb(0xccddeeff),
371                        Limb(0x8899aabb),
372                        Limb(0x44556677),
373                        Limb(0x00112233)
374                    ]
375                );
376                assert_eq!(n.bits_precision(), 128);
377            }
378        }
379        64 => {
380            #[test]
381            #[should_panic]
382            fn from_be_hex_short() {
383                let hex = "00112233445566778899aabbccddee";
384                let _ = BoxedUint::from_be_hex(hex, 128).unwrap();
385            }
386
387            #[test]
388            fn from_be_slice_eq() {
389                let bytes = hex!("00112233445566778899aabbccddeeff");
390                let n = BoxedUint::from_be_slice(&bytes, 128).unwrap();
391                assert_eq!(
392                    n.as_limbs(),
393                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
394                );
395            }
396
397            #[test]
398            fn from_be_slice_short() {
399                let bytes = hex!("00112233445566778899aabbccddeeff");
400                let n = BoxedUint::from_be_slice(&bytes, 256).unwrap();
401                assert_eq!(
402                    n.as_limbs(),
403                    &[
404                        Limb(0x8899aabbccddeeff),
405                        Limb(0x0011223344556677),
406                        Limb::ZERO,
407                        Limb::ZERO
408                    ]
409                );
410            }
411
412            #[test]
413            fn from_be_slice_not_word_sized() {
414                let bytes = hex!("112233445566778899aabbccddeeff");
415                let n = BoxedUint::from_be_slice(&bytes, 127).unwrap();
416                assert_eq!(
417                    n.as_limbs(),
418                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
419                );
420                assert_eq!(n.bits_precision(), 128);
421            }
422
423            #[test]
424            fn from_le_slice_eq() {
425                let bytes = hex!("ffeeddccbbaa99887766554433221100");
426                let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
427                assert_eq!(
428                    n.as_limbs(),
429                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
430                );
431            }
432
433            #[test]
434            fn from_le_slice_short() {
435                let bytes = hex!("ffeeddccbbaa99887766554433221100");
436                let n = BoxedUint::from_le_slice(&bytes, 256).unwrap();
437                assert_eq!(
438                    n.as_limbs(),
439                    &[
440                        Limb(0x8899aabbccddeeff),
441                        Limb(0x0011223344556677),
442                        Limb::ZERO,
443                        Limb::ZERO
444                    ]
445                );
446            }
447
448            #[test]
449            fn from_le_slice_not_word_sized() {
450                let bytes = hex!("ffeeddccbbaa998877665544332211");
451                let n = BoxedUint::from_le_slice(&bytes, 127).unwrap();
452                assert_eq!(
453                    n.as_limbs(),
454                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
455                );
456                assert_eq!(n.bits_precision(), 128);
457            }
458        }
459    }
460
461    #[test]
462    fn from_be_slice_too_long() {
463        let bytes = hex!("00112233445566778899aabbccddeeff");
464        assert_eq!(
465            BoxedUint::from_be_slice(&bytes, 64),
466            Err(DecodeError::InputSize)
467        );
468    }
469
470    #[test]
471    fn from_be_slice_non_multiple_precision() {
472        let bytes = hex!("0f112233445566778899aabbccddeeff");
473        assert_eq!(
474            BoxedUint::from_be_slice(&bytes, 121),
475            Err(DecodeError::Precision)
476        );
477    }
478
479    #[test]
480    fn from_be_slice_vartime() {
481        let bytes = hex!(
482            "111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111F"
483        );
484        let uint = BoxedUint::from_be_slice_vartime(&bytes);
485        assert_eq!(&*uint.to_be_bytes_trimmed_vartime(), bytes.as_slice());
486    }
487
488    #[test]
489    fn from_le_slice_too_long() {
490        let bytes = hex!("ffeeddccbbaa99887766554433221100");
491        assert_eq!(
492            BoxedUint::from_be_slice(&bytes, 64),
493            Err(DecodeError::InputSize)
494        );
495    }
496
497    #[test]
498    fn from_le_slice_non_multiple_precision() {
499        let bytes = hex!("ffeeddccbbaa998877665544332211f0");
500        assert_eq!(
501            BoxedUint::from_le_slice(&bytes, 121),
502            Err(DecodeError::Precision)
503        );
504    }
505
506    #[test]
507    fn from_le_slice_vartime() {
508        let bytes = hex!(
509            "111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111F"
510        );
511        let uint = BoxedUint::from_le_slice_vartime(&bytes);
512        assert_eq!(&*uint.to_le_bytes_trimmed_vartime(), bytes.as_slice());
513    }
514
515    #[test]
516    fn to_be_bytes() {
517        let bytes = hex!("00112233445566778899aabbccddeeff");
518        let n = BoxedUint::from_be_slice(&bytes, 128).unwrap();
519        assert_eq!(bytes.as_slice(), &*n.to_be_bytes());
520    }
521
522    #[test]
523    fn to_be_bytes_trimmed_vartime() {
524        let bytes = hex!("ff112233445566778899aabbccddeeff");
525        let n = BoxedUint::from_be_slice(&bytes, 128).unwrap();
526        assert_eq!(&bytes, &*n.to_be_bytes_trimmed_vartime());
527
528        let bytes = hex!("00112233445566778899aabbccddeeff");
529        let n = BoxedUint::from_be_slice(&bytes, 128).unwrap();
530        assert_eq!(&bytes.as_slice()[1..], &*n.to_be_bytes_trimmed_vartime());
531
532        let bytes: &[u8] = b"";
533        let n = BoxedUint::from_be_slice(bytes, 128).unwrap();
534        assert_eq!(
535            hex!("00000000000000000000000000000000"),
536            n.to_be_bytes().as_ref()
537        );
538        assert_eq!(bytes, n.to_be_bytes_trimmed_vartime().as_ref());
539
540        let bytes = hex!("00012233445566778899aabbccddeeff");
541        let n = BoxedUint::from_be_slice(&bytes, 128).unwrap();
542        assert_eq!(&bytes.as_slice()[1..], &*n.to_be_bytes_trimmed_vartime());
543
544        let bytes = hex!("00000000000000000000000000000001");
545        let n = BoxedUint::from_be_slice(&bytes, 128).unwrap();
546        assert_eq!(bytes, n.to_be_bytes().as_ref());
547        assert_eq!(&bytes.as_slice()[15..], &*n.to_be_bytes_trimmed_vartime());
548    }
549
550    #[test]
551    fn to_le_bytes() {
552        let bytes = hex!("ffeeddccbbaa99887766554433221100");
553        let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
554        assert_eq!(bytes.as_slice(), &*n.to_le_bytes());
555    }
556
557    #[test]
558    fn to_le_bytes_trimmed_vartime() {
559        let bytes = hex!("ffeeddccbbaa998877665544332211ff");
560        let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
561        assert_eq!(bytes.as_slice(), &*n.to_le_bytes_trimmed_vartime());
562
563        let bytes = hex!("ffeeddccbbaa99887766554433221100");
564        let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
565        assert_eq!(&bytes.as_slice()[..15], &*n.to_le_bytes_trimmed_vartime());
566
567        let bytes = hex!("ff000000000000000000000000000000");
568        let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
569        assert_eq!(&bytes.as_slice()[..1], &*n.to_le_bytes_trimmed_vartime());
570
571        let bytes = hex!("01000000000000000000000000000000");
572        let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
573        assert_eq!(&bytes.as_slice()[..1], &*n.to_le_bytes_trimmed_vartime());
574
575        let bytes = hex!("00000000000000000000000000000000");
576        let n = BoxedUint::from_le_slice(&bytes, 128).unwrap();
577        assert_eq!(b"", &*n.to_le_bytes_trimmed_vartime());
578    }
579
580    #[test]
581    fn from_str_radix_invalid() {
582        assert_eq!(
583            BoxedUint::from_str_radix_vartime("?", 10,),
584            Err(DecodeError::InvalidDigit)
585        );
586        assert_eq!(
587            BoxedUint::from_str_radix_with_precision_vartime(
588                "ffffffffffffffff_ffffffffffffffff_f",
589                16,
590                128
591            ),
592            Err(DecodeError::InputSize)
593        );
594        assert_eq!(
595            BoxedUint::from_str_radix_with_precision_vartime("1111111111111111", 2, 10),
596            Err(DecodeError::Precision)
597        );
598    }
599
600    #[test]
601    fn from_str_radix_10() {
602        let dec = "+340_282_366_920_938_463_463_374_607_431_768_211_455";
603        let res = BoxedUint::from_str_radix_vartime(dec, 10).expect("error decoding");
604        assert_eq!(res, BoxedUint::max(128));
605    }
606
607    #[test]
608    fn from_str_radix_16() {
609        let hex = "fedcba9876543210fedcba9876543210";
610        let res = BoxedUint::from_str_radix_vartime(hex, 16).expect("error decoding");
611        assert_eq!(hex, format!("{res:x}"));
612    }
613
614    #[test]
615    #[cfg(feature = "rand_core")]
616    fn encode_radix_round_trip() {
617        use crate::RandomBits;
618        use rand_core::SeedableRng;
619        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
620
621        let rounds = if cfg!(miri) { 10 } else { 100 };
622        let bits = if cfg!(miri) { 256 } else { 4096 };
623        for _ in 0..rounds {
624            let uint = BoxedUint::random_bits(&mut rng, bits);
625            for radix in 2..=36 {
626                let enc = uint.to_string_radix_vartime(radix);
627                let res = BoxedUint::from_str_radix_vartime(&enc, radix).expect("decoding error");
628                assert_eq!(
629                    res, uint,
630                    "round trip failure: radix {radix} encoded {uint} as {enc}"
631                );
632            }
633        }
634    }
635}
crypto_bigint/uint/boxed/encoding.rs

crypto_bigint/uint/boxed/
encoding.rs
