blvm_secp256k1/
group.rs

1//! Group operations for secp256k1.
2//!
3//! Affine (Ge) and Jacobian (Gej) point representation.
4//! Curve: y² = x³ + 7
5
6use std::sync::OnceLock;
7use subtle::Choice;
8
9use crate::field::{FeStorage, FieldElement};
10
11/// secp256k1 curve constant: y² = x³ + B
12const SECP256K1_B: u32 = 7;
13
14/// Beta: nontrivial cube root of 1 in Fp. (x,y) -> (beta*x, y) is an endomorphism.
15pub(crate) fn const_beta() -> FieldElement {
16    let b: [u8; 32] = [
17        0x7a, 0xe9, 0x6a, 0x2b, 0x65, 0x7c, 0x07, 0x10, 0x6e, 0x64, 0x47, 0x9e, 0xac, 0x34, 0x34,
18        0xe9, 0x9c, 0xf0, 0x49, 0x75, 0x12, 0xf5, 0x89, 0x95, 0xc1, 0x39, 0x6c, 0x28, 0x71, 0x95,
19        0x01, 0xee,
20    ];
21    let mut r = FieldElement::zero();
22    r.set_b32_mod(&b);
23    r
24}
25
26/// Affine point (x, y) or infinity.
27#[repr(C)]
28#[derive(Clone, Copy, Debug, Default)]
29pub struct Ge {
30    pub x: FieldElement,
31    pub y: FieldElement,
32    pub infinity: bool,
33}
34
35/// Compact storage for affine point. Matches libsecp256k1 ge_storage.
36#[derive(Clone, Copy, Debug)]
37pub struct GeStorage {
38    pub x: FeStorage,
39    pub y: FeStorage,
40}
41
42impl GeStorage {
43    pub fn cmov(&mut self, a: &GeStorage, flag: Choice) {
44        self.x.cmov(&a.x, flag);
45        self.y.cmov(&a.y, flag);
46    }
47}
48
49/// Jacobian point (X, Y, Z) representing (X/Z², Y/Z³) or infinity.
50#[repr(C)]
51#[derive(Clone, Copy, Debug, Default)]
52pub struct Gej {
53    pub x: FieldElement,
54    pub y: FieldElement,
55    pub z: FieldElement,
56    pub infinity: bool,
57}
58
59impl Ge {
60    pub fn set_xy(&mut self, x: &FieldElement, y: &FieldElement) {
61        self.infinity = false;
62        self.x = *x;
63        self.y = *y;
64    }
65
66    pub fn set_infinity(&mut self) {
67        self.infinity = true;
68        self.x.set_int(0);
69        self.y.set_int(0);
70    }
71
72    pub fn is_infinity(&self) -> bool {
73        self.infinity
74    }
75
76    pub fn neg(&mut self, a: &Ge) {
77        *self = *a;
78        if !a.infinity {
79            self.y.normalize_weak();
80            let y = self.y;
81            self.y.negate(&y, 1);
82        }
83    }
84
85    /// Set from Jacobian. Modifies a (inverts z in place).
86    pub fn set_gej(&mut self, a: &mut Gej) {
87        if a.infinity {
88            self.set_infinity();
89            return;
90        }
91        self.infinity = false;
92        let z = a.z;
93        a.z.inv(&z);
94        let mut z2 = FieldElement::zero();
95        let mut z3 = FieldElement::zero();
96        z2.sqr(&a.z);
97        z3.mul(&z2, &a.z);
98        let ax = a.x;
99        let ay = a.y;
100        a.x.mul(&ax, &z2);
101        a.y.mul(&ay, &z3);
102        a.z.set_int(1);
103        self.x = a.x;
104        self.y = a.y;
105    }
106
107    /// Set from Jacobian (variable-time, doesn't modify a).
108    #[inline(always)]
109    pub fn set_gej_var(&mut self, a: &Gej) {
110        if a.is_infinity() {
111            self.set_infinity();
112            return;
113        }
114        self.infinity = false;
115        let mut zi = FieldElement::zero();
116        zi.inv(&a.z);
117        let mut z2 = FieldElement::zero();
118        let mut z3 = FieldElement::zero();
119        z2.sqr(&zi);
120        z3.mul(&z2, &zi);
121        let mut x = FieldElement::zero();
122        let mut y = FieldElement::zero();
123        x.mul(&a.x, &z2);
124        y.mul(&a.y, &z3);
125        self.set_xy(&x, &y);
126    }
127
128    /// Set r = (a.x*zi², a.y*zi³). a must not be infinity.
129    #[inline(always)]
130    pub fn set_gej_zinv(&mut self, a: &Gej, zi: &FieldElement) {
131        debug_assert!(!a.infinity);
132        self.infinity = false;
133        let mut zi2 = FieldElement::zero();
134        let mut zi3 = FieldElement::zero();
135        zi2.sqr(zi);
136        zi3.mul(&zi2, zi);
137        self.x.mul(&a.x, &zi2);
138        self.y.mul(&a.y, &zi3);
139    }
140
141    /// Set r = (a.x*zi², a.y*zi³). a must not be infinity.
142    pub fn set_ge_zinv(&mut self, a: &Ge, zi: &FieldElement) {
143        debug_assert!(!a.infinity);
144        self.infinity = false;
145        let mut zi2 = FieldElement::zero();
146        let mut zi3 = FieldElement::zero();
147        zi2.sqr(zi);
148        zi3.mul(&zi2, zi);
149        self.x.mul(&a.x, &zi2);
150        self.y.mul(&a.y, &zi3);
151    }
152
153    /// Endomorphism: r = (beta*a.x, a.y). lambda*(x,y) = (beta*x, y).
154    pub fn mul_lambda(&mut self, a: &Ge) {
155        *self = *a;
156        if !a.infinity {
157            let beta = const_beta();
158            let x = self.x;
159            self.x.mul(&x, &beta);
160        }
161    }
162
163    /// Set from compact storage.
164    pub fn from_storage(&mut self, a: &GeStorage) {
165        self.infinity = false;
166        self.x.from_storage(&a.x);
167        self.y.from_storage(&a.y);
168    }
169
170    /// Check if x is a valid X coordinate on the curve (y² = x³ + 7).
171    #[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
172    pub fn x_on_curve_var(x: &FieldElement) -> bool {
173        let mut c = FieldElement::zero();
174        c.sqr(x);
175        let c_val = c;
176        c.mul(&c_val, x);
177        c.add_int(SECP256K1_B);
178        FieldElement::is_square_var(&c)
179    }
180
181    /// Check if fraction xn/xd is a valid X coordinate on the curve.
182    /// xd must not be zero.
183    #[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
184    pub fn x_frac_on_curve_var(xn: &FieldElement, xd: &FieldElement) -> bool {
185        let mut r = FieldElement::zero();
186        let mut t = FieldElement::zero();
187        r.mul(xd, xn);
188        t.sqr(xn);
189        let r_val = r;
190        r.mul(&r_val, &t);
191        t.sqr(xd);
192        let t_val = t;
193        t.sqr(&t_val);
194        t.mul_int(SECP256K1_B);
195        r.add_assign(&t);
196        FieldElement::is_square_var(&r)
197    }
198
199    /// Set from x coordinate and y oddness. Returns true if x is on curve.
200    #[inline(always)]
201    pub fn set_xo_var(&mut self, x: &FieldElement, odd: bool) -> bool {
202        let mut x2 = FieldElement::zero();
203        let mut x3 = FieldElement::zero();
204        x2.sqr(x);
205        x3.mul(x, &x2);
206        self.x = *x;
207        self.infinity = false;
208        x3.add_int(SECP256K1_B);
209        let ok = self.y.sqrt(&x3);
210        self.y.normalize();
211        if self.y.is_odd() != odd {
212            let y = self.y;
213            self.y.negate(&y, 1);
214        }
215        ok
216    }
217}
218
219impl Gej {
220    pub fn set_infinity(&mut self) {
221        self.infinity = true;
222        self.x.set_int(0);
223        self.y.set_int(0);
224        self.z.set_int(0);
225    }
226
227    pub fn is_infinity(&self) -> bool {
228        self.infinity
229    }
230
231    #[inline(always)]
232    pub fn set_ge(&mut self, a: &Ge) {
233        self.infinity = a.infinity;
234        self.x = a.x;
235        self.y = a.y;
236        self.z.set_int(1);
237    }
238
239    pub fn neg(&mut self, a: &Gej) {
240        self.infinity = a.infinity;
241        self.x = a.x;
242        self.y = a.y;
243        self.z = a.z;
244        if !a.infinity {
245            self.y.normalize_weak();
246            let y = self.y;
247            self.y.negate(&y, 1);
248        }
249    }
250
251    #[inline(always)]
252    pub fn double(&mut self, a: &Gej) {
253        let mut l = FieldElement::zero();
254        let mut s = FieldElement::zero();
255        let mut t = FieldElement::zero();
256
257        self.infinity = a.infinity;
258        if a.infinity {
259            return;
260        }
261
262        self.z.mul(&a.z, &a.y);
263        s.sqr(&a.y);
264        l.sqr(&a.x);
265        l.mul_int(3);
266        l.half();
267        t.negate(&s, 1);
268        let t_in = t;
269        t.mul(&t_in, &a.x);
270        self.x.sqr(&l);
271        self.x.add_assign(&t);
272        self.x.add_assign(&t);
273        let s_in = s;
274        s.sqr(&s_in);
275        t.add_assign(&self.x);
276        self.y.mul(&t, &l);
277        self.y.add_assign(&s);
278        let y_in = self.y;
279        self.y.negate(&y_in, 2);
280    }
281
282    #[inline(always)]
283    pub fn double_var(&mut self, a: &Gej) {
284        if a.infinity {
285            self.set_infinity();
286            return;
287        }
288        self.double(a);
289    }
290
291    #[inline(always)]
292    pub fn add_var(&mut self, a: &Gej, b: &Gej) {
293        if a.infinity {
294            *self = *b;
295            return;
296        }
297        if b.infinity {
298            *self = *a;
299            return;
300        }
301
302        let mut z22 = FieldElement::zero();
303        let mut z12 = FieldElement::zero();
304        let mut u1 = FieldElement::zero();
305        let mut u2 = FieldElement::zero();
306        let mut s1 = FieldElement::zero();
307        let mut s2 = FieldElement::zero();
308        let mut h = FieldElement::zero();
309        let mut i = FieldElement::zero();
310        let mut h2 = FieldElement::zero();
311        let mut h3 = FieldElement::zero();
312        let mut t = FieldElement::zero();
313
314        z22.sqr(&b.z);
315        z12.sqr(&a.z);
316        u1.mul(&a.x, &z22);
317        u2.mul(&b.x, &z12);
318        s1.mul(&a.y, &z22);
319        let s1_in = s1;
320        s1.mul(&s1_in, &b.z);
321        s2.mul(&b.y, &z12);
322        let s2_in = s2;
323        s2.mul(&s2_in, &a.z);
324        h.negate(&u1, 1);
325        h.add_assign(&u2);
326        i.negate(&s2, 1);
327        i.add_assign(&s1);
328
329        if h.normalizes_to_zero_var() {
330            if i.normalizes_to_zero_var() {
331                self.double_var(a);
332            } else {
333                self.set_infinity();
334            }
335            return;
336        }
337
338        self.infinity = false;
339        t.mul(&h, &b.z);
340        self.z.mul(&a.z, &t);
341        h2.sqr(&h);
342        let h2_in = h2;
343        h2.negate(&h2_in, 1);
344        h3.mul(&h2, &h);
345        t.mul(&u1, &h2);
346        self.x.sqr(&i);
347        self.x.add_assign(&h3);
348        self.x.add_assign(&t);
349        self.x.add_assign(&t);
350        t.add_assign(&self.x);
351        self.y.mul(&t, &i);
352        let h3_in = h3;
353        h3.mul(&h3_in, &s1);
354        self.y.add_assign(&h3);
355    }
356
357    /// Rescale: r = (r.x*s², r.y*s³, r.z*s). s must not be zero.
358    pub fn rescale(&mut self, s: &FieldElement) {
359        debug_assert!(!s.normalizes_to_zero_var());
360        let mut zz = FieldElement::zero();
361        zz.sqr(s);
362        let x = self.x;
363        let y = self.y;
364        let z = self.z;
365        self.x.mul(&x, &zz);
366        self.y.mul(&y, &zz);
367        let y_zz = self.y;
368        self.y.mul(&y_zz, s);
369        self.z.mul(&z, s);
370    }
371
372    /// r = a + b with b's z known as bzinv (1/z). For adding affine to Jacobian.
373    #[inline(always)]
374    pub fn add_zinv_var(&mut self, a: &Gej, b: &Ge, bzinv: &FieldElement) {
375        if a.infinity {
376            self.infinity = b.infinity;
377            if !b.infinity {
378                let mut bzinv2 = FieldElement::zero();
379                let mut bzinv3 = FieldElement::zero();
380                bzinv2.sqr(bzinv);
381                bzinv3.mul(&bzinv2, bzinv);
382                self.x.mul(&b.x, &bzinv2);
383                self.y.mul(&b.y, &bzinv3);
384                self.z.set_int(1);
385            }
386            return;
387        }
388        if b.infinity {
389            *self = *a;
390            return;
391        }
392        let mut az = FieldElement::zero();
393        az.mul(&a.z, bzinv);
394        let mut z12 = FieldElement::zero();
395        z12.sqr(&az);
396        let u1 = a.x;
397        let mut u2 = FieldElement::zero();
398        u2.mul(&b.x, &z12);
399        let s1 = a.y;
400        let mut s2 = FieldElement::zero();
401        s2.mul(&b.y, &z12);
402        let s2_in = s2;
403        s2.mul(&s2_in, &az);
404        let mut h = FieldElement::zero();
405        h.negate(&u1, 4);
406        h.add_assign(&u2);
407        let mut i = FieldElement::zero();
408        i.negate(&s2, 1);
409        i.add_assign(&s1);
410        if h.normalizes_to_zero_var() {
411            if i.normalizes_to_zero_var() {
412                self.double_var(a);
413            } else {
414                self.set_infinity();
415            }
416            return;
417        }
418        self.infinity = false;
419        self.z.mul(&a.z, &h);
420        let mut h2 = FieldElement::zero();
421        h2.sqr(&h);
422        let h2_in = h2;
423        h2.negate(&h2_in, 1);
424        let mut h3 = FieldElement::zero();
425        h3.mul(&h2, &h);
426        let mut t = FieldElement::zero();
427        t.mul(&u1, &h2);
428        self.x.sqr(&i);
429        self.x.add_assign(&h3);
430        self.x.add_assign(&t);
431        self.x.add_assign(&t);
432        t.add_assign(&self.x);
433        self.y.mul(&t, &i);
434        let h3_in = h3;
435        h3.mul(&h3_in, &s1);
436        self.y.add_assign(&h3);
437    }
438
439    /// add_ge_var with optional z-ratio output (for odd_multiples_table).
440    #[inline(always)]
441    pub fn add_ge_var_rzr(&mut self, a: &Gej, b: &Ge, rzr: Option<&mut FieldElement>) {
442        if a.infinity {
443            if let Some(rzr) = rzr {
444                rzr.set_int(1);
445            }
446            self.set_ge(b);
447            return;
448        }
449        if b.infinity {
450            if let Some(rzr) = rzr {
451                rzr.set_int(0);
452            }
453            *self = *a;
454            return;
455        }
456
457        let mut z12 = FieldElement::zero();
458        let u1 = a.x;
459        let mut u2 = FieldElement::zero();
460        let s1 = a.y;
461        let mut s2 = FieldElement::zero();
462        let mut h = FieldElement::zero();
463        let mut i = FieldElement::zero();
464        let mut h2 = FieldElement::zero();
465        let mut h3 = FieldElement::zero();
466        let mut t = FieldElement::zero();
467
468        z12.sqr(&a.z);
469        u2.mul(&b.x, &z12);
470        s2.mul(&b.y, &z12);
471        let s2_in = s2;
472        s2.mul(&s2_in, &a.z);
473        h.negate(&u1, 4); // GEJ_X_MAGNITUDE_MAX
474        h.add_assign(&u2);
475        i.negate(&s2, 1);
476        i.add_assign(&s1);
477
478        if h.normalizes_to_zero_var() {
479            if let Some(rzr) = rzr {
480                rzr.set_int(0);
481            }
482            if i.normalizes_to_zero_var() {
483                self.double_var(a);
484            } else {
485                self.set_infinity();
486            }
487            return;
488        }
489
490        self.infinity = false;
491        if let Some(rzr) = rzr {
492            *rzr = h;
493        }
494        self.z.mul(&a.z, &h);
495        h2.sqr(&h);
496        let h2_in = h2;
497        h2.negate(&h2_in, 1);
498        h3.mul(&h2, &h);
499        t.mul(&u1, &h2);
500        self.x.sqr(&i);
501        self.x.add_assign(&h3);
502        self.x.add_assign(&t);
503        self.x.add_assign(&t);
504        t.add_assign(&self.x);
505        self.y.mul(&t, &i);
506        let h3_in = h3;
507        h3.mul(&h3_in, &s1);
508        self.y.add_assign(&h3);
509    }
510
511    #[inline(always)]
512    pub fn add_ge_var(&mut self, a: &Gej, b: &Ge) {
513        self.add_ge_var_rzr(a, b, None);
514    }
515
516    /// Check whether affine x of this Jacobian point equals the given x.
517    /// Returns x * z² == self.x (avoids inversion in ECDSA verify).
518    pub fn eq_x_var(&self, x: &FieldElement) -> bool {
519        debug_assert!(!self.infinity);
520        let mut z2 = FieldElement::zero();
521        z2.sqr(&self.z);
522        let mut r = FieldElement::zero();
523        r.mul(&z2, x);
524        FieldElement::fe_equal(&r, &self.x)
525    }
526}
527
528/// Batch convert Gej -> Ge using one field inversion instead of N.
529/// Uses r[i].x as scratch for z-products; after: r[i] = affine(a[i]).
530pub fn ge_set_all_gej_var(r: &mut [Ge], a: &[Gej]) {
531    let len = r.len().min(a.len());
532    let mut last_i: Option<usize> = None;
533
534    for i in 0..len {
535        if a[i].infinity {
536            r[i].set_infinity();
537        } else {
538            if let Some(li) = last_i {
539                let r_li_x = r[li].x;
540                let a_i_z = a[i].z;
541                r[i].x.mul(&r_li_x, &a_i_z);
542            } else {
543                r[i].x = a[i].z;
544            }
545            r[i].infinity = false; // will be overwritten by set_gej_zinv
546            last_i = Some(i);
547        }
548    }
549
550    let Some(mut last_i) = last_i else {
551        return;
552    };
553
554    let mut u = FieldElement::zero();
555    u.inv(&r[last_i].x);
556
557    let mut i = last_i;
558    while i > 0 {
559        i -= 1;
560        if !a[i].infinity {
561            let r_i_x = r[i].x;
562            r[last_i].x.mul(&r_i_x, &u);
563            let u_in = u;
564            let a_last_z = a[last_i].z;
565            u.mul(&u_in, &a_last_z);
566            last_i = i;
567        }
568    }
569    r[last_i].x = u;
570
571    for i in 0..len {
572        if !a[i].infinity {
573            let zi = r[i].x;
574            r[i].set_gej_zinv(&a[i], &zi);
575        }
576    }
577}
578
579/// Bring pre_a[0..len] to same global z. zr[i] = z(pre_a[i])/z(pre_a[i-1]), zr[0] unused.
580/// Uses r[i].x as scratch. After: z(pre_a[i]) = z(pre_a[len-1]) for all i.
581#[inline(always)]
582pub fn ge_table_set_globalz(len: usize, pre_a: &mut [Ge], zr: &[FieldElement]) {
583    if len == 0 {
584        return;
585    }
586    let mut i = len - 1;
587    pre_a[i].y.normalize_weak();
588    let mut zs = zr[i];
589    while i > 0 {
590        if i != len - 1 {
591            let zs_in = zs;
592            zs.mul(&zs_in, &zr[i]);
593        }
594        i -= 1;
595        let ai = pre_a[i];
596        pre_a[i].set_ge_zinv(&ai, &zs);
597    }
598}
599
600/// secp256k1 generator G (SEC2 2.7.1). Cached for performance.
601pub fn generator_g() -> Ge {
602    *GENERATOR_G.get_or_init(|| {
603        let gx = [
604            0x79, 0xbe, 0x66, 0x7e, 0xf9, 0xdc, 0xbb, 0xac, 0x55, 0xa0, 0x62, 0x95, 0xce, 0x87,
605            0x0b, 0x07, 0x02, 0x9b, 0xfc, 0xdb, 0x2d, 0xce, 0x28, 0xd9, 0x59, 0xf2, 0x81, 0x5b,
606            0x16, 0xf8, 0x17, 0x98,
607        ];
608        let gy = [
609            0x48, 0x3a, 0xda, 0x77, 0x26, 0xa3, 0xc4, 0x65, 0x5d, 0xa4, 0xfb, 0xfc, 0x0e, 0x11,
610            0x08, 0xa8, 0xfd, 0x17, 0xb4, 0x48, 0xa6, 0x85, 0x54, 0x19, 0x9c, 0x47, 0xd0, 0x8f,
611            0xfb, 0x10, 0xd4, 0xb8,
612        ];
613        let mut x = FieldElement::zero();
614        let mut y = FieldElement::zero();
615        x.set_b32_mod(&gx);
616        y.set_b32_mod(&gy);
617        let mut g = Ge {
618            x: FieldElement::zero(),
619            y: FieldElement::zero(),
620            infinity: false,
621        };
622        g.set_xy(&x, &y);
623        g
624    })
625}
626
627static GENERATOR_G: OnceLock<Ge> = OnceLock::new();
blvm_secp256k1/group.rs

blvm_secp256k1/
group.rs
