| /* | |
| 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. | |
| */ | |
| // | |
| // ecp2.swift | |
| // | |
| // | |
| // Created by Michael Scott on 07/07/2015. | |
| // Copyright (c) 2015 Michael Scott. All rights reserved. | |
| // | |
| /* CLINT Weierstrass elliptic curve functions over FP2 */ | |
| final class ECP2 { | |
| private var x:FP2 | |
| private var y:FP2 | |
| private var z:FP2 | |
| private var INF:Bool | |
| /* Constructor - set self=O */ | |
| init() | |
| { | |
| INF=true | |
| x=FP2(0) | |
| y=FP2(1) | |
| z=FP2(1) | |
| } | |
| /* Test self=O? */ | |
| func is_infinity() -> Bool | |
| { | |
| return INF | |
| } | |
| /* copy self=P */ | |
| func copy(P:ECP2) | |
| { | |
| x.copy(P.x) | |
| y.copy(P.y) | |
| z.copy(P.z) | |
| INF=P.INF | |
| } | |
| /* set self=O */ | |
| func inf() { | |
| INF=true | |
| x.zero() | |
| y.zero() | |
| z.zero() | |
| } | |
| /* Conditional move of Q to P dependant on d */ | |
| func cmove(Q:ECP2,_ d:Int32) | |
| { | |
| x.cmove(Q.x,d); | |
| y.cmove(Q.y,d); | |
| z.cmove(Q.z,d); | |
| var bd:Bool | |
| if d==0 {bd=false} | |
| else {bd=true} | |
| INF = (INF != ((INF != Q.INF) && bd)) | |
| } | |
| /* return 1 if b==c, no branching */ | |
| private static func teq(b:Int32,_ c:Int32) -> Int32 | |
| { | |
| var x=b^c | |
| x-=1 // if x=0, x now -1 | |
| return ((x>>31)&1) | |
| } | |
| /* Constant time select from pre-computed table */ | |
| func select(W:[ECP2],_ b:Int32) | |
| { | |
| let MP=ECP2() | |
| let m=b>>31 | |
| var babs=(b^m)-m | |
| babs=(babs-1)/2 | |
| cmove(W[0],ECP2.teq(babs,0)) // conditional move | |
| cmove(W[1],ECP2.teq(babs,1)) | |
| cmove(W[2],ECP2.teq(babs,2)) | |
| cmove(W[3],ECP2.teq(babs,3)) | |
| cmove(W[4],ECP2.teq(babs,4)) | |
| cmove(W[5],ECP2.teq(babs,5)) | |
| cmove(W[6],ECP2.teq(babs,6)) | |
| cmove(W[7],ECP2.teq(babs,7)) | |
| MP.copy(self) | |
| MP.neg() | |
| cmove(MP,(m&1)) | |
| } | |
| /* Test if P == Q */ | |
| func equals(Q:ECP2) -> Bool | |
| { | |
| if is_infinity() && Q.is_infinity() {return true} | |
| if is_infinity() || Q.is_infinity() {return false} | |
| let zs2=FP2(z); zs2.sqr() | |
| let zo2=FP2(Q.z); zo2.sqr() | |
| let zs3=FP2(zs2); zs3.mul(z) | |
| let zo3=FP2(zo2); zo3.mul(Q.z) | |
| zs2.mul(Q.x) | |
| zo2.mul(x) | |
| if !zs2.equals(zo2) {return false} | |
| zs3.mul(Q.y) | |
| zo3.mul(y) | |
| if !zs3.equals(zo3) {return false} | |
| return true; | |
| } | |
| /* set self=-self */ | |
| func neg() | |
| { | |
| if is_infinity() {return} | |
| y.neg(); y.norm() | |
| return | |
| } | |
| /* set to Affine - (x,y,z) to (x,y) */ | |
| func affine() { | |
| if is_infinity() {return} | |
| let one=FP2(1) | |
| if z.equals(one) {return} | |
| z.inverse() | |
| let z2=FP2(z) | |
| z2.sqr() | |
| x.mul(z2); x.reduce() | |
| y.mul(z2) | |
| y.mul(z); y.reduce() | |
| z.copy(one) | |
| } | |
| /* extract affine x as FP2 */ | |
| func getX() -> FP2 | |
| { | |
| affine() | |
| return x | |
| } | |
| /* extract affine y as FP2 */ | |
| func getY() -> FP2 | |
| { | |
| affine() | |
| return y | |
| } | |
| /* extract projective x */ | |
| func getx() -> FP2 | |
| { | |
| return x | |
| } | |
| /* extract projective y */ | |
| func gety() -> FP2 | |
| { | |
| return y | |
| } | |
| /* extract projective z */ | |
| func getz() -> FP2 | |
| { | |
| return z | |
| } | |
| /* convert to byte array */ | |
| func toBytes(inout b:[UInt8]) | |
| { | |
| let RM=Int(ROM.MODBYTES) | |
| var t=[UInt8](count:RM,repeatedValue:0) | |
| affine(); | |
| x.getA().toBytes(&t) | |
| for var i=0;i<RM;i++ | |
| {b[i]=t[i]} | |
| x.getB().toBytes(&t); | |
| for var i=0;i<RM;i++ | |
| {b[i+RM]=t[i]} | |
| y.getA().toBytes(&t); | |
| for var i=0;i<RM;i++ | |
| {b[i+2*RM]=t[i]} | |
| y.getB().toBytes(&t); | |
| for var i=0;i<RM;i++ | |
| {b[i+3*RM]=t[i]} | |
| } | |
| /* convert from byte array to point */ | |
| static func fromBytes(b:[UInt8]) -> ECP2 | |
| { | |
| let RM=Int(ROM.MODBYTES) | |
| var t=[UInt8](count:RM,repeatedValue:0) | |
| for var i=0;i<RM;i++ {t[i]=b[i]} | |
| var ra=BIG.fromBytes(t); | |
| for var i=0;i<RM;i++ {t[i]=b[i+RM]} | |
| var rb=BIG.fromBytes(t); | |
| let rx=FP2(ra,rb) | |
| for var i=0;i<RM;i++ {t[i]=b[i+2*RM]} | |
| ra=BIG.fromBytes(t) | |
| for var i=0;i<RM;i++ {t[i]=b[i+3*RM]} | |
| rb=BIG.fromBytes(t) | |
| let ry=FP2(ra,rb) | |
| return ECP2(rx,ry) | |
| } | |
| /* convert self to hex string */ | |
| func toString() -> String | |
| { | |
| if is_infinity() {return "infinity"} | |
| affine() | |
| return "("+x.toString()+","+y.toString()+")" | |
| } | |
| /* Calculate RHS of twisted curve equation x^3+B/i */ | |
| static func RHS(x:FP2) -> FP2 | |
| { | |
| x.norm() | |
| let r=FP2(x) | |
| r.sqr() | |
| let b=FP2(BIG(ROM.CURVE_B)) | |
| b.div_ip(); | |
| r.mul(x); | |
| r.add(b); | |
| r.reduce(); | |
| return r; | |
| } | |
| /* construct self from (x,y) - but set to O if not on curve */ | |
| init(_ ix:FP2,_ iy:FP2) | |
| { | |
| x=FP2(ix) | |
| y=FP2(iy) | |
| z=FP2(1) | |
| let rhs=ECP2.RHS(x) | |
| let y2=FP2(y) | |
| y2.sqr() | |
| if y2.equals(rhs) {INF=false} | |
| else {x.zero(); INF=true} | |
| } | |
| /* construct this from x - but set to O if not on curve */ | |
| init(_ ix:FP2) | |
| { | |
| x=FP2(ix) | |
| y=FP2(1) | |
| z=FP2(1) | |
| let rhs=ECP2.RHS(x) | |
| if rhs.sqrt() | |
| { | |
| y.copy(rhs); | |
| INF=false; | |
| } | |
| else {x.zero(); INF=true;} | |
| } | |
| /* this+=this */ | |
| func dbl() -> Int | |
| { | |
| if (INF) {return -1} | |
| if y.iszilch() | |
| { | |
| inf(); | |
| return -1; | |
| } | |
| let w1=FP2(x) | |
| let w2=FP2(0) | |
| let w3=FP2(x) | |
| let w8=FP2(x) | |
| w1.sqr() | |
| w8.copy(w1) | |
| w8.imul(3) | |
| w2.copy(y); w2.sqr() | |
| w3.copy(x); w3.mul(w2) | |
| w3.imul(4) | |
| w1.copy(w3); w1.neg() | |
| w1.norm() | |
| x.copy(w8); x.sqr() | |
| x.add(w1) | |
| x.add(w1) | |
| x.norm() | |
| z.mul(y) | |
| z.add(z) | |
| w2.add(w2) | |
| w2.sqr() | |
| w2.add(w2) | |
| w3.sub(x) | |
| y.copy(w8); y.mul(w3) | |
| w2.norm() | |
| y.sub(w2) | |
| y.norm() | |
| z.norm() | |
| return 1 | |
| } | |
| /* this+=Q - return 0 for add, 1 for double, -1 for O */ | |
| func add(Q:ECP2) -> Int | |
| { | |
| if INF | |
| { | |
| copy(Q) | |
| return -1 | |
| } | |
| if Q.INF {return -1} | |
| var aff=false | |
| if Q.z.isunity() {aff=true} | |
| var A:FP2 | |
| var C:FP2 | |
| let B=FP2(z) | |
| let D=FP2(z) | |
| if (!aff) | |
| { | |
| A=FP2(Q.z) | |
| C=FP2(Q.z) | |
| A.sqr(); B.sqr() | |
| C.mul(A); D.mul(B) | |
| A.mul(x) | |
| C.mul(y) | |
| } | |
| else | |
| { | |
| A=FP2(x) | |
| C=FP2(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() | |
| { | |
| dbl() | |
| return 1 | |
| } | |
| else | |
| { | |
| INF=true | |
| return -1 | |
| } | |
| } | |
| if !aff {z.mul(Q.z)} | |
| z.mul(B) | |
| let e=FP2(B); e.sqr() | |
| B.mul(e) | |
| A.mul(e) | |
| e.copy(A) | |
| e.add(A); e.add(B) | |
| x.copy(D); x.sqr(); x.sub(e) | |
| A.sub(x) | |
| y.copy(A); y.mul(D) | |
| C.mul(B); y.sub(C) | |
| x.norm() | |
| y.norm() | |
| z.norm() | |
| return 0 | |
| } | |
| /* set self-=Q */ | |
| func sub(Q:ECP2) -> Int | |
| { | |
| Q.neg() | |
| let D=add(Q) | |
| Q.neg() | |
| return D | |
| } | |
| /* set self*=q, where q is Modulus, using Frobenius */ | |
| func frob(X:FP2) | |
| { | |
| if INF {return} | |
| let X2=FP2(X) | |
| X2.sqr() | |
| x.conj() | |
| y.conj() | |
| z.conj() | |
| z.reduce() | |
| x.mul(X2) | |
| y.mul(X2) | |
| y.mul(X) | |
| } | |
| /* normalises m-array of ECP2 points. Requires work vector of m FP2s */ | |
| private static func multiaffine(m:Int,_ P:[ECP2]) | |
| { | |
| let t1=FP2(0) | |
| let t2=FP2(0) | |
| var work=[FP2]() | |
| for var i=0;i<m;i++ | |
| {work.append(FP2(0))} | |
| work[0].one() | |
| work[1].copy(P[0].z) | |
| for var 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 var 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 var 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 mul(e:BIG) -> ECP2 | |
| { | |
| /* fixed size windows */ | |
| let mt=BIG() | |
| let t=BIG() | |
| let P=ECP2() | |
| let Q=ECP2() | |
| let C=ECP2() | |
| var W=[ECP2](); | |
| for var i=0;i<8;i++ {W.append(ECP2())} | |
| var w=[Int8](count:1+(ROM.NLEN*Int(ROM.BASEBITS)+3)/4,repeatedValue:0) | |
| if is_infinity() {return ECP2()} | |
| affine() | |
| /* precompute table */ | |
| Q.copy(self) | |
| Q.dbl() | |
| W[0].copy(self) | |
| for var i=1;i<8;i++ | |
| { | |
| W[i].copy(W[i-1]) | |
| W[i].add(Q) | |
| } | |
| /* convert the table to affine */ | |
| ECP2.multiaffine(8,W); | |
| /* make exponent odd - add 2P if even, P if odd */ | |
| t.copy(e) | |
| let s=t.parity() | |
| t.inc(1); t.norm(); let ns=t.parity(); mt.copy(t); mt.inc(1); mt.norm() | |
| t.cmove(mt,s) | |
| Q.cmove(self,ns) | |
| C.copy(Q) | |
| let nb=1+(t.nbits()+3)/4 | |
| /* convert exponent to signed 4-bit window */ | |
| for var i=0;i<nb;i++ | |
| { | |
| w[i]=Int8(t.lastbits(5)-16) | |
| t.dec(Int32(w[i])); t.norm() | |
| t.fshr(4) | |
| } | |
| w[nb]=Int8(t.lastbits(5)) | |
| P.copy(W[(w[nb]-1)/2]) | |
| for var i=nb-1;i>=0;i-- | |
| { | |
| Q.select(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 */ | |
| static func mul4(Q:[ECP2],_ u:[BIG]) -> ECP2 | |
| { | |
| var a=[Int32](count:4,repeatedValue:0) | |
| let T=ECP2() | |
| let C=ECP2() | |
| let P=ECP2() | |
| var W=[ECP2](); | |
| for var i=0;i<8;i++ {W.append(ECP2())} | |
| let mt=BIG() | |
| var t=[BIG]() | |
| var w=[Int8](count:ROM.NLEN*Int(ROM.BASEBITS)+1,repeatedValue:0) | |
| for var i=0;i<4;i++ | |
| { | |
| t.append(BIG(u[i])) | |
| Q[i].affine() | |
| } | |
| /* precompute table */ | |
| W[0].copy(Q[0]); W[0].sub(Q[1]) | |
| W[1].copy(W[0]) | |
| W[2].copy(W[0]) | |
| W[3].copy(W[0]) | |
| W[4].copy(Q[0]); W[4].add(Q[1]) | |
| W[5].copy(W[4]) | |
| W[6].copy(W[4]) | |
| 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) | |
| ECP2.multiaffine(8,W); | |
| /* if multiplier is even add 1 to multiplier, and add P to correction */ | |
| mt.zero(); C.inf() | |
| for var 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() | |
| } | |
| let nb=1+mt.nbits(); | |
| /* convert exponent to signed 1-bit window */ | |
| for var j=0;j<nb;j++ | |
| { | |
| for var i=0;i<4;i++ | |
| { | |
| a[i]=(t[i].lastbits(2)-2) | |
| t[i].dec(a[i]); t[i].norm() | |
| t[i].fshr(1) | |
| } | |
| w[j]=Int8(8*a[0]+4*a[1]+2*a[2]+a[3]) | |
| } | |
| w[nb]=Int8(8*t[0].lastbits(2)+4*t[1].lastbits(2)) | |
| w[nb]+=Int8(2*t[2].lastbits(2)+t[3].lastbits(2)) | |
| P.copy(W[(w[nb]-1)/2]) | |
| for var i=nb-1;i>=0;i-- | |
| { | |
| T.select(W,Int32(w[i])) | |
| P.dbl() | |
| P.add(T) | |
| } | |
| P.sub(C) /* apply correction */ | |
| P.affine() | |
| return P | |
| } | |
| } |