primeorder/tables/
radix16.rs

1//! Radix-16 signed-digit decomposition for constant-time scalar multiplication.
2
3use crate::PrimeFieldExt;
4use core::ops::{Add, Index};
5use elliptic_curve::{
6    FieldBytesSize,
7    array::{Array, ArraySize, sizes::U1},
8};
9
10/// Compute number of radix-16 digits for the given elliptic curve's scalar field.
11///
12/// Two nibbles per scalar byte, plus one carry digit for signed re-centering.
13pub type Radix16Digits<C> = <<FieldBytesSize<C> as Add>::Output as Add<U1>>::Output;
14
15/// Signed radix-16 decomposition of a scalar.
16#[derive(Clone, Debug, Default)]
17pub struct Radix16Decomposition<Digits: ArraySize> {
18    digits: Array<i8, Digits>,
19}
20
21impl<Digits: ArraySize> Radix16Decomposition<Digits> {
22    /// Decompose a scalar into signed radix-16 digits.
23    ///
24    /// Produces `[a_0, ..., a_{digits-1}]` such that `scalar = sum(a_j * 16^j)` and each `a_j` is
25    /// within `[-8, 8]`.
26    ///
27    /// `a_0` is the least significant position; `a_{digits-1}` absorbs carry: the resulting
28    /// decomposition can be negative, so we need an additional byte to store it.
29    ///
30    /// Assumes `x < 2^(4*(digits-1))`.
31    pub fn new<Scalar: PrimeFieldExt>(scalar: &Scalar) -> Self {
32        // TODO(tarcieri): `debug_assert!` that `scalar < 2^(4*(digits-1))`
33        let mut ret = Self::default();
34
35        // Step 1: change radix.
36        // Convert from big endian radix-256 (bytes) to radix-16 (nibbles).
37        let repr = scalar.to_be_repr();
38        let bytes = repr.as_ref();
39
40        #[allow(clippy::cast_possible_wrap, reason = "TODO")]
41        for i in 0..(Digits::USIZE - 1) / 2 {
42            let b = bytes[bytes.len() - 1 - i];
43            ret.digits[2 * i] = (b & 0xf) as i8;
44            ret.digits[2 * i + 1] = ((b >> 4) & 0xf) as i8;
45        }
46
47        // Step 2: recenter coefficients from [0, 16) to [-8, 8)
48        for i in 0..(Digits::USIZE - 1) {
49            let carry = (ret.digits[i] + 8) >> 4;
50            ret.digits[i] -= carry << 4;
51            ret.digits[i + 1] += carry;
52        }
53
54        ret
55    }
56}
57
58impl<Digits: ArraySize> Index<usize> for Radix16Decomposition<Digits> {
59    type Output = i8;
60
61    #[inline]
62    fn index(&self, index: usize) -> &i8 {
63        &self.digits[index]
64    }
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70    use elliptic_curve::array::sizes::{U57, U65, U133};
71
72    /// Mirror `Decomposition::new` byte extraction for raw big endian `Uint` buffers.
73    fn decompose_from_padded_be_uint<Digits: ArraySize>(
74        bytes: &[u8],
75        byte_len: usize,
76    ) -> Radix16Decomposition<Digits> {
77        let uint_byte_len = bytes.len();
78        assert!(uint_byte_len >= byte_len);
79
80        let len = 2 * byte_len + 1;
81        let mut digits = Array::<i8, Digits>::default();
82
83        #[allow(clippy::cast_possible_wrap, reason = "TODO")]
84        for i in 0..byte_len {
85            let b = bytes[uint_byte_len - 1 - i];
86            digits[2 * i] = (b & 0xf) as i8;
87            digits[2 * i + 1] = ((b >> 4) & 0xf) as i8;
88        }
89
90        for i in 0..(len - 1) {
91            let carry = (digits[i] + 8) >> 4;
92            digits[i] -= carry << 4;
93            digits[i + 1] += carry;
94        }
95
96        Radix16Decomposition { digits }
97    }
98
99    fn decompose_be_bytes<Digits: ArraySize>(bytes: &[u8]) -> Radix16Decomposition<Digits> {
100        decompose_from_padded_be_uint(bytes, bytes.len())
101    }
102
103    fn assert_digits_in_range<Digits: ArraySize>(d: &Radix16Decomposition<Digits>) {
104        for i in 0..Digits::USIZE {
105            let digit = d[i];
106            assert!((-8..=8).contains(&digit), "digit[{i}] = {digit}");
107        }
108    }
109
110    #[test]
111    fn digit_range() {
112        let d = decompose_be_bytes::<U65>(&[0xabu8; 32]);
113        assert_digits_in_range(&d);
114    }
115
116    /// p224 stores 224-bit scalars in a wider `Uint` (e.g. 32-byte U256 on 64-bit).
117    #[test]
118    fn p224_padded_uint_ignores_high_prefix() {
119        let mut bytes = [0xffu8; 32];
120        bytes[4..32].fill(0);
121        bytes[31] = 2;
122
123        let d = decompose_from_padded_be_uint::<U57>(&bytes, 28);
124        assert_eq!(d[0], 2);
125        assert_digits_in_range(&d);
126        for i in 1..57 {
127            assert_eq!(d[i], 0);
128        }
129    }
130
131    /// p521 uses a 72-byte `Uint` for a 521-bit (66-byte) scalar field.
132    #[test]
133    fn p521_padded_uint_ignores_high_prefix() {
134        let mut bytes = [0xffu8; 72];
135        bytes[6..72].fill(0);
136        bytes[71] = 3;
137
138        let d = decompose_from_padded_be_uint::<U133>(&bytes, 66);
139        assert_eq!(d[0], 3);
140        assert_digits_in_range(&d);
141        for i in 1..133 {
142            assert_eq!(d[i], 0);
143        }
144    }
145
146    #[test]
147    fn reconstruction() {
148        let bytes: [u8; 8] = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
149        let d = decompose_be_bytes::<U65>(&bytes);
150
151        let mut acc: i128 = 0;
152        let mut radix: i128 = 1;
153        for i in 0..17 {
154            acc += i128::from(d[i]) * radix;
155            radix *= 16;
156        }
157
158        let mut expected: i128 = 0;
159        for b in bytes {
160            expected = (expected << 8) | i128::from(b);
161        }
162
163        assert_eq!(acc, expected);
164    }
165
166    #[test]
167    fn zero_scalar() {
168        let d = decompose_be_bytes::<U65>(&[0u8; 32]);
169        for i in 0..65 {
170            assert_eq!(d[i], 0);
171        }
172    }
173}
primeorder/tables/radix16.rs

primeorder/tables/
radix16.rs
