dcrypt_algorithms/ec/bls12_381/
g1.rs

1//! G₁ group implementation for BLS12-381.
2
3use crate::error::{validate, Error, Result};
4use core::borrow::Borrow;
5use core::fmt;
6use core::iter::Sum;
7use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
8use dcrypt_internal::constant_time::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
9use dcrypt_internal::random::{try_fill_bytes_zeroing_on_error, CryptoRng, Error as RandomError};
10use dcrypt_internal::zeroing::Zeroize;
11
12use super::field::fp::Fp;
13use super::scalar::secret_be_bytes_are_valid;
14use super::Scalar;
15#[cfg(feature = "alloc")]
16use alloc::vec;
17
18/// G₁ affine point representation.
19#[derive(Copy, Clone, Debug)]
20pub struct G1Affine {
21    pub(crate) x: Fp,
22    pub(crate) y: Fp,
23    infinity: Choice,
24}
25
26impl Default for G1Affine {
27    fn default() -> G1Affine {
28        G1Affine::identity()
29    }
30}
31
32impl Zeroize for G1Affine {
33    fn zeroize(&mut self) {
34        self.x.zeroize();
35        self.y.zeroize();
36        self.infinity = Choice::from(0);
37    }
38}
39
40impl fmt::Display for G1Affine {
41    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
42        write!(f, "{:?}", self)
43    }
44}
45
46impl<'a> From<&'a G1Projective> for G1Affine {
47    fn from(p: &'a G1Projective) -> G1Affine {
48        let zinv = p.z.invert().unwrap_or(Fp::zero());
49        let x = p.x * zinv;
50        let y = p.y * zinv;
51
52        let tmp = G1Affine {
53            x,
54            y,
55            infinity: Choice::from(0u8),
56        };
57
58        G1Affine::conditional_select(&tmp, &G1Affine::identity(), zinv.is_zero())
59    }
60}
61
62impl From<G1Projective> for G1Affine {
63    fn from(p: G1Projective) -> G1Affine {
64        G1Affine::from(&p)
65    }
66}
67
68impl ConstantTimeEq for G1Affine {
69    fn ct_eq(&self, other: &Self) -> Choice {
70        (self.infinity & other.infinity)
71            | ((!self.infinity)
72                & (!other.infinity)
73                & self.x.ct_eq(&other.x)
74                & self.y.ct_eq(&other.y))
75    }
76}
77
78impl ConditionallySelectable for G1Affine {
79    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
80        G1Affine {
81            x: Fp::conditional_select(&a.x, &b.x, choice),
82            y: Fp::conditional_select(&a.y, &b.y, choice),
83            infinity: Choice::conditional_select(&a.infinity, &b.infinity, choice),
84        }
85    }
86}
87
88impl Eq for G1Affine {}
89impl PartialEq for G1Affine {
90    #[inline]
91    fn eq(&self, other: &Self) -> bool {
92        bool::from(self.ct_eq(other))
93    }
94}
95
96impl<'a> Neg for &'a G1Affine {
97    type Output = G1Affine;
98
99    #[inline]
100    fn neg(self) -> G1Affine {
101        G1Affine {
102            x: self.x,
103            y: Fp::conditional_select(&-self.y, &Fp::one(), self.infinity),
104            infinity: self.infinity,
105        }
106    }
107}
108
109impl Neg for G1Affine {
110    type Output = G1Affine;
111
112    #[inline]
113    fn neg(self) -> G1Affine {
114        -&self
115    }
116}
117
118impl<'a, 'b> Add<&'b G1Projective> for &'a G1Affine {
119    type Output = G1Projective;
120
121    #[inline]
122    fn add(self, rhs: &'b G1Projective) -> G1Projective {
123        rhs.add_mixed(self)
124    }
125}
126
127impl<'a, 'b> Add<&'b G1Affine> for &'a G1Projective {
128    type Output = G1Projective;
129
130    #[inline]
131    fn add(self, rhs: &'b G1Affine) -> G1Projective {
132        self.add_mixed(rhs)
133    }
134}
135
136impl<'a, 'b> Sub<&'b G1Projective> for &'a G1Affine {
137    type Output = G1Projective;
138
139    #[inline]
140    fn sub(self, rhs: &'b G1Projective) -> G1Projective {
141        self + &(-rhs)
142    }
143}
144
145impl<'a, 'b> Sub<&'b G1Affine> for &'a G1Projective {
146    type Output = G1Projective;
147
148    #[inline]
149    fn sub(self, rhs: &'b G1Affine) -> G1Projective {
150        self + &(-rhs)
151    }
152}
153
154impl<T> Sum<T> for G1Projective
155where
156    T: Borrow<G1Projective>,
157{
158    fn sum<I>(iter: I) -> Self
159    where
160        I: Iterator<Item = T>,
161    {
162        iter.fold(Self::identity(), |acc, item| acc + item.borrow())
163    }
164}
165
166// Binop implementations for G1Projective with G1Affine
167impl<'b> Add<&'b G1Affine> for G1Projective {
168    type Output = G1Projective;
169    #[inline]
170    fn add(self, rhs: &'b G1Affine) -> G1Projective {
171        &self + rhs
172    }
173}
174impl<'a> Add<G1Affine> for &'a G1Projective {
175    type Output = G1Projective;
176    #[inline]
177    fn add(self, rhs: G1Affine) -> G1Projective {
178        self + &rhs
179    }
180}
181impl Add<G1Affine> for G1Projective {
182    type Output = G1Projective;
183    #[inline]
184    fn add(self, rhs: G1Affine) -> G1Projective {
185        &self + &rhs
186    }
187}
188impl<'b> Sub<&'b G1Affine> for G1Projective {
189    type Output = G1Projective;
190    #[inline]
191    fn sub(self, rhs: &'b G1Affine) -> G1Projective {
192        &self - rhs
193    }
194}
195impl<'a> Sub<G1Affine> for &'a G1Projective {
196    type Output = G1Projective;
197    #[inline]
198    fn sub(self, rhs: G1Affine) -> G1Projective {
199        self - &rhs
200    }
201}
202impl Sub<G1Affine> for G1Projective {
203    type Output = G1Projective;
204    #[inline]
205    fn sub(self, rhs: G1Affine) -> G1Projective {
206        &self - &rhs
207    }
208}
209impl SubAssign<G1Affine> for G1Projective {
210    #[inline]
211    fn sub_assign(&mut self, rhs: G1Affine) {
212        *self = &*self - &rhs;
213    }
214}
215impl AddAssign<G1Affine> for G1Projective {
216    #[inline]
217    fn add_assign(&mut self, rhs: G1Affine) {
218        *self = &*self + &rhs;
219    }
220}
221impl<'b> SubAssign<&'b G1Affine> for G1Projective {
222    #[inline]
223    fn sub_assign(&mut self, rhs: &'b G1Affine) {
224        *self = &*self - rhs;
225    }
226}
227impl<'b> AddAssign<&'b G1Affine> for G1Projective {
228    #[inline]
229    fn add_assign(&mut self, rhs: &'b G1Affine) {
230        *self = &*self + rhs;
231    }
232}
233
234// Binop implementations for G1Affine with G1Projective
235impl<'b> Add<&'b G1Projective> for G1Affine {
236    type Output = G1Projective;
237    #[inline]
238    fn add(self, rhs: &'b G1Projective) -> G1Projective {
239        &self + rhs
240    }
241}
242impl<'a> Add<G1Projective> for &'a G1Affine {
243    type Output = G1Projective;
244    #[inline]
245    fn add(self, rhs: G1Projective) -> G1Projective {
246        self + &rhs
247    }
248}
249impl Add<G1Projective> for G1Affine {
250    type Output = G1Projective;
251    #[inline]
252    fn add(self, rhs: G1Projective) -> G1Projective {
253        &self + &rhs
254    }
255}
256impl<'b> Sub<&'b G1Projective> for G1Affine {
257    type Output = G1Projective;
258    #[inline]
259    fn sub(self, rhs: &'b G1Projective) -> G1Projective {
260        &self - rhs
261    }
262}
263impl<'a> Sub<G1Projective> for &'a G1Affine {
264    type Output = G1Projective;
265    #[inline]
266    fn sub(self, rhs: G1Projective) -> G1Projective {
267        self - &rhs
268    }
269}
270impl Sub<G1Projective> for G1Affine {
271    type Output = G1Projective;
272    #[inline]
273    fn sub(self, rhs: G1Projective) -> G1Projective {
274        &self - &rhs
275    }
276}
277
278// Curve parameter b = 4
279const B: Fp = Fp::from_raw_unchecked([
280    0xaa27_0000_000c_fff3,
281    0x53cc_0032_fc34_000a,
282    0x478f_e97a_6b0a_807f,
283    0xb1d3_7ebe_e6ba_24d7,
284    0x8ec9_733b_bf78_ab2f,
285    0x09d6_4551_3d83_de7e,
286]);
287
288/// Cube root of unity in Fp
289pub const BETA: Fp = Fp::from_raw_unchecked([
290    0x30f1_361b_798a_64e8,
291    0xf3b8_ddab_7ece_5a2a,
292    0x16a8_ca3a_c615_77f7,
293    0xc26a_2ff8_74fd_029b,
294    0x3636_b766_6070_1c6e,
295    0x051b_a4ab_241b_6160,
296]);
297
298fn endomorphism(p: &G1Affine) -> G1Affine {
299    let mut res = *p;
300    res.x *= BETA;
301    res
302}
303
304impl G1Affine {
305    /// Point at infinity.
306    pub fn identity() -> G1Affine {
307        G1Affine {
308            x: Fp::zero(),
309            y: Fp::one(),
310            infinity: Choice::from(1u8),
311        }
312    }
313
314    /// Fixed generator.
315    pub fn generator() -> G1Affine {
316        G1Affine {
317            x: Fp::from_raw_unchecked([
318                0x5cb3_8790_fd53_0c16,
319                0x7817_fc67_9976_fff5,
320                0x154f_95c7_143b_a1c1,
321                0xf0ae_6acd_f3d0_e747,
322                0xedce_6ecc_21db_f440,
323                0x1201_7741_9e0b_fb75,
324            ]),
325            y: Fp::from_raw_unchecked([
326                0xbaac_93d5_0ce7_2271,
327                0x8c22_631a_7918_fd8e,
328                0xdd59_5f13_5707_25ce,
329                0x51ac_5829_5040_5194,
330                0x0e1c_8c3f_ad00_59c0,
331                0x0bbc_3efc_5008_a26a,
332            ]),
333            infinity: Choice::from(0u8),
334        }
335    }
336
337    /// Check if point at infinity.
338    #[inline]
339    pub fn is_identity(&self) -> Choice {
340        self.infinity
341    }
342
343    /// Curve membership check.
344    pub fn is_on_curve(&self) -> Choice {
345        (self.y.square() - (self.x.square() * self.x)).ct_eq(&B) | self.infinity
346    }
347
348    /// Subgroup check using endomorphism.
349    pub fn is_torsion_free(&self) -> Choice {
350        let minus_x_squared_times_p = G1Projective::from(self).mul_by_x().mul_by_x().neg();
351        let endomorphism_p = endomorphism(self);
352        minus_x_squared_times_p.ct_eq(&G1Projective::from(endomorphism_p))
353    }
354
355    /// Compress to 48 bytes.
356    pub fn to_compressed(&self) -> [u8; 48] {
357        let mut res = Fp::conditional_select(&self.x, &Fp::zero(), self.infinity).to_bytes();
358        res[0] |= 1u8 << 7; // compression flag
359        res[0] |= u8::conditional_select(&0u8, &(1u8 << 6), self.infinity); // infinity flag
360        res[0] |= u8::conditional_select(
361            &0u8,
362            &(1u8 << 5),
363            (!self.infinity) & self.y.lexicographically_largest(), // sign flag
364        );
365        res
366    }
367
368    /// Serialize to 96 bytes uncompressed.
369    pub fn to_uncompressed(&self) -> [u8; 96] {
370        let mut res = [0; 96];
371        res[0..48].copy_from_slice(
372            &Fp::conditional_select(&self.x, &Fp::zero(), self.infinity).to_bytes()[..],
373        );
374        res[48..96].copy_from_slice(
375            &Fp::conditional_select(&self.y, &Fp::zero(), self.infinity).to_bytes()[..],
376        );
377        res[0] |= u8::conditional_select(&0u8, &(1u8 << 6), self.infinity);
378        res
379    }
380
381    /// Deserialize from uncompressed bytes.
382    pub fn from_uncompressed(bytes: &[u8; 96]) -> CtOption<Self> {
383        Self::from_uncompressed_unchecked(bytes)
384            .and_then(|p| CtOption::new(p, p.is_on_curve() & p.is_torsion_free()))
385    }
386
387    /// Internal decoder that omits curve and subgroup validation.
388    pub(crate) fn from_uncompressed_unchecked(bytes: &[u8; 96]) -> CtOption<Self> {
389        let compression_flag_set = Choice::from((bytes[0] >> 7) & 1);
390        let infinity_flag_set = Choice::from((bytes[0] >> 6) & 1);
391        let sort_flag_set = Choice::from((bytes[0] >> 5) & 1);
392        let x = {
393            let mut tmp = [0; 48];
394            tmp.copy_from_slice(&bytes[0..48]);
395            tmp[0] &= 0b0001_1111;
396            Fp::from_bytes(&tmp)
397        };
398        let y = Fp::from_bytes(<&[u8; 48]>::try_from(&bytes[48..96]).unwrap());
399
400        x.and_then(|x| {
401            y.and_then(|y| {
402                let p = G1Affine::conditional_select(
403                    &G1Affine {
404                        x,
405                        y,
406                        infinity: infinity_flag_set,
407                    },
408                    &G1Affine::identity(),
409                    infinity_flag_set,
410                );
411                CtOption::new(
412                    p,
413                    ((!infinity_flag_set) | (infinity_flag_set & x.is_zero() & y.is_zero()))
414                        & (!compression_flag_set)
415                        & (!sort_flag_set),
416                )
417            })
418        })
419    }
420
421    /// Deserialize from compressed bytes with dcrypt error handling
422    pub fn from_compressed(bytes: &[u8; 48]) -> Result<Self> {
423        Self::from_compressed_unchecked(bytes)
424            .into_option() // Convert CtOption to Option
425            .ok_or_else(|| Error::Parameter {
426                name: "compressed_bytes".into(),
427                reason: "invalid G1 point encoding".into(),
428            })
429            .and_then(|p| {
430                if !bool::from(p.is_torsion_free()) {
431                    Err(Error::param("point", "not in correct subgroup"))
432                } else {
433                    Ok(p)
434                }
435            })
436    }
437
438    /// Internal implementation keeping CtOption for constant-time operations
439    pub(crate) fn from_compressed_unchecked(bytes: &[u8; 48]) -> CtOption<Self> {
440        let compression_flag_set = Choice::from((bytes[0] >> 7) & 1);
441        let infinity_flag_set = Choice::from((bytes[0] >> 6) & 1);
442        let sort_flag_set = Choice::from((bytes[0] >> 5) & 1);
443        let x = {
444            let mut tmp = *bytes;
445            tmp[0] &= 0b0001_1111;
446            Fp::from_bytes(&tmp)
447        };
448
449        x.and_then(|x| {
450            CtOption::new(
451                G1Affine::identity(),
452                infinity_flag_set & compression_flag_set & (!sort_flag_set) & x.is_zero(),
453            )
454            .or_else(|| {
455                ((x.square() * x) + B).sqrt().and_then(|y| {
456                    let y = Fp::conditional_select(
457                        &y,
458                        &-y,
459                        y.lexicographically_largest() ^ sort_flag_set,
460                    );
461                    CtOption::new(
462                        G1Affine {
463                            x,
464                            y,
465                            infinity: infinity_flag_set,
466                        },
467                        (!infinity_flag_set) & compression_flag_set,
468                    )
469                })
470            })
471        })
472    }
473}
474
475/// G₁ projective point representation.
476#[derive(Copy, Clone, Debug)]
477pub struct G1Projective {
478    pub(crate) x: Fp,
479    pub(crate) y: Fp,
480    pub(crate) z: Fp,
481}
482
483impl Default for G1Projective {
484    fn default() -> G1Projective {
485        G1Projective::identity()
486    }
487}
488
489impl Zeroize for G1Projective {
490    fn zeroize(&mut self) {
491        self.x.zeroize();
492        self.y.zeroize();
493        self.z.zeroize();
494    }
495}
496
497impl fmt::Display for G1Projective {
498    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
499        write!(f, "{:?}", self)
500    }
501}
502
503impl<'a> From<&'a G1Affine> for G1Projective {
504    fn from(p: &'a G1Affine) -> G1Projective {
505        G1Projective {
506            x: p.x,
507            y: p.y,
508            z: Fp::conditional_select(&Fp::one(), &Fp::zero(), p.infinity),
509        }
510    }
511}
512
513impl From<G1Affine> for G1Projective {
514    fn from(p: G1Affine) -> G1Projective {
515        G1Projective::from(&p)
516    }
517}
518
519impl ConstantTimeEq for G1Projective {
520    fn ct_eq(&self, other: &Self) -> Choice {
521        let x1 = self.x * other.z;
522        let x2 = other.x * self.z;
523        let y1 = self.y * other.z;
524        let y2 = other.y * self.z;
525        let self_is_zero = self.z.is_zero();
526        let other_is_zero = other.z.is_zero();
527
528        (self_is_zero & other_is_zero)
529            | ((!self_is_zero) & (!other_is_zero) & x1.ct_eq(&x2) & y1.ct_eq(&y2))
530    }
531}
532
533impl ConditionallySelectable for G1Projective {
534    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
535        G1Projective {
536            x: Fp::conditional_select(&a.x, &b.x, choice),
537            y: Fp::conditional_select(&a.y, &b.y, choice),
538            z: Fp::conditional_select(&a.z, &b.z, choice),
539        }
540    }
541}
542
543impl Eq for G1Projective {}
544impl PartialEq for G1Projective {
545    #[inline]
546    fn eq(&self, other: &Self) -> bool {
547        bool::from(self.ct_eq(other))
548    }
549}
550
551impl<'a> Neg for &'a G1Projective {
552    type Output = G1Projective;
553
554    #[inline]
555    fn neg(self) -> G1Projective {
556        G1Projective {
557            x: self.x,
558            y: -self.y,
559            z: self.z,
560        }
561    }
562}
563
564impl Neg for G1Projective {
565    type Output = G1Projective;
566
567    #[inline]
568    fn neg(self) -> G1Projective {
569        -&self
570    }
571}
572
573impl<'a, 'b> Add<&'b G1Projective> for &'a G1Projective {
574    type Output = G1Projective;
575
576    #[inline]
577    fn add(self, rhs: &'b G1Projective) -> G1Projective {
578        self.add(rhs)
579    }
580}
581
582impl<'a, 'b> Sub<&'b G1Projective> for &'a G1Projective {
583    type Output = G1Projective;
584
585    #[inline]
586    fn sub(self, rhs: &'b G1Projective) -> G1Projective {
587        self + &(-rhs)
588    }
589}
590
591impl<'a, 'b> Mul<&'b Scalar> for &'a G1Projective {
592    type Output = G1Projective;
593
594    fn mul(self, other: &'b Scalar) -> Self::Output {
595        let mut bytes = other.to_bytes();
596        let result = self.multiply(&bytes);
597        bytes.zeroize();
598        result
599    }
600}
601
602impl<'a, 'b> Mul<&'b G1Projective> for &'a Scalar {
603    type Output = G1Projective;
604
605    #[inline]
606    fn mul(self, rhs: &'b G1Projective) -> Self::Output {
607        rhs * self
608    }
609}
610
611impl<'a, 'b> Mul<&'b Scalar> for &'a G1Affine {
612    type Output = G1Projective;
613
614    fn mul(self, other: &'b Scalar) -> Self::Output {
615        let mut bytes = other.to_bytes();
616        let result = G1Projective::from(self).multiply(&bytes);
617        bytes.zeroize();
618        result
619    }
620}
621
622impl<'a, 'b> Mul<&'b G1Affine> for &'a Scalar {
623    type Output = G1Projective;
624
625    #[inline]
626    fn mul(self, rhs: &'b G1Affine) -> Self::Output {
627        rhs * self
628    }
629}
630
631// Binop implementations for G1Projective
632impl<'b> Add<&'b G1Projective> for G1Projective {
633    type Output = G1Projective;
634    #[inline]
635    fn add(self, rhs: &'b G1Projective) -> G1Projective {
636        &self + rhs
637    }
638}
639impl<'a> Add<G1Projective> for &'a G1Projective {
640    type Output = G1Projective;
641    #[inline]
642    fn add(self, rhs: G1Projective) -> G1Projective {
643        self + &rhs
644    }
645}
646impl Add<G1Projective> for G1Projective {
647    type Output = G1Projective;
648    #[inline]
649    fn add(self, rhs: G1Projective) -> G1Projective {
650        &self + &rhs
651    }
652}
653impl<'b> Sub<&'b G1Projective> for G1Projective {
654    type Output = G1Projective;
655    #[inline]
656    fn sub(self, rhs: &'b G1Projective) -> G1Projective {
657        &self - rhs
658    }
659}
660impl<'a> Sub<G1Projective> for &'a G1Projective {
661    type Output = G1Projective;
662    #[inline]
663    fn sub(self, rhs: G1Projective) -> G1Projective {
664        self - &rhs
665    }
666}
667impl Sub<G1Projective> for G1Projective {
668    type Output = G1Projective;
669    #[inline]
670    fn sub(self, rhs: G1Projective) -> G1Projective {
671        &self - &rhs
672    }
673}
674impl SubAssign<G1Projective> for G1Projective {
675    #[inline]
676    fn sub_assign(&mut self, rhs: G1Projective) {
677        *self = &*self - &rhs;
678    }
679}
680impl AddAssign<G1Projective> for G1Projective {
681    #[inline]
682    fn add_assign(&mut self, rhs: G1Projective) {
683        *self = &*self + &rhs;
684    }
685}
686impl<'b> SubAssign<&'b G1Projective> for G1Projective {
687    #[inline]
688    fn sub_assign(&mut self, rhs: &'b G1Projective) {
689        *self = &*self - rhs;
690    }
691}
692impl<'b> AddAssign<&'b G1Projective> for G1Projective {
693    #[inline]
694    fn add_assign(&mut self, rhs: &'b G1Projective) {
695        *self = &*self + rhs;
696    }
697}
698
699// Scalar multiplication binops for G1Projective
700impl<'b> Mul<&'b Scalar> for G1Projective {
701    type Output = G1Projective;
702    #[inline]
703    fn mul(self, rhs: &'b Scalar) -> G1Projective {
704        &self * rhs
705    }
706}
707impl<'a> Mul<Scalar> for &'a G1Projective {
708    type Output = G1Projective;
709    #[inline]
710    fn mul(self, rhs: Scalar) -> G1Projective {
711        self * &rhs
712    }
713}
714impl Mul<Scalar> for G1Projective {
715    type Output = G1Projective;
716    #[inline]
717    fn mul(self, rhs: Scalar) -> G1Projective {
718        &self * &rhs
719    }
720}
721impl MulAssign<Scalar> for G1Projective {
722    #[inline]
723    fn mul_assign(&mut self, rhs: Scalar) {
724        *self = &*self * &rhs;
725    }
726}
727impl<'b> MulAssign<&'b Scalar> for G1Projective {
728    #[inline]
729    fn mul_assign(&mut self, rhs: &'b Scalar) {
730        *self = &*self * rhs;
731    }
732}
733
734// Scalar multiplication binops for G1Affine
735impl<'b> Mul<&'b Scalar> for G1Affine {
736    type Output = G1Projective;
737    #[inline]
738    fn mul(self, rhs: &'b Scalar) -> G1Projective {
739        &self * rhs
740    }
741}
742impl<'a> Mul<Scalar> for &'a G1Affine {
743    type Output = G1Projective;
744    #[inline]
745    fn mul(self, rhs: Scalar) -> G1Projective {
746        self * &rhs
747    }
748}
749impl Mul<Scalar> for G1Affine {
750    type Output = G1Projective;
751    #[inline]
752    fn mul(self, rhs: Scalar) -> G1Projective {
753        &self * &rhs
754    }
755}
756
757// Scalar * G1Affine binops
758impl<'b> Mul<&'b G1Affine> for Scalar {
759    type Output = G1Projective;
760    #[inline]
761    fn mul(self, rhs: &'b G1Affine) -> G1Projective {
762        &self * rhs
763    }
764}
765impl<'a> Mul<G1Affine> for &'a Scalar {
766    type Output = G1Projective;
767    #[inline]
768    fn mul(self, rhs: G1Affine) -> G1Projective {
769        self * &rhs
770    }
771}
772impl Mul<G1Affine> for Scalar {
773    type Output = G1Projective;
774    #[inline]
775    fn mul(self, rhs: G1Affine) -> G1Projective {
776        &self * &rhs
777    }
778}
779
780// Scalar * G1Projective binops
781impl<'b> Mul<&'b G1Projective> for Scalar {
782    type Output = G1Projective;
783    #[inline]
784    fn mul(self, rhs: &'b G1Projective) -> G1Projective {
785        &self * rhs
786    }
787}
788impl<'a> Mul<G1Projective> for &'a Scalar {
789    type Output = G1Projective;
790    #[inline]
791    fn mul(self, rhs: G1Projective) -> G1Projective {
792        self * &rhs
793    }
794}
795impl Mul<G1Projective> for Scalar {
796    type Output = G1Projective;
797    #[inline]
798    fn mul(self, rhs: G1Projective) -> G1Projective {
799        &self * &rhs
800    }
801}
802
803#[inline(always)]
804fn mul_by_3b(a: Fp) -> Fp {
805    let a = a + a; // 2
806    let a = a + a; // 4
807    a + a + a // 12
808}
809
810impl G1Projective {
811    /// Point at infinity.
812    pub fn identity() -> G1Projective {
813        G1Projective {
814            x: Fp::zero(),
815            y: Fp::one(),
816            z: Fp::zero(),
817        }
818    }
819
820    /// Fixed generator.
821    pub fn generator() -> G1Projective {
822        G1Projective {
823            x: G1Affine::generator().x,
824            y: G1Affine::generator().y,
825            z: Fp::one(),
826        }
827    }
828
829    /// Multiply by a canonical, nonzero scalar encoded as a 32-byte
830    /// big-endian secret key.
831    ///
832    /// This path validates and consumes the borrowed big-endian bytes directly:
833    /// it does not construct the generic `Copy` scalar type or materialize a
834    /// second byte-order representation. Multiplication uses exactly 256
835    /// MSB-first rounds, always computes both the doubled and added candidate,
836    /// and selects with a constant-time mask. Secret-derived point scratch is
837    /// explicitly cleared after every round. Platform-specific compiler
838    /// inspection is still required for a concrete side-channel claim.
839    pub fn multiply_secret_be_bytes(&self, secret: &[u8; 32]) -> Result<Self> {
840        if !bool::from(secret_be_bytes_are_valid(secret)) {
841            return Err(Error::param(
842                "secret_scalar",
843                "scalar must be canonical and nonzero",
844            ));
845        }
846
847        let mut accumulator = Self::identity();
848        for byte in secret {
849            for bit_index in (0..8).rev() {
850                let mut doubled = accumulator.double();
851                accumulator.zeroize();
852                let mut added = doubled + self;
853                let mut bit = Choice::from((byte >> bit_index) & 1);
854                accumulator = Self::conditional_select(&doubled, &added, bit);
855                bit.zeroize();
856                doubled.zeroize();
857                added.zeroize();
858            }
859        }
860        Ok(accumulator)
861    }
862
863    /// Random point generation.
864    pub fn random(mut rng: impl CryptoRng) -> core::result::Result<Self, RandomError> {
865        loop {
866            let x = Fp::random(&mut rng)?;
867            let mut sign = [0u8; 1];
868            try_fill_bytes_zeroing_on_error(&mut rng, &mut sign)?;
869            let flip_sign = sign[0] & 1 != 0;
870
871            let p = ((x.square() * x) + B).sqrt().map(|y| G1Affine {
872                x,
873                y: if flip_sign { -y } else { y },
874                infinity: 0.into(),
875            });
876
877            if p.is_some().into() {
878                let p_proj = G1Projective::from(p.unwrap());
879                let p_cleared = p_proj.clear_cofactor();
880                if !bool::from(p_cleared.is_identity()) {
881                    return Ok(p_cleared);
882                }
883            }
884        }
885    }
886
887    // ============================================================================
888    // START: New MSM Implementation
889    // ============================================================================
890
891    /// Multi-scalar multiplication using a variable-time Pippenger's algorithm.
892    ///
893    /// Every scalar passed to this low-level helper must be public. It contains
894    /// input-dependent branches and does not provide secret-scratch ownership.
895    /// Use [`Self::multiply_secret_be_bytes`] for secret scalar multiplication,
896    /// or the high-level BLS APIs in `dcrypt-sign`.
897    ///
898    /// # Panics
899    /// Panics if `points.len() != scalars.len()`.
900    #[cfg(feature = "alloc")]
901    pub fn msm_vartime(points: &[G1Affine], scalars: &[Scalar]) -> Result<Self> {
902        if points.len() != scalars.len() {
903            return Err(Error::Parameter {
904                name: "points/scalars".into(),
905                reason: "Input slices must have the same length".into(),
906            });
907        }
908        Ok(Self::pippenger_vartime(points, scalars))
909    }
910
911    /// Internal public-input Pippenger implementation.
912    #[cfg(feature = "alloc")]
913    fn pippenger_vartime(points: &[G1Affine], scalars: &[Scalar]) -> Self {
914        if points.is_empty() {
915            return Self::identity();
916        }
917
918        let num_entries = points.len();
919        let scalar_bits = 255; // BLS12-381 scalar size
920
921        // 1. Choose window size `c` from the public batch length.
922        let c = if num_entries < 32 {
923            3
924        } else {
925            // Integer log2 equivalent: floor(log2(n)).
926            // Works in no_std without libm.
927            let log2 = (usize::BITS - num_entries.leading_zeros() - 1) as usize;
928            log2 + 2
929        };
930
931        let num_windows = (scalar_bits + c - 1) / c;
932        let num_buckets = 1 << c;
933        let mut global_acc = Self::identity();
934
935        // 2. Iterate through each window
936        for w in (0..num_windows).rev() {
937            let mut window_acc = Self::identity();
938            let mut buckets = vec![Self::identity(); num_buckets];
939
940            // 3. Populate buckets for the current window
941            for i in 0..num_entries {
942                let scalar_bytes = scalars[i].to_bytes();
943
944                // Extract c-bit window from scalar
945                let mut k = 0;
946                for bit_idx in 0..c {
947                    let total_bit_idx = w * c + bit_idx;
948                    if total_bit_idx < scalar_bits {
949                        let byte_idx = total_bit_idx / 8;
950                        let inner_bit_idx = total_bit_idx % 8;
951                        let byte = scalar_bytes[byte_idx];
952                        let bit = (byte >> inner_bit_idx) & 1;
953                        k |= (bit as usize) << bit_idx;
954                    }
955                }
956
957                if k > 0 {
958                    buckets[k - 1] = buckets[k - 1].add_mixed(&points[i]);
959                }
960            }
961
962            // 4. Sum up buckets to get the window result
963            let mut running_sum = Self::identity();
964            for i in (0..num_buckets).rev() {
965                running_sum = running_sum.add(&buckets[i]);
966                window_acc = window_acc.add(&running_sum);
967            }
968
969            // 5. Add to global accumulator
970            global_acc = global_acc.add(&window_acc);
971
972            // Scale accumulator for next window if not the last one
973            if w > 0 {
974                for _ in 0..c {
975                    global_acc = global_acc.double();
976                }
977            }
978        }
979
980        global_acc
981    }
982
983    // ============================================================================
984    // END: New MSM Implementation
985    // ============================================================================
986
987    /// Point doubling.
988    pub fn double(&self) -> G1Projective {
989        // Algorithm 9 from https://eprint.iacr.org/2015/1060.pdf
990        let t0 = self.y.square();
991        let z3 = t0 + t0;
992        let z3 = z3 + z3;
993        let z3 = z3 + z3;
994        let t1 = self.y * self.z;
995        let t2 = self.z.square();
996        let t2 = mul_by_3b(t2);
997        let x3 = t2 * z3;
998        let y3 = t0 + t2;
999        let z3 = t1 * z3;
1000        let t1 = t2 + t2;
1001        let t2 = t1 + t2;
1002        let t0 = t0 - t2;
1003        let y3 = t0 * y3;
1004        let y3 = x3 + y3;
1005        let t1 = self.x * self.y;
1006        let x3 = t0 * t1;
1007        let x3 = x3 + x3;
1008
1009        let tmp = G1Projective {
1010            x: x3,
1011            y: y3,
1012            z: z3,
1013        };
1014        G1Projective::conditional_select(&tmp, &G1Projective::identity(), self.is_identity())
1015    }
1016
1017    /// Point addition.
1018    pub fn add(&self, rhs: &G1Projective) -> G1Projective {
1019        // Algorithm 7 from https://eprint.iacr.org/2015/1060.pdf
1020        let t0 = self.x * rhs.x;
1021        let t1 = self.y * rhs.y;
1022        let t2 = self.z * rhs.z;
1023        let t3 = self.x + self.y;
1024        let t4 = rhs.x + rhs.y;
1025        let t3 = t3 * t4;
1026        let t4 = t0 + t1;
1027        let t3 = t3 - t4;
1028        let t4 = self.y + self.z;
1029        let x3 = rhs.y + rhs.z;
1030        let t4 = t4 * x3;
1031        let x3 = t1 + t2;
1032        let t4 = t4 - x3;
1033        let x3 = self.x + self.z;
1034        let y3 = rhs.x + rhs.z;
1035        let x3 = x3 * y3;
1036        let y3 = t0 + t2;
1037        let y3 = x3 - y3;
1038        let x3 = t0 + t0;
1039        let t0 = x3 + t0;
1040        let t2 = mul_by_3b(t2);
1041        let z3 = t1 + t2;
1042        let t1 = t1 - t2;
1043        let y3 = mul_by_3b(y3);
1044        let x3 = t4 * y3;
1045        let t2 = t3 * t1;
1046        let x3 = t2 - x3;
1047        let y3 = y3 * t0;
1048        let t1 = t1 * z3;
1049        let y3 = t1 + y3;
1050        let t0 = t0 * t3;
1051        let z3 = z3 * t4;
1052        let z3 = z3 + t0;
1053
1054        G1Projective {
1055            x: x3,
1056            y: y3,
1057            z: z3,
1058        }
1059    }
1060
1061    /// Mixed addition with affine point.
1062    pub fn add_mixed(&self, rhs: &G1Affine) -> G1Projective {
1063        // Algorithm 8 from https://eprint.iacr.org/2015/1060.pdf
1064        let t0 = self.x * rhs.x;
1065        let t1 = self.y * rhs.y;
1066        let t3 = rhs.x + rhs.y;
1067        let t4 = self.x + self.y;
1068        let t3 = t3 * t4;
1069        let t4 = t0 + t1;
1070        let t3 = t3 - t4;
1071        let t4 = rhs.y * self.z;
1072        let t4 = t4 + self.y;
1073        let y3 = rhs.x * self.z;
1074        let y3 = y3 + self.x;
1075        let x3 = t0 + t0;
1076        let t0 = x3 + t0;
1077        let t2 = mul_by_3b(self.z);
1078        let z3 = t1 + t2;
1079        let t1 = t1 - t2;
1080        let y3 = mul_by_3b(y3);
1081        let x3 = t4 * y3;
1082        let t2 = t3 * t1;
1083        let x3 = t2 - x3;
1084        let y3 = y3 * t0;
1085        let t1 = t1 * z3;
1086        let y3 = t1 + y3;
1087        let t0 = t0 * t3;
1088        let z3 = z3 * t4;
1089        let z3 = z3 + t0;
1090
1091        let tmp = G1Projective {
1092            x: x3,
1093            y: y3,
1094            z: z3,
1095        };
1096        G1Projective::conditional_select(&tmp, self, rhs.is_identity())
1097    }
1098
1099    fn multiply(&self, by: &[u8; 32]) -> G1Projective {
1100        let mut acc = G1Projective::identity();
1101        for &byte in by.iter().rev() {
1102            for i in (0..8).rev() {
1103                acc = acc.double();
1104                let bit = Choice::from((byte >> i) & 1u8);
1105                acc = G1Projective::conditional_select(&acc, &(acc + self), bit);
1106            }
1107        }
1108        acc
1109    }
1110
1111    fn mul_by_x(&self) -> G1Projective {
1112        let mut xself = G1Projective::identity();
1113        let mut x = super::BLS_X >> 1;
1114        let mut tmp = *self;
1115        while x != 0 {
1116            tmp = tmp.double();
1117            if x % 2 == 1 {
1118                xself += tmp;
1119            }
1120            x >>= 1;
1121        }
1122        if super::BLS_X_IS_NEGATIVE {
1123            xself = -xself;
1124        }
1125        xself
1126    }
1127
1128    /// Clear cofactor using [x - 1] method.
1129    pub fn clear_cofactor(&self) -> G1Projective {
1130        self - &self.mul_by_x()
1131    }
1132
1133    /// Batch affine conversion.
1134    pub fn batch_normalize(p: &[Self], q: &mut [G1Affine]) {
1135        assert_eq!(p.len(), q.len());
1136
1137        let mut acc = Fp::one();
1138        for (p, q) in p.iter().zip(q.iter_mut()) {
1139            q.x = acc;
1140            acc = Fp::conditional_select(&(acc * p.z), &acc, p.is_identity());
1141        }
1142
1143        acc = acc.invert().unwrap();
1144
1145        for (p, q) in p.iter().rev().zip(q.iter_mut().rev()) {
1146            let skip = p.is_identity();
1147            let tmp = q.x * acc;
1148            acc = Fp::conditional_select(&(acc * p.z), &acc, skip);
1149            q.x = p.x * tmp;
1150            q.y = p.y * tmp;
1151            q.infinity = Choice::from(0u8);
1152            *q = G1Affine::conditional_select(q, &G1Affine::identity(), skip);
1153        }
1154    }
1155
1156    /// Check if point at infinity.
1157    #[inline]
1158    pub fn is_identity(&self) -> Choice {
1159        self.z.is_zero()
1160    }
1161
1162    /// Curve membership check.
1163    pub fn is_on_curve(&self) -> Choice {
1164        (self.y.square() * self.z).ct_eq(&(self.x.square() * self.x + self.z.square() * self.z * B))
1165            | self.z.is_zero()
1166    }
1167
1168    /// Deserialize a standard compressed group element and enforce subgroup
1169    /// membership. The canonical identity encoding is accepted; protocols such
1170    /// as BLS that prohibit identity inputs should use
1171    /// [`Self::from_bytes_validated`].
1172    pub fn from_bytes(bytes: &[u8; 48]) -> CtOption<Self> {
1173        G1Affine::from_compressed_unchecked(bytes)
1174            .and_then(|point| CtOption::new(point, point.is_torsion_free()))
1175            .map(G1Projective::from)
1176    }
1177
1178    /// Deserialize a nonidentity standard compressed point with strict BLS input
1179    /// validation: canonical encoding, curve membership, and subgroup membership.
1180    pub fn from_bytes_validated(bytes: &[u8]) -> Result<Self> {
1181        // Use dcrypt validation
1182        validate::length("G1Projective::from_bytes", bytes.len(), 48)?;
1183
1184        let mut array = [0u8; 48];
1185        array.copy_from_slice(bytes);
1186
1187        let point = Self::from_bytes(&array)
1188            .into_option()
1189            .ok_or_else(|| Error::Processing {
1190                operation: "G1 deserialization",
1191                details: "invalid encoding or point outside the prime-order subgroup",
1192            })?;
1193        if bool::from(point.is_identity()) {
1194            return Err(Error::param("point", "identity is not a valid BLS input"));
1195        }
1196        Ok(point)
1197    }
1198
1199    /// Serialize to compressed bytes.
1200    pub fn to_bytes(&self) -> [u8; 48] {
1201        G1Affine::from(self).to_compressed()
1202    }
1203}
1204
1205#[cfg(test)]
1206mod tests {
1207    use super::*;
1208
1209    #[test]
1210    fn checked_decoders_reject_on_curve_non_subgroup_point() {
1211        // A point on E(Fp) whose order is not in the prime-order G1 subgroup.
1212        let point = G1Affine {
1213            x: Fp::from_raw_unchecked([
1214                0x0aba_f895_b97e_43c8,
1215                0xba4c_6432_eb9b_61b0,
1216                0x1250_6f52_adfe_307f,
1217                0x7502_8c34_3933_6b72,
1218                0x8474_4f05_b8e9_bd71,
1219                0x113d_554f_b095_54f7,
1220            ]),
1221            y: Fp::from_raw_unchecked([
1222                0x73e9_0e88_f5cf_01c0,
1223                0x3700_7b65_dd31_97e2,
1224                0x5cf9_a199_2f0d_7c78,
1225                0x4f83_c10b_9eb3_330d,
1226                0xf6a6_3f6f_07f6_0961,
1227                0x0c53_b5b9_7e63_4df3,
1228            ]),
1229            infinity: Choice::from(0u8),
1230        };
1231        assert!(bool::from(point.is_on_curve()));
1232        assert!(!bool::from(point.is_torsion_free()));
1233
1234        let encoded = point.to_compressed();
1235        assert!(bool::from(
1236            G1Affine::from_compressed_unchecked(&encoded).is_some()
1237        ));
1238        assert!(bool::from(G1Projective::from_bytes(&encoded).is_none()));
1239        assert!(G1Projective::from_bytes_validated(&encoded).is_err());
1240        assert!(G1Affine::from_compressed(&encoded).is_err());
1241
1242        // Identity public keys and signatures satisfy the min-pk pairing
1243        // equation for every message. Group-element decoding intentionally
1244        // accepts the canonical identity, while the strict BLS input decoder
1245        // rejects it; protocol code must use the latter for attacker inputs.
1246        use crate::ec::bls12_381::{pairing, G2Affine, G2Projective};
1247        let message_point = G2Affine::from(
1248            G2Projective::hash_to_curve(
1249                b"arbitrary message",
1250                b"BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_",
1251            )
1252            .unwrap(),
1253        );
1254        assert_eq!(
1255            pairing(&G1Affine::identity(), &message_point),
1256            pairing(&G1Affine::generator(), &G2Affine::identity())
1257        );
1258    }
1259
1260    #[test]
1261    fn test_g1_msm() {
1262        let g = G1Affine::generator();
1263        let s1 = Scalar::from(2u64);
1264        let s2 = Scalar::from(3u64);
1265        let s3 = Scalar::from(4u64);
1266
1267        let p1 = G1Affine::from(G1Projective::from(g) * s1); // [2]G
1268        let p2 = G1Affine::from(G1Projective::from(g) * s2); // [3]G
1269        let p3 = G1Affine::from(G1Projective::from(g) * s3); // [4]G
1270
1271        let scalars = vec![s1, s2, s3];
1272        let points = vec![p1, p2, p3];
1273
1274        // Expected result: 2*[2]G + 3*[3]G + 4*[4]G = (4 + 9 + 16)[G] = [29]G
1275        let expected = G1Projective::from(g) * Scalar::from(29u64);
1276
1277        // Naive MSM for comparison
1278        let naive_result = (p1 * s1) + (p2 * s2) + (p3 * s3);
1279        assert_eq!(G1Affine::from(naive_result), G1Affine::from(expected));
1280
1281        // Test msm_vartime
1282        let msm_result_vartime = G1Projective::msm_vartime(&points, &scalars).unwrap();
1283        assert_eq!(G1Affine::from(msm_result_vartime), G1Affine::from(expected));
1284
1285        // Test empty input
1286        let empty_res = G1Projective::msm_vartime(&[], &[]).unwrap();
1287        assert_eq!(empty_res, G1Projective::identity());
1288    }
1289}
dcrypt_algorithms/ec/bls12_381/g1.rs

dcrypt_algorithms/ec/bls12_381/
g1.rs
