1 /*############################################################################
2 # Copyright 2016-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
17 /*!
18 * \file
19 * \brief Intel(R) EPID 1.1 pairing implementation.
20 */
21
22 #include "epid/common/math/tatepairing.h"
23 #include "epid/common/1.1/types.h"
24 #include "epid/common/math/src/bignum-internal.h"
25 #include "epid/common/math/src/ecgroup-internal.h"
26 #include "epid/common/math/src/finitefield-internal.h"
27 #include "epid/common/math/src/tatepairing-internal.h"
28 #include "epid/common/src/memory.h"
29 #include "ext/ipp/include/ippcp.h"
30
31 /// Handle Ipp Errors with Break
32 #define BREAK_ON_IPP_ERROR(sts, ret) \
33 { \
34 IppStatus temp_sts = (sts); \
35 if (ippStsNoErr != temp_sts) { \
36 if (ippStsContextMatchErr == temp_sts) { \
37 (ret) = kEpidMathErr; \
38 } else { \
39 (ret) = kEpidBadArgErr; \
40 } \
41 break; \
42 } \
43 }
44
45 /// Handle SDK Error with Break
46 #define BREAK_ON_EPID_ERROR(ret) \
47 if (kEpidNoErr != (ret)) { \
48 break; \
49 }
50
51 /// Count of elements in array
52 #define COUNT_OF(a) (sizeof(a) / sizeof((a)[0]))
53
54 #pragma pack(1)
55 /// Data for element in Fq
56 typedef struct FqElemDat {
57 Ipp32u x[sizeof(FqElemStr) / sizeof(Ipp32u)]; ///< element in Fq
58 } FqElemDat;
59 /// Data for element in Fq
60 typedef struct Fq3ElemDat {
61 FqElemDat x[3]; ///< element in Fq3
62 } Fq3ElemDat;
63 #pragma pack()
64
65 // Forward Declarations
66 static EpidStatus Fq6FromFq(FiniteField* fq6, FiniteField* fq,
67 FfElement const* a, FfElement* r);
68
69 static EpidStatus JoinFq3(Epid11PairingState* ps, FfElement const* a,
70 FfElement const* b, FfElement* r);
71
72 static EpidStatus SplitFq6(Epid11PairingState* ps, FfElement const* a,
73 FfElement* a0, FfElement* a1);
74
75 static EpidStatus FinalExp(Epid11PairingState* ps, FfElement const* r,
76 FfElement* d);
77
78 static EpidStatus Transform(Epid11PairingState* ps, FfElement const* a,
79 FfElement* b);
80
NewEpid11PairingState(EcGroup const * ga,EcGroup const * gb,FiniteField const * ff,Epid11PairingState ** ps)81 EpidStatus NewEpid11PairingState(EcGroup const* ga, EcGroup const* gb,
82 FiniteField const* ff,
83 Epid11PairingState** ps) {
84 EpidStatus result = kEpidErr;
85 Epid11PairingState* pairing_state_ctx = NULL;
86 BigNum* tmp = NULL;
87 BigNum* p = NULL;
88 FfElement* qnr = NULL;
89 FfElement* inv_qnr = NULL;
90 FfElement* neg_qnr = NULL;
91 Fq3ElemStr fq3_str = {0};
92 int i = 0;
93
94 do {
95 IppStatus sts = ippStsNoErr;
96 IppsGFpState* Fq3 = NULL;
97 IppsGFpState* Fq = NULL;
98 Fq3ElemDat ff_modulus = {0};
99 uint8_t one_str[] = {1};
100 uint8_t remainder_str = 0xff;
101 Fq3ElemStr trans_100 = {0};
102 Fq3ElemStr trans_010 = {0};
103 FiniteField* Ffq = NULL;
104
105 // validate inputs
106 if (!ga || !gb || !ff || !ps) {
107 result = kEpidBadArgErr;
108 break;
109 }
110 if (!ga->ff || !ga->ipp_ec || !gb->ff || !gb->ipp_ec || !ff->ipp_ff) {
111 result = kEpidBadArgErr;
112 break;
113 }
114 if (1 != ga->ff->basic_degree || 3 != gb->ff->basic_degree ||
115 6 != ff->basic_degree ||
116 sizeof(Epid11G1ElemStr) != (ga->ff->element_len << 3) ||
117 sizeof(Epid11G2ElemStr) != (gb->ff->element_len << 3) ||
118 sizeof(Epid11GtElemStr) != (ff->element_len << 2)) {
119 result = kEpidBadArgErr;
120 break;
121 }
122 pairing_state_ctx =
123 (Epid11PairingState*)SAFE_ALLOC(sizeof(Epid11PairingState));
124 if (!pairing_state_ctx) {
125 result = kEpidMemAllocErr;
126 break;
127 }
128
129 // store Intel(R) EPID fields and groups
130 pairing_state_ctx->ga = (EcGroup*)ga;
131 pairing_state_ctx->gb = (EcGroup*)gb;
132 pairing_state_ctx->ff = (FiniteField*)ff;
133
134 // get Fq3, Fq
135 pairing_state_ctx->Fq3 = ff->ground_ff;
136 if (!pairing_state_ctx->Fq3) {
137 result = kEpidBadArgErr;
138 break;
139 }
140 Fq3 = pairing_state_ctx->Fq3->ipp_ff;
141 pairing_state_ctx->Fq = pairing_state_ctx->Fq3->ground_ff;
142 Ffq = pairing_state_ctx->Fq;
143 if (!pairing_state_ctx->Fq) {
144 result = kEpidBadArgErr;
145 break;
146 }
147 Fq = pairing_state_ctx->Fq->ipp_ff;
148
149 // compute fq3_inv_constant = (inverse(qnr), 0, 0)
150 result = NewFfElement(pairing_state_ctx->Fq3,
151 &pairing_state_ctx->fq3_inv_constant);
152 BREAK_ON_EPID_ERROR(result);
153 result = NewFfElement(pairing_state_ctx->Fq, &neg_qnr);
154 BREAK_ON_EPID_ERROR(result);
155 result = NewFfElement(pairing_state_ctx->Fq, &qnr);
156 BREAK_ON_EPID_ERROR(result);
157 result = NewFfElement(pairing_state_ctx->Fq, &inv_qnr);
158 BREAK_ON_EPID_ERROR(result);
159 result = WriteBigNum(ff->modulus_0, sizeof(ff_modulus), &ff_modulus);
160 BREAK_ON_EPID_ERROR(result);
161 result = SetFfElementOctString((ConstOctStr)ff_modulus.x[0].x,
162 sizeof(ff_modulus.x[0].x), neg_qnr,
163 pairing_state_ctx->Fq);
164 BREAK_ON_EPID_ERROR(result);
165 result = FfNeg(pairing_state_ctx->Fq, neg_qnr, qnr);
166 BREAK_ON_EPID_ERROR(result);
167 result = FfInv(pairing_state_ctx->Fq, qnr, inv_qnr);
168 BREAK_ON_EPID_ERROR(result);
169 result = WriteFfElement(pairing_state_ctx->Fq, inv_qnr, &fq3_str.a[0],
170 sizeof(fq3_str.a[0]));
171 BREAK_ON_EPID_ERROR(result);
172 result = ReadFfElement(pairing_state_ctx->Fq3, &fq3_str, sizeof(fq3_str),
173 pairing_state_ctx->fq3_inv_constant);
174 BREAK_ON_EPID_ERROR(result);
175
176 // compute fq3_inv2_constant = (inverse(qnr)^2, 0, 0)
177 // inv_qnr = inv_qnr^2
178 result = NewFfElement(pairing_state_ctx->Fq3,
179 &pairing_state_ctx->fq3_inv2_constant);
180 BREAK_ON_EPID_ERROR(result);
181 result = FfMul(pairing_state_ctx->Fq, inv_qnr, inv_qnr, inv_qnr);
182 BREAK_ON_EPID_ERROR(result);
183 result = WriteFfElement(pairing_state_ctx->Fq, inv_qnr, &fq3_str.a[0],
184 sizeof(fq3_str.a[0]));
185 BREAK_ON_EPID_ERROR(result);
186 result = ReadFfElement(pairing_state_ctx->Fq3, &fq3_str, sizeof(fq3_str),
187 pairing_state_ctx->fq3_inv2_constant);
188 BREAK_ON_EPID_ERROR(result);
189
190 // save parameters a and p for future use
191 result = NewFfElement(pairing_state_ctx->Fq, &pairing_state_ctx->a);
192 BREAK_ON_EPID_ERROR(result);
193 result = NewBigNum(sizeof(BigNumStr), &p);
194 BREAK_ON_EPID_ERROR(result);
195 sts =
196 ippsGFpECGet(NULL, pairing_state_ctx->a->ipp_ff_elem, NULL, ga->ipp_ec);
197 BREAK_ON_IPP_ERROR(sts, result);
198 sts = ippsGFpECGetSubgroup(NULL, NULL, NULL, p->ipp_bn, NULL, ga->ipp_ec);
199 BREAK_ON_IPP_ERROR(sts, result);
200 // compute p bit size requred for pairing
201 sts = ippsGetOctString_BN((OctStr)&pairing_state_ctx->p,
202 sizeof(pairing_state_ctx->p), p->ipp_bn);
203 BREAK_ON_IPP_ERROR(sts, result);
204 pairing_state_ctx->p_bitsize = OctStrBitSize(
205 pairing_state_ctx->p.data.data, sizeof(pairing_state_ctx->p.data.data));
206
207 // compute final_exp_constant = (q^2 - q + 1)/p
208 result = NewBigNum(2 * sizeof(BigNumStr),
209 &pairing_state_ctx->final_exp_constant);
210 BREAK_ON_EPID_ERROR(result);
211 result = NewBigNum(sizeof(BigNumStr), &tmp);
212 BREAK_ON_EPID_ERROR(result);
213 result = ReadBigNum(one_str, sizeof(one_str), tmp);
214 BREAK_ON_EPID_ERROR(result);
215
216 result = BigNumMul(Ffq->modulus_0, Ffq->modulus_0,
217 pairing_state_ctx->final_exp_constant);
218 BREAK_ON_EPID_ERROR(result);
219 result = BigNumSub(pairing_state_ctx->final_exp_constant, Ffq->modulus_0,
220 pairing_state_ctx->final_exp_constant);
221 BREAK_ON_EPID_ERROR(result);
222 result = BigNumAdd(pairing_state_ctx->final_exp_constant, tmp,
223 pairing_state_ctx->final_exp_constant);
224 BREAK_ON_EPID_ERROR(result);
225 result = BigNumDiv(pairing_state_ctx->final_exp_constant, p,
226 pairing_state_ctx->final_exp_constant, tmp);
227 BREAK_ON_EPID_ERROR(result);
228 result = WriteBigNum(tmp, sizeof(remainder_str), &remainder_str);
229 if (kEpidNoErr != result || 0 != remainder_str) {
230 result = kEpidBadArgErr; // p does not divide (q^2 - q + 1)
231 break;
232 }
233
234 for (i = 0; i < 3; i++) {
235 result = NewFfElement(pairing_state_ctx->Fq3,
236 &(pairing_state_ctx->alpha_q[i]));
237 BREAK_ON_EPID_ERROR(result);
238 }
239 BREAK_ON_EPID_ERROR(result);
240 /* t^(0*q) */
241 trans_100.a[0].data.data[31] = 1;
242 result = ReadFfElement(pairing_state_ctx->Fq3, &trans_100,
243 sizeof(trans_100), pairing_state_ctx->alpha_q[0]);
244 BREAK_ON_EPID_ERROR(result);
245 /* t^(1*q) */
246 trans_010.a[1].data.data[31] = 1;
247 result = ReadFfElement(pairing_state_ctx->Fq3, &trans_010,
248 sizeof(trans_010), pairing_state_ctx->alpha_q[1]);
249 BREAK_ON_EPID_ERROR(result);
250 result = FfExp(pairing_state_ctx->Fq3, pairing_state_ctx->alpha_q[1],
251 Ffq->modulus_0, pairing_state_ctx->alpha_q[1]);
252 BREAK_ON_EPID_ERROR(result);
253 /* t^(2*q) */
254 result =
255 FfMul(pairing_state_ctx->Fq3, pairing_state_ctx->alpha_q[1],
256 pairing_state_ctx->alpha_q[1], pairing_state_ctx->alpha_q[2]);
257 BREAK_ON_EPID_ERROR(result);
258
259 *ps = pairing_state_ctx;
260 result = kEpidNoErr;
261 } while (0);
262
263 EpidZeroMemory(&fq3_str, sizeof(fq3_str));
264 DeleteBigNum(&p);
265 DeleteBigNum(&tmp);
266 DeleteFfElement(&qnr);
267 DeleteFfElement(&inv_qnr);
268 DeleteFfElement(&neg_qnr);
269 if (kEpidNoErr != result) {
270 if (pairing_state_ctx) {
271 DeleteFfElement(&pairing_state_ctx->a);
272 DeleteFfElement(&pairing_state_ctx->fq3_inv_constant);
273 DeleteFfElement(&pairing_state_ctx->fq3_inv2_constant);
274 DeleteBigNum(&pairing_state_ctx->final_exp_constant);
275 for (i = 0; i < 3; i++) {
276 DeleteFfElement(&(pairing_state_ctx->alpha_q[i]));
277 }
278 SAFE_FREE(pairing_state_ctx);
279 }
280 }
281 return result;
282 }
283
DeleteEpid11PairingState(Epid11PairingState ** ps)284 void DeleteEpid11PairingState(Epid11PairingState** ps) {
285 size_t i;
286 if (ps && *ps) {
287 DeleteFfElement(&(*ps)->a);
288 DeleteFfElement(&(*ps)->fq3_inv_constant);
289 DeleteFfElement(&(*ps)->fq3_inv2_constant);
290 DeleteBigNum(&(*ps)->final_exp_constant);
291 for (i = 0; i < 3; i++) {
292 DeleteFfElement(&(*ps)->alpha_q[i]);
293 }
294 SAFE_FREE(*ps);
295 }
296 }
297
Epid11Pairing(Epid11PairingState * ps,EcPoint const * a,EcPoint const * b,FfElement * d)298 EpidStatus Epid11Pairing(Epid11PairingState* ps, EcPoint const* a,
299 EcPoint const* b, FfElement* d) {
300 EpidStatus result = kEpidErr;
301 IppStatus sts;
302 FfElement* b0 = NULL;
303 FfElement* b1 = NULL;
304 FfElement* pQx = NULL;
305 FfElement* pQy = NULL;
306 FfElement* px = NULL;
307 FfElement* py = NULL;
308 FfElement* X = NULL;
309 FfElement* Y = NULL;
310 FfElement* Z = NULL;
311 FfElement* X2 = NULL;
312 FfElement* Y2 = NULL;
313 FfElement* Z2 = NULL;
314 FfElement* w = NULL;
315 FfElement* v = NULL;
316 FfElement* ty = NULL;
317 FfElement* ry = NULL;
318 FfElement* tx = NULL;
319 FfElement* rx = NULL;
320 FfElement* t1 = NULL;
321 FfElement* t2 = NULL;
322 FfElement* t3 = NULL;
323 FfElement* tt1 = NULL;
324 FfElement* tt2 = NULL;
325 FfElement* r = NULL;
326 Epid11G1ElemStr a_str = {0};
327 Epid11G2ElemStr b_str = {0};
328 Epid11GtElemStr bx_str = {0};
329 Epid11GtElemStr by_str = {0};
330 bool is_identity;
331 int i;
332
333 if (!ps || !a || !b || !d) return kEpidBadArgErr;
334 if (!ps->Fq || !ps->Fq3) {
335 return kEpidBadArgErr;
336 }
337 if (!ps->Fq->ipp_ff || !ps->Fq3->ipp_ff) {
338 return kEpidBadArgErr;
339 }
340 do {
341 Epid11GtElemStr one_fq6 = {0};
342 FqElemStr one_fq = {0};
343 one_fq6.a[0].a[0].data.data[31] = 1;
344 one_fq.data.data[31] = 1;
345
346 // If P = O, point at infinity, then return r = 1
347 result = EcIsIdentity(ps->ga, a, &is_identity);
348 BREAK_ON_EPID_ERROR(result);
349 if (is_identity) {
350 result = ReadFfElement(ps->ff, &one_fq6, sizeof(one_fq6), d);
351 BREAK_ON_EPID_ERROR(result);
352 result = kEpidNoErr;
353 break;
354 }
355
356 // Let Q = (Q.x, Q.y), where Q.x and Q.y are elements in Fqd.
357 result = NewFfElement(ps->Fq3, &b0);
358 BREAK_ON_EPID_ERROR(result);
359 result = NewFfElement(ps->Fq3, &b1);
360 BREAK_ON_EPID_ERROR(result);
361 result = WriteEcPoint(ps->gb, b, &b_str, sizeof(b_str));
362 BREAK_ON_EPID_ERROR(result);
363 result = ReadFfElement(ps->Fq3, &b_str.x, sizeof(b_str.x), b0);
364 BREAK_ON_EPID_ERROR(result);
365 result = ReadFfElement(ps->Fq3, &b_str.y, sizeof(b_str.y), b1);
366 BREAK_ON_EPID_ERROR(result);
367
368 // Now we compute Qx, Qy, two elements in GT, as follows.
369 result = NewFfElement(ps->ff, &pQx);
370 BREAK_ON_EPID_ERROR(result);
371 result = NewFfElement(ps->ff, &pQy);
372 BREAK_ON_EPID_ERROR(result);
373
374 // Compute Qx = (inv * Q.x, 0).
375 result = FfMul(ps->Fq3, ps->fq3_inv_constant, b0, b0);
376 BREAK_ON_EPID_ERROR(result);
377 result = WriteFfElement(ps->Fq3, b0, &bx_str.a[0], sizeof(bx_str.a[0]));
378 BREAK_ON_EPID_ERROR(result);
379 result = ReadFfElement(ps->ff, &bx_str, sizeof(bx_str), pQx);
380 BREAK_ON_EPID_ERROR(result);
381
382 // Compute Qy = (0, inv^2 * Q.y).
383 result = FfMul(ps->Fq3, ps->fq3_inv2_constant, b1, b1);
384 BREAK_ON_EPID_ERROR(result);
385 result = WriteFfElement(ps->Fq3, b1, &by_str.a[1], sizeof(by_str.a[1]));
386 BREAK_ON_EPID_ERROR(result);
387 result = ReadFfElement(ps->ff, &by_str, sizeof(by_str), pQy);
388 BREAK_ON_EPID_ERROR(result);
389
390 // Let P = (px, py), where px, py are big integers.
391 result = NewFfElement(ps->Fq, &px);
392 BREAK_ON_EPID_ERROR(result);
393 result = NewFfElement(ps->Fq, &py);
394 BREAK_ON_EPID_ERROR(result);
395 result = WriteEcPoint(ps->ga, a, &a_str, sizeof(a_str));
396 BREAK_ON_EPID_ERROR(result);
397 result = ReadFfElement(ps->Fq, &a_str.x, sizeof(a_str.x), px);
398 BREAK_ON_EPID_ERROR(result);
399 result = ReadFfElement(ps->Fq, &a_str.y, sizeof(a_str.y), py);
400 BREAK_ON_EPID_ERROR(result);
401
402 // Let X, Y, Z, X', Y', Z', w, v, ty, ry be elements in Fq.
403 result = NewFfElement(ps->Fq, &X);
404 BREAK_ON_EPID_ERROR(result);
405 result = NewFfElement(ps->Fq, &Y);
406 BREAK_ON_EPID_ERROR(result);
407 result = NewFfElement(ps->Fq, &Z);
408 BREAK_ON_EPID_ERROR(result);
409 result = NewFfElement(ps->Fq, &X2);
410 BREAK_ON_EPID_ERROR(result);
411 result = NewFfElement(ps->Fq, &Y2);
412 BREAK_ON_EPID_ERROR(result);
413 result = NewFfElement(ps->Fq, &Z2);
414 BREAK_ON_EPID_ERROR(result);
415 result = NewFfElement(ps->Fq, &w);
416 BREAK_ON_EPID_ERROR(result);
417 result = NewFfElement(ps->Fq, &v);
418 BREAK_ON_EPID_ERROR(result);
419 result = NewFfElement(ps->Fq, &ty);
420 BREAK_ON_EPID_ERROR(result);
421 result = NewFfElement(ps->Fq, &ry);
422 BREAK_ON_EPID_ERROR(result);
423 result = NewFfElement(ps->Fq, &t1);
424 BREAK_ON_EPID_ERROR(result);
425 result = NewFfElement(ps->Fq, &t2);
426 BREAK_ON_EPID_ERROR(result);
427 result = NewFfElement(ps->Fq, &t3);
428 BREAK_ON_EPID_ERROR(result);
429
430 // Let tx, rx be elements in GT.
431 result = NewFfElement(ps->ff, &tx);
432 BREAK_ON_EPID_ERROR(result);
433 result = NewFfElement(ps->ff, &rx);
434 BREAK_ON_EPID_ERROR(result);
435 result = NewFfElement(ps->ff, &tt1);
436 BREAK_ON_EPID_ERROR(result);
437 result = NewFfElement(ps->ff, &tt2);
438 BREAK_ON_EPID_ERROR(result);
439 result = NewFfElement(ps->ff, &r);
440 BREAK_ON_EPID_ERROR(result);
441
442 // Set X = px,
443 result = ReadFfElement(ps->Fq, &a_str.x, sizeof(a_str.x), X);
444 BREAK_ON_EPID_ERROR(result);
445
446 // Y = py,
447 result = ReadFfElement(ps->Fq, &a_str.y, sizeof(a_str.y), Y);
448 BREAK_ON_EPID_ERROR(result);
449
450 // Z = 1,
451 result = ReadFfElement(ps->Fq, &one_fq, sizeof(one_fq), Z);
452 BREAK_ON_EPID_ERROR(result);
453
454 // ry = 1.
455 result = ReadFfElement(ps->Fq, &one_fq, sizeof(one_fq), ry);
456 BREAK_ON_EPID_ERROR(result);
457
458 // Set rx = 1, identity element of GT.
459 result = ReadFfElement(ps->ff, &one_fq6, sizeof(one_fq6), rx);
460 BREAK_ON_EPID_ERROR(result);
461
462 // Let pn ... p1 p0 be the binary representation of p
463 // For i = n-1, ..., 0 do
464 for (i = (int)ps->p_bitsize - 2; i >= 0; i--) {
465 bool pi = ps->p.data.data[sizeof(ps->p) - 1 - (i >> 3)] & (1 << (i & 7));
466
467 result = FfMul(ps->Fq, Z, Z, ty); // ty = Z^2
468 BREAK_ON_EPID_ERROR(result);
469 result = FfMul(ps->Fq, ty, ty, t1); // t1 = Z^4
470 BREAK_ON_EPID_ERROR(result);
471 result = FfMul(ps->Fq, t1, ps->a, t1); // t1 = a*Z^4
472 BREAK_ON_EPID_ERROR(result);
473 result = FfMul(ps->Fq, X, X, w); // w = X^2
474 BREAK_ON_EPID_ERROR(result);
475 result = FfAdd(ps->Fq, w, w, t2); // t2 = 2 * X^2
476 BREAK_ON_EPID_ERROR(result);
477 result = FfAdd(ps->Fq, w, t2, w); // w = 3 * X^2
478 BREAK_ON_EPID_ERROR(result);
479 result = FfAdd(ps->Fq, w, t1, w); // w = 3 * X^2 + a * Z^4
480 BREAK_ON_EPID_ERROR(result);
481
482 result = FfMul(ps->Fq, Y, Y, t1); // t1 = Y^2
483 BREAK_ON_EPID_ERROR(result);
484 result = FfAdd(ps->Fq, t1, t1, t3); // t3 = 2* Y^2
485 BREAK_ON_EPID_ERROR(result);
486 result = FfMul(ps->Fq, t3, X, v); // v = 2 * X * Y^2
487 BREAK_ON_EPID_ERROR(result);
488 result = FfAdd(ps->Fq, v, v, v); // v = 4 * X * Y^2
489 BREAK_ON_EPID_ERROR(result);
490
491 result = FfMul(ps->Fq, w, w, X2); // X2 = w^2
492 BREAK_ON_EPID_ERROR(result);
493 result = FfSub(ps->Fq, X2, v, X2); // X2 = w^2 - v
494 BREAK_ON_EPID_ERROR(result);
495 result = FfSub(ps->Fq, X2, v, X2); // X2 = w^2 - 2 * w
496 BREAK_ON_EPID_ERROR(result);
497
498 result = FfMul(ps->Fq, t3, t3, t3); // t3 = 4 * Y^4
499 BREAK_ON_EPID_ERROR(result);
500 result = FfAdd(ps->Fq, t3, t3, t3); // t3 = 8 * Y^4
501 BREAK_ON_EPID_ERROR(result);
502 result = FfSub(ps->Fq, v, X2, Y2); // Y2 = v - X2
503 BREAK_ON_EPID_ERROR(result);
504 result = FfMul(ps->Fq, Y2, w, Y2); // Y2 = w * (v - X2)
505 BREAK_ON_EPID_ERROR(result);
506 result = FfSub(ps->Fq, Y2, t3, Y2); // Y2 = w * (v - X2) - 8 * Y^4
507 BREAK_ON_EPID_ERROR(result);
508
509 result = FfMul(ps->Fq, Y, Z, Z2); // Z2 = Y * Z
510 BREAK_ON_EPID_ERROR(result);
511 result = FfAdd(ps->Fq, Z2, Z2, Z2); // Z2 = 2 * Y * Z
512 BREAK_ON_EPID_ERROR(result);
513
514 /* compute line */
515 result = FfMul(ps->Fq, ty, w, t2); // t2 = w * Z^2
516 BREAK_ON_EPID_ERROR(result);
517 result = Fq6FromFq(ps->ff, ps->Fq, t2, tt2);
518 BREAK_ON_EPID_ERROR(result);
519 result = FfMul(ps->ff, pQx, tt2, tt1); // tt1 = w * Z^2 * Qx
520 BREAK_ON_EPID_ERROR(result);
521 result = FfMul(ps->Fq, w, X, t2); // t2 = w * X
522 BREAK_ON_EPID_ERROR(result);
523 result = FfSub(ps->Fq, t2, t1, t2); // t2 = w * X - Y^2
524 BREAK_ON_EPID_ERROR(result);
525 result = FfSub(ps->Fq, t2, t1, t2); // t2 = w * X - 2 * Y^2
526 BREAK_ON_EPID_ERROR(result);
527 result = FfMul(ps->Fq, ty, Z2, ty); // ty = Z2 * Z^2
528 BREAK_ON_EPID_ERROR(result);
529 result = Fq6FromFq(ps->ff, ps->Fq, ty, tt2);
530 BREAK_ON_EPID_ERROR(result);
531 result = FfMul(ps->ff, pQy, tt2, tx); // tx = ty * Qy
532 BREAK_ON_EPID_ERROR(result);
533 result = FfSub(ps->ff, tx, tt1, tx); // tx = ty * Qy - w * Z^2 * Qx
534 BREAK_ON_EPID_ERROR(result);
535 result = Fq6FromFq(ps->ff, ps->Fq, t2, tt2);
536 BREAK_ON_EPID_ERROR(result);
537 result = FfAdd(ps->ff, tx, tt2,
538 tx); // tx = ty * Qy - w * Z^2 * Qx + w * X - 2 * Y^2
539 BREAK_ON_EPID_ERROR(result);
540
541 sts = ippsGFpCpyElement(X2->ipp_ff_elem, X->ipp_ff_elem,
542 ps->Fq->ipp_ff); // X = X2
543 BREAK_ON_IPP_ERROR(sts, result);
544 sts = ippsGFpCpyElement(Y2->ipp_ff_elem, Y->ipp_ff_elem,
545 ps->Fq->ipp_ff); // Y = Y2
546 BREAK_ON_IPP_ERROR(sts, result);
547 sts = ippsGFpCpyElement(Z2->ipp_ff_elem, Z->ipp_ff_elem,
548 ps->Fq->ipp_ff); // Z = Z2
549 BREAK_ON_IPP_ERROR(sts, result);
550
551 /* udpate rx, ry */
552 result = FfMul(ps->ff, rx, rx, tt1); // tt1 = rx * rx
553 BREAK_ON_EPID_ERROR(result);
554 result = FfMul(ps->ff, tx, tt1, rx); // rx = tx * rx * rx
555 BREAK_ON_EPID_ERROR(result);
556 result = FfMul(ps->Fq, ry, ry, t1); // t1 = ry * ry
557 BREAK_ON_EPID_ERROR(result);
558 result = FfMul(ps->Fq, ty, t1, ry); // ry = ty * ry * ry
559 BREAK_ON_EPID_ERROR(result);
560
561 if (pi && i) {
562 result = FfMul(ps->Fq, Z, Z, t1); // t1 = Z^2
563 BREAK_ON_EPID_ERROR(result);
564 result = FfMul(ps->Fq, px, t1, w); // w = px * Z^2
565 BREAK_ON_EPID_ERROR(result);
566 result = FfSub(ps->Fq, w, X, w); // w = px * Z^2 - X
567 BREAK_ON_EPID_ERROR(result);
568 result = FfMul(ps->Fq, t1, Z, t1); // t1 = Z^3
569 BREAK_ON_EPID_ERROR(result);
570 result = FfMul(ps->Fq, py, t1, v); // v = py * Z^3
571 BREAK_ON_EPID_ERROR(result);
572 result = FfSub(ps->Fq, v, Y, v); // v = py * Z^3 - Y
573 BREAK_ON_EPID_ERROR(result);
574
575 result = FfMul(ps->Fq, w, w, t1); // t1 = w^2
576 BREAK_ON_EPID_ERROR(result);
577 result = FfMul(ps->Fq, w, t1, t2); // t2 = w^3
578 BREAK_ON_EPID_ERROR(result);
579 result = FfMul(ps->Fq, X, t1, t3); // t3 = X * w^2
580 BREAK_ON_EPID_ERROR(result);
581 result = FfMul(ps->Fq, v, v, X2); // X2 = v^2
582 BREAK_ON_EPID_ERROR(result);
583 result = FfSub(ps->Fq, X2, t2, X2); // X2 = v^2 - w^3
584 BREAK_ON_EPID_ERROR(result);
585 result = FfSub(ps->Fq, X2, t3, X2); // X2 = v^2 - w^3 - X * w^2
586 BREAK_ON_EPID_ERROR(result);
587 result = FfSub(ps->Fq, X2, t3, X2); // X2 = v^2 - w^3 - 2 * X * w^2
588 BREAK_ON_EPID_ERROR(result);
589 result = FfSub(ps->Fq, t3, X2, Y2); // Y2 = X * w^2 - X2
590 BREAK_ON_EPID_ERROR(result);
591 result = FfMul(ps->Fq, Y2, v, Y2); // Y2 = v * (X * w^2 - X2)
592 BREAK_ON_EPID_ERROR(result);
593 result = FfMul(ps->Fq, t2, Y, t2); // t2 = Y * w^3
594 BREAK_ON_EPID_ERROR(result);
595 result =
596 FfSub(ps->Fq, Y2, t2, Y2); // Y2 = v * (X * w^2 - X2) - Y * w^3
597 BREAK_ON_EPID_ERROR(result);
598 result = FfMul(ps->Fq, w, Z, Z2); // Z2 = w * Z
599 BREAK_ON_EPID_ERROR(result);
600
601 /* compute tx, ty */
602 sts = ippsGFpCpyElement(Z2->ipp_ff_elem, ty->ipp_ff_elem,
603 ps->Fq->ipp_ff); // ty = Z2
604 BREAK_ON_IPP_ERROR(sts, result);
605 result = Fq6FromFq(ps->ff, ps->Fq, py, tt2);
606 BREAK_ON_EPID_ERROR(result);
607 result = FfSub(ps->ff, pQy, tt2, tx); // tx = Qy - py
608 BREAK_ON_EPID_ERROR(result);
609 result = Fq6FromFq(ps->ff, ps->Fq, Z2, tt2);
610 BREAK_ON_EPID_ERROR(result);
611 result = FfMul(ps->ff, tx, tt2, tx); // tx = Z2 * (Qy - py)
612 BREAK_ON_EPID_ERROR(result);
613 result = Fq6FromFq(ps->ff, ps->Fq, px, tt2);
614 BREAK_ON_EPID_ERROR(result);
615 result = FfSub(ps->ff, pQx, tt2, tt1); // tt1 = Qx - px
616 BREAK_ON_EPID_ERROR(result);
617 result = Fq6FromFq(ps->ff, ps->Fq, v, tt2);
618 BREAK_ON_EPID_ERROR(result);
619 result = FfMul(ps->ff, tt1, tt2, tt1); // tt1 = v * (Qx - px)
620 BREAK_ON_EPID_ERROR(result);
621 result =
622 FfSub(ps->ff, tx, tt1, tx); // tx = Z2 * (Qy - py) - v * (Qx - px)
623 BREAK_ON_EPID_ERROR(result);
624
625 sts = ippsGFpCpyElement(X2->ipp_ff_elem, X->ipp_ff_elem,
626 ps->Fq->ipp_ff); // X = X2
627 BREAK_ON_IPP_ERROR(sts, result);
628 sts = ippsGFpCpyElement(Y2->ipp_ff_elem, Y->ipp_ff_elem,
629 ps->Fq->ipp_ff); // Y = Y2
630 BREAK_ON_IPP_ERROR(sts, result);
631 sts = ippsGFpCpyElement(Z2->ipp_ff_elem, Z->ipp_ff_elem,
632 ps->Fq->ipp_ff); // Z = Z2
633 BREAK_ON_IPP_ERROR(sts, result);
634
635 /* udpate rx, ry */
636 result = FfMul(ps->ff, rx, tx, rx); // rx = rx * tx
637 BREAK_ON_EPID_ERROR(result);
638 result = FfMul(ps->Fq, ry, ty, ry); // ry = ry * ty
639 BREAK_ON_EPID_ERROR(result);
640 }
641 }
642 BREAK_ON_EPID_ERROR(result);
643
644 result = FfInv(ps->Fq, ry, ry); // ry = ry^-1
645 BREAK_ON_EPID_ERROR(result);
646 result = Fq6FromFq(ps->ff, ps->Fq, ry, tt2);
647 BREAK_ON_EPID_ERROR(result);
648 result = FfMul(ps->ff, rx, tt2, r); // r = rx * ry
649 BREAK_ON_EPID_ERROR(result);
650
651 result = FinalExp(ps, r, d);
652 BREAK_ON_EPID_ERROR(result);
653
654 result = kEpidNoErr;
655 BREAK_ON_EPID_ERROR(result);
656 } while (0);
657
658 EpidZeroMemory(&a_str, sizeof(a_str));
659 EpidZeroMemory(&b_str, sizeof(b_str));
660 EpidZeroMemory(&bx_str, sizeof(bx_str));
661 EpidZeroMemory(&by_str, sizeof(by_str));
662 DeleteFfElement(&b0);
663 DeleteFfElement(&b1);
664 DeleteFfElement(&pQx);
665 DeleteFfElement(&pQy);
666 DeleteFfElement(&px);
667 DeleteFfElement(&py);
668 DeleteFfElement(&X);
669 DeleteFfElement(&Y);
670 DeleteFfElement(&Z);
671 DeleteFfElement(&X2);
672 DeleteFfElement(&Y2);
673 DeleteFfElement(&Z2);
674 DeleteFfElement(&w);
675 DeleteFfElement(&v);
676 DeleteFfElement(&ty);
677 DeleteFfElement(&ry);
678 DeleteFfElement(&tx);
679 DeleteFfElement(&rx);
680 DeleteFfElement(&t1);
681 DeleteFfElement(&t2);
682 DeleteFfElement(&t3);
683 DeleteFfElement(&tt1);
684 DeleteFfElement(&tt2);
685 DeleteFfElement(&r);
686 return result;
687 }
688
Fq6FromFq(FiniteField * fq6,FiniteField * fq,FfElement const * a,FfElement * r)689 static EpidStatus Fq6FromFq(FiniteField* fq6, FiniteField* fq,
690 FfElement const* a, FfElement* r) {
691 EpidStatus result = kEpidErr;
692 // initialize all Fq6 coefficients to 0
693 Fq6ElemStr r_str = {0};
694
695 if (!fq6 || !fq || !a || !r) return kEpidBadArgErr;
696
697 do {
698 // set Fq6 degree zero coefficient to 'a'
699 result = WriteFfElement(fq, a, &r_str.a[0].a[0], sizeof(r_str.a[0].a[0]));
700 BREAK_ON_EPID_ERROR(result);
701 result = ReadFfElement(fq6, &r_str, sizeof(r_str), r);
702 BREAK_ON_EPID_ERROR(result);
703 result = kEpidNoErr;
704 } while (0);
705 EpidZeroMemory(&r_str, sizeof(r_str));
706 return result;
707 }
708
709 /// Set r from Fq6 to (a, b), where a and b from Fq3
JoinFq3(Epid11PairingState * ps,FfElement const * a,FfElement const * b,FfElement * r)710 static EpidStatus JoinFq3(Epid11PairingState* ps, FfElement const* a,
711 FfElement const* b, FfElement* r) {
712 EpidStatus result = kEpidErr;
713 Epid11GtElemStr r_str = {0};
714
715 do {
716 // validate inputs
717 if (!ps || !a || !b || !r) {
718 result = kEpidBadArgErr;
719 break;
720 }
721 result = WriteFfElement(ps->Fq3, a, &r_str.a[0], sizeof(r_str.a[0]));
722 BREAK_ON_EPID_ERROR(result);
723 result = WriteFfElement(ps->Fq3, b, &r_str.a[1], sizeof(r_str.a[1]));
724 BREAK_ON_EPID_ERROR(result);
725 result = ReadFfElement(ps->ff, &r_str, sizeof(r_str), r);
726 BREAK_ON_EPID_ERROR(result);
727 result = kEpidNoErr;
728 } while (0);
729
730 EpidZeroMemory(&r_str, sizeof(r_str));
731 return result;
732 }
733
734 /// Set a0 and a1 from Fq3 to a0' and a1', where a = (a0', a1') from Fq6
SplitFq6(Epid11PairingState * ps,FfElement const * a,FfElement * a0,FfElement * a1)735 static EpidStatus SplitFq6(Epid11PairingState* ps, FfElement const* a,
736 FfElement* a0, FfElement* a1) {
737 EpidStatus result = kEpidErr;
738 Epid11GtElemStr a_str = {0};
739
740 do {
741 // validate inputs
742 if (!ps || !a0 || !a1 || !a) {
743 result = kEpidBadArgErr;
744 break;
745 }
746 result = WriteFfElement(ps->ff, a, &a_str, sizeof(a_str));
747 BREAK_ON_EPID_ERROR(result);
748 result = ReadFfElement(ps->Fq3, &a_str.a[0], sizeof(a_str.a[0]), a0);
749 BREAK_ON_EPID_ERROR(result);
750 result = ReadFfElement(ps->Fq3, &a_str.a[1], sizeof(a_str.a[1]), a1);
751 BREAK_ON_EPID_ERROR(result);
752 result = kEpidNoErr;
753 } while (0);
754
755 EpidZeroMemory(&a_str, sizeof(a_str));
756 return result;
757 }
758
FinalExp(Epid11PairingState * ps,FfElement const * r,FfElement * d)759 static EpidStatus FinalExp(Epid11PairingState* ps, FfElement const* r,
760 FfElement* d) {
761 EpidStatus result = kEpidErr;
762 FfElement* r0 = NULL;
763 FfElement* r1 = NULL;
764 FfElement* neg_r1 = NULL;
765 FfElement* x = NULL;
766 FfElement* y = NULL;
767 FfElement* neg_y = NULL;
768 FfElement* t1 = NULL;
769 FfElement* t2 = NULL;
770 FfElement* t3 = NULL;
771 FfElement* t4 = NULL;
772 FfElement* d1 = NULL;
773 FfElement* d2 = NULL;
774 FfElement* inv_d2 = NULL;
775 do {
776 // validate inputs
777 if (!ps || !r || !d) {
778 result = kEpidBadArgErr;
779 break;
780 }
781
782 // a.Let r = (r[0], r[1]), where r[0] and r[1] are elements in Fqd,
783 result = NewFfElement(ps->Fq3, &r0);
784 BREAK_ON_EPID_ERROR(result);
785 result = NewFfElement(ps->Fq3, &r1);
786 BREAK_ON_EPID_ERROR(result);
787 result = SplitFq6(ps, r, r0, r1);
788 BREAK_ON_EPID_ERROR(result);
789
790 // b.Compute x = transform(r[0]), where x is an element in Fqd,
791 result = NewFfElement(ps->Fq3, &x);
792 BREAK_ON_EPID_ERROR(result);
793 result = Transform(ps, r0, x);
794 BREAK_ON_EPID_ERROR(result);
795
796 // c.Compute y = transform(r[1]), where x is an element in Fqd,
797 result = NewFfElement(ps->Fq3, &y);
798 BREAK_ON_EPID_ERROR(result);
799 result = Transform(ps, r1, y);
800 BREAK_ON_EPID_ERROR(result);
801
802 // d.Let t1, t2, t3, t4 be four variables in GT,
803 result = NewFfElement(ps->ff, &t1);
804 BREAK_ON_EPID_ERROR(result);
805 result = NewFfElement(ps->ff, &t2);
806 BREAK_ON_EPID_ERROR(result);
807 result = NewFfElement(ps->ff, &t3);
808 BREAK_ON_EPID_ERROR(result);
809 result = NewFfElement(ps->ff, &t4);
810
811 //
812 // e.t1 = (x, y), t2 = (r[0], -r[1]), t3 = (x, -y), t4 = (r[0], r[1]),
813 //
814
815 // t1 = (x, y)
816 result = JoinFq3(ps, x, y, t1);
817 BREAK_ON_EPID_ERROR(result);
818
819 // t2 = (r[0], -r[1])
820 result = NewFfElement(ps->Fq3, &neg_r1);
821 BREAK_ON_EPID_ERROR(result);
822 result = FfNeg(ps->Fq3, r1, neg_r1);
823 BREAK_ON_EPID_ERROR(result);
824 result = JoinFq3(ps, r0, neg_r1, t2);
825 BREAK_ON_EPID_ERROR(result);
826
827 // t3 = (x, -y)
828 result = NewFfElement(ps->Fq3, &neg_y);
829 BREAK_ON_EPID_ERROR(result);
830 result = FfNeg(ps->Fq3, y, neg_y);
831 BREAK_ON_EPID_ERROR(result);
832 result = JoinFq3(ps, x, neg_y, t3);
833 BREAK_ON_EPID_ERROR(result);
834
835 // t4 = (r[0], r[1])
836 result = JoinFq3(ps, r0, r1, t4);
837 BREAK_ON_EPID_ERROR(result);
838
839 //
840 // f. d = (t1 * t2) / (t3 * t4),
841 //
842
843 // d1 = t1 * t2
844 result = NewFfElement(ps->ff, &d1);
845 BREAK_ON_EPID_ERROR(result);
846 result = FfMul(ps->ff, t1, t2, d1);
847 BREAK_ON_EPID_ERROR(result);
848
849 // d2 = t3 * t4
850 result = NewFfElement(ps->ff, &d2);
851 BREAK_ON_EPID_ERROR(result);
852 result = FfMul(ps->ff, t3, t4, d2);
853 BREAK_ON_EPID_ERROR(result);
854
855 // d = d1 / d2
856 result = NewFfElement(ps->ff, &inv_d2);
857 BREAK_ON_EPID_ERROR(result);
858 result = FfInv(ps->ff, d2, inv_d2);
859 BREAK_ON_EPID_ERROR(result);
860 result = FfMul(ps->ff, d1, inv_d2, d);
861 BREAK_ON_EPID_ERROR(result);
862
863 // g.Compute d = GT.exp(d, (q2 - q + 1) / p).
864 result = FfExp(ps->ff, d, ps->final_exp_constant, d);
865 BREAK_ON_EPID_ERROR(result);
866
867 result = kEpidNoErr;
868 } while (0);
869
870 DeleteFfElement(&r0);
871 DeleteFfElement(&r1);
872 DeleteFfElement(&neg_r1);
873 DeleteFfElement(&x);
874 DeleteFfElement(&y);
875 DeleteFfElement(&neg_y);
876 DeleteFfElement(&t1);
877 DeleteFfElement(&t2);
878 DeleteFfElement(&t3);
879 DeleteFfElement(&t4);
880 DeleteFfElement(&d1);
881 DeleteFfElement(&d2);
882 DeleteFfElement(&inv_d2);
883 return result;
884 }
885
Transform(Epid11PairingState * ps,FfElement const * a,FfElement * b)886 static EpidStatus Transform(Epid11PairingState* ps, FfElement const* a,
887 FfElement* b) {
888 EpidStatus result = kEpidErr;
889 FfElement* tmp = NULL;
890 Fq3ElemStr zero = {0};
891 Fq3ElemStr a_str = {0};
892 Fq3ElemStr tmp_str = {0};
893 int i = 0;
894
895 if (!ps || !a || !b) return kEpidBadArgErr;
896
897 do {
898 result = WriteFfElement(ps->Fq3, a, &a_str, sizeof(a_str));
899 BREAK_ON_EPID_ERROR(result);
900 result = NewFfElement(ps->Fq3, &tmp);
901 BREAK_ON_EPID_ERROR(result);
902 // b = 0
903 result = ReadFfElement(ps->Fq3, &zero, sizeof(zero), b);
904 BREAK_ON_EPID_ERROR(result);
905 for (i = 0; i < 3; i++) {
906 // tmp = (a[0][i], 0, 0)
907 tmp_str.a[0] = a_str.a[i];
908 result = ReadFfElement(ps->Fq3, &tmp_str, sizeof(tmp_str), tmp);
909 BREAK_ON_EPID_ERROR(result);
910 // tmp *= alpha_q[i]
911 result = FfMul(ps->Fq3, ps->alpha_q[i], tmp, tmp);
912 BREAK_ON_EPID_ERROR(result);
913 // b += tmp
914 result = FfAdd(ps->Fq3, tmp, b, b);
915 BREAK_ON_EPID_ERROR(result);
916 }
917 BREAK_ON_EPID_ERROR(result);
918 result = kEpidNoErr;
919 } while (0);
920
921 EpidZeroMemory(&a_str, sizeof(a_str));
922 EpidZeroMemory(&tmp_str, sizeof(tmp_str));
923 DeleteFfElement(&tmp);
924 return result;
925 }
926