ark-curves-cherry-picked/bls12_377/src/curves/g1.rs
bls12_377/src/curves/g1.rsRaw
1use ark_ec::{
2 bls12::Bls12Config,
3 models::{
4 short_weierstrass::{Affine as SWAffine, SWCurveConfig},
5 twisted_edwards::{
6 Affine as TEAffine, MontCurveConfig, Projective as TEProjective, TECurveConfig,
7 },
8 },
9 CurveConfig,
10};
11use ark_ff::{Field, MontFp, PrimeField, Zero};
12use ark_std::{ops::Neg, One};
13
14use crate::{Fq, Fr};
15
16#[derive(Clone, Default, PartialEq, Eq)]
17pub struct Config;
18
19impl CurveConfig for Config {
20 type BaseField = Fq;
21 type ScalarField = Fr;
22
23 /// COFACTOR = (x - 1)^2 / 3 = 30631250834960419227450344600217059328
24 const COFACTOR: &'static [u64] = &[0x0, 0x170b5d4430000000];
25
26 /// COFACTOR_INV = COFACTOR^{-1} mod r
27 /// = 5285428838741532253824584287042945485047145357130994810877
28 const COFACTOR_INV: Fr = MontFp!("5285428838741532253824584287042945485047145357130994810877");
29}
30
31impl SWCurveConfig for Config {
32 /// COEFF_A = 0
33 const COEFF_A: Fq = Fq::ZERO;
34
35 /// COEFF_B = 1
36 const COEFF_B: Fq = Fq::ONE;
37
38 /// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
39 const GENERATOR: G1SWAffine = G1SWAffine::new_unchecked(G1_GENERATOR_X, G1_GENERATOR_Y);
40
41 #[inline(always)]
42 fn mul_by_a(_: Self::BaseField) -> Self::BaseField {
43 Self::BaseField::zero()
44 }
45
46 #[inline]
47 fn clear_cofactor(p: &G1SWAffine) -> G1SWAffine {
48 // Using the effective cofactor.
49 //
50 // It is enough to multiply by (x - 1), instead of (x - 1)^2 / 3
51 let h_eff = x_minus_one().into_bigint();
52 <Config as SWCurveConfig>::mul_affine(p, h_eff.as_ref()).into()
53 }
54}
55
56fn x_minus_one() -> Fr {
57 const X: Fr = Fr::from_sign_and_limbs(!crate::Config::X_IS_NEGATIVE, crate::Config::X);
58 X - Fr::one()
59}
60
61pub type G1SWAffine = SWAffine<Config>;
62pub type G1TEAffine = TEAffine<Config>;
63pub type G1TEProjective = TEProjective<Config>;
64
65/// Bls12_377::G1 also has a twisted Edwards form.
66/// It can be obtained via the following script, implementing
67/// 1. SW -> Montgomery -> TE1 transformation: <https://en.wikipedia.org/wiki/Montgomery_curve>
68/// 2. TE1 -> TE2 normalization (enforcing `a = -1`)
69/// ``` sage
70/// # modulus
71/// p = 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
72/// Fp = Zmod(p)
73///
74/// #####################################################
75/// # Weierstrass curve: y² = x³ + A * x + B
76/// #####################################################
77/// # curve y^2 = x^3 + 1
78/// WA = Fp(0)
79/// WB = Fp(1)
80///
81/// #####################################################
82/// # Montgomery curve: By² = x³ + A * x² + x
83/// #####################################################
84/// # root for x^3 + 1 = 0
85/// alpha = -1
86/// # s = 1 / (sqrt(3alpha^2 + a))
87/// s = 1/(Fp(3).sqrt())
88///
89/// # MA = 3 * alpha * s
90/// MA = Fp(228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384)
91/// # MB = s
92/// MB = Fp(10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931)
93///
94/// # #####################################################
95/// # # Twisted Edwards curve 1: a * x² + y² = 1 + d * x² * y²
96/// # #####################################################
97/// # We first convert to TE form obtaining a curve with a != -1, and then
98/// # apply a transformation to obtain a TE curve with a = -1.
99/// # a = (MA+2)/MB
100/// TE1a = Fp(61134141799337779744243169579317764548490943457438569789767076791016838392692895365021181670618017873462480451583)
101/// # b = (MA-2)/MB
102/// TE1d = Fp(197530284213631314266409564115575768987902569297476090750117185875703629955647927409947706468955342250977841006588)
103///
104/// # #####################################################
105/// # # Twisted Edwards curve 2: a * x² + y² = 1 + d * x² * y²
106/// # #####################################################
107/// # a = -1
108/// TE2a = Fp(-1)
109/// # b = -TE1d/TE1a
110/// TE2d = Fp(122268283598675559488486339158635529096981886914877139579534153582033676785385790730042363341236035746924960903179)
111/// ```
112impl TECurveConfig for Config {
113 /// COEFF_A = -1
114 const COEFF_A: Fq = MontFp!("-1");
115
116 /// COEFF_D = 122268283598675559488486339158635529096981886914877139579534153582033676785385790730042363341236035746924960903179 mod q
117 const COEFF_D: Fq = MontFp!("122268283598675559488486339158635529096981886914877139579534153582033676785385790730042363341236035746924960903179");
118
119 /// AFFINE_GENERATOR_COEFFS = (GENERATOR_X, GENERATOR_Y)
120 const GENERATOR: G1TEAffine = G1TEAffine::new_unchecked(TE_GENERATOR_X, TE_GENERATOR_Y);
121
122 type MontCurveConfig = Config;
123
124 /// Multiplication by `a` is multiply by `-1`.
125 #[inline(always)]
126 fn mul_by_a(elem: Self::BaseField) -> Self::BaseField {
127 elem.neg()
128 }
129}
130
131// BLS12-377::G1 also has a Montgomery form.
132// BLS12-377::G1 also has a twisted Edwards form.
133// It can be obtained via the following script, implementing
134// SW -> Montgomery transformation: <https://en.wikipedia.org/wiki/Montgomery_curve>
135// ``` sage
136// # modulus
137// p=0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
138// Fp=Zmod(p)
139//
140// #####################################################
141// # Weierstrass curve: y² = x³ + A * x + B
142// #####################################################
143// # curve y^2 = x^3 + 1
144// WA=Fp(0)
145// WB=Fp(1)
146//
147// #####################################################
148// # Montgomery curve: By² = x³ + A * x² + x
149// #####################################################
150// # root for x^3 + 1 = 0
151// alpha = -1
152// # s = 1 / (sqrt(3alpha^2 + a))
153// s = 1/(Fp(3).sqrt())
154//
155// # MA = 3 * alpha * s
156// MA=Fp(228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384)
157// # MB = s
158// MB=Fp(10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931)
159// ```
160impl MontCurveConfig for Config {
161 /// COEFF_A = 228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384
162 const COEFF_A: Fq = MontFp!("228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384");
163
164 /// COEFF_B = 10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931
165 const COEFF_B: Fq = MontFp!("10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931");
166
167 type TECurveConfig = Config;
168}
169
170/// G1_GENERATOR_X =
171/// 81937999373150964239938255573465948239988671502647976594219695644855304257327692006745978603320413799295628339695
172pub const G1_GENERATOR_X: Fq = MontFp!("81937999373150964239938255573465948239988671502647976594219695644855304257327692006745978603320413799295628339695");
173
174/// G1_GENERATOR_Y =
175/// 241266749859715473739788878240585681733927191168601896383759122102112907357779751001206799952863815012735208165030
176pub const G1_GENERATOR_Y: Fq = MontFp!("241266749859715473739788878240585681733927191168601896383759122102112907357779751001206799952863815012735208165030");
177
178// The generator for twisted Edward form is the same SW generator converted into
179// the normalized TE form (TE2).
180//``` sage
181// # following scripts in previous section
182// #####################################################
183// # Weierstrass curve generator
184// #####################################################
185// Wx = Fp(81937999373150964239938255573465948239988671502647976594219695644855304257327692006745978603320413799295628339695)
186// Wy = Fp(241266749859715473739788878240585681733927191168601896383759122102112907357779751001206799952863815012735208165030)
187//
188// assert(Wy^2 - Wx^3 - WA * Wx - WB == 0)
189//
190// #####################################################
191// # Montgomery curve generator
192// #####################################################
193// # x = s * (x - alpha)
194// Mx = Fp(251803586774461569862800610331871502335378228972505599912537082323947581271784390797244487924068052270360793200630)
195// # y = s * y
196// My = Fp(77739247071951651095607889637653357561348174979132042929587539214321586851215673796661346812932566642719051699820)
197//
198// assert(MB * My^2 == Mx^3+ MA * Mx^2 + Mx)
199//
200// # #####################################################
201// # # Twisted Edwards curve 1 generator
202// # #####################################################
203// # x = Mx/My
204// TE1x = Fp(82241236807150726090333472814441006963902378430536027612759193445733851062772474760677400112551677454953925168208)
205// # y = (Mx - 1)/(Mx+1)
206// TE1y = Fp(6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235)
207//
208// assert( TE1a * TE1x^2 + TE1y^2 == 1 + TE1d * TE1x^2 * TE1y^2 )
209//
210//
211// # #####################################################
212// # # Twisted Edwards curve 2 generator
213// # #####################################################
214// beta = (-TE1a).sqrt()
215// # x = TE1x * sqrt(-TE1a)
216// TE2x = Fp(71222569531709137229370268896323705690285216175189308202338047559628438110820800641278662592954630774340654489393)
217// # y = TE1y
218// TE2y = Fp(6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235)
219//
220// assert( TE2a * TE2x^2 + TE2y^2 == 1 + TE2d * TE2x^2 * TE2y^2 )
221// ```
222/// TE_GENERATOR_X =
223/// 71222569531709137229370268896323705690285216175189308202338047559628438110820800641278662592954630774340654489393
224pub const TE_GENERATOR_X: Fq = MontFp!("71222569531709137229370268896323705690285216175189308202338047559628438110820800641278662592954630774340654489393");
225
226/// TE_GENERATOR_Y =
227/// 6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235
228pub const TE_GENERATOR_Y: Fq = MontFp!("6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235");
229
230#[cfg(test)]
231mod test {
232
233 use super::*;
234 use crate::g1;
235 use ark_std::{rand::Rng, UniformRand};
236
237 fn sample_unchecked() -> SWAffine<g1::Config> {
238 let mut rng = ark_std::test_rng();
239 loop {
240 let x = Fq::rand(&mut rng);
241 let greatest = rng.gen();
242
243 if let Some(p) = SWAffine::get_point_from_x_unchecked(x, greatest) {
244 return p;
245 }
246 }
247 }
248
249 #[test]
250 fn test_cofactor_clearing() {
251 const SAMPLES: usize = 100;
252 for _ in 0..SAMPLES {
253 let p: SWAffine<g1::Config> = sample_unchecked();
254 let p = <Config as SWCurveConfig>::clear_cofactor(&p);
255 assert!(p.is_on_curve());
256 assert!(p.is_in_correct_subgroup_assuming_on_curve());
257 }
258 }
259}