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 Fq12 math
17 /*! \file */
18
19 #include "epid/member/tiny/math/fq12.h"
20
21 #include "epid/member/tiny/math/fq.h"
22 #include "epid/member/tiny/math/fq2.h"
23 #include "epid/member/tiny/math/fq6.h"
24 #include "epid/member/tiny/math/mathtypes.h"
25 #include "epid/member/tiny/math/vli.h"
26 #include "epid/member/tiny/stdlib/tiny_stdlib.h"
27
Fq12MulScalar(Fq12Elem * result,Fq12Elem const * left,Fq6Elem const * right)28 static void Fq12MulScalar(Fq12Elem* result, Fq12Elem const* left,
29 Fq6Elem const* right) {
30 Fq6Mul(&result->z0, &left->z0, right);
31 Fq6Mul(&result->z1, &left->z1, right);
32 }
33
Fq4Square(Fq2Elem * out0,Fq2Elem * out1,Fq2Elem const * in0,Fq2Elem const * in1)34 static void Fq4Square(Fq2Elem* out0, Fq2Elem* out1, Fq2Elem const* in0,
35 Fq2Elem const* in1) {
36 Fq2Elem tmp;
37 Fq2Elem* temp = &tmp;
38 Fq2Square(temp, in1);
39 Fq2Add(out1, in0, in1);
40 Fq2Square(out0, in0);
41 Fq2Square(out1, out1);
42 Fq2Sub(out1, out1, temp);
43 Fq2Sub(out1, out1, out0);
44 Fq2MulXi(temp, temp);
45 Fq2Add(out0, out0, temp);
46 }
47
Fq12CondSet(Fq12Elem * result,Fq12Elem const * true_val,Fq12Elem const * false_val,int truth_val)48 static void Fq12CondSet(Fq12Elem* result, Fq12Elem const* true_val,
49 Fq12Elem const* false_val, int truth_val) {
50 Fq6CondSet(&result->z0, &true_val->z0, &false_val->z0, truth_val);
51 Fq6CondSet(&result->z1, &true_val->z1, &false_val->z1, truth_val);
52 }
53
Fq12Add(Fq12Elem * result,Fq12Elem const * left,Fq12Elem const * right)54 void Fq12Add(Fq12Elem* result, Fq12Elem const* left, Fq12Elem const* right) {
55 Fq6Add(&result->z0, &left->z0, &right->z0);
56 Fq6Add(&result->z1, &left->z1, &right->z1);
57 }
58
Fq12Sub(Fq12Elem * result,Fq12Elem const * left,Fq12Elem const * right)59 void Fq12Sub(Fq12Elem* result, Fq12Elem const* left, Fq12Elem const* right) {
60 Fq6Sub(&result->z0, &left->z0, &right->z0);
61 Fq6Sub(&result->z1, &left->z1, &right->z1);
62 }
63
Fq12Square(Fq12Elem * result,Fq12Elem const * in)64 void Fq12Square(Fq12Elem* result, Fq12Elem const* in) {
65 Fq6Elem tmpa;
66 Fq6Elem* temp_a = &tmpa;
67 Fq6Square(temp_a, &in->z1);
68 Fq6Add(&result->z1, &in->z0, &in->z1);
69 Fq6Square(&result->z0, &in->z0);
70 Fq6Square(&result->z1, &result->z1);
71 Fq6Sub(&result->z1, &result->z1, (&result->z0));
72 Fq6Sub(&result->z1, &result->z1, temp_a);
73 Fq6MulV(temp_a, temp_a);
74 Fq6Add((&result->z0), (&result->z0), temp_a);
75 }
76
Fq12Mul(Fq12Elem * result,Fq12Elem const * left,Fq12Elem const * right)77 void Fq12Mul(Fq12Elem* result, Fq12Elem const* left, Fq12Elem const* right) {
78 Fq6Elem A;
79 Fq6Elem B;
80 Fq6Elem* t0 = &A;
81 Fq6Elem* t1 = &B;
82
83 Fq6Add(t0, &left->z0, &left->z1);
84 Fq6Add(t1, &right->z0, &right->z1);
85 Fq6Mul(t0, t0, t1);
86 Fq6Mul(&result->z0, &left->z0, &right->z0);
87 Fq6Sub(t0, t0, &result->z0);
88 Fq6Mul(t1, &left->z1, &right->z1);
89 Fq6Sub(&result->z1, t0, t1);
90 Fq6MulV(t1, t1);
91 Fq6Add(&result->z0, &result->z0, t1);
92 }
93
Fq12Inv(Fq12Elem * result,Fq12Elem const * in)94 void Fq12Inv(Fq12Elem* result, Fq12Elem const* in) {
95 Fq12Elem tmp3;
96 Fq12Elem tmp4;
97 Fq12Elem* const temp3 = &tmp3;
98 Fq12Elem* const temp4 = &tmp4;
99 Fq12Conj(temp3, in);
100 Fq12Mul(temp4, temp3, in);
101 Fq6Inv(&temp4->z0, &temp4->z0);
102 Fq12MulScalar(result, temp3, &temp4->z0);
103 }
104
Fq12Neg(Fq12Elem * result,Fq12Elem const * in)105 void Fq12Neg(Fq12Elem* result, Fq12Elem const* in) {
106 Fq6Neg(&result->z0, &in->z0);
107 Fq6Neg(&result->z1, &in->z1);
108 }
109
Fq12Set(Fq12Elem * result,uint32_t val)110 void Fq12Set(Fq12Elem* result, uint32_t val) {
111 Fq12Clear(result);
112 FqSet(&(*result).z0.y0.x0, val);
113 }
114
Fq12Exp(Fq12Elem * result,Fq12Elem const * base,VeryLargeInt const * exp)115 void Fq12Exp(Fq12Elem* result, Fq12Elem const* base, VeryLargeInt const* exp) {
116 int i;
117 Fq12Elem tmp, tmp2, *const temp = &tmp, *const temp2 = &tmp2;
118 Fq12Clear(temp);
119 temp->z0.y0.x0.limbs.word[0]++;
120 for (i = NUM_ECC_DIGITS * 32 - 1; i >= 0; i--) {
121 Fq12Square(temp, temp);
122 Fq12Mul(temp2, temp, base);
123
124 Fq12CondSet(temp, temp2, temp,
125 (int)((exp->word[i / 32] >> (i & 31)) & (0x1)));
126 }
127 Fq12Cp(result, temp);
128 }
129
Fq12MultiExp(Fq12Elem * result,Fq12Elem const * base0,VeryLargeInt const * exp0,Fq12Elem const * base1,VeryLargeInt const * exp1,Fq12Elem const * base2,VeryLargeInt const * exp2,Fq12Elem const * base3,VeryLargeInt const * exp3)130 void Fq12MultiExp(Fq12Elem* result, Fq12Elem const* base0,
131 VeryLargeInt const* exp0, Fq12Elem const* base1,
132 VeryLargeInt const* exp1, Fq12Elem const* base2,
133 VeryLargeInt const* exp2, Fq12Elem const* base3,
134 VeryLargeInt const* exp3) {
135 Fq12Elem tmp;
136 Fq12Exp(result, base0, exp0);
137 Fq12Exp(&tmp, base1, exp1);
138 Fq12Mul(result, result, &tmp);
139 Fq12Exp(&tmp, base2, exp2);
140 Fq12Mul(result, result, &tmp);
141 Fq12Exp(&tmp, base3, exp3);
142 Fq12Mul(result, result, &tmp);
143 }
144
Fq12Eq(Fq12Elem const * left,Fq12Elem const * right)145 int Fq12Eq(Fq12Elem const* left, Fq12Elem const* right) {
146 return Fq6Eq(&left->z0, &right->z0) && Fq6Eq(&left->z0, &right->z0);
147 }
148
Fq12Conj(Fq12Elem * result,Fq12Elem const * in)149 void Fq12Conj(Fq12Elem* result, Fq12Elem const* in) {
150 Fq6Cp(&result->z0, &in->z0);
151 Fq6Neg(&result->z1, &in->z1);
152 }
153
Fq12ExpCyc(Fq12Elem * result,Fq12Elem const * in,VeryLargeInt const * t)154 void Fq12ExpCyc(Fq12Elem* result, Fq12Elem const* in, VeryLargeInt const* t) {
155 int i = 0;
156 Fq12Elem ac;
157 Fq12Elem* const acc = ∾
158 Fq12Cp(acc, in);
159 Fq12Cp(result, in);
160
161 for (i = 61; i >= 0; i--) {
162 Fq12SqCyc(result, result);
163
164 if (VliTestBit(t, (uint32_t)i)) {
165 Fq12Mul(result, result, acc);
166 }
167 }
168 }
169
Fq12SqCyc(Fq12Elem * result,Fq12Elem const * in)170 void Fq12SqCyc(Fq12Elem* result, Fq12Elem const* in) {
171 Fq2Elem const* a0 = &(in->z0).y0;
172 Fq2Elem const* a1 = &(in->z1).y0;
173 Fq2Elem const* a2 = &(in->z0).y1;
174 Fq2Elem const* a3 = &(in->z1).y1;
175 Fq2Elem const* a4 = &(in->z0).y2;
176 Fq2Elem const* a5 = &(in->z1).y2;
177 Fq2Elem* e0 = &(result->z0).y0;
178 Fq2Elem* e1 = &(result->z1).y0;
179 Fq2Elem* e2 = &(result->z0).y1;
180 Fq2Elem* e3 = &(result->z1).y1;
181 Fq2Elem* e4 = &(result->z0).y2;
182 Fq2Elem* e5 = &(result->z1).y2;
183 Fq2Elem tmp1;
184 Fq2Elem tmp2;
185 Fq2Elem tmp3;
186 Fq2Elem tmp4;
187 Fq2Elem* temp1 = &tmp1;
188 Fq2Elem* temp2 = &tmp2;
189 Fq2Elem* temp3 = &tmp3;
190 Fq2Elem* temp4 = &tmp4;
191
192 Fq4Square(temp1, temp2, a0, a3); // t00,t11 = sq(a0,a3)
193 Fq2Add(e0, a0, a0); // e0 = 3*t00 - 2*a0
194 Fq2Sub(e0, temp1, e0);
195 Fq2Add(e0, temp1, e0);
196 Fq2Add(e0, temp1, e0);
197 Fq2Add(e3, a3, a3); // e3 = 3*t11 - 2*a3
198 Fq2Add(e3, temp2, e3);
199 Fq2Add(e3, temp2, e3);
200 Fq2Add(e3, temp2, e3);
201
202 Fq4Square(temp1, temp2, a2, a5); // t02, t10 = sq(a2,a5)
203 Fq2MulXi(temp2, temp2);
204 Fq4Square(temp3, temp4, a1, a4); // t01, t12 = sq(a1,a4)
205
206 Fq2Add(e4, a4, a4);
207 Fq2Sub(e4, temp1, e4);
208 Fq2Add(e4, temp1, e4);
209 Fq2Add(e4, temp1, e4);
210 Fq2Add(e1, a1, a1);
211 Fq2Add(e1, temp2, e1);
212 Fq2Add(e1, temp2, e1);
213 Fq2Add(e1, temp2, e1);
214
215 Fq2Add(e2, a2, a2);
216 Fq2Sub(e2, temp3, e2);
217 Fq2Add(e2, temp3, e2);
218 Fq2Add(e2, temp3, e2);
219 Fq2Add(e5, a5, a5);
220 Fq2Add(e5, temp4, e5);
221 Fq2Add(e5, temp4, e5);
222 Fq2Add(e5, temp4, e5);
223 }
224
Fq12MulSpecial(Fq12Elem * result,Fq12Elem const * left,Fq12Elem const * right)225 void Fq12MulSpecial(Fq12Elem* result, Fq12Elem const* left,
226 Fq12Elem const* right) {
227 Fq2Elem T3;
228 Fq2Elem* t3 = &T3;
229 Fq2Elem const* b0 = &(right->z0.y0);
230 Fq2Elem const* b1 = &right->z1.y0;
231 Fq2Elem const* b3 = &right->z1.y1;
232 Fq6Elem T0;
233 Fq6Elem T1;
234 Fq6Elem T2;
235 Fq6Elem* t0 = &T0;
236 Fq6Elem* t1 = &T1;
237 Fq6Elem* t2 = &T2;
238 Fq6Elem const* a0 = &left->z0;
239 Fq6Elem const* a1 = &left->z1;
240 Fq6Elem* r0 = &result->z0;
241 Fq6Elem* r1 = &result->z1;
242
243 #if defined(DEBUG)
244 // validate algorithm precondition
245 if (!Fq2IsZero(&right->z0.y1) || !Fq2IsZero(&right->z0.y2) ||
246 !Fq2IsZero(&right->z1.y2)) {
247 memset(&result, 0xff, sizeof(result));
248 return;
249 }
250 #endif // defined(DEBUG)
251
252 Fq6Add(t0, a0, a1);
253 Fq2Add(t3, b0, b1);
254 Fq6MulScalar(t0, t0, t3);
255
256 Fq6MulScalar(t2, a1, b3);
257 Fq6MulV(t2, t2);
258
259 Fq6MulScalar(t1, a1, b1);
260 Fq6Sub(t0, t0, t1);
261 Fq6Add(t2, t2, t1);
262 Fq6MulV(t2, t2);
263
264 Fq6MulScalar(t1, a0, b0);
265 Fq6Add(t2, t2, t1);
266 Fq6Sub(t0, t0, t1);
267
268 Fq6MulScalar(t1, a0, b3);
269 Fq6MulV(t1, t1);
270 Fq6Add(r1, t1, t0);
271 Fq6Cp(r0, t2);
272 }
273
Fq12Cp(Fq12Elem * result,Fq12Elem const * in)274 void Fq12Cp(Fq12Elem* result, Fq12Elem const* in) {
275 Fq6Cp(&result->z0, &in->z0);
276 Fq6Cp(&result->z1, &in->z1);
277 }
278
Fq12Clear(Fq12Elem * result)279 void Fq12Clear(Fq12Elem* result) {
280 Fq6Clear(&result->z0);
281 Fq6Clear(&result->z1);
282 }
283