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        for i in 0..(Digits::USIZE - 1) / 2 {
41            let b = bytes[bytes.len() - 1 - i];
42            ret.digits[2 * i] = (b & 0xf) as i8;
43            ret.digits[2 * i + 1] = ((b >> 4) & 0xf) as i8;
44        }
45
46        // Step 2: recenter coefficients from [0, 16) to [-8, 8)
47        for i in 0..(Digits::USIZE - 1) {
48            let carry = (ret.digits[i] + 8) >> 4;
49            ret.digits[i] -= carry << 4;
50            ret.digits[i + 1] += carry;
51        }
52
53        ret
54    }
55}
56
57impl<Digits: ArraySize> Index<usize> for Radix16Decomposition<Digits> {
58    type Output = i8;
59
60    #[inline]
61    fn index(&self, index: usize) -> &i8 {
62        &self.digits[index]
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69    use elliptic_curve::array::sizes::{U57, U65, U133};
70
71    /// Mirror `Decomposition::new` byte extraction for raw big endian `Uint` buffers.
72    fn decompose_from_padded_be_uint<Digits: ArraySize>(
73        bytes: &[u8],
74        byte_len: usize,
75    ) -> Radix16Decomposition<Digits> {
76        let uint_byte_len = bytes.len();
77        assert!(uint_byte_len >= byte_len);
78
79        let len = 2 * byte_len + 1;
80        let mut digits = Array::<i8, Digits>::default();
81
82        for i in 0..byte_len {
83            let b = bytes[uint_byte_len - 1 - i];
84            digits[2 * i] = (b & 0xf) as i8;
85            digits[2 * i + 1] = ((b >> 4) & 0xf) as i8;
86        }
87
88        for i in 0..(len - 1) {
89            let carry = (digits[i] + 8) >> 4;
90            digits[i] -= carry << 4;
91            digits[i + 1] += carry;
92        }
93
94        Radix16Decomposition { digits }
95    }
96
97    fn decompose_be_bytes<Digits: ArraySize>(bytes: &[u8]) -> Radix16Decomposition<Digits> {
98        decompose_from_padded_be_uint(bytes, bytes.len())
99    }
100
101    fn assert_digits_in_range<Digits: ArraySize>(d: &Radix16Decomposition<Digits>) {
102        for i in 0..Digits::USIZE {
103            let digit = d[i];
104            assert!((-8..=8).contains(&digit), "digit[{i}] = {digit}");
105        }
106    }
107
108    #[test]
109    fn digit_range() {
110        let d = decompose_be_bytes::<U65>(&[0xabu8; 32]);
111        assert_digits_in_range(&d);
112    }
113
114    /// p224 stores 224-bit scalars in a wider `Uint` (e.g. 32-byte U256 on 64-bit).
115    #[test]
116    fn p224_padded_uint_ignores_high_prefix() {
117        let mut bytes = [0xffu8; 32];
118        bytes[4..32].fill(0);
119        bytes[31] = 2;
120
121        let d = decompose_from_padded_be_uint::<U57>(&bytes, 28);
122        assert_eq!(d[0], 2);
123        assert_digits_in_range(&d);
124        for i in 1..57 {
125            assert_eq!(d[i], 0);
126        }
127    }
128
129    /// p521 uses a 72-byte `Uint` for a 521-bit (66-byte) scalar field.
130    #[test]
131    fn p521_padded_uint_ignores_high_prefix() {
132        let mut bytes = [0xffu8; 72];
133        bytes[6..72].fill(0);
134        bytes[71] = 3;
135
136        let d = decompose_from_padded_be_uint::<U133>(&bytes, 66);
137        assert_eq!(d[0], 3);
138        assert_digits_in_range(&d);
139        for i in 1..133 {
140            assert_eq!(d[i], 0);
141        }
142    }
143
144    #[test]
145    fn reconstruction() {
146        let bytes: [u8; 8] = [0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef];
147        let d = decompose_be_bytes::<U65>(&bytes);
148
149        let mut acc: i128 = 0;
150        let mut radix: i128 = 1;
151        for i in 0..17 {
152            acc += i128::from(d[i]) * radix;
153            radix *= 16;
154        }
155
156        let mut expected: i128 = 0;
157        for b in bytes {
158            expected = (expected << 8) | i128::from(b);
159        }
160
161        assert_eq!(acc, expected);
162    }
163
164    #[test]
165    fn zero_scalar() {
166        let d = decompose_be_bytes::<U65>(&[0u8; 32]);
167        for i in 0..65 {
168            assert_eq!(d[i], 0);
169        }
170    }
171}
primeorder/tables/radix16.rs

primeorder/tables/
radix16.rs
