sp1_curves/edwards/
mod.rs

1pub mod ed25519;
2
3use generic_array::GenericArray;
4use num::{BigUint, Zero};
5use serde::{Deserialize, Serialize};
6
7use super::CurveType;
8use crate::{
9    params::{FieldParameters, NumLimbs},
10    AffinePoint, EllipticCurve, EllipticCurveParameters,
11};
12
13use crate::{edwards::ed25519::Ed25519BaseField, params::NumWords};
14use typenum::Unsigned;
15
16pub type Limbs = <Ed25519BaseField as NumLimbs>::Limbs;
17pub const NUM_LIMBS: usize = Limbs::USIZE;
18
19pub type WordsFieldElement = <Ed25519BaseField as NumWords>::WordsFieldElement;
20pub const WORDS_FIELD_ELEMENT: usize = WordsFieldElement::USIZE;
21
22#[allow(unused)]
23pub type WordsCurvePoint = <Ed25519BaseField as NumWords>::WordsCurvePoint;
24pub const WORDS_CURVE_POINT: usize = WordsCurvePoint::USIZE;
25
26pub trait EdwardsParameters: EllipticCurveParameters {
27    const D: GenericArray<u8, <Self::BaseField as NumLimbs>::Limbs>;
28
29    fn generator() -> (BigUint, BigUint);
30
31    fn prime_group_order() -> BigUint;
32
33    fn d_biguint() -> BigUint {
34        let mut modulus = BigUint::zero();
35        for (i, limb) in Self::D.iter().enumerate() {
36            modulus += BigUint::from(*limb) << (8 * i);
37        }
38        modulus
39    }
40
41    fn neutral() -> (BigUint, BigUint) {
42        (BigUint::from(0u32), BigUint::from(1u32))
43    }
44}
45
46#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Serialize, Deserialize)]
47#[serde(bound = "")]
48pub struct EdwardsCurve<E: EdwardsParameters>(pub E);
49
50impl<E: EdwardsParameters> EdwardsParameters for EdwardsCurve<E> {
51    const D: GenericArray<u8, <Self::BaseField as NumLimbs>::Limbs> = E::D;
52
53    fn generator() -> (BigUint, BigUint) {
54        E::generator()
55    }
56
57    fn prime_group_order() -> BigUint {
58        E::prime_group_order()
59    }
60
61    fn d_biguint() -> BigUint {
62        E::d_biguint()
63    }
64
65    fn neutral() -> (BigUint, BigUint) {
66        E::neutral()
67    }
68}
69
70impl<E: EdwardsParameters> EllipticCurveParameters for EdwardsCurve<E> {
71    type BaseField = E::BaseField;
72    const CURVE_TYPE: CurveType = E::CURVE_TYPE;
73}
74
75impl<E: EdwardsParameters> EdwardsCurve<E> {
76    pub fn prime_group_order() -> BigUint {
77        E::prime_group_order()
78    }
79
80    pub fn neutral() -> AffinePoint<Self> {
81        let (x, y) = E::neutral();
82        AffinePoint::new(x, y)
83    }
84}
85
86impl<E: EdwardsParameters> EllipticCurve for EdwardsCurve<E> {
87    fn ec_add(p: &AffinePoint<Self>, q: &AffinePoint<Self>) -> AffinePoint<Self> {
88        p.ed_add(q)
89    }
90
91    fn ec_double(p: &AffinePoint<Self>) -> AffinePoint<Self> {
92        p.ed_double()
93    }
94
95    fn ec_generator() -> AffinePoint<Self> {
96        let (x, y) = E::generator();
97        AffinePoint::new(x, y)
98    }
99
100    fn ec_neutral() -> Option<AffinePoint<Self>> {
101        Some(Self::neutral())
102    }
103
104    fn ec_neg(p: &AffinePoint<Self>) -> AffinePoint<Self> {
105        let modulus = E::BaseField::modulus();
106        AffinePoint::new(&modulus - &p.x, p.y.clone())
107    }
108}
109
110impl<E: EdwardsParameters> AffinePoint<EdwardsCurve<E>> {
111    pub(crate) fn ed_add(
112        &self,
113        other: &AffinePoint<EdwardsCurve<E>>,
114    ) -> AffinePoint<EdwardsCurve<E>> {
115        let p = <E as EllipticCurveParameters>::BaseField::modulus();
116        let x_3n = (&self.x * &other.y + &self.y * &other.x) % &p;
117        let y_3n = (&self.y * &other.y + &self.x * &other.x) % &p;
118
119        let all_xy = (&self.x * &self.y * &other.x * &other.y) % &p;
120        let d = E::d_biguint();
121        let dxy = (d * &all_xy) % &p;
122        let den_x = ((1u32 + &dxy) % &p).modpow(&(&p - 2u32), &p);
123        let den_y = ((1u32 + &p - &dxy) % &p).modpow(&(&p - 2u32), &p);
124
125        let x_3 = (&x_3n * &den_x) % &p;
126        let y_3 = (&y_3n * &den_y) % &p;
127
128        AffinePoint::new(x_3, y_3)
129    }
130
131    pub(crate) fn ed_double(&self) -> AffinePoint<EdwardsCurve<E>> {
132        self.ed_add(self)
133    }
134}
135
136#[cfg(test)]
137mod tests {
138
139    use num::bigint::RandBigInt;
140    use rand::thread_rng;
141
142    use super::*;
143    use crate::edwards::ed25519::{Ed25519, Ed25519Parameters};
144
145    #[test]
146    fn test_bigint_ed_add() {
147        type E = Ed25519;
148        let neutral = E::neutral();
149        let base = E::ec_generator();
150
151        assert_eq!(&base + &neutral, base);
152        assert_eq!(&neutral + &base, base);
153        assert_eq!(&neutral + &neutral, neutral);
154    }
155
156    #[test]
157    fn test_biguint_scalar_mul() {
158        type E = Ed25519;
159        let base = E::ec_generator();
160
161        let d = Ed25519Parameters::d_biguint();
162        let p = <E as EllipticCurveParameters>::BaseField::modulus();
163        assert_eq!((d * 121666u32) % &p, (&p - 121665u32) % &p);
164
165        let mut rng = thread_rng();
166        for _ in 0..10 {
167            let x = rng.gen_biguint(24);
168            let y = rng.gen_biguint(25);
169
170            let x_base = &base * &x;
171            let y_x_base = &x_base * &y;
172            let xy = &x * &y;
173            let xy_base = &base * &xy;
174            assert_eq!(y_x_base, xy_base);
175        }
176
177        let order = BigUint::from(2u32).pow(252) +
178            BigUint::from(27742317777372353535851937790883648493u128);
179        assert_eq!(base, &base + &(&base * &order));
180    }
181}
sp1_curves/edwards/mod.rs

sp1_curves/edwards/
mod.rs
