class_groups/crypto_bigint/encoding/compressed/
bigint.rs

1//! Encoding of unsigned big integers of size known ahead of time
2//!
3//! ```py
4//! fn encode_bigint(bigint, bits) {
5//!   result = bigint.to_le_bytes()
6//!   # Trim any trailing zero bytes
7//!   while result.len() != 0 {
8//!     if result[result.len() - 1] == 0 {
9//!       result.pop()
10//!     }
11//!   }
12//!   # Pad this to the bound, as necessary
13//!   while result.len() < ((bits + 7) / 8) {
14//!     result.push(0)
15//!   }
16//!   return result
17//! }
18//!
19//! fn decode_bigint(bytestream, bits) {
20//!   result = []
21//!   while result.len() != ((bits + 7) / 8) {
22//!     result.push(bytestream.next_byte())
23//!   }
24//!   return BigInt::from_le_bytes(result)
25//! }
26//! ```
27//!
28//! This accepts bit bounds for the size of the integers, from which it applies a ceiling division
29//! to obtain a byte bound for the length of the encoding, but the bit bound is never strictly
30//! enforced. These methods assume the caller will ensure the encoded values were appropriate. The
31//! alignment to byte boundaries is to simplify decoding.
32
33use alloc::{vec::Vec, vec};
34
35#[cfg(feature = "std")]
36use std::io;
37
38use crypto_bigint::BoxedUint;
39
40use super::Error;
41
42/// This function runs in time variable to the input.
43pub(super) fn encode_bigint(bigint: &BoxedUint, bits: usize) -> Vec<u8> {
44  let mut result = bigint.to_le_bytes().to_vec();
45  while result.last() == Some(&0) {
46    result.pop();
47  }
48  while result.len() < bits.div_ceil(8) {
49    result.push(0);
50  }
51  result
52}
53
54/// This function runs in time variable to the input.
55#[cfg(feature = "std")]
56pub(super) fn decode_bigint(mut reader: impl io::Read, bit_bound: u32) -> Result<BoxedUint, Error> {
57  let result = BoxedUint::from_le_slice(
58    ({
59      let mut buf = vec![0xff; usize::try_from(bit_bound.div_ceil(8)).unwrap()];
60      reader.read_exact(&mut buf).map_err(|_| Error::UnexpectedEof)?;
61      buf
62    })
63    .as_slice(),
64    bit_bound,
65  )
66  .map_err(|_| Error::Overflow)?;
67  Ok(result)
68}
69
70#[test]
71fn bigint() {
72  use crypto_bigint::{RandomBits as _, Uint};
73
74  let mut rng = rand::rand_core::UnwrapErr(rand::rngs::SysRng);
75
76  let test = |value| {
77    let encoding = encode_bigint(&value, usize::try_from(value.bits_precision()).unwrap());
78    {
79      let mut encoding = encoding.as_slice();
80      assert_eq!(decode_bigint(&mut encoding, value.bits_precision()).unwrap(), value);
81      assert!(encoding.is_empty());
82    }
83    encoding
84  };
85
86  assert_eq!(test(BoxedUint::zero()), vec![0; Uint::<1>::BYTES]);
87  assert_eq!(test(BoxedUint::one()), {
88    let mut one = vec![0; Uint::<1>::BYTES];
89    one[0] = 1;
90    one
91  });
92
93  for i in 0 .. 256 {
94    test(BoxedUint::random_bits(&mut rng, 8 * i));
95  }
96
97  // TODO: Test error cases
98}
class_groups/crypto_bigint/encoding/compressed/bigint.rs

class_groups/crypto_bigint/encoding/compressed/
bigint.rs
