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