arcis_compiler/utils/
elliptic_curve.rs

1use crate::{
2    core::{
3        circuits::{
4            arithmetic::{
5                sqrt,
6                AffineEdwardsPointAdditionCircuit,
7                ProjectiveEdwardsPointAdditionCircuit,
8            },
9            boolean::{boolean_value::Boolean, utils::CircuitType},
10            general::edwards_mul::ProjectiveEdwards25519MultiplicationCircuit,
11        },
12        expressions::{domain::Domain, other_expr::OtherExpr},
13        global_value::{field_array::FieldArray, value::FieldValue},
14    },
15    traits::{Equal, FromLeBytes, GetBit, Invert, Pow, Reveal, Select, WithBooleanBounds},
16    utils::{
17        curve_point::CurvePoint,
18        field::{BaseField, ScalarField},
19        number::Number,
20    },
21};
22use ff::Field;
23use std::ops::{Add, Mul, Neg, Sub};
24
25// 0 in F_{2^255-19}.
26pub const ZERO: [u8; 32] = [
27    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
28    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
29];
30
31// 1 in F_{2^255-19}.
32// ONE is in little-endian encoding.
33pub const ONE: [u8; 32] = [
34    0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
35    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
36];
37
38// The square-root of -1 in F_{2^255-19}.
39// SQRT_NEG_ONE is in little-endian encoding.
40pub const SQRT_NEG_ONE: [u8; 32] = [
41    0xb0, 0xa0, 0xe, 0x4a, 0x27, 0x1b, 0xee, 0xc4, 0x78, 0xe4, 0x2f, 0xad, 0x6, 0x18, 0x43, 0x2f,
42    0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x0, 0x4d, 0x2b, 0xb, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b,
43];
44
45/// 1/sqrt(a-d), where a = -1 (mod p) and d are the Edwards curve parameters.
46/// INVSQRT_NEG_ONE_MINUS_D is in little-endian encoding.
47pub const INVSQRT_NEG_ONE_MINUS_D: [u8; 32] = [
48    0xea, 0x40, 0x5d, 0x80, 0xaa, 0xfd, 0xc8, 0x99, 0xbe, 0x72, 0x41, 0x5a, 0x17, 0x16, 0x2f, 0x9d,
49    0x40, 0xd8, 0x1, 0xfe, 0x91, 0x7b, 0xc2, 0x16, 0xa2, 0xfc, 0xaf, 0xcf, 0x5, 0x89, 0x6c, 0x78,
50];
51
52// The equation of CURVE25519 is v^2 = u^3 + CURVE25519_A*u^2 + u over F_{2^255-19}.
53// CURVE25519_A is in little-endian encoding.
54pub const CURVE25519_A: [u8; 32] = [
55    0x6, 0x6d, 0x7, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
56    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
57];
58
59// CURVE25519_T = sqrt(-CURVE25519_A - 2). This is needed to convert between the Montgomery and
60// the Edwards model.
61// CURVE25519_T is in little-endian encoding.
62pub const CURVE25519_T: [u8; 32] = [
63    0xe7, 0x81, 0xba, 0x0, 0x55, 0xfb, 0x91, 0x33, 0x7d, 0xe5, 0x82, 0xb4, 0x2e, 0x2c, 0x5e, 0x3a,
64    0x81, 0xb0, 0x3, 0xfc, 0x23, 0xf7, 0x84, 0x2d, 0x44, 0xf9, 0x5f, 0x9f, 0xb, 0x12, 0xd9, 0x70,
65];
66
67// The equation of Edwards25519 is -x^2 + y^2 = 1 + EDWARDS25519_D*x^2*y^2 over
68// F_{2^255-19}. Note that EDWARDS25519_D = -(CURVE25519_A-2)/(CURVE25519_A+2).
69// EDWARDS25519_D is in little-endian encoding.
70pub const EDWARDS25519_D: [u8; 32] = [
71    0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75, 0xab, 0xd8, 0x41, 0x41, 0x4d, 0xa, 0x70, 0x0,
72    0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c, 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x3, 0x52,
73];
74
75// The x-coordinate of the generator G of the cyclic subgroup of prime order ell.
76// The birational map sends this point to the Montgomery point with u-coordinate = 9.
77// EDWARDS25519_G_X is in little-endian encoding.
78pub const EDWARDS25519_G_X: [u8; 32] = [
79    0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9, 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69,
80    0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0, 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21,
81];
82
83// The y-coordinate of the generator G of the cyclic subgroup of prime order ell.
84// The birational map sends this point to the Montgomery point with u-coordinate = 9.
85// EDWARDS25519_G_Y is in little-endian encoding.
86pub const EDWARDS25519_G_Y: [u8; 32] = [
87    0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
88    0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
89];
90
91// The x-coordinate of the point of order 8 with smallest y-coordinate.
92// EDWARDS25519_Q_X is in little-endian encoding.
93pub const EDWARDS25519_Q_X: [u8; 32] = [
94    0x4a, 0xd1, 0x45, 0xc5, 0x46, 0x46, 0xa1, 0xde, 0x38, 0xe2, 0xe5, 0x13, 0x70, 0x3c, 0x19, 0x5c,
95    0xbb, 0x4a, 0xde, 0x38, 0x32, 0x99, 0x33, 0xe9, 0x28, 0x4a, 0x39, 0x6, 0xa0, 0xb9, 0xd5, 0x1f,
96];
97
98// The smallest y-coordinate of a point of order 8 (a 251-bit number).
99// EDWARDS25519_Q_Y is in little-endian encoding.
100pub const EDWARDS25519_Q_Y: [u8; 32] = [
101    0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98, 0xf0,
102    0xd5, 0xdf, 0xac, 0x5, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x2, 0x88, 0x6d, 0x53, 0xfc, 0x5,
103];
104
105// The equation of Edwards25519_twist is -x^2 + y^2 = 1 + EDWARDS25519_D_TWIST*x^2*y^2
106// over F_{2^255-19}. Note that EDWARDS25519_D_TWIST = EDWARDS25519_D^{-1}.
107// EDWARDS25519_D_TWIST is in little-endian encoding.
108pub const EDWARDS25519_D_TWIST: [u8; 32] = [
109    0x43, 0xf8, 0xc9, 0xcd, 0x76, 0xf2, 0xe0, 0x25, 0x2e, 0x54, 0x79, 0x42, 0x98, 0xd6, 0x5d, 0xb,
110    0x66, 0xcf, 0xb9, 0xcd, 0x14, 0x21, 0x16, 0x2b, 0x43, 0xce, 0xd5, 0x14, 0xd2, 0x7e, 0x90, 0x40,
111];
112
113// 4^{-1} mod ell.
114// FOUR_INV_MOD_ELL is in little-endian encoding.
115pub const FOUR_INV_MOD_ELL: [u8; 32] = [
116    0xf2, 0x5e, 0xb8, 0xc5, 0x53, 0xca, 0xd, 0xc2, 0xa0, 0xb5, 0x39, 0xfa, 0x66, 0x3b, 0xa7, 0xf,
117    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc,
118];
119
120// 8^{-1} mod ell.
121// EIGHT_INV_MOD_ELL is in little-endian encoding.
122pub const EIGHT_INV_MOD_ELL: [u8; 32] = [
123    0x79, 0x2f, 0xdc, 0xe2, 0x29, 0xe5, 0x6, 0x61, 0xd0, 0xda, 0x1c, 0x7d, 0xb3, 0x9d, 0xd3, 0x7,
124    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x6,
125];
126
127// Lsb-to-msb binary expansion of ScalarField::modulus().
128pub const ELL_BIN: &str = "1011011111001011101011110011101001011000110001100100100000011010011010110011100111101111010001010111101110011111011110110010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001";
129
130/// A trait that represents BaseField-related arithmetic. Should be implememented by BaseField,
131/// FieldValue<BaseField> and FieldArray<N, BaseField>.
132pub trait F25519:
133    Add<Self, Output = Self>
134    + Sub<Self, Output = Self>
135    + Mul<Self, Output = Self>
136    + Neg<Output = Self>
137    + Pow
138    + Invert
139    + Reveal
140    + Copy
141    + WithBooleanBounds
142    + From<i32>
143    + From<Number>
144    + From<BaseField>
145{
146}
147
148impl F25519 for BaseField {}
149impl F25519 for FieldValue<BaseField> {}
150impl<const N: usize> F25519 for FieldArray<N, BaseField> {}
151
152/// Affine point on the twisted Edwards25519 curve -x^2 + y^2 = 1 + d*x^2*y^2.
153/// We set `is_on_curve: true` if we know the coordinates define a point on the curve.
154/// We set `is_ell_torsion: true` if we know the coordinates define a \ell-torsion point.
155#[derive(Debug, Clone, Copy, PartialEq)]
156pub struct AffineEdwardsPoint<T: F25519> {
157    pub x: T,
158    pub y: T,
159    pub is_on_curve: bool,
160    pub is_ell_torsion: bool,
161}
162
163#[allow(non_snake_case)]
164impl<T: F25519> AffineEdwardsPoint<T> {
165    pub fn new(P: (T, T), is_on_curve: bool, is_ell_torsion: bool) -> Self {
166        assert!(
167            is_on_curve || !is_ell_torsion,
168            "A point that is not on the curve cannot be a ell-torsion point."
169        );
170        Self {
171            x: P.0,
172            y: P.1,
173            is_on_curve,
174            is_ell_torsion,
175        }
176    }
177
178    pub fn inner(&self) -> (T, T) {
179        (self.x, self.y)
180    }
181
182    pub fn identity() -> Self {
183        Self::new((T::from(0), T::from(1)), true, true)
184    }
185
186    pub fn to_projective(self) -> ProjectiveEdwardsPoint<T> {
187        ProjectiveEdwardsPoint::new(
188            (self.x, self.y, T::from(1)),
189            self.is_on_curve,
190            self.is_ell_torsion,
191        )
192    }
193
194    /// Convert a Montgomery point to an Edwards point.
195    /// Although the birational map is not well-defined at the 2-torsion point P = (0, 0),
196    /// this function sends P to the 2-torsion point (0, -1) (as long as 0.invert() = 0).
197    pub fn from_montgomery(P: (T, T)) -> Self {
198        let (u, v) = P;
199        // send (u, v) to the Edwards curve
200        let t = T::from(BaseField::from_le_bytes(CURVE25519_T));
201        // v can be zero (for the 2-torsion point P = (0, 0) or for an invalid point)
202        let x = t * u * v.invert(false);
203        // there is no point on the curve with u-coordinate equal to -1, but P could be an invalid
204        // point
205        let y = (u - T::from(BaseField::ONE)) * (u + T::from(BaseField::ONE)).invert(false);
206        Self::new((x, y), false, false)
207    }
208
209    /// Convert an Edwards point to a Montgomery point.
210    /// Although the birational map is not well-defined at the identity and at the 2-torsion
211    /// point P = (0, -1), this function sends both points to the 2-torsion point (0, 0)
212    /// (as long as 0.invert() = 0).
213    pub fn to_montgomery(self, is_expected_non_identity: bool) -> (T, T) {
214        // send (x, y) to the Montgomery curve
215        let neg_t = -T::from(BaseField::from_le_bytes(CURVE25519_T));
216        // note: the only point with y-coordinate equal to 1 is the identity
217        let u = (T::from(BaseField::ONE) + self.y)
218            * (T::from(BaseField::ONE) - self.y)
219                .invert(self.is_on_curve && is_expected_non_identity);
220        // the identity and the 2-torsion point P = (0, -1) have x-coordinate 0
221        let v = neg_t
222            * u
223            * self
224                .x
225                .invert(self.is_on_curve && self.is_ell_torsion && is_expected_non_identity);
226        (u, v)
227    }
228
229    pub fn try_from_y<B: Boolean + Select<T, T, T>>(y: T) -> (B, Self)
230    where
231        T: GetBit<Output = B> + Equal<T, Output = B> + From<B>,
232    {
233        let y2 = y * y;
234        // here, the base is non-zero (because -d * y2 is a quadratic non-residue)
235        let b = (T::from(BaseField::ONE) + T::from(BaseField::from_le_bytes(EDWARDS25519_D)) * y2)
236            .invert(true);
237        let y2_minus_one = y2 - T::from(BaseField::ONE);
238        let x2 = y2_minus_one * b;
239        // x^2 could be zero, namely if y = 1 (the y-coordinate of the identity) or if y = -1 (the
240        // y-coordinate of the 2-torsion point). We therefore need to set is_expected_non_zero =
241        // false when calling the square-root function. However, if we mask x^2 with
242        // y^2 - 1 == 0 we can set is_expected_non_zero = true and save a couple of rounds compared
243        // to calling sqrt(x2, false), which would compute x^2 == 0.
244        let is_zero = y2_minus_one.eq(T::from(0));
245        let (is_on_curve, x) = sqrt::<BaseField, B, T>(x2 + T::from(is_zero), true);
246        let x = x - T::from(is_zero);
247        // we don't know the bools is_on_curve and is_ell_torsion at compile time
248        (is_on_curve, Self::new((x, y), false, false))
249    }
250
251    /// The point of order 8 with smallest y-coordinate (a 251-bit number).
252    pub fn eight_torsion_point() -> Self {
253        Self::new(
254            (
255                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_X)),
256                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_Y)),
257            ),
258            true,
259            false,
260        )
261    }
262}
263
264impl<T: F25519> Add for AffineEdwardsPoint<T> {
265    type Output = Self;
266
267    fn add(self, rhs: Self) -> Self::Output {
268        let addition_circuit = AffineEdwardsPointAdditionCircuit::<BaseField>::new(
269            BaseField::from_le_bytes(EDWARDS25519_D),
270        );
271        Self::new(
272            addition_circuit.add(
273                (self.inner(), self.is_on_curve),
274                (rhs.inner(), rhs.is_on_curve),
275            ),
276            self.is_on_curve && rhs.is_on_curve,
277            self.is_ell_torsion && rhs.is_ell_torsion,
278        )
279    }
280}
281
282impl<T: F25519> Sub for AffineEdwardsPoint<T> {
283    type Output = Self;
284
285    fn sub(self, rhs: Self) -> Self::Output {
286        self + (-rhs)
287    }
288}
289
290impl Mul<AffineEdwardsPoint<BaseField>> for ScalarField {
291    type Output = AffineEdwardsPoint<BaseField>;
292
293    fn mul(self, rhs: AffineEdwardsPoint<BaseField>) -> Self::Output {
294        (self * rhs.to_projective()).to_affine()
295    }
296}
297
298impl Mul<AffineEdwardsPoint<FieldValue<BaseField>>> for FieldValue<ScalarField> {
299    type Output = AffineEdwardsPoint<FieldValue<BaseField>>;
300
301    fn mul(self, rhs: AffineEdwardsPoint<FieldValue<BaseField>>) -> Self::Output {
302        (self * rhs.to_projective()).to_affine()
303    }
304}
305
306impl<T: F25519> Neg for AffineEdwardsPoint<T> {
307    type Output = Self;
308
309    fn neg(self) -> Self::Output {
310        Self::new((-self.x, self.y), self.is_on_curve, self.is_ell_torsion)
311    }
312}
313
314impl<T: F25519> Reveal for AffineEdwardsPoint<T> {
315    fn reveal(self) -> Self {
316        Self::new(
317            (self.x.reveal(), self.y.reveal()),
318            self.is_on_curve,
319            self.is_ell_torsion,
320        )
321    }
322}
323
324/// Conversion from CurvePoint to affine coordinates.
325/// Note: this clears the 4-torsion component of the representative of value, i.e.,
326/// it returns a point of order ell.
327impl From<CurvePoint> for AffineEdwardsPoint<BaseField> {
328    fn from(value: CurvePoint) -> Self {
329        let x = BaseField::unwrap(
330            OtherExpr::PlaintextCurveToExtendedEdwards(value, 0)
331                .eval()
332                .unwrap(),
333        );
334        let y = BaseField::unwrap(
335            OtherExpr::PlaintextCurveToExtendedEdwards(value, 1)
336                .eval()
337                .unwrap(),
338        );
339        Self::new((x, y), true, true)
340    }
341}
342
343/// Projective point on the twisted Edwards25519 curve -X^2*Z^2 + Y^2*Z^2 = Z^4 + d*X^2*Y^2.
344/// We set `is_on_curve: true` if we know the coordinates define a non-singular point on the curve.
345/// We set `is_ell_torsion: true` if we know the coordinates define a \ell-torsion point.
346/// Note: in the PP^2 closure, the points at infinity (1:0:0) and (0:1:0) satisfy the curve
347/// equation, but they are singularities and the addition law is not well-defined.
348#[derive(Debug, Clone, Copy)]
349#[allow(non_snake_case)]
350pub struct ProjectiveEdwardsPoint<T: F25519> {
351    pub X: T,
352    pub Y: T,
353    pub Z: T,
354    pub is_on_curve: bool,
355    pub is_ell_torsion: bool,
356}
357
358#[allow(non_snake_case)]
359impl<T: F25519> ProjectiveEdwardsPoint<T> {
360    pub fn new(P: (T, T, T), is_on_curve: bool, is_ell_torsion: bool) -> Self {
361        assert!(
362            is_on_curve || !is_ell_torsion,
363            "A point that is not on the curve cannot be a ell-torsion point."
364        );
365        Self {
366            X: P.0,
367            Y: P.1,
368            Z: P.2,
369            is_on_curve,
370            is_ell_torsion,
371        }
372    }
373
374    pub fn inner(&self) -> (T, T, T) {
375        (self.X, self.Y, self.Z)
376    }
377
378    pub fn identity() -> Self {
379        Self::new((T::from(0), T::from(1), T::from(1)), true, true)
380    }
381
382    /// Generator of the cryptographic prime order group.
383    pub fn generator() -> Self {
384        Self::new(
385            (
386                T::from(BaseField::from_le_bytes(EDWARDS25519_G_X)),
387                T::from(BaseField::from_le_bytes(EDWARDS25519_G_Y)),
388                T::from(1),
389            ),
390            true,
391            true,
392        )
393    }
394
395    /// The point of order 8 with smallest y-coordinate (a 251-bit number).
396    pub fn eight_torsion_point() -> Self {
397        Self::new(
398            (
399                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_X)),
400                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_Y)),
401                T::from(1),
402            ),
403            true,
404            false,
405        )
406    }
407
408    /// Random 8-torsion point.
409    pub fn random_eight_torsion_point<B: Boolean + Select<T, T, T>>() -> Self {
410        let rand = (0..3).map(|_| B::random()).collect::<Vec<B>>();
411        ProjectiveEdwardsPoint::eight_torsion_point().mul_bits(rand)
412    }
413
414    pub fn to_affine(self) -> AffineEdwardsPoint<T> {
415        let Z_inv = self.Z.invert(self.is_on_curve);
416        AffineEdwardsPoint::new(
417            (self.X * Z_inv, self.Y * Z_inv),
418            self.is_on_curve,
419            self.is_ell_torsion,
420        )
421    }
422
423    pub fn mul_str(&self, k: &str) -> Self {
424        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
425        Self::new(
426            multiplication_circuit.mul_str(k, self.inner(), CircuitType::default()),
427            self.is_on_curve,
428            self.is_ell_torsion,
429        )
430    }
431
432    /// Performs the multiplication k * P, where k_bits is an array of secret-shared bits and P is a
433    /// projective point on Edwards25519.
434    pub fn mul_bits<B: Boolean + Select<T, T, T>>(&self, k_bits: Vec<B>) -> Self {
435        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
436        Self::new(
437            multiplication_circuit.mul_bits(k_bits, self.inner(), CircuitType::default()),
438            self.is_on_curve,
439            self.is_ell_torsion,
440        )
441    }
442
443    /// Performs the multiplication k * G, where k_bits is an array of secret-shared bits and G is
444    /// the fixed generator of the cyclic subgroup of Edwards25519 of prime order ell.
445    pub fn mul_bits_generator<B: Boolean + Select<T, T, T>>(k_bits: Vec<B>) -> Self {
446        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
447        Self::new(
448            multiplication_circuit.mul_bits_generator(k_bits, CircuitType::default()),
449            true,
450            true,
451        )
452    }
453
454    /// Performs the clamped multiplication (2^251 + k) * 8 * self, where k is a 251-bit number.
455    pub fn mul_clamped<B: Boolean + Select<T, T, T>>(
456        &self,
457        k: [B; 251],
458    ) -> ProjectiveEdwardsPoint<T>
459    where
460        T: GetBit<Output = B>,
461    {
462        let mut k_bits = vec![B::from(false); 3];
463        k_bits.extend(k.iter());
464        k_bits.push(B::from(true));
465        self.mul_bits(k_bits)
466    }
467}
468
469impl ProjectiveEdwardsPoint<BaseField> {
470    /// Verifies if self is the identity.
471    fn is_identity(&self) -> bool {
472        self.is_on_curve && self.Z != BaseField::ZERO && self.Y == self.Z
473    }
474}
475
476impl<T: F25519> Add for ProjectiveEdwardsPoint<T> {
477    type Output = Self;
478
479    fn add(self, rhs: Self) -> Self::Output {
480        let addition_circuit = ProjectiveEdwardsPointAdditionCircuit::<BaseField>::new(
481            BaseField::from_le_bytes(EDWARDS25519_D),
482        );
483        Self::new(
484            addition_circuit.add(self.inner(), rhs.inner()),
485            self.is_on_curve && rhs.is_on_curve,
486            self.is_ell_torsion && rhs.is_ell_torsion,
487        )
488    }
489}
490
491impl<T: F25519> Sub for ProjectiveEdwardsPoint<T> {
492    type Output = Self;
493
494    fn sub(self, rhs: Self) -> Self::Output {
495        self + (-rhs)
496    }
497}
498
499impl Mul<ProjectiveEdwardsPoint<BaseField>> for ScalarField {
500    type Output = ProjectiveEdwardsPoint<BaseField>;
501
502    fn mul(self, rhs: ProjectiveEdwardsPoint<BaseField>) -> Self::Output {
503        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
504        Self::Output::new(
505            multiplication_circuit.mul(self, rhs.inner(), CircuitType::default()),
506            rhs.is_on_curve,
507            rhs.is_ell_torsion,
508        )
509    }
510}
511
512impl Mul<ProjectiveEdwardsPoint<FieldValue<BaseField>>> for FieldValue<ScalarField> {
513    type Output = ProjectiveEdwardsPoint<FieldValue<BaseField>>;
514
515    fn mul(self, rhs: ProjectiveEdwardsPoint<FieldValue<BaseField>>) -> Self::Output {
516        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
517        Self::Output::new(
518            multiplication_circuit.mul(self, rhs.inner(), CircuitType::default()),
519            rhs.is_on_curve,
520            rhs.is_ell_torsion,
521        )
522    }
523}
524
525impl<T: F25519> Neg for ProjectiveEdwardsPoint<T> {
526    type Output = Self;
527
528    fn neg(self) -> Self::Output {
529        Self::new(
530            (-self.X, self.Y, self.Z),
531            self.is_on_curve,
532            self.is_ell_torsion,
533        )
534    }
535}
536
537impl<T: F25519> Reveal for ProjectiveEdwardsPoint<T> {
538    fn reveal(self) -> Self {
539        Self::new(
540            (self.X.reveal(), self.Y.reveal(), self.Z.reveal()),
541            self.is_on_curve,
542            self.is_ell_torsion,
543        )
544    }
545}
546
547impl PartialEq for ProjectiveEdwardsPoint<BaseField> {
548    fn eq(&self, other: &Self) -> bool {
549        self.is_on_curve
550            && other.is_on_curve
551            && self.X * other.Z == other.X * self.Z
552            && self.Y * other.Z == other.Y * self.Z
553    }
554}
555
556pub fn decompress_montgomery_u<
557    T: F25519 + GetBit<Output = B> + Equal<T, Output = B> + From<B>,
558    B: Boolean + Select<T, T, T>,
559>(
560    u: T,
561) -> (B, (T, T)) {
562    let (is_on_curve, v) = sqrt::<BaseField, B, T>(
563        u * u * u + T::from(BaseField::from_le_bytes(CURVE25519_A)) * u * u + u,
564        // u is the only root of the polynomial
565        false,
566    );
567    (is_on_curve, (u, v))
568}
569
570#[allow(non_snake_case)]
571/// Returns the affine Montogmery coordinates if bytes is a valid x25519 public key, and None
572/// otherwise.
573pub fn is_valid_x25519_public_key(bytes: [u8; 32]) -> Option<(BaseField, BaseField)> {
574    match BaseField::from_le_bytes_checked(bytes) {
575        Some(u) => {
576            if u == BaseField::ZERO {
577                // In this case `u` corresponds to the point at infinity or to the point of order 2.
578                // Note that `u` cannot be the identity since the public key is obtained by a
579                // clamped multiplication between 32 random bytes and the generator.
580                // The clamped scalar is a 255-bit multiple of 8. Yet, the lcm of 8
581                // and \ell is 8 * \ell and is 256 bits long.
582                None
583            } else if u == BaseField::ONE {
584                // In this case `u` corresponds to a point of order 4.
585                None
586            } else if u
587                == BaseField::from_le_bytes([
588                    0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1,
589                    0x9f, 0xc4, 0x6a, 0xda, 0x9, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62,
590                    0x5, 0x16, 0x5f, 0x49, 0xb8, 0x0,
591                ])
592                || u == BaseField::from_le_bytes([
593                    0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c,
594                    0x83, 0xef, 0x5b, 0x4, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22,
595                    0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57,
596                ])
597            {
598                // In this case `u` corresponds to a point of order 8.
599                None
600            } else if u == BaseField::from(9) {
601                // In this case `u` corresponds to the generator G. This is not possible since the
602                // public key is obtained by a clamped multiplication between 32
603                // random bytes and the generator. The clamped scalar is a 255-bit
604                // multiple of 8. None of the 255-bit numbers 4 * \ell + 1, .., 7 *
605                // \ell + 1 is a multiple of 8.
606                None
607            } else {
608                let (is_on_curve, (u, v)) = decompress_montgomery_u(u);
609                if is_on_curve {
610                    let mut P =
611                        AffineEdwardsPoint::<BaseField>::from_montgomery((u, v)).to_projective();
612                    P.is_on_curve = true;
613                    if P.mul_str(ELL_BIN).is_identity() {
614                        Some((u, v))
615                    } else {
616                        None
617                    }
618                } else {
619                    None
620                }
621            }
622        }
623        None => None,
624    }
625}
626
627#[allow(non_snake_case)]
628/// Verify that `bytes` is a valid ed25519 signature.
629pub fn is_valid_signature(bytes: [u8; 64]) -> bool {
630    let mut R_encoded = bytes.to_vec();
631    let S = R_encoded.split_off(32);
632    let x_lsb = R_encoded[31] >> 7;
633    // clear the bit x_lsb
634    R_encoded[31] &= 127;
635    match (
636        BaseField::from_le_bytes_checked(R_encoded.try_into().unwrap_or_else(|v: Vec<u8>| {
637            panic!("Expected a Vec of length 32 (found {})", v.len())
638        })),
639        ScalarField::from_le_bytes_checked(S.try_into().unwrap_or_else(|v: Vec<u8>| {
640            panic!("Expected a Vec of length 32 (found {})", v.len())
641        })),
642    ) {
643        (Some(y), Some(_)) => {
644            if y == BaseField::ONE && x_lsb == 1u8 {
645                // In this case `y` corresponds to the identity, whose x-coordinate has lsb = 0.
646                false
647            } else if y == -BaseField::ONE {
648                // In this case `y` corresponds to the point of order 2.
649                false
650            } else if y == BaseField::ZERO {
651                // In this case `y` corresponds to a point of order 4.
652                false
653            } else if y
654                == BaseField::from_le_bytes([
655                    0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2,
656                    0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x5, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38,
657                    0x2, 0x88, 0x6d, 0x53, 0xfc, 0x5,
658                ])
659                || y == -BaseField::from_le_bytes([
660                    0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2,
661                    0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x5, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38,
662                    0x2, 0x88, 0x6d, 0x53, 0xfc, 0x5,
663                ])
664            {
665                // In this case `y` corresponds to a point of order 8.
666                false
667            } else {
668                let (is_on_curve, mut P) = AffineEdwardsPoint::try_from_y(y);
669                if is_on_curve {
670                    P.is_on_curve = true;
671                    P.to_projective().mul_str(ELL_BIN).is_identity()
672                } else {
673                    false
674                }
675            }
676        }
677        _ => false,
678    }
679}
680
681#[test]
682#[allow(non_snake_case)]
683fn test_is_valid_public_key() {
684    // The below input is randomly generated and the outcome is validated against a sagemath
685    // implementation.
686
687    let bytes1 = [
688        0xe5, 0xb5, 0xd4, 0xd0, 0x79, 0x1f, 0xe5, 0xe3, 0x5d, 0x6, 0x17, 0x1c, 0xda, 0x3d, 0x8,
689        0xe, 0x8f, 0x5f, 0x8c, 0xe9, 0xc7, 0x97, 0xbe, 0x5f, 0x10, 0x1a, 0xa, 0x64, 0x52, 0x29,
690        0x2d, 0x55,
691    ];
692    // point is on the curve but of order 4 * ell
693    assert!(is_valid_x25519_public_key(bytes1).is_none());
694
695    let bytes2 = [
696        0x7c, 0xd, 0x4a, 0x2f, 0xa9, 0x5d, 0x5e, 0x3d, 0x8e, 0xc, 0xcc, 0xdd, 0x7, 0xb3, 0x14,
697        0xcb, 0x6, 0x40, 0x56, 0x5a, 0xe5, 0xd, 0x1c, 0xc9, 0x67, 0xa7, 0xf2, 0xbc, 0x18, 0x46,
698        0x4e, 0x69,
699    ];
700    // u2 does not correspond to a point on the curve
701    assert!(is_valid_x25519_public_key(bytes2).is_none());
702
703    let bytes3 = [
704        0x9f, 0x5b, 0xe0, 0xf0, 0x6c, 0xea, 0xa2, 0x33, 0xcc, 0x1f, 0x64, 0xae, 0x36, 0xfa, 0x52,
705        0x99, 0x8a, 0x1f, 0x23, 0xe, 0x3b, 0x8e, 0xd0, 0x29, 0x2d, 0x9e, 0x11, 0xff, 0x89, 0x33,
706        0xcd, 0xd,
707    ];
708    // point is of prime order ell
709    assert!(is_valid_x25519_public_key(bytes3).is_some());
710
711    // generator G
712    let bytes_G = [
713        0x9, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
714        0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
715    ];
716    assert!(is_valid_x25519_public_key(bytes_G).is_none());
717
718    // generator G plus the 2-torsion point P = (0, 0)
719    let bytes_G_plus_P = [
720        0x12, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71,
721        0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71,
722        0x1c, 0x47,
723    ];
724    assert!(is_valid_x25519_public_key(bytes_G_plus_P).is_none());
725}
726
727#[test]
728#[allow(non_snake_case)]
729fn test_is_valid_signature() {
730    let mut sig1 = [
731        0x31, 0xa1, 0x2d, 0x8e, 0x69, 0xcf, 0x4, 0xd3, 0xf9, 0x64, 0x1d, 0x3a, 0xee, 0x59, 0x1d,
732        0xca, 0x45, 0x5a, 0x3f, 0xcf, 0xc4, 0xa7, 0x3c, 0x58, 0x8a, 0x8, 0xbb, 0x33, 0xae, 0x46,
733        0xd7, 0x1f, 0x61, 0x70, 0xba, 0xed, 0x32, 0x88, 0x30, 0xb9, 0x95, 0x45, 0x3b, 0x6e, 0xc0,
734        0xcc, 0x9e, 0xfc, 0xd, 0xd6, 0x1b, 0x94, 0xd9, 0xef, 0x1, 0xa2, 0xfa, 0xe9, 0xac, 0x69,
735        0xf, 0x7a, 0x91, 0x5,
736    ];
737    assert!(is_valid_signature(sig1));
738
739    // this makes S greater than ell
740    sig1[63] |= 64;
741    assert!(!is_valid_signature(sig1));
742
743    let mut sig2 = [
744        0xc1, 0xf7, 0xe5, 0x88, 0x54, 0x6d, 0x72, 0xb, 0xd2, 0xb9, 0x1, 0x98, 0xc8, 0x8d, 0xf3,
745        0xd0, 0x67, 0x78, 0x4, 0x25, 0x84, 0xb9, 0xd5, 0xab, 0x5c, 0x8a, 0xd, 0x48, 0x4f, 0xac,
746        0x5d, 0x30, 0x45, 0x7, 0x15, 0xaa, 0xbf, 0xd0, 0x7, 0x48, 0x49, 0xf, 0xb, 0xb1, 0x96, 0xb8,
747        0x28, 0x36, 0x22, 0xdd, 0xf9, 0xb9, 0xe0, 0xe6, 0x2b, 0x21, 0x36, 0x57, 0x9b, 0xc5, 0x5c,
748        0xa2, 0x26, 0x5,
749    ];
750    assert!(is_valid_signature(sig2));
751
752    // this makes S greater than ell
753    sig2[63] |= 128;
754    assert!(!is_valid_signature(sig2));
755}
arcis_compiler/utils/elliptic_curve.rs

arcis_compiler/utils/
elliptic_curve.rs
