k256/
scalar.rs

1use alloc::vec::Vec;
2use core::{cmp::Ordering, ops::ShrAssign};
3
4use elliptic_curve::{
5    bigint::{ArrayEncoding, Encoding, U256},
6    ops::{Invert, Reduce},
7    rand_core::RngCore,
8    scalar::{FromUintUnchecked, IsHigh},
9    subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption},
10    zeroize::DefaultIsZeroes,
11    Field, PrimeField, ScalarPrimitive,
12};
13use hex_literal::hex;
14use openvm_algebra_guest::IntMod;
15
16use crate::{
17    internal::{seven_le, Secp256k1Scalar},
18    point::FieldBytes,
19    Secp256k1, ORDER_HEX,
20};
21
22impl Secp256k1Scalar {
23    /// Returns the SEC1 encoding of this scalar.
24    pub fn to_bytes(&self) -> FieldBytes {
25        self.to_be_bytes().into()
26    }
27}
28// --- Implement elliptic_curve traits on Secp256k1Scalar ---
29
30impl Copy for Secp256k1Scalar {}
31
32impl From<u64> for Secp256k1Scalar {
33    fn from(value: u64) -> Self {
34        Self::from_u64(value)
35    }
36}
37
38impl Default for Secp256k1Scalar {
39    fn default() -> Self {
40        <Self as IntMod>::ZERO
41    }
42}
43
44impl ConstantTimeEq for Secp256k1Scalar {
45    /// Compares raw little-endian byte representations for equality.
46    ///
47    /// **Note:** both operands must be in canonical (reduced) form.
48    /// Values created via `from_le_bytes_unchecked` or `from_be_bytes_unchecked`
49    /// must be reduced before calling `ct_eq`; otherwise two representations of
50    /// the same field element may compare as unequal.
51    fn ct_eq(&self, other: &Self) -> Choice {
52        self.as_le_bytes().ct_eq(other.as_le_bytes())
53    }
54}
55
56impl ConditionallySelectable for Secp256k1Scalar {
57    fn conditional_select(
58        a: &Secp256k1Scalar,
59        b: &Secp256k1Scalar,
60        choice: Choice,
61    ) -> Secp256k1Scalar {
62        Secp256k1Scalar::from_le_bytes_unchecked(
63            &a.as_le_bytes()
64                .iter()
65                .zip(b.as_le_bytes().iter())
66                .map(|(a, b)| u8::conditional_select(a, b, choice))
67                .collect::<Vec<_>>(),
68        )
69    }
70}
71
72impl Field for Secp256k1Scalar {
73    const ZERO: Self = <Self as IntMod>::ZERO;
74    const ONE: Self = <Self as IntMod>::ONE;
75
76    fn random(mut _rng: impl RngCore) -> Self {
77        unimplemented!()
78    }
79
80    fn square(&self) -> Self {
81        self * self
82    }
83
84    fn double(&self) -> Self {
85        self + self
86    }
87
88    fn invert(&self) -> CtOption<Self> {
89        // needs to be in canonical form for ct_eq
90        self.assert_reduced();
91        let is_zero = self.ct_eq(&<Self as IntMod>::ZERO);
92        CtOption::new(
93            <Secp256k1Scalar as openvm_algebra_guest::Field>::invert(self),
94            !is_zero,
95        )
96    }
97
98    #[allow(clippy::many_single_char_names)]
99    fn sqrt(&self) -> CtOption<Self> {
100        match <Self as openvm_algebra_guest::Sqrt>::sqrt(self) {
101            Some(sqrt) => CtOption::new(sqrt, 1.into()),
102            None => CtOption::new(<Self as Field>::ZERO, 0.into()),
103        }
104    }
105
106    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
107        ff::helpers::sqrt_ratio_generic(num, div)
108    }
109}
110
111impl PrimeField for Secp256k1Scalar {
112    type Repr = FieldBytes;
113
114    const MODULUS: &'static str = ORDER_HEX;
115    const NUM_BITS: u32 = 256;
116    const CAPACITY: u32 = 255;
117    const TWO_INV: Self = Self::from_const_bytes(hex!(
118        "a1201b68462fe9df1d50a457736e575dffffffffffffffffffffffffffffff7f"
119    ));
120    const MULTIPLICATIVE_GENERATOR: Self = Self::from_const_bytes(seven_le());
121    const S: u32 = 6;
122    const ROOT_OF_UNITY: Self = Self::from_const_bytes(hex!(
123        "f252b002544b2f9945607580b6eabd98a883c4fba37998df8619a9e760c01d0c"
124    ));
125    const ROOT_OF_UNITY_INV: Self = Self::from_const_bytes(hex!(
126        "1c0d4f88a030fbb6c313a40a9175a27772bb8c5bc7b0c7ef96702df181e13afd"
127    ));
128    const DELTA: Self = Self::from_const_bytes(hex!(
129        "0176bbc0c81794191e34e180e7783bd6c86145fe21bc0c000000000000000000"
130    ));
131
132    /// Attempts to parse the given byte array as an SEC1-encoded scalar.
133    ///
134    /// Returns None if the byte array does not contain a big-endian integer in the range
135    /// [0, p).
136    fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
137        let ret = Self::from_be_bytes_unchecked(bytes.as_slice());
138        CtOption::new(ret, (ret.is_reduced() as u8).into())
139    }
140
141    // Endianness should match from_repr
142    fn to_repr(&self) -> FieldBytes {
143        *FieldBytes::from_slice(&self.to_be_bytes())
144    }
145
146    fn is_odd(&self) -> Choice {
147        (self.as_le_bytes()[0] & 1).into()
148    }
149}
150
151impl ShrAssign<usize> for Secp256k1Scalar {
152    fn shr_assign(&mut self, _rhs: usize) {
153        // I don't think this is used anywhere
154        unimplemented!()
155    }
156}
157
158impl Reduce<U256> for Secp256k1Scalar {
159    type Bytes = FieldBytes;
160
161    fn reduce(w: U256) -> Self {
162        <Self as openvm_algebra_guest::Reduce>::reduce_le_bytes(&w.to_le_bytes())
163    }
164
165    #[inline]
166    fn reduce_bytes(bytes: &FieldBytes) -> Self {
167        Self::reduce(U256::from_be_byte_array(*bytes))
168    }
169}
170
171impl PartialOrd for Secp256k1Scalar {
172    // requires self and other to be in canonical form
173    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
174        self.assert_reduced();
175        other.assert_reduced();
176        Some(
177            self.to_be_bytes()
178                .iter()
179                .zip(other.to_be_bytes().iter())
180                .map(|(a, b)| a.cmp(b))
181                .find(|ord| *ord != Ordering::Equal)
182                .unwrap_or(Ordering::Equal),
183        )
184    }
185}
186
187impl IsHigh for Secp256k1Scalar {
188    fn is_high(&self) -> Choice {
189        // self > n/2
190        // iff self + self overflows
191        // iff self + self < self
192        ((self + self < *self) as u8).into()
193    }
194}
195
196impl Invert for Secp256k1Scalar {
197    type Output = CtOption<Self>;
198
199    fn invert(&self) -> CtOption<Self> {
200        <Self as Field>::invert(self)
201    }
202}
203
204impl FromUintUnchecked for Secp256k1Scalar {
205    type Uint = U256;
206
207    fn from_uint_unchecked(uint: Self::Uint) -> Self {
208        Self::from_le_bytes_unchecked(&uint.to_le_bytes())
209    }
210}
211
212impl From<ScalarPrimitive<Secp256k1>> for Secp256k1Scalar {
213    fn from(scalar: ScalarPrimitive<Secp256k1>) -> Self {
214        Self::from_le_bytes_unchecked(&scalar.as_uint().to_le_bytes())
215    }
216}
217
218impl From<Secp256k1Scalar> for ScalarPrimitive<Secp256k1> {
219    fn from(scalar: Secp256k1Scalar) -> ScalarPrimitive<Secp256k1> {
220        ScalarPrimitive::from_slice(&scalar.to_be_bytes()).unwrap()
221    }
222}
223
224impl DefaultIsZeroes for Secp256k1Scalar {}
225
226impl AsRef<Secp256k1Scalar> for Secp256k1Scalar {
227    fn as_ref(&self) -> &Secp256k1Scalar {
228        self
229    }
230}
231
232impl From<Secp256k1Scalar> for U256 {
233    fn from(scalar: Secp256k1Scalar) -> Self {
234        U256::from_be_slice(&scalar.to_be_bytes())
235    }
236}
237
238impl From<Secp256k1Scalar> for FieldBytes {
239    fn from(scalar: Secp256k1Scalar) -> Self {
240        *FieldBytes::from_slice(&scalar.to_be_bytes())
241    }
242}
k256/scalar.rs

k256/
scalar.rs
