libsecp256k1_core/
group.rs

1use crate::field::{Field, FieldStorage};
2
3#[derive(Debug, Clone, Copy, Eq, PartialEq)]
4/// A group element of the secp256k1 curve, in affine coordinates.
5pub struct Affine {
6    pub x: Field,
7    pub y: Field,
8    pub infinity: bool,
9}
10
11#[derive(Debug, Clone, Copy)]
12/// A group element of the secp256k1 curve, in jacobian coordinates.
13pub struct Jacobian {
14    pub x: Field,
15    pub y: Field,
16    pub z: Field,
17    pub infinity: bool,
18}
19
20#[derive(Debug, Clone, Copy, Eq, PartialEq)]
21/// Affine coordinate group element compact storage.
22pub struct AffineStorage {
23    pub x: FieldStorage,
24    pub y: FieldStorage,
25}
26
27impl Default for Affine {
28    fn default() -> Affine {
29        Affine {
30            x: Field::default(),
31            y: Field::default(),
32            infinity: false,
33        }
34    }
35}
36
37impl Default for Jacobian {
38    fn default() -> Jacobian {
39        Jacobian {
40            x: Field::default(),
41            y: Field::default(),
42            z: Field::default(),
43            infinity: false,
44        }
45    }
46}
47
48impl Default for AffineStorage {
49    fn default() -> AffineStorage {
50        AffineStorage {
51            x: FieldStorage::default(),
52            y: FieldStorage::default(),
53        }
54    }
55}
56
57pub static AFFINE_INFINITY: Affine = Affine {
58    x: Field::new(0, 0, 0, 0, 0, 0, 0, 0),
59    y: Field::new(0, 0, 0, 0, 0, 0, 0, 0),
60    infinity: true,
61};
62
63pub static JACOBIAN_INFINITY: Jacobian = Jacobian {
64    x: Field::new(0, 0, 0, 0, 0, 0, 0, 0),
65    y: Field::new(0, 0, 0, 0, 0, 0, 0, 0),
66    z: Field::new(0, 0, 0, 0, 0, 0, 0, 0),
67    infinity: true,
68};
69
70pub static AFFINE_G: Affine = Affine::new(
71    Field::new(
72        0x79BE667E, 0xF9DCBBAC, 0x55A06295, 0xCE870B07, 0x029BFCDB, 0x2DCE28D9, 0x59F2815B,
73        0x16F81798,
74    ),
75    Field::new(
76        0x483ADA77, 0x26A3C465, 0x5DA4FBFC, 0x0E1108A8, 0xFD17B448, 0xA6855419, 0x9C47D08F,
77        0xFB10D4B8,
78    ),
79);
80
81pub const CURVE_B: u32 = 7;
82
83impl Affine {
84    /// Create a new affine.
85    pub const fn new(x: Field, y: Field) -> Self {
86        Self {
87            x,
88            y,
89            infinity: false,
90        }
91    }
92
93    /// Set a group element equal to the point with given X and Y
94    /// coordinates.
95    pub fn set_xy(&mut self, x: &Field, y: &Field) {
96        self.infinity = false;
97        self.x = *x;
98        self.y = *y;
99    }
100
101    /// Set a group element (affine) equal to the point with the given
102    /// X coordinate and a Y coordinate that is a quadratic residue
103    /// modulo p. The return value is true iff a coordinate with the
104    /// given X coordinate exists.
105    pub fn set_xquad(&mut self, x: &Field) -> bool {
106        self.x = *x;
107        let x2 = x.sqr();
108        let x3 = *x * x2;
109        self.infinity = false;
110        let mut c = Field::default();
111        c.set_int(CURVE_B);
112        c += x3;
113        let (v, ret) = c.sqrt();
114        self.y = v;
115        ret
116    }
117
118    /// Set a group element (affine) equal to the point with the given
119    /// X coordinate, and given oddness for Y. Return value indicates
120    /// whether the result is valid.
121    pub fn set_xo_var(&mut self, x: &Field, odd: bool) -> bool {
122        if !self.set_xquad(x) {
123            return false;
124        }
125        self.y.normalize_var();
126        if self.y.is_odd() != odd {
127            self.y = self.y.neg(1);
128        }
129        true
130    }
131
132    /// Check whether a group element is the point at infinity.
133    pub fn is_infinity(&self) -> bool {
134        self.infinity
135    }
136
137    /// Check whether a group element is valid (i.e., on the curve).
138    pub fn is_valid_var(&self) -> bool {
139        if self.is_infinity() {
140            return false;
141        }
142        let y2 = self.y.sqr();
143        let mut x3 = self.x.sqr();
144        x3 *= &self.x;
145        let mut c = Field::default();
146        c.set_int(CURVE_B);
147        x3 += &c;
148        x3.normalize_weak();
149        y2.eq_var(&x3)
150    }
151
152    pub fn neg_in_place(&mut self, other: &Affine) {
153        *self = *other;
154        self.y.normalize_weak();
155        self.y = self.y.neg(1);
156    }
157
158    pub fn neg(&self) -> Affine {
159        let mut ret = Affine::default();
160        ret.neg_in_place(self);
161        ret
162    }
163
164    /// Set a group element equal to another which is given in
165    /// jacobian coordinates.
166    pub fn set_gej(&mut self, a: &Jacobian) {
167        self.infinity = a.infinity;
168        let mut a = *a;
169        a.z = a.z.inv();
170        let z2 = a.z.sqr();
171        let z3 = a.z * z2;
172        a.x *= z2;
173        a.y *= z3;
174        a.z.set_int(1);
175        self.x = a.x;
176        self.y = a.y;
177    }
178
179    pub fn from_gej(a: &Jacobian) -> Self {
180        let mut ge = Self::default();
181        ge.set_gej(a);
182        ge
183    }
184
185    pub fn set_gej_var(&mut self, a: &Jacobian) {
186        let mut a = *a;
187        self.infinity = a.infinity;
188        if a.is_infinity() {
189            return;
190        }
191        a.z = a.z.inv_var();
192        let z2 = a.z.sqr();
193        let z3 = a.z * z2;
194        a.x *= &z2;
195        a.y *= &z3;
196        a.z.set_int(1);
197        self.x = a.x;
198        self.y = a.y;
199    }
200
201    pub fn set_gej_zinv(&mut self, a: &Jacobian, zi: &Field) {
202        let zi2 = zi.sqr();
203        let zi3 = zi2 * *zi;
204        self.x = a.x * zi2;
205        self.y = a.y * zi3;
206        self.infinity = a.infinity;
207    }
208
209    /// Clear a secp256k1_ge to prevent leaking sensitive information.
210    pub fn clear(&mut self) {
211        self.infinity = false;
212        self.x.clear();
213        self.y.clear();
214    }
215}
216
217pub fn set_table_gej_var(r: &mut [Affine], a: &[Jacobian], zr: &[Field]) {
218    debug_assert!(r.len() == a.len());
219
220    let mut i = r.len() - 1;
221    let mut zi: Field;
222
223    if !r.is_empty() {
224        zi = a[i].z.inv();
225        r[i].set_gej_zinv(&a[i], &zi);
226
227        while i > 0 {
228            zi *= &zr[i];
229            i -= 1;
230            r[i].set_gej_zinv(&a[i], &zi);
231        }
232    }
233}
234
235pub fn globalz_set_table_gej(r: &mut [Affine], globalz: &mut Field, a: &[Jacobian], zr: &[Field]) {
236    debug_assert!(r.len() == a.len() && a.len() == zr.len());
237
238    let mut i = r.len() - 1;
239    let mut zs: Field;
240
241    if !r.is_empty() {
242        r[i].x = a[i].x;
243        r[i].y = a[i].y;
244        *globalz = a[i].z;
245        r[i].infinity = false;
246        zs = zr[i];
247
248        while i > 0 {
249            if i != r.len() - 1 {
250                zs *= zr[i];
251            }
252            i -= 1;
253            r[i].set_gej_zinv(&a[i], &zs);
254        }
255    }
256}
257
258impl Jacobian {
259    /// Create a new jacobian.
260    pub const fn new(x: Field, y: Field) -> Self {
261        Self {
262            x,
263            y,
264            infinity: false,
265            z: Field::new(0, 0, 0, 0, 0, 0, 0, 1),
266        }
267    }
268
269    /// Set a group element (jacobian) equal to the point at infinity.
270    pub fn set_infinity(&mut self) {
271        self.infinity = true;
272        self.x.clear();
273        self.y.clear();
274        self.z.clear();
275    }
276
277    /// Set a group element (jacobian) equal to another which is given
278    /// in affine coordinates.
279    pub fn set_ge(&mut self, a: &Affine) {
280        self.infinity = a.infinity;
281        self.x = a.x;
282        self.y = a.y;
283        self.z.set_int(1);
284    }
285
286    pub fn from_ge(a: &Affine) -> Self {
287        let mut gej = Self::default();
288        gej.set_ge(a);
289        gej
290    }
291
292    /// Compare the X coordinate of a group element (jacobian).
293    pub fn eq_x_var(&self, x: &Field) -> bool {
294        debug_assert!(!self.is_infinity());
295        let mut r = self.z.sqr();
296        r *= x;
297        let mut r2 = self.x;
298        r2.normalize_weak();
299        r.eq_var(&r2)
300    }
301
302    /// Set r equal to the inverse of a (i.e., mirrored around the X
303    /// axis).
304    pub fn neg_in_place(&mut self, a: &Jacobian) {
305        self.infinity = a.infinity;
306        self.x = a.x;
307        self.y = a.y;
308        self.z = a.z;
309        self.y.normalize_weak();
310        self.y = self.y.neg(1);
311    }
312
313    pub fn neg(&self) -> Jacobian {
314        let mut ret = Jacobian::default();
315        ret.neg_in_place(self);
316        ret
317    }
318
319    /// Check whether a group element is the point at infinity.
320    pub fn is_infinity(&self) -> bool {
321        self.infinity
322    }
323
324    /// Check whether a group element's y coordinate is a quadratic residue.
325    pub fn has_quad_y_var(&self) -> bool {
326        if self.infinity {
327            return false;
328        }
329
330        let yz = self.y * self.z;
331        yz.is_quad_var()
332    }
333
334    /// Set r equal to the double of a. If rzr is not-NULL, r->z =
335    /// a->z * *rzr (where infinity means an implicit z = 0). a may
336    /// not be zero. Constant time.
337    pub fn double_nonzero_in_place(&mut self, a: &Jacobian, rzr: Option<&mut Field>) {
338        debug_assert!(!self.is_infinity());
339        self.double_var_in_place(a, rzr);
340    }
341
342    /// Set r equal to the double of a. If rzr is not-NULL, r->z =
343    /// a->z * *rzr (where infinity means an implicit z = 0).
344    pub fn double_var_in_place(&mut self, a: &Jacobian, rzr: Option<&mut Field>) {
345        self.infinity = a.infinity;
346        if self.infinity {
347            if let Some(rzr) = rzr {
348                rzr.set_int(1);
349            }
350            return;
351        }
352
353        if let Some(rzr) = rzr {
354            *rzr = a.y;
355            rzr.normalize_weak();
356            rzr.mul_int(2);
357        }
358
359        self.z = a.z * a.y;
360        self.z.mul_int(2);
361        let mut t1 = a.x.sqr();
362        t1.mul_int(3);
363        let mut t2 = t1.sqr();
364        let mut t3 = a.y.sqr();
365        t3.mul_int(2);
366        let mut t4 = t3.sqr();
367        t4.mul_int(2);
368        t3 *= &a.x;
369        self.x = t3;
370        self.x.mul_int(4);
371        self.x = self.x.neg(4);
372        self.x += &t2;
373        t2 = t2.neg(1);
374        t3.mul_int(6);
375        t3 += &t2;
376        self.y = t1 * t3;
377        t2 = t4.neg(2);
378        self.y += t2;
379    }
380
381    pub fn double_var(&self, rzr: Option<&mut Field>) -> Jacobian {
382        let mut ret = Jacobian::default();
383        ret.double_var_in_place(&self, rzr);
384        ret
385    }
386
387    /// Set r equal to the sum of a and b. If rzr is non-NULL, r->z =
388    /// a->z * *rzr (a cannot be infinity in that case).
389    pub fn add_var_in_place(&mut self, a: &Jacobian, b: &Jacobian, rzr: Option<&mut Field>) {
390        if a.is_infinity() {
391            debug_assert!(rzr.is_none());
392            *self = *b;
393            return;
394        }
395        if b.is_infinity() {
396            if let Some(rzr) = rzr {
397                rzr.set_int(1);
398            }
399            *self = *a;
400            return;
401        }
402
403        self.infinity = false;
404        let z22 = b.z.sqr();
405        let z12 = a.z.sqr();
406        let u1 = a.x * z22;
407        let u2 = b.x * z12;
408        let mut s1 = a.y * z22;
409        s1 *= b.z;
410        let mut s2 = b.y * z12;
411        s2 *= a.z;
412        let mut h = u1.neg(1);
413        h += u2;
414        let mut i = s1.neg(1);
415        i += s2;
416        if h.normalizes_to_zero_var() {
417            if i.normalizes_to_zero_var() {
418                self.double_var_in_place(a, rzr);
419            } else {
420                if let Some(rzr) = rzr {
421                    rzr.set_int(0);
422                }
423                self.infinity = true;
424            }
425            return;
426        }
427        let i2 = i.sqr();
428        let h2 = h.sqr();
429        let mut h3 = h * h2;
430        h *= b.z;
431        if let Some(rzr) = rzr {
432            *rzr = h;
433        }
434        self.z = a.z * h;
435        let t = u1 * h2;
436        self.x = t;
437        self.x.mul_int(2);
438        self.x += h3;
439        self.x = self.x.neg(3);
440        self.x += i2;
441        self.y = self.x.neg(5);
442        self.y += t;
443        self.y *= i;
444        h3 *= s1;
445        h3 = h3.neg(1);
446        self.y += h3;
447    }
448
449    pub fn add_var(&self, b: &Jacobian, rzr: Option<&mut Field>) -> Jacobian {
450        let mut ret = Jacobian::default();
451        ret.add_var_in_place(self, b, rzr);
452        ret
453    }
454
455    /// Set r equal to the sum of a and b (with b given in affine
456    /// coordinates, and not infinity).
457    pub fn add_ge_in_place(&mut self, a: &Jacobian, b: &Affine) {
458        const FE1: Field = Field::new(0, 0, 0, 0, 0, 0, 0, 1);
459
460        debug_assert!(!b.infinity);
461
462        let zz = a.z.sqr();
463        let mut u1 = a.x;
464        u1.normalize_weak();
465        let u2 = b.x * zz;
466        let mut s1 = a.y;
467        s1.normalize_weak();
468        let mut s2 = b.y * zz;
469        s2 *= a.z;
470        let mut t = u1;
471        t += u2;
472        let mut m = s1;
473        m += s2;
474        let mut rr = t.sqr();
475        let mut m_alt = u2.neg(1);
476        let tt = u1 * m_alt;
477        rr += tt;
478        let degenerate = m.normalizes_to_zero() && rr.normalizes_to_zero();
479        let mut rr_alt = s1;
480        rr_alt.mul_int(2);
481        m_alt += u1;
482
483        rr_alt.cmov(&rr, !degenerate);
484        m_alt.cmov(&m, !degenerate);
485
486        let mut n = m_alt.sqr();
487        let mut q = n * t;
488
489        n = n.sqr();
490        n.cmov(&m, degenerate);
491        t = rr_alt.sqr();
492        self.z = a.z * m_alt;
493        let infinity = {
494            let p = self.z.normalizes_to_zero();
495            let q = a.infinity;
496
497            match (p, q) {
498                (true, true) => false,
499                (true, false) => true,
500                (false, true) => false,
501                (false, false) => false,
502            }
503        };
504        self.z.mul_int(2);
505        q = q.neg(1);
506        t += q;
507        t.normalize_weak();
508        self.x = t;
509        t.mul_int(2);
510        t += q;
511        t *= rr_alt;
512        t += n;
513        self.y = t.neg(3);
514        self.y.normalize_weak();
515        self.x.mul_int(4);
516        self.y.mul_int(4);
517
518        self.x.cmov(&b.x, a.infinity);
519        self.y.cmov(&b.y, a.infinity);
520        self.z.cmov(&FE1, a.infinity);
521        self.infinity = infinity;
522    }
523
524    pub fn add_ge(&self, b: &Affine) -> Jacobian {
525        let mut ret = Jacobian::default();
526        ret.add_ge_in_place(self, b);
527        ret
528    }
529
530    /// Set r equal to the sum of a and b (with b given in affine
531    /// coordinates). This is more efficient than
532    /// secp256k1_gej_add_var. It is identical to secp256k1_gej_add_ge
533    /// but without constant-time guarantee, and b is allowed to be
534    /// infinity. If rzr is non-NULL, r->z = a->z * *rzr (a cannot be
535    /// infinity in that case).
536    pub fn add_ge_var_in_place(&mut self, a: &Jacobian, b: &Affine, rzr: Option<&mut Field>) {
537        if a.is_infinity() {
538            debug_assert!(rzr.is_none());
539            self.set_ge(b);
540            return;
541        }
542        if b.is_infinity() {
543            if let Some(rzr) = rzr {
544                rzr.set_int(1);
545            }
546            *self = *a;
547            return;
548        }
549        self.infinity = false;
550
551        let z12 = a.z.sqr();
552        let mut u1 = a.x;
553        u1.normalize_weak();
554        let u2 = b.x * z12;
555        let mut s1 = a.y;
556        s1.normalize_weak();
557        let mut s2 = b.y * z12;
558        s2 *= a.z;
559        let mut h = u1.neg(1);
560        h += u2;
561        let mut i = s1.neg(1);
562        i += s2;
563        if h.normalizes_to_zero_var() {
564            if i.normalizes_to_zero_var() {
565                self.double_var_in_place(a, rzr);
566            } else {
567                if let Some(rzr) = rzr {
568                    rzr.set_int(0);
569                }
570                self.infinity = true;
571            }
572            return;
573        }
574        let i2 = i.sqr();
575        let h2 = h.sqr();
576        let mut h3 = h * h2;
577        if let Some(rzr) = rzr {
578            *rzr = h;
579        }
580        self.z = a.z * h;
581        let t = u1 * h2;
582        self.x = t;
583        self.x.mul_int(2);
584        self.x += h3;
585        self.x = self.x.neg(3);
586        self.x += i2;
587        self.y = self.x.neg(5);
588        self.y += t;
589        self.y *= i;
590        h3 *= s1;
591        h3 = h3.neg(1);
592        self.y += h3;
593    }
594
595    pub fn add_ge_var(&self, b: &Affine, rzr: Option<&mut Field>) -> Jacobian {
596        let mut ret = Jacobian::default();
597        ret.add_ge_var_in_place(&self, b, rzr);
598        ret
599    }
600
601    /// Set r equal to the sum of a and b (with the inverse of b's Z
602    /// coordinate passed as bzinv).
603    pub fn add_zinv_var_in_place(&mut self, a: &Jacobian, b: &Affine, bzinv: &Field) {
604        if b.is_infinity() {
605            *self = *a;
606            return;
607        }
608        if a.is_infinity() {
609            self.infinity = b.infinity;
610            let bzinv2 = bzinv.sqr();
611            let bzinv3 = &bzinv2 * bzinv;
612            self.x = b.x * bzinv2;
613            self.y = b.y * bzinv3;
614            self.z.set_int(1);
615            return;
616        }
617        self.infinity = false;
618
619        let az = a.z * *bzinv;
620        let z12 = az.sqr();
621        let mut u1 = a.x;
622        u1.normalize_weak();
623        let u2 = b.x * z12;
624        let mut s1 = a.y;
625        s1.normalize_weak();
626        let mut s2 = b.y * z12;
627        s2 *= &az;
628        let mut h = u1.neg(1);
629        h += &u2;
630        let mut i = s1.neg(1);
631        i += &s2;
632        if h.normalizes_to_zero_var() {
633            if i.normalizes_to_zero_var() {
634                self.double_var_in_place(a, None);
635            } else {
636                self.infinity = true;
637            }
638            return;
639        }
640        let i2 = i.sqr();
641        let h2 = h.sqr();
642        let mut h3 = h * h2;
643        self.z = a.z;
644        self.z *= h;
645        let t = u1 * h2;
646        self.x = t;
647        self.x.mul_int(2);
648        self.x += h3;
649        self.x = self.x.neg(3);
650        self.x += i2;
651        self.y = self.x.neg(5);
652        self.y += t;
653        self.y *= i;
654        h3 *= s1;
655        h3 = h3.neg(1);
656        self.y += h3;
657    }
658
659    pub fn add_zinv_var(&mut self, b: &Affine, bzinv: &Field) -> Jacobian {
660        let mut ret = Jacobian::default();
661        ret.add_zinv_var_in_place(&self, b, bzinv);
662        ret
663    }
664
665    /// Clear a secp256k1_gej to prevent leaking sensitive
666    /// information.
667    pub fn clear(&mut self) {
668        self.infinity = false;
669        self.x.clear();
670        self.y.clear();
671        self.z.clear();
672    }
673
674    /// Rescale a jacobian point by b which must be
675    /// non-zero. Constant-time.
676    pub fn rescale(&mut self, s: &Field) {
677        debug_assert!(!s.is_zero());
678        let zz = s.sqr();
679        self.x *= &zz;
680        self.y *= &zz;
681        self.y *= s;
682        self.z *= s;
683    }
684}
685
686impl From<AffineStorage> for Affine {
687    fn from(a: AffineStorage) -> Affine {
688        Affine::new(a.x.into(), a.y.into())
689    }
690}
691
692impl Into<AffineStorage> for Affine {
693    fn into(mut self) -> AffineStorage {
694        debug_assert!(!self.is_infinity());
695        self.x.normalize();
696        self.y.normalize();
697        AffineStorage::new(self.x.into(), self.y.into())
698    }
699}
700
701impl AffineStorage {
702    /// Create a new affine storage.
703    pub const fn new(x: FieldStorage, y: FieldStorage) -> Self {
704        Self { x, y }
705    }
706
707    /// If flag is true, set *r equal to *a; otherwise leave
708    /// it. Constant-time.
709    pub fn cmov(&mut self, a: &AffineStorage, flag: bool) {
710        self.x.cmov(&a.x, flag);
711        self.y.cmov(&a.y, flag);
712    }
713}
libsecp256k1_core/group.rs

libsecp256k1_core/
group.rs
