1 /*############################################################################
2 # Copyright 2017 Intel Corporation
3 #
4 # Licensed under the Apache License, Version 2.0 (the "License");
5 # you may not use this file except in compliance with the License.
6 # You may obtain a copy of the License at
7 #
8 #     http://www.apache.org/licenses/LICENSE-2.0
9 #
10 # Unless required by applicable law or agreed to in writing, software
11 # distributed under the License is distributed on an "AS IS" BASIS,
12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 # See the License for the specific language governing permissions and
14 # limitations under the License.
15 ############################################################################*/
16 /// Implementation of Tate pairing
17 /*! \file */
18 
19 #include "epid/member/tiny/math/pairing.h"
20 #include "epid/member/tiny/math/efq2.h"
21 #include "epid/member/tiny/math/fq.h"
22 #include "epid/member/tiny/math/fq12.h"
23 #include "epid/member/tiny/math/fq2.h"
24 #include "epid/member/tiny/math/mathtypes.h"
25 #include "epid/member/tiny/math/vli.h"
26 
27 static const VeryLargeInt epid_e = {{0xf2788803, 0x7886dcf9, 0x2dc401c0,
28                                      0xd77a10ff, 0x27bd9b6f, 0x367ba865,
29                                      0xaaaa2822, 0x2aaaaaaa}};
30 static const VeryLargeInt epid_t = {{0x30B0A801, 0x6882F5C0, 0, 0, 0, 0, 0, 0}};
31 static const Fq2Elem epid_xi = {
32     {{{0x00000002, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
33        0x00000000, 0x00000000}}},
34     {{{0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
35        0x00000000, 0x00000000}}}};
36 static const int neg = 1;
37 
PairingInit(PairingState * state)38 void PairingInit(PairingState* state) {
39   int i;
40   Fq2Exp(&state->g[0][0], &epid_xi, &epid_e);
41   for (i = 1; i < 5; i++) {
42     Fq2Mul(&state->g[0][i], &state->g[0][i - 1], &state->g[0][0]);
43   }
44   for (i = 0; i < 5; i++) {
45     FqSquare(&state->g[1][i].x0, &state->g[0][i].x0);
46     FqSquare(&state->g[1][i].x1, &state->g[0][i].x1);
47     FqAdd(&state->g[1][i].x0, &state->g[1][i].x0, &state->g[1][i].x1);
48     FqClear(&state->g[1][i].x1);
49     Fq2Mul(&state->g[2][i], &state->g[0][i], &state->g[1][i]);
50   }
51 }
52 
piOp(EccPointFq2 * Qout,EccPointFq2 const * Qin,int e,PairingState const * scratch)53 static void piOp(EccPointFq2* Qout, EccPointFq2 const* Qin, int e,
54                  PairingState const* scratch) {
55   if (e == 1) {
56     Fq2Conj(&Qout->x, &Qin->x);
57     Fq2Conj(&Qout->y, &Qin->y);
58   } else {
59     Fq2Cp(&Qout->x, &Qin->x);
60     Fq2Cp(&Qout->y, &Qin->y);
61   }
62   Fq2Mul(&Qout->x, &Qout->x, &scratch->g[e - 1][1]);
63   Fq2Mul(&Qout->y, &Qout->y, &scratch->g[e - 1][2]);
64 }
65 
66 /*
67  * Computes the Frobenius endomorphism Pout = Pin^(p^e)
68  */
frob_op(Fq12Elem * Pout,Fq12Elem const * Pin,int e,PairingState const * state)69 static void frob_op(Fq12Elem* Pout, Fq12Elem const* Pin, int e,
70                     PairingState const* state) {
71   if (e == 1 || e == 3) {
72     Fq2Conj(&Pout->z0.y0, &Pin->z0.y0);
73     Fq2Conj(&Pout->z1.y0, &Pin->z1.y0);
74     Fq2Conj(&Pout->z0.y1, &Pin->z0.y1);
75     Fq2Conj(&Pout->z1.y1, &Pin->z1.y1);
76     Fq2Conj(&Pout->z0.y2, &Pin->z0.y2);
77     Fq2Conj(&Pout->z1.y2, &Pin->z1.y2);
78   } else {
79     Fq2Cp(&Pout->z0.y0, &Pin->z0.y0);
80     Fq2Cp(&Pout->z1.y0, &Pin->z1.y0);
81     Fq2Cp(&Pout->z0.y1, &Pin->z0.y1);
82     Fq2Cp(&Pout->z1.y1, &Pin->z1.y1);
83     Fq2Cp(&Pout->z0.y2, &Pin->z0.y2);
84     Fq2Cp(&Pout->z1.y2, &Pin->z1.y2);
85   }
86   Fq2Mul(&Pout->z1.y0, &Pout->z1.y0, &state->g[e - 1][0]);
87   Fq2Mul(&Pout->z0.y1, &Pout->z0.y1, &state->g[e - 1][1]);
88   Fq2Mul(&Pout->z1.y1, &Pout->z1.y1, &state->g[e - 1][2]);
89   Fq2Mul(&Pout->z0.y2, &Pout->z0.y2, &state->g[e - 1][3]);
90   Fq2Mul(&Pout->z1.y2, &Pout->z1.y2, &state->g[e - 1][4]);
91 }
92 
finalExp(Fq12Elem * f,PairingState const * state)93 static void finalExp(Fq12Elem* f, PairingState const* state) {
94   Fq12Elem t3;
95   Fq12Elem t2;
96   Fq12Elem t1;
97   Fq12Elem t0;
98 
99   Fq12Conj(&t1, f);
100   Fq12Inv(&t2, f);
101   Fq12Mul(f, &t1, &t2);
102   frob_op(&t2, f, 2, state);
103   Fq12Mul(f, f, &t2);
104   Fq12ExpCyc(&t1, f, &epid_t);
105   if (neg) {
106     Fq12Conj(&t1, &t1);
107   }
108   Fq12ExpCyc(&t3, &t1, &epid_t);
109   if (neg) {
110     Fq12Conj(&t3, &t3);
111   }
112   Fq12ExpCyc(&t0, &t3, &epid_t);
113   if (neg) {
114     Fq12Conj(&t0, &t0);
115   }
116   frob_op(&t2, &t0, 1, state);
117   Fq12Mul(&t2, &t2, &t0);
118   Fq12Conj(&t2, &t2);
119   Fq12SqCyc(&t0, &t2);
120   frob_op(&t2, &t3, 1, state);
121   Fq12Mul(&t2, &t2, &t1);
122   Fq12Conj(&t2, &t2);
123   Fq12Mul(&t0, &t0, &t2);
124   Fq12Conj(&t2, &t3);
125   Fq12Mul(&t0, &t0, &t2);
126   frob_op(&t1, &t1, 1, state);
127   Fq12Conj(&t1, &t1);
128   Fq12Mul(&t1, &t1, &t2);
129   Fq12Mul(&t1, &t1, &t0);
130   frob_op(&t2, &t3, 2, state);
131   Fq12Mul(&t0, &t0, &t2);
132   Fq12SqCyc(&t1, &t1);
133   Fq12Mul(&t1, &t1, &t0);
134   Fq12SqCyc(&t1, &t1);
135   Fq12Conj(&t2, f);
136   Fq12Mul(&t0, &t1, &t2);
137   frob_op(&t2, f, 1, state);
138   Fq12Mul(&t1, &t1, &t2);
139   frob_op(&t2, f, 2, state);
140   Fq12Mul(&t1, &t1, &t2);
141   frob_op(&t2, f, 3, state);
142   Fq12Mul(&t1, &t1, &t2);
143   Fq12SqCyc(&t0, &t0);
144   Fq12Mul(f, &t1, &t0);
145 }
146 
pair_tangent(Fq12Elem * f,Fq2Elem * X,Fq2Elem * Y,Fq2Elem * Z,Fq2Elem * Z2,EccPointFq const * P)147 static void pair_tangent(Fq12Elem* f, Fq2Elem* X, Fq2Elem* Y, Fq2Elem* Z,
148                          Fq2Elem* Z2, EccPointFq const* P) {
149   Fq2Mul(&f->z0.y0, X, X);
150   Fq2Add(&f->z0.y2, &f->z0.y0, &f->z0.y0);
151   Fq2Add(&f->z0.y2, &f->z0.y2, &f->z0.y0);
152   Fq2Add(&f->z1.y1, X, &f->z0.y2);
153   Fq2Mul(&f->z1.y1, &f->z1.y1, &f->z1.y1);
154   Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z0.y0);
155   Fq2Mul(&f->z0.y1, Y, Y);
156   Fq2Add(&f->z1.y0, &f->z0.y1, X);
157   Fq2Mul(&f->z1.y0, &f->z1.y0, &f->z1.y0);
158   Fq2Sub(&f->z1.y0, &f->z1.y0, &f->z0.y0);
159   Fq2Mul(&f->z0.y0, &f->z0.y1, &f->z0.y1);
160   Fq2Sub(&f->z1.y0, &f->z1.y0, &f->z0.y0);
161   Fq2Add(&f->z1.y0, &f->z1.y0, &f->z1.y0);
162   Fq2Mul(&f->z1.y2, &f->z0.y2, &f->z0.y2);
163   Fq2Add(Z, Y, Z);
164   Fq2Mul(Z, Z, Z);
165   Fq2Sub(Z, Z, &f->z0.y1);
166   Fq2Sub(Z, Z, Z2);
167   Fq2Add(&f->z0.y1, &f->z0.y1, &f->z0.y1);
168   Fq2Add(&f->z0.y1, &f->z0.y1, &f->z0.y1);
169   Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z1.y2);
170   Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z0.y1);
171   Fq2Sub(X, &f->z1.y2, &f->z1.y0);
172   Fq2Sub(X, X, &f->z1.y0);
173   Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0);
174   Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0);
175   Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0);
176   Fq2Sub(Y, &f->z1.y0, X);
177   Fq2Mul(Y, Y, &f->z0.y2);
178   Fq2Sub(Y, Y, &f->z0.y0);
179   Fq2Mul(&f->z1.y0, &f->z0.y2, Z2);
180   Fq2Neg(&f->z1.y0, &f->z1.y0);
181   Fq2Add(&f->z1.y0, &f->z1.y0, &f->z1.y0);
182   Fq2MulScalar(&f->z1.y0, &f->z1.y0, &P->x);
183   Fq2Mul(&f->z0.y0, Z, Z2);
184   Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0);
185   Fq2MulScalar(&f->z0.y0, &f->z0.y0, &P->y);
186   Fq2Mul(Z2, Z, Z);
187   Fq2Clear(&f->z0.y1);
188   Fq2Clear(&f->z0.y2);
189   Fq2Clear(&f->z1.y2);
190   Fq2Square(Z2, Z);
191 }
192 
pair_line(Fq12Elem * f,Fq2Elem * X,Fq2Elem * Y,Fq2Elem * Z,Fq2Elem * Z2,EccPointFq const * P,EccPointFq2 const * Q)193 static void pair_line(Fq12Elem* f, Fq2Elem* X, Fq2Elem* Y, Fq2Elem* Z,
194                       Fq2Elem* Z2, EccPointFq const* P, EccPointFq2 const* Q) {
195   Fq2Mul(&f->z0.y1, &Q->x, Z2);
196   Fq2Add(&f->z1.y0, &Q->y, Z);
197   Fq2Mul(&f->z1.y0, &f->z1.y0, &f->z1.y0);
198   Fq2Square(&f->z0.y0, &Q->y);
199   Fq2Sub(&f->z1.y0, &f->z1.y0, &f->z0.y0);
200   Fq2Sub(&f->z1.y0, &f->z1.y0, Z2);
201   Fq2Mul(&f->z1.y0, &f->z1.y0, Z2);
202   Fq2Sub(&f->z0.y1, &f->z0.y1, X);
203   Fq2Mul(&f->z0.y2, &f->z0.y1, &f->z0.y1);
204   Fq2Add(Z, Z, &f->z0.y1);
205   Fq2Square(Z, Z);
206   Fq2Sub(Z, Z, Z2);
207   Fq2Sub(Z, Z, &f->z0.y2);
208   Fq2Mul(Z2, Z, Z);
209   Fq2Add(&f->z1.y2, &Q->y, Z);
210   Fq2Mul(&f->z1.y2, &f->z1.y2, &f->z1.y2);
211   Fq2Sub(&f->z1.y2, &f->z1.y2, &f->z0.y0);
212   Fq2Sub(&f->z1.y2, &f->z1.y2, Z2);
213   Fq2Sub(&f->z1.y0, &f->z1.y0, Y);
214   Fq2Sub(&f->z1.y0, &f->z1.y0, Y);
215   Fq2Mul(&f->z1.y1, &f->z1.y0, &Q->x);
216   Fq2Add(&f->z1.y1, &f->z1.y1, &f->z1.y1);
217   Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z1.y2);
218   Fq2Add(&f->z0.y2, &f->z0.y2, &f->z0.y2);
219   Fq2Add(&f->z0.y2, &f->z0.y2, &f->z0.y2);
220   Fq2Mul(&f->z0.y1, &f->z0.y2, &f->z0.y1);
221   Fq2Mul(&f->z0.y2, X, &f->z0.y2);
222   Fq2Mul(X, &f->z1.y0, &f->z1.y0);
223   Fq2Sub(X, X, &f->z0.y1);
224   Fq2Sub(X, X, &f->z0.y2);
225   Fq2Sub(X, X, &f->z0.y2);
226   Fq2Sub(&f->z0.y2, &f->z0.y2, X);
227   Fq2Mul(&f->z0.y2, &f->z0.y2, &f->z1.y0);
228   Fq2Mul(&f->z0.y1, Y, &f->z0.y1);
229   Fq2Add(&f->z0.y1, &f->z0.y1, &f->z0.y1);
230   Fq2Sub(Y, &f->z0.y2, &f->z0.y1);
231   Fq2MulScalar(&f->z0.y0, Z, &P->y);
232   Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0);
233   Fq2Neg(&f->z1.y0, &f->z1.y0);
234   Fq2MulScalar(&f->z1.y0, &f->z1.y0, &P->x);
235   Fq2Add(&f->z1.y0, &f->z1.y0, &f->z1.y0);
236   Fq2Clear(&f->z0.y1);
237   Fq2Clear(&f->z0.y2);
238   Fq2Clear(&f->z1.y2);
239 }
240 
PairingCompute(Fq12Elem * d,EccPointFq const * P,EccPointFq2 const * Q,PairingState const * state)241 void PairingCompute(Fq12Elem* d, EccPointFq const* P, EccPointFq2 const* Q,
242                     PairingState const* state) {
243   Fq2Elem X;
244   Fq2Elem Y;
245   Fq2Elem Z;
246   Fq2Elem Z2;
247   EccPointFq2 Qp;
248   Fq12Elem f;
249   VeryLargeInt s;
250   const VeryLargeInt two = {{2}};
251   uint32_t i;
252 
253   VliAdd(&s, &epid_t, &epid_t);  // s = 2*t
254   VliAdd(&s, &s, &epid_t);       // s = 3*t
255   VliAdd(&s, &s, &s);            // s = 6*t
256   if (neg) {
257     VliSub(&s, &s, &two);
258   } else {
259     VliAdd(&s, &s, &two);
260   }
261   Fq2Cp(&X, &Q->x);
262   Fq2Cp(&Y, &Q->y);
263   Fq2Set(&Z, 1);
264   Fq2Set(&Z2, 1);
265   Fq12Set(d, 1);
266 
267   Fq12Clear(&f);
268   // s has 66 bits, 0 through 65, so starting point is bit 64
269   i = 65;
270   while (i > 0) {
271     i -= 1;
272     pair_tangent(&f, &X, &Y, &Z, &Z2, P);
273     Fq12Square(d, d);
274     Fq12MulSpecial(d, d, &f);
275     if (VliTestBit(&s, i)) {
276       pair_line(&f, &X, &Y, &Z, &Z2, P, Q);
277       Fq12MulSpecial(d, d, &f);
278     }
279   }
280   if (neg) {
281     Fq2Neg(&Y, &Y);
282     Fq12Conj(d, d);
283   }
284   piOp(&Qp, Q, 1, state);
285   pair_line(&f, &X, &Y, &Z, &Z2, P, &Qp);
286   Fq12MulSpecial(d, d, &f);
287   piOp(&Qp, Q, 2, state);
288   Fq2Neg(&Qp.y, &Qp.y);
289   pair_line(&f, &X, &Y, &Z, &Z2, P, &Qp);
290   Fq12MulSpecial(d, d, &f);
291   finalExp(d, state);
292   // s doesn't have secret information; no need to clear it.
293   Fq12Clear(&f);
294   Fq2Clear(&X);
295   Fq2Clear(&Y);
296   Fq2Clear(&Z);
297   Fq2Clear(&Z2);
298   Fq2Clear(&Qp.x);
299   Fq2Clear(&Qp.y);
300 }
301