| /* |
| Licensed to the Apache Software Foundation (ASF) under one |
| or more contributor license agreements. See the NOTICE file |
| distributed with this work for additional information |
| regarding copyright ownership. The ASF licenses this file |
| to you under the Apache License, Version 2.0 (the |
| "License"); you may not use this file except in compliance |
| with the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, |
| software distributed under the License is distributed on an |
| "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| KIND, either express or implied. See the License for the |
| specific language governing permissions and limitations |
| under the License. |
| */ |
| |
| /* AMCL Weierstrass elliptic curve functions over FP2 */ |
| |
| package amcl |
| |
| //import "fmt" |
| |
| type ECP2 struct { |
| x *FP2 |
| y *FP2 |
| z *FP2 |
| INF bool |
| } |
| |
| func NewECP2() *ECP2 { |
| E := new(ECP2) |
| E.x = NewFP2int(0) |
| E.y = NewFP2int(1) |
| E.z = NewFP2int(1) |
| E.INF = true |
| return E |
| } |
| |
| /* Test this=O? */ |
| func (E *ECP2) is_infinity() bool { |
| return E.INF |
| } |
| |
| /* copy this=P */ |
| func (E *ECP2) copy(P *ECP2) { |
| E.x.copy(P.x) |
| E.y.copy(P.y) |
| E.z.copy(P.z) |
| E.INF = P.INF |
| } |
| |
| /* set this=O */ |
| func (E *ECP2) inf() { |
| E.INF = true |
| E.x.zero() |
| E.y.zero() |
| E.z.zero() |
| } |
| |
| /* set this=-this */ |
| func (E *ECP2) neg() { |
| if E.is_infinity() { |
| return |
| } |
| E.y.neg() |
| E.y.reduce() |
| } |
| |
| /* Conditional move of Q to P dependant on d */ |
| func (E *ECP2) cmove(Q *ECP2, d int32) { |
| E.x.cmove(Q.x, d) |
| E.y.cmove(Q.y, d) |
| E.z.cmove(Q.z, d) |
| |
| var bd bool |
| if d == 0 { |
| bd = false |
| } else { |
| bd = true |
| } |
| E.INF = (E.INF != (E.INF != Q.INF) && bd) |
| } |
| |
| /* Constant time select from pre-computed table */ |
| func (E *ECP2) selector(W []*ECP2, b int32) { |
| MP := NewECP2() |
| m := b >> 31 |
| babs := (b ^ m) - m |
| |
| babs = (babs - 1) / 2 |
| |
| E.cmove(W[0], teq(babs, 0)) // conditional move |
| E.cmove(W[1], teq(babs, 1)) |
| E.cmove(W[2], teq(babs, 2)) |
| E.cmove(W[3], teq(babs, 3)) |
| E.cmove(W[4], teq(babs, 4)) |
| E.cmove(W[5], teq(babs, 5)) |
| E.cmove(W[6], teq(babs, 6)) |
| E.cmove(W[7], teq(babs, 7)) |
| |
| MP.copy(E) |
| MP.neg() |
| E.cmove(MP, (m & 1)) |
| } |
| |
| /* Test if P == Q */ |
| func (E *ECP2) equals(Q *ECP2) bool { |
| if E.is_infinity() && Q.is_infinity() { |
| return true |
| } |
| if E.is_infinity() || Q.is_infinity() { |
| return false |
| } |
| |
| zs2 := NewFP2copy(E.z) |
| zs2.sqr() |
| zo2 := NewFP2copy(Q.z) |
| zo2.sqr() |
| zs3 := NewFP2copy(zs2) |
| zs3.mul(E.z) |
| zo3 := NewFP2copy(zo2) |
| zo3.mul(Q.z) |
| zs2.mul(Q.x) |
| zo2.mul(E.x) |
| if !zs2.equals(zo2) { |
| return false |
| } |
| zs3.mul(Q.y) |
| zo3.mul(E.y) |
| if !zs3.equals(zo3) { |
| return false |
| } |
| |
| return true |
| } |
| |
| /* set to Affine - (x,y,z) to (x,y) */ |
| func (E *ECP2) affine() { |
| if E.is_infinity() { |
| return |
| } |
| one := NewFP2int(1) |
| if E.z.equals(one) { |
| return |
| } |
| E.z.inverse() |
| |
| z2 := NewFP2copy(E.z) |
| z2.sqr() |
| E.x.mul(z2) |
| E.x.reduce() |
| E.y.mul(z2) |
| E.y.mul(E.z) |
| E.y.reduce() |
| E.z.copy(one) |
| } |
| |
| /* extract affine x as FP2 */ |
| func (E *ECP2) getX() *FP2 { |
| E.affine() |
| return E.x |
| } |
| |
| /* extract affine y as FP2 */ |
| func (E *ECP2) getY() *FP2 { |
| E.affine() |
| return E.y |
| } |
| |
| /* extract projective x */ |
| func (E *ECP2) getx() *FP2 { |
| return E.x |
| } |
| |
| /* extract projective y */ |
| func (E *ECP2) gety() *FP2 { |
| return E.y |
| } |
| |
| /* extract projective z */ |
| func (E *ECP2) getz() *FP2 { |
| return E.z |
| } |
| |
| /* convert to byte array */ |
| func (E *ECP2) toBytes(b []byte) { |
| var t [int(MODBYTES)]byte |
| MB := int(MODBYTES) |
| |
| E.affine() |
| E.x.getA().toBytes(t[:]) |
| for i := 0; i < MB; i++ { |
| b[i] = t[i] |
| } |
| E.x.getB().toBytes(t[:]) |
| for i := 0; i < MB; i++ { |
| b[i+MB] = t[i] |
| } |
| |
| E.y.getA().toBytes(t[:]) |
| for i := 0; i < MB; i++ { |
| b[i+2*MB] = t[i] |
| } |
| E.y.getB().toBytes(t[:]) |
| for i := 0; i < MB; i++ { |
| b[i+3*MB] = t[i] |
| } |
| } |
| |
| /* convert from byte array to point */ |
| func ECP2_fromBytes(b []byte) *ECP2 { |
| var t [int(MODBYTES)]byte |
| MB := int(MODBYTES) |
| |
| for i := 0; i < MB; i++ { |
| t[i] = b[i] |
| } |
| ra := fromBytes(t[:]) |
| for i := 0; i < MB; i++ { |
| t[i] = b[i+MB] |
| } |
| rb := fromBytes(t[:]) |
| rx := NewFP2bigs(ra, rb) |
| |
| for i := 0; i < MB; i++ { |
| t[i] = b[i+2*MB] |
| } |
| ra = fromBytes(t[:]) |
| for i := 0; i < MB; i++ { |
| t[i] = b[i+3*MB] |
| } |
| rb = fromBytes(t[:]) |
| ry := NewFP2bigs(ra, rb) |
| |
| return NewECP2fp2s(rx, ry) |
| } |
| |
| /* convert this to hex string */ |
| func (E *ECP2) toString() string { |
| if E.is_infinity() { |
| return "infinity" |
| } |
| E.affine() |
| return "(" + E.x.toString() + "," + E.y.toString() + ")" |
| } |
| |
| /* Calculate RHS of twisted curve equation x^3+B/i */ |
| func RHS2(x *FP2) *FP2 { |
| x.norm() |
| r := NewFP2copy(x) |
| r.sqr() |
| b := NewFP2big(NewBIGints(CURVE_B)) |
| b.div_ip() |
| r.mul(x) |
| r.add(b) |
| |
| r.reduce() |
| return r |
| } |
| |
| /* construct this from (x,y) - but set to O if not on curve */ |
| func NewECP2fp2s(ix *FP2, iy *FP2) *ECP2 { |
| E := new(ECP2) |
| E.x = NewFP2copy(ix) |
| E.y = NewFP2copy(iy) |
| E.z = NewFP2int(1) |
| rhs := RHS2(E.x) |
| y2 := NewFP2copy(E.y) |
| y2.sqr() |
| if y2.equals(rhs) { |
| E.INF = false |
| } else { |
| E.x.zero() |
| E.INF = true |
| } |
| return E |
| } |
| |
| /* construct this from x - but set to O if not on curve */ |
| func NewECP2fp2(ix *FP2) *ECP2 { |
| E := new(ECP2) |
| E.x = NewFP2copy(ix) |
| E.y = NewFP2int(1) |
| E.z = NewFP2int(1) |
| rhs := RHS2(E.x) |
| if rhs.sqrt() { |
| E.y.copy(rhs) |
| E.INF = false |
| } else { |
| E.x.zero() |
| E.INF = true |
| } |
| return E |
| } |
| |
| /* this+=this */ |
| func (E *ECP2) dbl() int { |
| if E.INF { |
| return -1 |
| } |
| if E.y.iszilch() { |
| E.inf() |
| return -1 |
| } |
| |
| w1 := NewFP2copy(E.x) |
| w2 := NewFP2int(0) |
| w3 := NewFP2copy(E.x) |
| w8 := NewFP2copy(E.x) |
| |
| w1.sqr() |
| w8.copy(w1) |
| w8.imul(3) |
| |
| w2.copy(E.y) |
| w2.sqr() |
| w3.copy(E.x) |
| w3.mul(w2) |
| w3.imul(4) |
| w1.copy(w3) |
| w1.neg() |
| // w1.norm(); |
| |
| E.x.copy(w8) |
| E.x.sqr() |
| E.x.add(w1) |
| E.x.add(w1) |
| E.x.norm() |
| |
| E.z.mul(E.y) |
| E.z.add(E.z) |
| |
| w2.add(w2) |
| w2.sqr() |
| w2.add(w2) |
| w3.sub(E.x) |
| E.y.copy(w8) |
| E.y.mul(w3) |
| // w2.norm(); |
| E.y.sub(w2) |
| |
| E.y.norm() |
| E.z.norm() |
| |
| return 1 |
| } |
| |
| /* this+=Q - return 0 for add, 1 for double, -1 for O */ |
| func (E *ECP2) add(Q *ECP2) int { |
| if E.INF { |
| E.copy(Q) |
| return -1 |
| } |
| if Q.INF { |
| return -1 |
| } |
| |
| aff := false |
| |
| if Q.z.isunity() { |
| aff = true |
| } |
| |
| var A, C *FP2 |
| B := NewFP2copy(E.z) |
| D := NewFP2copy(E.z) |
| if !aff { |
| A = NewFP2copy(Q.z) |
| C = NewFP2copy(Q.z) |
| |
| A.sqr() |
| B.sqr() |
| C.mul(A) |
| D.mul(B) |
| |
| A.mul(E.x) |
| C.mul(E.y) |
| } else { |
| A = NewFP2copy(E.x) |
| C = NewFP2copy(E.y) |
| |
| B.sqr() |
| D.mul(B) |
| } |
| |
| B.mul(Q.x) |
| B.sub(A) |
| D.mul(Q.y) |
| D.sub(C) |
| |
| if B.iszilch() { |
| if D.iszilch() { |
| E.dbl() |
| return 1 |
| } else { |
| E.INF = true |
| return -1 |
| } |
| } |
| |
| if !aff { |
| E.z.mul(Q.z) |
| } |
| E.z.mul(B) |
| |
| e := NewFP2copy(B) |
| e.sqr() |
| B.mul(e) |
| A.mul(e) |
| |
| e.copy(A) |
| e.add(A) |
| e.add(B) |
| E.x.copy(D) |
| E.x.sqr() |
| E.x.sub(e) |
| |
| A.sub(E.x) |
| E.y.copy(A) |
| E.y.mul(D) |
| C.mul(B) |
| E.y.sub(C) |
| |
| E.x.norm() |
| E.y.norm() |
| E.z.norm() |
| |
| return 0 |
| } |
| |
| /* set this-=Q */ |
| func (E *ECP2) sub(Q *ECP2) int { |
| Q.neg() |
| D := E.add(Q) |
| Q.neg() |
| return D |
| } |
| |
| /* set this*=q, where q is Modulus, using Frobenius */ |
| func (E *ECP2) frob(X *FP2) { |
| if E.INF { |
| return |
| } |
| X2 := NewFP2copy(X) |
| X2.sqr() |
| E.x.conj() |
| E.y.conj() |
| E.z.conj() |
| E.z.reduce() |
| E.x.mul(X2) |
| E.y.mul(X2) |
| E.y.mul(X) |
| } |
| |
| /* normalises m-array of ECP2 points. Requires work vector of m FP2s */ |
| |
| func multiaffine2(m int, P []*ECP2) { |
| t1 := NewFP2int(0) |
| t2 := NewFP2int(0) |
| |
| var work []*FP2 |
| |
| for i := 0; i < m; i++ { |
| work = append(work, NewFP2int(0)) |
| } |
| |
| work[0].one() |
| work[1].copy(P[0].z) |
| |
| for i := 2; i < m; i++ { |
| work[i].copy(work[i-1]) |
| work[i].mul(P[i-1].z) |
| } |
| |
| t1.copy(work[m-1]) |
| t1.mul(P[m-1].z) |
| |
| t1.inverse() |
| |
| t2.copy(P[m-1].z) |
| work[m-1].mul(t1) |
| |
| for i := m - 2; ; i-- { |
| if i == 0 { |
| work[0].copy(t1) |
| work[0].mul(t2) |
| break |
| } |
| work[i].mul(t2) |
| work[i].mul(t1) |
| t2.mul(P[i].z) |
| } |
| /* now work[] contains inverses of all Z coordinates */ |
| |
| for i := 0; i < m; i++ { |
| P[i].z.one() |
| t1.copy(work[i]) |
| t1.sqr() |
| P[i].x.mul(t1) |
| t1.mul(work[i]) |
| P[i].y.mul(t1) |
| } |
| } |
| |
| /* P*=e */ |
| func (E *ECP2) mul(e *BIG) *ECP2 { |
| /* fixed size windows */ |
| mt := NewBIG() |
| t := NewBIG() |
| P := NewECP2() |
| Q := NewECP2() |
| C := NewECP2() |
| |
| if E.is_infinity() { |
| return NewECP2() |
| } |
| |
| var W []*ECP2 |
| var w [1 + (NLEN*int(BASEBITS)+3)/4]int8 |
| |
| E.affine() |
| |
| /* precompute table */ |
| Q.copy(E) |
| Q.dbl() |
| |
| W = append(W, NewECP2()) |
| W[0].copy(E) |
| |
| for i := 1; i < 8; i++ { |
| W = append(W, NewECP2()) |
| W[i].copy(W[i-1]) |
| W[i].add(Q) |
| } |
| |
| /* convert the table to affine */ |
| |
| multiaffine2(8, W[:]) |
| |
| /* make exponent odd - add 2P if even, P if odd */ |
| t.copy(e) |
| s := int32(t.parity()) |
| t.inc(1) |
| t.norm() |
| ns := int32(t.parity()) |
| mt.copy(t) |
| mt.inc(1) |
| mt.norm() |
| t.cmove(mt, s) |
| Q.cmove(E, ns) |
| C.copy(Q) |
| |
| nb := 1 + (t.nbits()+3)/4 |
| /* convert exponent to signed 4-bit window */ |
| for i := 0; i < nb; i++ { |
| w[i] = int8(t.lastbits(5) - 16) |
| t.dec(int(w[i])) |
| t.norm() |
| t.fshr(4) |
| } |
| w[nb] = int8(t.lastbits(5)) |
| |
| P.copy(W[(w[nb]-1)/2]) |
| for i := nb - 1; i >= 0; i-- { |
| Q.selector(W, int32(w[i])) |
| P.dbl() |
| P.dbl() |
| P.dbl() |
| P.dbl() |
| P.add(Q) |
| } |
| P.sub(C) |
| P.affine() |
| return P |
| } |
| |
| /* P=u0.Q0+u1*Q1+u2*Q2+u3*Q3 */ |
| func mul4(Q []*ECP2, u []*BIG) *ECP2 { |
| var a [4]int8 |
| T := NewECP2() |
| C := NewECP2() |
| P := NewECP2() |
| |
| var W []*ECP2 |
| |
| mt := NewBIG() |
| var t []*BIG |
| |
| var w [NLEN*int(BASEBITS) + 1]int8 |
| |
| for i := 0; i < 4; i++ { |
| t = append(t, NewBIGcopy(u[i])) |
| Q[i].affine() |
| } |
| |
| /* precompute table */ |
| |
| W = append(W, NewECP2()) |
| W[0].copy(Q[0]) |
| W[0].sub(Q[1]) |
| W = append(W, NewECP2()) |
| W[1].copy(W[0]) |
| W = append(W, NewECP2()) |
| W[2].copy(W[0]) |
| W = append(W, NewECP2()) |
| W[3].copy(W[0]) |
| W = append(W, NewECP2()) |
| W[4].copy(Q[0]) |
| W[4].add(Q[1]) |
| W = append(W, NewECP2()) |
| W[5].copy(W[4]) |
| W = append(W, NewECP2()) |
| W[6].copy(W[4]) |
| W = append(W, NewECP2()) |
| W[7].copy(W[4]) |
| |
| T.copy(Q[2]) |
| T.sub(Q[3]) |
| W[1].sub(T) |
| W[2].add(T) |
| W[5].sub(T) |
| W[6].add(T) |
| T.copy(Q[2]) |
| T.add(Q[3]) |
| W[0].sub(T) |
| W[3].add(T) |
| W[4].sub(T) |
| W[7].add(T) |
| |
| multiaffine2(8, W[:]) |
| |
| /* if multiplier is even add 1 to multiplier, and add P to correction */ |
| mt.zero() |
| C.inf() |
| for i := 0; i < 4; i++ { |
| if t[i].parity() == 0 { |
| t[i].inc(1) |
| t[i].norm() |
| C.add(Q[i]) |
| } |
| mt.add(t[i]) |
| mt.norm() |
| } |
| |
| nb := 1 + mt.nbits() |
| |
| /* convert exponent to signed 1-bit window */ |
| for j := 0; j < nb; j++ { |
| for i := 0; i < 4; i++ { |
| a[i] = int8(t[i].lastbits(2) - 2) |
| t[i].dec(int(a[i])) |
| t[i].norm() |
| t[i].fshr(1) |
| } |
| w[j] = (8*a[0] + 4*a[1] + 2*a[2] + a[3]) |
| } |
| w[nb] = int8(8*t[0].lastbits(2) + 4*t[1].lastbits(2) + 2*t[2].lastbits(2) + t[3].lastbits(2)) |
| |
| P.copy(W[(w[nb]-1)/2]) |
| for i := nb - 1; i >= 0; i-- { |
| T.selector(W, int32(w[i])) |
| P.dbl() |
| P.add(T) |
| } |
| P.sub(C) /* apply correction */ |
| |
| P.affine() |
| return P |
| } |