| /* |
| 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 Fp^12 functions */ |
| /* FP12 elements are of the form a+i.b+i^2.c */ |
| |
| public sealed class FP12 |
| { |
| private readonly FP4 a; |
| private readonly FP4 b; |
| private readonly FP4 c; |
| /* reduce all components of this mod Modulus */ |
| public void reduce() |
| { |
| a.reduce(); |
| b.reduce(); |
| c.reduce(); |
| } |
| /* normalise all components of this */ |
| public void norm() |
| { |
| a.norm(); |
| b.norm(); |
| c.norm(); |
| } |
| /* test x==0 ? */ |
| public bool iszilch() |
| { |
| reduce(); |
| return (a.iszilch() && b.iszilch() && c.iszilch()); |
| } |
| /* test x==1 ? */ |
| public bool isunity() |
| { |
| FP4 one = new FP4(1); |
| return (a.Equals(one) && b.iszilch() && c.iszilch()); |
| } |
| /* return 1 if x==y, else 0 */ |
| public bool Equals(FP12 x) |
| { |
| return (a.Equals(x.a) && b.Equals(x.b) && c.Equals(x.c)); |
| } |
| /* extract a from this */ |
| public FP4 geta() |
| { |
| return a; |
| } |
| /* extract b */ |
| public FP4 getb() |
| { |
| return b; |
| } |
| /* extract c */ |
| public FP4 getc() |
| { |
| return c; |
| } |
| /* copy this=x */ |
| public void copy(FP12 x) |
| { |
| a.copy(x.a); |
| b.copy(x.b); |
| c.copy(x.c); |
| } |
| /* set this=1 */ |
| public void one() |
| { |
| a.one(); |
| b.zero(); |
| c.zero(); |
| } |
| /* this=conj(this) */ |
| public void conj() |
| { |
| a.conj(); |
| b.nconj(); |
| c.conj(); |
| } |
| /* Constructors */ |
| public FP12(FP4 d) |
| { |
| a = new FP4(d); |
| b = new FP4(0); |
| c = new FP4(0); |
| } |
| |
| public FP12(int d) |
| { |
| a = new FP4(d); |
| b = new FP4(0); |
| c = new FP4(0); |
| } |
| |
| public FP12(FP4 d, FP4 e, FP4 f) |
| { |
| a = new FP4(d); |
| b = new FP4(e); |
| c = new FP4(f); |
| } |
| |
| public FP12(FP12 x) |
| { |
| a = new FP4(x.a); |
| b = new FP4(x.b); |
| c = new FP4(x.c); |
| } |
| |
| /* Granger-Scott Unitary Squaring */ |
| public void usqr() |
| { |
| FP4 A = new FP4(a); |
| FP4 B = new FP4(c); |
| FP4 C = new FP4(b); |
| FP4 D = new FP4(0); |
| |
| a.sqr(); |
| D.copy(a); |
| D.add(a); |
| a.add(D); |
| |
| // a.norm(); |
| A.nconj(); |
| |
| A.add(A); |
| a.add(A); |
| B.sqr(); |
| B.times_i(); |
| |
| D.copy(B); |
| D.add(B); |
| B.add(D); |
| // B.norm(); |
| |
| C.sqr(); |
| D.copy(C); |
| D.add(C); |
| C.add(D); |
| // C.norm(); |
| |
| b.conj(); |
| b.add(b); |
| c.nconj(); |
| |
| c.add(c); |
| b.add(B); |
| c.add(C); |
| reduce(); |
| |
| } |
| |
| /* Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */ |
| public void sqr() |
| { |
| FP4 A = new FP4(a); |
| FP4 B = new FP4(b); |
| FP4 C = new FP4(c); |
| FP4 D = new FP4(a); |
| |
| A.sqr(); |
| B.mul(c); |
| B.add(B); |
| C.sqr(); |
| D.mul(b); |
| D.add(D); |
| |
| c.add(a); |
| c.add(b); |
| c.sqr(); |
| |
| a.copy(A); |
| |
| A.add(B); |
| // A.norm(); |
| A.add(C); |
| A.add(D); |
| // A.norm(); |
| |
| A.neg(); |
| B.times_i(); |
| C.times_i(); |
| |
| a.add(B); |
| |
| b.copy(C); |
| b.add(D); |
| c.add(A); |
| norm(); |
| } |
| |
| /* FP12 full multiplication this=this*y */ |
| public void mul(FP12 y) |
| { |
| FP4 z0 = new FP4(a); |
| FP4 z1 = new FP4(0); |
| FP4 z2 = new FP4(b); |
| FP4 z3 = new FP4(0); |
| FP4 t0 = new FP4(a); |
| FP4 t1 = new FP4(y.a); |
| |
| z0.mul(y.a); |
| z2.mul(y.b); |
| |
| t0.add(b); |
| t1.add(y.b); |
| |
| z1.copy(t0); |
| z1.mul(t1); |
| t0.copy(b); |
| t0.add(c); |
| |
| t1.copy(y.b); |
| t1.add(y.c); |
| z3.copy(t0); |
| z3.mul(t1); |
| |
| t0.copy(z0); |
| t0.neg(); |
| t1.copy(z2); |
| t1.neg(); |
| |
| z1.add(t0); |
| // z1.norm(); |
| b.copy(z1); |
| b.add(t1); |
| |
| z3.add(t1); |
| z2.add(t0); |
| |
| t0.copy(a); |
| t0.add(c); |
| t1.copy(y.a); |
| t1.add(y.c); |
| t0.mul(t1); |
| z2.add(t0); |
| |
| t0.copy(c); |
| t0.mul(y.c); |
| t1.copy(t0); |
| t1.neg(); |
| |
| // z2.norm(); |
| // z3.norm(); |
| // b.norm(); |
| |
| c.copy(z2); |
| c.add(t1); |
| z3.add(t1); |
| t0.times_i(); |
| b.add(t0); |
| |
| z3.times_i(); |
| a.copy(z0); |
| a.add(z3); |
| norm(); |
| } |
| |
| /* Special case of multiplication arises from special form of ATE pairing line function */ |
| public void smul(FP12 y) |
| { |
| FP4 z0 = new FP4(a); |
| FP4 z2 = new FP4(b); |
| FP4 z3 = new FP4(b); |
| FP4 t0 = new FP4(0); |
| FP4 t1 = new FP4(y.a); |
| |
| z0.mul(y.a); |
| z2.pmul(y.b.real()); |
| b.add(a); |
| t1.real().add(y.b.real()); |
| |
| b.mul(t1); |
| z3.add(c); |
| z3.pmul(y.b.real()); |
| |
| t0.copy(z0); |
| t0.neg(); |
| t1.copy(z2); |
| t1.neg(); |
| |
| b.add(t0); |
| // b.norm(); |
| |
| b.add(t1); |
| z3.add(t1); |
| z2.add(t0); |
| |
| t0.copy(a); |
| t0.add(c); |
| t0.mul(y.a); |
| c.copy(z2); |
| c.add(t0); |
| |
| z3.times_i(); |
| a.copy(z0); |
| a.add(z3); |
| |
| norm(); |
| } |
| |
| /* this=1/this */ |
| public void inverse() |
| { |
| FP4 f0 = new FP4(a); |
| FP4 f1 = new FP4(b); |
| FP4 f2 = new FP4(a); |
| FP4 f3 = new FP4(0); |
| |
| norm(); |
| f0.sqr(); |
| f1.mul(c); |
| f1.times_i(); |
| f0.sub(f1); |
| |
| f1.copy(c); |
| f1.sqr(); |
| f1.times_i(); |
| f2.mul(b); |
| f1.sub(f2); |
| |
| f2.copy(b); |
| f2.sqr(); |
| f3.copy(a); |
| f3.mul(c); |
| f2.sub(f3); |
| |
| f3.copy(b); |
| f3.mul(f2); |
| f3.times_i(); |
| a.mul(f0); |
| f3.add(a); |
| c.mul(f1); |
| c.times_i(); |
| |
| f3.add(c); |
| f3.inverse(); |
| a.copy(f0); |
| a.mul(f3); |
| b.copy(f1); |
| b.mul(f3); |
| c.copy(f2); |
| c.mul(f3); |
| } |
| |
| /* this=this^p using Frobenius */ |
| public void frob(FP2 f) |
| { |
| FP2 f2 = new FP2(f); |
| FP2 f3 = new FP2(f); |
| |
| f2.sqr(); |
| f3.mul(f2); |
| |
| a.frob(f3); |
| b.frob(f3); |
| c.frob(f3); |
| |
| b.pmul(f); |
| c.pmul(f2); |
| } |
| |
| /* trace function */ |
| public FP4 trace() |
| { |
| FP4 t = new FP4(0); |
| t.copy(a); |
| t.imul(3); |
| t.reduce(); |
| return t; |
| } |
| |
| /* convert from byte array to FP12 */ |
| public static FP12 fromBytes(sbyte[] w) |
| { |
| BIG a, b; |
| FP2 c, d; |
| FP4 e, f, g; |
| sbyte[] t = new sbyte[ROM.MODBYTES]; |
| |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i]; |
| } |
| a = BIG.fromBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + ROM.MODBYTES]; |
| } |
| b = BIG.fromBytes(t); |
| c = new FP2(a,b); |
| |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 2 * ROM.MODBYTES]; |
| } |
| a = BIG.fromBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 3 * ROM.MODBYTES]; |
| } |
| b = BIG.fromBytes(t); |
| d = new FP2(a,b); |
| |
| e = new FP4(c,d); |
| |
| |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 4 * ROM.MODBYTES]; |
| } |
| a = BIG.fromBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 5 * ROM.MODBYTES]; |
| } |
| b = BIG.fromBytes(t); |
| c = new FP2(a,b); |
| |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 6 * ROM.MODBYTES]; |
| } |
| a = BIG.fromBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 7 * ROM.MODBYTES]; |
| } |
| b = BIG.fromBytes(t); |
| d = new FP2(a,b); |
| |
| f = new FP4(c,d); |
| |
| |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 8 * ROM.MODBYTES]; |
| } |
| a = BIG.fromBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 9 * ROM.MODBYTES]; |
| } |
| b = BIG.fromBytes(t); |
| c = new FP2(a,b); |
| |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 10 * ROM.MODBYTES]; |
| } |
| a = BIG.fromBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| t[i] = w[i + 11 * ROM.MODBYTES]; |
| } |
| b = BIG.fromBytes(t); |
| d = new FP2(a,b); |
| |
| g = new FP4(c,d); |
| |
| return new FP12(e,f,g); |
| } |
| |
| /* convert this to byte array */ |
| public void toBytes(sbyte[] w) |
| { |
| sbyte[] t = new sbyte[ROM.MODBYTES]; |
| a.geta().A.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i] = t[i]; |
| } |
| a.geta().B.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + ROM.MODBYTES] = t[i]; |
| } |
| a.getb().A.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 2 * ROM.MODBYTES] = t[i]; |
| } |
| a.getb().B.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 3 * ROM.MODBYTES] = t[i]; |
| } |
| |
| b.geta().A.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 4 * ROM.MODBYTES] = t[i]; |
| } |
| b.geta().B.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 5 * ROM.MODBYTES] = t[i]; |
| } |
| b.getb().A.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 6 * ROM.MODBYTES] = t[i]; |
| } |
| b.getb().B.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 7 * ROM.MODBYTES] = t[i]; |
| } |
| |
| c.geta().A.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 8 * ROM.MODBYTES] = t[i]; |
| } |
| c.geta().B.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 9 * ROM.MODBYTES] = t[i]; |
| } |
| c.getb().A.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 10 * ROM.MODBYTES] = t[i]; |
| } |
| c.getb().B.toBytes(t); |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| w[i + 11 * ROM.MODBYTES] = t[i]; |
| } |
| } |
| |
| /* convert to hex string */ |
| public override string ToString() |
| { |
| return ("[" + a.ToString() + "," + b.ToString() + "," + c.ToString() + "]"); |
| } |
| |
| /* this=this^e */ |
| public FP12 pow(BIG e) |
| { |
| norm(); |
| e.norm(); |
| FP12 w = new FP12(this); |
| BIG z = new BIG(e); |
| FP12 r = new FP12(1); |
| |
| while (true) |
| { |
| int bt = z.parity(); |
| z.fshr(1); |
| if (bt == 1) |
| { |
| r.mul(w); |
| } |
| if (z.iszilch()) |
| { |
| break; |
| } |
| w.usqr(); |
| } |
| r.reduce(); |
| return r; |
| } |
| |
| /* constant time powering by small integer of max length bts */ |
| public void pinpow(int e, int bts) |
| { |
| int i, b; |
| FP12[] R = new FP12[2]; |
| R[0] = new FP12(1); |
| R[1] = new FP12(this); |
| for (i = bts - 1;i >= 0;i--) |
| { |
| b = (e >> i) & 1; |
| R[1 - b].mul(R[b]); |
| R[b].usqr(); |
| } |
| this.copy(R[0]); |
| } |
| |
| /* p=q0^u0.q1^u1.q2^u2.q3^u3 */ |
| /* Timing attack secure, but not cache attack secure */ |
| |
| public static FP12 pow4(FP12[] q, BIG[] u) |
| { |
| int i, j, nb, m; |
| int[] a = new int[4]; |
| FP12[] g = new FP12[8]; |
| FP12[] s = new FP12[2]; |
| FP12 c = new FP12(1); |
| FP12 p = new FP12(0); |
| BIG[] t = new BIG[4]; |
| BIG mt = new BIG(0); |
| sbyte[] w = new sbyte[ROM.NLEN * ROM.BASEBITS + 1]; |
| |
| for (i = 0;i < 4;i++) |
| { |
| t[i] = new BIG(u[i]); |
| } |
| |
| s[0] = new FP12(0); |
| s[1] = new FP12(0); |
| |
| g[0] = new FP12(q[0]); |
| s[0].copy(q[1]); |
| s[0].conj(); |
| g[0].mul(s[0]); |
| g[1] = new FP12(g[0]); |
| g[2] = new FP12(g[0]); |
| g[3] = new FP12(g[0]); |
| g[4] = new FP12(q[0]); |
| g[4].mul(q[1]); |
| g[5] = new FP12(g[4]); |
| g[6] = new FP12(g[4]); |
| g[7] = new FP12(g[4]); |
| |
| s[1].copy(q[2]); |
| s[0].copy(q[3]); |
| s[0].conj(); |
| s[1].mul(s[0]); |
| s[0].copy(s[1]); |
| s[0].conj(); |
| g[1].mul(s[0]); |
| g[2].mul(s[1]); |
| g[5].mul(s[0]); |
| g[6].mul(s[1]); |
| s[1].copy(q[2]); |
| s[1].mul(q[3]); |
| s[0].copy(s[1]); |
| s[0].conj(); |
| g[0].mul(s[0]); |
| g[3].mul(s[1]); |
| g[4].mul(s[0]); |
| g[7].mul(s[1]); |
| |
| /* if power is even add 1 to power, and add q to correction */ |
| |
| for (i = 0;i < 4;i++) |
| { |
| if (t[i].parity() == 0) |
| { |
| t[i].inc(1); |
| t[i].norm(); |
| c.mul(q[i]); |
| } |
| mt.add(t[i]); |
| mt.norm(); |
| } |
| c.conj(); |
| 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] = (t[i].lastbits(2) - 2); |
| t[i].dec(a[i]); |
| t[i].norm(); |
| t[i].fshr(1); |
| } |
| w[j] = (sbyte)(8 * a[0] + 4 * a[1] + 2 * a[2] + a[3]); |
| } |
| w[nb] = (sbyte)(8 * t[0].lastbits(2) + 4 * t[1].lastbits(2) + 2 * t[2].lastbits(2) + t[3].lastbits(2)); |
| p.copy(g[(w[nb] - 1) / 2]); |
| |
| for (i = nb - 1;i >= 0;i--) |
| { |
| m = w[i] >> 7; |
| j = (w[i] ^ m) - m; // j=abs(w[i]) |
| j = (j - 1) / 2; |
| s[0].copy(g[j]); |
| s[1].copy(g[j]); |
| s[1].conj(); |
| p.usqr(); |
| p.mul(s[m & 1]); |
| } |
| p.mul(c); // apply correction |
| p.reduce(); |
| return p; |
| } |
| |
| /* |
| public static void main(String[] args) { |
| BIG p=new BIG(ROM.Modulus); |
| FP2 w0,w1; |
| BIG a=new BIG(0); |
| BIG b=new BIG(0); |
| |
| a.zero(); b.zero(); a.inc(1); b.inc(2); |
| w0=new FP2(a,b); |
| a.zero(); b.zero(); a.inc(3); b.inc(4); |
| w1=new FP2(a,b); |
| FP4 t0=new FP4(w0,w1); |
| |
| a.zero(); b.zero(); a.inc(5); b.inc(6); |
| w0=new FP2(a,b); |
| a.zero(); b.zero(); a.inc(7); b.inc(8); |
| w1=new FP2(a,b); |
| FP4 t1=new FP4(w0,w1); |
| |
| a.zero(); b.zero(); a.inc(9); b.inc(10); |
| w0=new FP2(a,b); |
| a.zero(); b.zero(); a.inc(11); b.inc(12); |
| w1=new FP2(a,b); |
| FP4 t2=new FP4(w0,w1); |
| |
| FP12 w=new FP12(t0,t1,t2); |
| FP12 t=new FP12(w); |
| |
| System.out.println("w= "+w.toString()); |
| |
| a=new BIG(ROM.CURVE_Fra); |
| b=new BIG(ROM.CURVE_Frb); |
| |
| FP2 f=new FP2(a,b); |
| |
| w.frob(f); |
| System.out.println("w= "+w.toString()); |
| |
| w=t.pow(p); |
| |
| System.out.println("w= "+w.toString()); |
| |
| w.inverse(); |
| |
| System.out.println("1/w= "+w.toString()); |
| |
| w.inverse(); |
| |
| System.out.println("w= "+w.toString()); |
| |
| t.copy(w); |
| w.conj(); |
| t.inverse(); |
| w.mul(t); |
| |
| System.out.println("w^(p^6-1)= "+w.toString()); |
| |
| t.copy(w); |
| w.frob(f); |
| w.frob(f); |
| w.mul(t); |
| |
| System.out.println("w^(p^6-1)(p^2+1)= "+w.toString()); |
| |
| t.copy(w); |
| |
| t.inverse(); |
| w.conj(); |
| |
| System.out.println("w= "+w.toString()); |
| System.out.println("t= "+t.toString()); |
| } */ |
| } |