miracl_core/bls12381/
ecp2.rs

1/*
2 * Copyright (c) 2012-2020 MIRACL UK Ltd.
3 *
4 * This file is part of MIRACL Core
5 * (see https://github.com/miracl/core).
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 *     http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20use crate::bls12381::big;
21use crate::bls12381::big::BIG;
22use crate::bls12381::ecp;
23use crate::bls12381::fp2::FP2;
24use crate::bls12381::rom;
25use crate::bls12381::fp;
26use crate::bls12381::fp::FP;
27use crate::bls12381::dbig::DBIG;
28
29#[derive(Clone)]
30pub struct ECP2 {
31    x: FP2,
32    y: FP2,
33    z: FP2,
34}
35
36#[cfg(feature = "std")]
37impl std::fmt::Debug for ECP2 {
38    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
39        write!(formatter, "{}", self.tostring())
40    }
41}    
42
43#[cfg(feature = "std")]
44impl std::fmt::Display for ECP2 {
45    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
46        write!(formatter, "{}", self.tostring())
47    }
48}
49
50#[allow(non_snake_case)]
51impl ECP2 {
52    pub fn new() -> ECP2 {
53        ECP2 {
54            x: FP2::new(),
55            y: FP2::new_int(1),
56            z: FP2::new(),
57        }
58    }
59    #[allow(non_snake_case)]
60    /* construct this from (x,y) - but set to O if not on curve */
61    pub fn new_fp2s(ix: &FP2, iy: &FP2) -> ECP2 {
62        let mut E = ECP2::new();
63        E.x.copy(&ix);
64        E.y.copy(&iy);
65        E.z.one();
66        E.x.norm();
67
68        let rhs = ECP2::rhs(&E.x);
69        let mut y2 = FP2::new_copy(&E.y);
70        y2.sqr();
71        if !y2.equals(&rhs) {
72            E.inf();
73        }
74        E
75    }
76
77    /* construct this from x - but set to O if not on curve */
78    pub fn new_fp2(ix: &FP2, s:isize) -> ECP2 {
79        let mut E = ECP2::new();
80        let mut h = FP::new();
81        E.x.copy(&ix);
82        E.y.one();
83        E.z.one();
84        E.x.norm();
85        let mut rhs = ECP2::rhs(&E.x);
86 	    if rhs.qr(Some(&mut h)) == 1 {
87		    rhs.sqrt(Some(&h));
88		    if rhs.sign() != s {
89			    rhs.neg();
90		    }
91		    rhs.reduce();
92		    E.y.copy(&rhs);
93        } else {
94            E.inf();
95        }
96        E
97    }
98
99    /* Test this=O? */
100    pub fn is_infinity(&self) -> bool {
101        self.x.iszilch() && self.z.iszilch()
102    }
103
104    /* copy self=P */
105    pub fn copy(&mut self, P: &ECP2) {
106        self.x.copy(&P.x);
107        self.y.copy(&P.y);
108        self.z.copy(&P.z);
109    }
110
111    /* set self=O */
112    pub fn inf(&mut self) {
113        self.x.zero();
114        self.y.one();
115        self.z.zero();
116    }
117
118    /* set self=-self */
119    pub fn neg(&mut self) {
120        self.y.norm();
121        self.y.neg();
122        self.y.norm();
123    }
124
125    /* Conditional move of Q to self dependant on d */
126    pub fn cmove(&mut self, Q: &ECP2, d: isize) {
127        self.x.cmove(&Q.x, d);
128        self.y.cmove(&Q.y, d);
129        self.z.cmove(&Q.z, d);
130    }
131
132    /* return 1 if b==c, no branching */
133    fn teq(b: i32, c: i32) -> isize {
134        let mut x = b ^ c;
135        x -= 1; // if x=0, x now -1
136        ((x >> 31) & 1) as isize
137    }
138
139    /* Constant time select from pre-computed table */
140    pub fn selector(&mut self, W: &[ECP2], b: i32) {
141        let mut MP = ECP2::new();
142        let m = b >> 31;
143        let mut babs = (b ^ m) - m;
144
145        babs = (babs - 1) / 2;
146
147        self.cmove(&W[0], ECP2::teq(babs, 0)); // conditional move
148        self.cmove(&W[1], ECP2::teq(babs, 1));
149        self.cmove(&W[2], ECP2::teq(babs, 2));
150        self.cmove(&W[3], ECP2::teq(babs, 3));
151        self.cmove(&W[4], ECP2::teq(babs, 4));
152        self.cmove(&W[5], ECP2::teq(babs, 5));
153        self.cmove(&W[6], ECP2::teq(babs, 6));
154        self.cmove(&W[7], ECP2::teq(babs, 7));
155
156        MP.copy(self);
157        MP.neg();
158        self.cmove(&MP, (m & 1) as isize);
159    }
160
161    /* Test if P == Q */
162    pub fn equals(&self, Q: &ECP2) -> bool {
163        let mut a = FP2::new_copy(&self.x);
164        let mut b = FP2::new_copy(&Q.x);
165
166        a.mul(&Q.z);
167        b.mul(&self.z);
168        if !a.equals(&b) {
169            return false;
170        }
171        a.copy(&self.y);
172        a.mul(&Q.z);
173        b.copy(&Q.y);
174        b.mul(&self.z);
175        if !a.equals(&b) {
176            return false;
177        }
178
179        true
180    }
181
182    /* set to Affine - (x,y,z) to (x,y) */
183    pub fn affine(&mut self) {
184        if self.is_infinity() {
185            return;
186        }
187        let one = FP2::new_int(1);
188        if self.z.equals(&one) {
189            return;
190        }
191        self.z.inverse(None);
192
193        self.x.mul(&self.z);
194        self.x.reduce();
195        self.y.mul(&self.z);
196        self.y.reduce();
197        self.z.copy(&one);
198    }
199
200    /* extract affine x as FP2 */
201    pub fn getx(&self) -> FP2 {
202        let mut W = ECP2::new();
203        W.copy(self);
204        W.affine();
205        FP2::new_copy(&W.x)
206    }
207
208    /* extract affine y as FP2 */
209    pub fn gety(&self) -> FP2 {
210        let mut W = ECP2::new();
211        W.copy(self);
212        W.affine();
213        FP2::new_copy(&W.y)
214    }
215
216    /* extract projective x */
217    pub fn getpx(&self) -> FP2 {
218        FP2::new_copy(&self.x)
219    }
220    /* extract projective y */
221    pub fn getpy(&self) -> FP2 {
222        FP2::new_copy(&self.y)
223    }
224    /* extract projective z */
225    pub fn getpz(&self) -> FP2 {
226        FP2::new_copy(&self.z)
227    }
228
229    /* convert to byte array */
230    pub fn tobytes(&self, b: &mut [u8], compress: bool) {
231        const MB:usize = 2*(big::MODBYTES as usize);
232        let mut t: [u8; MB] = [0; MB];
233        let mut alt=false;
234        let mut W = ECP2::new();
235        W.copy(self);
236        W.affine();
237        W.x.tobytes(&mut t);
238
239        if (fp::MODBITS-1)%8 <= 4 && ecp::ALLOW_ALT_COMPRESS {
240            alt=true;
241        }
242        if alt {
243		    for i in 0..MB {
244			    b[i]=t[i]
245		    }
246            if !compress {
247                W.y.tobytes(&mut t);
248                for i in 0..MB {
249				    b[i+MB]=t[i];
250			    }
251            } else {
252                b[0]|=0x80;
253                if W.y.islarger()==1 {
254				    b[0]|=0x20;
255			    }
256            }
257
258	    } else {
259		    for i in 0..MB {
260			    b[i+1]=t[i];
261		    }
262            if !compress {
263                b[0]=0x04;
264                W.y.tobytes(&mut t);
265	            for i in 0..MB {
266			        b[i+MB+1]=t[i];
267			    }
268            } else {
269                b[0]=0x02;
270                if W.y.sign() == 1 {
271                    b[0]=0x03;
272			    }
273            }
274	    }
275    }
276
277    /* convert from byte array to point */
278    pub fn frombytes(b: &[u8]) -> ECP2 {
279        const MB:usize = 2*(big::MODBYTES as usize);
280        let mut t: [u8; MB] = [0; MB];
281        let typ=b[0] as isize;
282        let mut alt=false;
283
284        if (fp::MODBITS-1)%8 <= 4 && ecp::ALLOW_ALT_COMPRESS {
285            alt=true;
286        }
287
288	if alt {
289            for i in 0..MB  {
290			    t[i]=b[i];
291		    }
292            t[0]&=0x1f;
293            let rx=FP2::frombytes(&t);
294            if (b[0]&0x80)==0 {
295                for i in 0..MB {
296				    t[i]=b[i+MB];
297			    }
298                let ry=FP2::frombytes(&t);
299                ECP2::new_fp2s(&rx,&ry)
300            } else {
301                let sgn=(b[0]&0x20)>>5;
302                let mut P=ECP2::new_fp2(&rx,0);
303                let cmp=P.y.islarger();
304                if (sgn == 1 && cmp != 1) || (sgn == 0 && cmp == 1) {
305				    P.neg();
306			    }
307                P
308            }
309        } else {
310            for i in 0..MB {
311                 t[i]=b[i+1];
312            }
313            let rx=FP2::frombytes(&t);
314            if typ == 0x04 {
315		        for i in 0..MB {
316				    t[i]=b[i+MB+1];
317			    }
318		        let ry=FP2::frombytes(&t);
319		        ECP2::new_fp2s(&rx,&ry)
320            } else {
321                ECP2::new_fp2(&rx,typ&1)
322            }
323        }
324    }
325
326    /* convert this to hex string */
327#[cfg(feature = "std")]
328    pub fn tostring(&self) -> String {
329        let mut W = ECP2::new();
330        W.copy(self);
331        W.affine();
332        if W.is_infinity() {
333            String::from("infinity")
334        } else {
335            format!("({},{})", W.x.tostring(), W.y.tostring())
336        }
337    }
338
339    /* Calculate RHS of twisted curve equation x^3+B/i */
340    pub fn rhs(x: &FP2) -> FP2 {
341        let mut r = FP2::new_copy(x);
342        r.sqr();
343        let mut b = FP2::new_big(&BIG::new_ints(&rom::CURVE_B));
344        if ecp::SEXTIC_TWIST == ecp::D_TYPE {
345            b.div_ip();
346        }
347        if ecp::SEXTIC_TWIST == ecp::M_TYPE {
348            b.norm();
349            b.mul_ip();
350            b.norm();
351        }
352
353        r.mul(x);
354        r.add(&b);
355
356        r.reduce();
357        r
358    }
359
360    /* self+=self */
361    pub fn dbl(&mut self) -> isize {
362        let mut iy = FP2::new_copy(&self.y);
363        if ecp::SEXTIC_TWIST == ecp::D_TYPE {
364            iy.mul_ip();
365            iy.norm();
366        }
367
368        let mut t0 = FP2::new_copy(&self.y); //***** Change
369        t0.sqr();
370        if ecp::SEXTIC_TWIST == ecp::D_TYPE {
371            t0.mul_ip();
372        }
373        let mut t1 = FP2::new_copy(&iy);
374        t1.mul(&self.z);
375        let mut t2 = FP2::new_copy(&self.z);
376        t2.sqr();
377
378        self.z.copy(&t0);
379        self.z.add(&t0);
380        self.z.norm();
381        self.z.dbl();
382        self.z.dbl();
383        self.z.norm();
384
385        t2.imul(3 * rom::CURVE_B_I);
386        if ecp::SEXTIC_TWIST == ecp::M_TYPE {
387            t2.mul_ip();
388            t2.norm();
389        }
390        let mut x3 = FP2::new_copy(&t2);
391        x3.mul(&self.z);
392
393        let mut y3 = FP2::new_copy(&t0);
394
395        y3.add(&t2);
396        y3.norm();
397        self.z.mul(&t1);
398        t1.copy(&t2);
399        t1.add(&t2);
400        t2.add(&t1);
401        t2.norm();
402        t0.sub(&t2);
403        t0.norm(); //y^2-9bz^2
404        y3.mul(&t0);
405        y3.add(&x3); //(y^2+3z*2)(y^2-9z^2)+3b.z^2.8y^2
406        t1.copy(&self.x);
407        t1.mul(&iy); //
408        self.x.copy(&t0);
409        self.x.norm();
410        self.x.mul(&t1);
411        self.x.dbl(); //(y^2-9bz^2)xy2
412
413        self.x.norm();
414        self.y.copy(&y3);
415        self.y.norm();
416
417        1
418    }
419
420    /* self+=Q - return 0 for add, 1 for double, -1 for O */
421    pub fn add(&mut self, Q: &ECP2) -> isize {
422        let b = 3 * rom::CURVE_B_I;
423        let mut t0 = FP2::new_copy(&self.x);
424        t0.mul(&Q.x); // x.Q.x
425        let mut t1 = FP2::new_copy(&self.y);
426        t1.mul(&Q.y); // y.Q.y
427
428        let mut t2 = FP2::new_copy(&self.z);
429        t2.mul(&Q.z);
430        let mut t3 = FP2::new_copy(&self.x);
431        t3.add(&self.y);
432        t3.norm(); //t3=X1+Y1
433        let mut t4 = FP2::new_copy(&Q.x);
434        t4.add(&Q.y);
435        t4.norm(); //t4=X2+Y2
436        t3.mul(&t4); //t3=(X1+Y1)(X2+Y2)
437        t4.copy(&t0);
438        t4.add(&t1); //t4=X1.X2+Y1.Y2
439
440        t3.sub(&t4);
441        t3.norm();
442        if ecp::SEXTIC_TWIST == ecp::D_TYPE {
443            t3.mul_ip();
444            t3.norm(); //t3=(X1+Y1)(X2+Y2)-(X1.X2+Y1.Y2) = X1.Y2+X2.Y1
445        }
446        t4.copy(&self.y);
447        t4.add(&self.z);
448        t4.norm(); //t4=Y1+Z1
449        let mut x3 = FP2::new_copy(&Q.y);
450        x3.add(&Q.z);
451        x3.norm(); //x3=Y2+Z2
452
453        t4.mul(&x3); //t4=(Y1+Z1)(Y2+Z2)
454        x3.copy(&t1); //
455        x3.add(&t2); //X3=Y1.Y2+Z1.Z2
456
457        t4.sub(&x3);
458        t4.norm();
459        if ecp::SEXTIC_TWIST == ecp::D_TYPE {
460            t4.mul_ip();
461            t4.norm(); //t4=(Y1+Z1)(Y2+Z2) - (Y1.Y2+Z1.Z2) = Y1.Z2+Y2.Z1
462        }
463        x3.copy(&self.x);
464        x3.add(&self.z);
465        x3.norm(); // x3=X1+Z1
466        let mut y3 = FP2::new_copy(&Q.x);
467        y3.add(&Q.z);
468        y3.norm(); // y3=X2+Z2
469        x3.mul(&y3); // x3=(X1+Z1)(X2+Z2)
470        y3.copy(&t0);
471        y3.add(&t2); // y3=X1.X2+Z1+Z2
472        y3.rsub(&x3);
473        y3.norm(); // y3=(X1+Z1)(X2+Z2) - (X1.X2+Z1.Z2) = X1.Z2+X2.Z1
474
475        if ecp::SEXTIC_TWIST == ecp::D_TYPE {
476            t0.mul_ip();
477            t0.norm(); // x.Q.x
478            t1.mul_ip();
479            t1.norm(); // y.Q.y
480        }
481        x3.copy(&t0);
482        x3.add(&t0);
483        t0.add(&x3);
484        t0.norm();
485        t2.imul(b);
486        if ecp::SEXTIC_TWIST == ecp::M_TYPE {
487            t2.mul_ip();
488            t2.norm();
489        }
490        let mut z3 = FP2::new_copy(&t1);
491        z3.add(&t2);
492        z3.norm();
493        t1.sub(&t2);
494        t1.norm();
495        y3.imul(b);
496        if ecp::SEXTIC_TWIST == ecp::M_TYPE {
497            y3.mul_ip();
498            y3.norm();
499        }
500        x3.copy(&y3);
501        x3.mul(&t4);
502        t2.copy(&t3);
503        t2.mul(&t1);
504        x3.rsub(&t2);
505        y3.mul(&t0);
506        t1.mul(&z3);
507        y3.add(&t1);
508        t0.mul(&t3);
509        z3.mul(&t4);
510        z3.add(&t0);
511
512        self.x.copy(&x3);
513        self.x.norm();
514        self.y.copy(&y3);
515        self.y.norm();
516        self.z.copy(&z3);
517        self.z.norm();
518
519        0
520    }
521
522    /* set this-=Q */
523    pub fn sub(&mut self, Q: &ECP2) -> isize {
524        let mut NQ = ECP2::new();
525        NQ.copy(Q);
526        NQ.neg();
527        self.add(&NQ)
528    }
529
530    /* set this*=q, where q is Modulus, using Frobenius */
531    pub fn frob(&mut self, x: &FP2) {
532        let mut x2 = FP2::new_copy(x);
533        x2.sqr();
534        self.x.conj();
535        self.y.conj();
536        self.z.conj();
537        self.z.reduce();
538        self.x.mul(&x2);
539        self.y.mul(&x2);
540        self.y.mul(x);
541    }
542
543    /* self*=e */
544    pub fn mul(&self, e: &BIG) -> ECP2 {
545        /* fixed size windows */
546        let mut mt = BIG::new();
547        let mut t = BIG::new();
548        let mut P = ECP2::new();
549        let mut Q = ECP2::new();
550        let mut C = ECP2::new();
551
552        if self.is_infinity() {
553            return P;
554        }
555
556        let mut W: [ECP2; 8] = [
557            ECP2::new(),
558            ECP2::new(),
559            ECP2::new(),
560            ECP2::new(),
561            ECP2::new(),
562            ECP2::new(),
563            ECP2::new(),
564            ECP2::new(),
565        ];
566
567        const CT: usize = 1 + (big::NLEN * (big::BASEBITS as usize) + 3) / 4;
568        let mut w: [i8; CT] = [0; CT];
569
570        /* precompute table */
571        Q.copy(&self);
572        Q.dbl();
573
574        W[0].copy(&self);
575
576        for i in 1..8 {
577            C.copy(&W[i - 1]);
578            W[i].copy(&C);
579            W[i].add(&Q);
580        }
581
582        /* make exponent odd - add 2P if even, P if odd */
583        t.copy(&e);
584        let s = t.parity();
585        t.inc(1);
586        t.norm();
587        let ns = t.parity();
588        mt.copy(&t);
589        mt.inc(1);
590        mt.norm();
591        t.cmove(&mt, s);
592        Q.cmove(&self, ns);
593        C.copy(&Q);
594
595        let nb = 1 + (t.nbits() + 3) / 4;
596
597        /* convert exponent to signed 4-bit window */
598        for i in 0..nb {
599            w[i] = (t.lastbits(5) - 16) as i8;
600            t.dec(w[i] as isize);
601            t.norm();
602            t.fshr(4);
603        }
604        w[nb] = (t.lastbits(5)) as i8;
605
606        //P.copy(&W[((w[nb] as usize) - 1) / 2]);
607
608        P.selector(&W, w[nb] as i32);
609        for i in (0..nb).rev() {
610            Q.selector(&W, w[i] as i32);
611            P.dbl();
612            P.dbl();
613            P.dbl();
614            P.dbl();
615            P.add(&Q);
616        }
617        P.sub(&C);
618        P
619    }
620
621    #[allow(non_snake_case)]
622    pub fn cfp(&mut self)  {
623        let mut X = FP2::new_bigs(&BIG::new_ints(&rom::FRA), &BIG::new_ints(&rom::FRB));
624        if ecp::SEXTIC_TWIST == ecp::M_TYPE {
625            X.inverse(None);
626            X.norm();
627        }
628        let x = BIG::new_ints(&rom::CURVE_BNX);
629    // Faster Hashing to G2 - Fuentes-Castaneda, Knapp and Rodriguez-Henriquez
630    // Q -> xQ + F(3xQ) + F(F(xQ)) + F(F(F(Q))).
631        if ecp::CURVE_PAIRING_TYPE == ecp::BN {
632            let mut T = self.mul(&x);
633            if ecp::SIGN_OF_X == ecp::NEGATIVEX {
634                T.neg();
635            }
636            let mut K = ECP2::new();
637            K.copy(&T);
638            K.dbl();
639            K.add(&T);
640
641            K.frob(&X);
642            self.frob(&X);
643            self.frob(&X);
644            self.frob(&X);
645            self.add(&T);
646            self.add(&K);
647            T.frob(&X);
648            T.frob(&X);
649            self.add(&T);
650        }
651    // Efficient hash maps to G2 on BLS curves - Budroni, Pintore
652    // Q -> x2Q -xQ -Q +F(xQ -Q) +F(F(2Q))
653        if ecp::CURVE_PAIRING_TYPE > ecp::BN {
654            let mut xQ = self.mul(&x);
655            let mut x2Q = xQ.mul(&x);
656
657            if ecp::SIGN_OF_X == ecp::NEGATIVEX {
658                xQ.neg();
659            }
660            x2Q.sub(&xQ);
661            x2Q.sub(&self);
662
663            xQ.sub(&self);
664            xQ.frob(&X);
665
666            self.dbl();
667            self.frob(&X);
668            self.frob(&X);
669
670            self.add(&x2Q);
671            self.add(&xQ);
672        }
673    }
674
675
676    /* P=u0.Q0+u1*Q1+u2*Q2+u3*Q3 */
677    // Bos & Costello https://eprint.iacr.org/2013/458.pdf
678    // Faz-Hernandez & Longa & Sanchez  https://eprint.iacr.org/2013/158.pdf
679    // Side channel attack secure
680
681    pub fn mul4(Q: &[ECP2], u: &[BIG]) -> ECP2 {
682        let mut W = ECP2::new();
683        let mut P = ECP2::new();
684
685        let mut T: [ECP2; 8] = [
686            ECP2::new(),
687            ECP2::new(),
688            ECP2::new(),
689            ECP2::new(),
690            ECP2::new(),
691            ECP2::new(),
692            ECP2::new(),
693            ECP2::new(),
694        ];
695
696        let mut mt = BIG::new();
697
698        let mut t: [BIG; 4] = [
699            BIG::new_copy(&u[0]),
700            BIG::new_copy(&u[1]),
701            BIG::new_copy(&u[2]),
702            BIG::new_copy(&u[3]),
703        ];
704
705        const CT: usize = 1 + big::NLEN * (big::BASEBITS as usize);
706        let mut w: [i8; CT] = [0; CT];
707        let mut s: [i8; CT] = [0; CT];
708
709        for i in 0..4 {
710            t[i].norm();
711        }
712
713        T[0].copy(&Q[0]);
714        W.copy(&T[0]);
715        T[1].copy(&W);
716        T[1].add(&Q[1]); // Q[0]+Q[1]
717        T[2].copy(&W);
718        T[2].add(&Q[2]);
719        W.copy(&T[1]); // Q[0]+Q[2]
720        T[3].copy(&W);
721        T[3].add(&Q[2]);
722        W.copy(&T[0]); // Q[0]+Q[1]+Q[2]
723        T[4].copy(&W);
724        T[4].add(&Q[3]);
725        W.copy(&T[1]); // Q[0]+Q[3]
726        T[5].copy(&W);
727        T[5].add(&Q[3]);
728        W.copy(&T[2]); // Q[0]+Q[1]+Q[3]
729        T[6].copy(&W);
730        T[6].add(&Q[3]);
731        W.copy(&T[3]); // Q[0]+Q[2]+Q[3]
732        T[7].copy(&W);
733        T[7].add(&Q[3]); // Q[0]+Q[1]+Q[2]+Q[3]
734
735        // Make it odd
736        let pb = 1 - t[0].parity();
737        t[0].inc(pb);
738        t[0].norm();
739
740        // Number of bits
741        mt.zero();
742        for i in 0..4 {
743            mt.or(&t[i]);
744        }
745
746        let nb = 1 + mt.nbits();
747
748        // Sign pivot
749
750        s[nb - 1] = 1;
751        for i in 0..nb - 1 {
752            t[0].fshr(1);
753            s[i] = (2 * t[0].parity() - 1) as i8;
754        }
755
756        // Recoded exponent
757        for i in 0..nb {
758            w[i] = 0;
759            let mut k = 1;
760            for j in 1..4 {
761                let bt = s[i] * (t[j].parity() as i8);
762                t[j].fshr(1);
763                t[j].dec((bt >> 1) as isize);
764                t[j].norm();
765                w[i] += bt * (k as i8);
766                k *= 2;
767            }
768        }
769
770        // Main loop
771        P.selector(&T, (2 * w[nb - 1] + 1) as i32);
772        for i in (0..nb - 1).rev() {
773            P.dbl();
774            W.selector(&T, (2 * w[i] + s[i]) as i32);
775            P.add(&W);
776        }
777
778        // apply correction
779        W.copy(&P);
780        W.sub(&Q[0]);
781        P.cmove(&W, pb);
782
783        P
784    }
785
786/* Hunt and Peck a BIG to a curve point */
787    #[allow(non_snake_case)]
788    pub fn hap2point(h: &BIG) -> ECP2 {
789        let mut Q: ECP2;
790        let one = BIG::new_int(1);
791        let mut x =BIG::new_copy(&h);
792        loop {
793            let X = FP2::new_bigs(&one, &x);
794            Q = ECP2::new_fp2(&X,0);
795            if !Q.is_infinity() {
796                break;
797            }
798            x.inc(1);
799            x.norm();
800        }
801        Q
802    }
803
804/* Constant time Map to Point */
805    #[allow(unreachable_code)]
806    #[allow(non_snake_case)]
807    pub fn map2point(H: &FP2) -> ECP2 {
808        let mut T=FP2::new_copy(H); /**/
809        let sgn=T.sign(); /**/
810        if ecp::HTC_ISO_G2 == 0 {
811    // Shallue and van de Woestijne
812/* CAHCNZS
813            let mut NY=FP2::new_int(1);
814            let mut Z=FP::new_int(fp::RIADZG2A);
815            let mut X1=FP2::new_fp(&Z);
816            let mut X3=FP2::new_copy(&X1);
817            let mut A=ECP2::rhs(&X1);
818            let mut W=FP2::new_copy(&A);
819
820            if fp::RIADZG2A==-1 && fp::RIADZG2B==0 && ecp::SEXTIC_TWIST == ecp::M_TYPE && rom::CURVE_B_I==4 {
821                W.copy(&FP2::new_ints(2,1));
822            } else {
823                W.sqrt(None);
824            }
825            let s = FP::new_big(&BIG::new_ints(&rom::SQRTM3));
826            Z.mul(&s);
827
828            T.sqr();
829            let mut Y=FP2::new_copy(&A); Y.mul(&T);
830            T.copy(&NY); T.add(&Y); T.norm();
831            Y.rsub(&NY); Y.norm();
832            NY.copy(&T); NY.mul(&Y); 
833        
834            NY.pmul(&Z);
835            NY.inverse(None);
836
837            W.pmul(&Z);
838            if W.sign()==1 {
839                W.neg();
840                W.norm();
841            }
842            W.pmul(&Z);
843            W.mul(&H); W.mul(&Y); W.mul(&NY);
844
845            X1.neg(); X1.norm(); X1.div2();
846            let mut X2=FP2::new_copy(&X1);
847            X1.sub(&W); X1.norm();
848            X2.add(&W); X2.norm();
849            A.dbl(); A.dbl(); A.norm();
850            T.sqr(); T.mul(&NY); T.sqr();
851            A.mul(&T);
852            X3.add(&A); X3.norm();
853
854            Y.copy(&ECP2::rhs(&X2));
855            X3.cmove(&X2,Y.qr(None));
856            Y.copy(&ECP2::rhs(&X1));
857            X3.cmove(&X1,Y.qr(None));
858            Y.copy(&ECP2::rhs(&X3));
859            Y.sqrt(None);
860
861            let ne=Y.sign()^sgn;
862            W.copy(&Y); W.neg(); W.norm();
863            Y.cmove(&W,ne);
864
865            return ECP2::new_fp2s(&X3,&Y);
866CAHCNZF */
867        } else {
868/* */
869            let NY=FP2::new_int(1);
870            let Ad=FP2::new_bigs(&BIG::new_ints(&rom::CURVE_ADR),&BIG::new_ints(&rom::CURVE_ADI));
871            let Bd=FP2::new_bigs(&BIG::new_ints(&rom::CURVE_BDR),&BIG::new_ints(&rom::CURVE_BDI));  
872            let ZZ=FP2::new_ints(fp::RIADZG2A,fp::RIADZG2B);
873            let mut hint=FP::new();
874
875            T.sqr();
876            T.mul(&ZZ);
877            let mut W=FP2::new_copy(&T);
878            W.add(&NY); W.norm();
879
880            W.mul(&T);
881            let mut D=FP2::new_copy(&Ad);
882            D.mul(&W);
883    
884            W.add(&NY); W.norm();
885            W.mul(&Bd);
886            W.neg(); W.norm();
887
888            let mut X2=FP2::new_copy(&W);
889            let mut X3=FP2::new_copy(&T);
890            X3.mul(&X2);
891
892            let mut GX1=FP2::new_copy(&X2); GX1.sqr();
893            let mut D2=FP2::new_copy(&D); D2.sqr();
894
895            W.copy(&Ad); W.mul(&D2); GX1.add(&W); GX1.norm(); GX1.mul(&X2); D2.mul(&D); W.copy(&Bd); W.mul(&D2); GX1.add(&W); GX1.norm(); // x^3+Ax+b
896
897            W.copy(&GX1); W.mul(&D);
898            let qr=W.qr(Some(&mut hint));
899            D.copy(&W); D.inverse(Some(&hint));
900            D.mul(&GX1);
901            X2.mul(&D);
902            X3.mul(&D);
903            T.mul(&H);
904            D2.copy(&D); D2.sqr();
905
906            D.copy(&D2); D.mul(&T);
907            T.copy(&W); T.mul(&ZZ);
908
909            let mut s=FP::new_big(&BIG::new_ints(&rom::CURVE_HTPC2));
910            s.mul(&hint);
911
912            X2.cmove(&X3,1-qr);
913            W.cmove(&T,1-qr);
914            D2.cmove(&D,1-qr);
915            hint.cmove(&s,1-qr);
916
917            let mut Y=FP2::new_copy(&W); Y.sqrt(Some(&hint));
918            Y.mul(&D2);
919
920            let ne=Y.sign()^sgn;
921            W.copy(&Y); W.neg(); W.norm();
922            Y.cmove(&W,ne);
923
924            let mut k=0;
925            let isox=ecp::HTC_ISO_G2;
926            let isoy=3*(isox-1)/2;
927
928        // xnum
929            let mut xnum=FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k])); k+=1;
930            for _ in 0..isox {
931                xnum.mul(&X2);
932                xnum.add(&FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k]))); k+=1;
933                xnum.norm();
934            }
935        //xden
936            let mut xden=FP2::new_copy(&X2);
937            xden.add(&FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k]))); k+=1;
938            xden.norm();
939            for _ in 0..isox-2 {
940                xden.mul(&X2);
941                xden.add(&FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k]))); k+=1;
942                xden.norm();                
943            }
944        //ynum
945            let mut ynum=FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k])); k+=1;            
946            for _ in 0..isoy {
947                ynum.mul(&X2);
948                ynum.add(&FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k]))); k+=1;
949                ynum.norm();
950            }
951        //yden
952            let mut yden=FP2::new_copy(&X2);
953            yden.add(&FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k]))); k+=1;
954            yden.norm(); 
955            for _ in 0..isoy-1 {
956                yden.mul(&X2);
957                yden.add(&FP2::new_bigs(&BIG::new_ints(&rom::PCR[k]),&BIG::new_ints(&rom::PCI[k]))); k+=1;
958                yden.norm();
959            }
960            ynum.mul(&Y);
961
962            let mut Q=ECP2::new();
963            T.copy(&xnum); T.mul(&yden);
964            Q.x.copy(&T);
965            T.copy(&ynum); T.mul(&xden);
966            Q.y.copy(&T);
967            T.copy(&xden); T.mul(&yden);
968            Q.z.copy(&T);
969            return Q;
970/* */
971
972        }
973        ECP2::new()
974    }
975
976/* Map byte string to curve point */
977    #[allow(non_snake_case)]
978    pub fn mapit(h: &[u8]) -> ECP2 {
979        let q = BIG::new_ints(&rom::MODULUS);
980        let mut dx = DBIG::frombytes(h);
981        let x=dx.dmod(&q);
982        let mut P=ECP2::hap2point(&x);
983        P.cfp();
984        P
985    }
986
987    pub fn generator() -> ECP2 {
988        ECP2::new_fp2s(
989            &FP2::new_bigs(
990                &BIG::new_ints(&rom::CURVE_PXA),
991                &BIG::new_ints(&rom::CURVE_PXB),
992            ),
993            &FP2::new_bigs(
994                &BIG::new_ints(&rom::CURVE_PYA),
995                &BIG::new_ints(&rom::CURVE_PYB),
996            ),
997        )
998    }
999}
miracl_core/bls12381/ecp2.rs

miracl_core/bls12381/
ecp2.rs
