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 EFq2 math
17 /*! \file */
18
19 #include "epid/member/tiny/math/efq2.h"
20
21 #include "epid/member/tiny/math/fq.h"
22 #include "epid/member/tiny/math/fq2.h"
23 #include "epid/member/tiny/math/mathtypes.h"
24 #include "epid/member/tiny/math/vli.h"
25
EFq2CondSet(EccPointJacobiFq2 * result,EccPointJacobiFq2 const * true_val,EccPointJacobiFq2 const * false_val,int truth_val)26 static void EFq2CondSet(EccPointJacobiFq2* result,
27 EccPointJacobiFq2 const* true_val,
28 EccPointJacobiFq2 const* false_val, int truth_val) {
29 Fq2CondSet(&result->X, &true_val->X, &false_val->X, truth_val);
30 Fq2CondSet(&result->Y, &true_val->Y, &false_val->Y, truth_val);
31 Fq2CondSet(&result->Z, &true_val->Z, &false_val->Z, truth_val);
32 }
33
EFq2Cp(EccPointJacobiFq2 * result,EccPointJacobiFq2 const * in)34 static void EFq2Cp(EccPointJacobiFq2* result, EccPointJacobiFq2 const* in) {
35 Fq2Cp(&result->X, &in->X);
36 Fq2Cp(&result->Y, &in->Y);
37 Fq2Cp(&result->Z, &in->Z);
38 }
39
EFq2Inf(EccPointJacobiFq2 * result)40 static void EFq2Inf(EccPointJacobiFq2* result) {
41 Fq2Set(&result->X, 0);
42 Fq2Set(&result->Y, 1);
43 Fq2Set(&result->Z, 0);
44 }
45
EFq2IsInf(EccPointJacobiFq2 const * in)46 int EFq2IsInf(EccPointJacobiFq2 const* in) {
47 return Fq2IsZero(&in->X) && Fq2IsZero(&in->Z) && (!Fq2IsZero(&in->Y));
48 }
49
EFq2FromAffine(EccPointJacobiFq2 * result,EccPointFq2 const * in)50 void EFq2FromAffine(EccPointJacobiFq2* result, EccPointFq2 const* in) {
51 Fq2Cp(&result->X, &in->x);
52 Fq2Cp(&result->Y, &in->y);
53 Fq2Set(&result->Z, 1);
54 }
55
EFq2ToAffine(EccPointFq2 * result,EccPointJacobiFq2 const * in)56 int EFq2ToAffine(EccPointFq2* result, EccPointJacobiFq2 const* in) {
57 Fq2Elem inverted_z;
58 if (EFq2IsInf(in)) {
59 return 0;
60 }
61 Fq2Inv(&inverted_z, &in->Z);
62 Fq2Mul(&result->x, &in->X, &inverted_z);
63 Fq2Mul(&result->x, &result->x, &inverted_z);
64 Fq2Mul(&result->y, &in->Y, &inverted_z);
65 Fq2Mul(&result->y, &result->y, &inverted_z);
66 Fq2Mul(&result->y, &result->y, &inverted_z);
67 return 1;
68 }
69
EFq2Dbl(EccPointJacobiFq2 * result,EccPointJacobiFq2 const * in)70 void EFq2Dbl(EccPointJacobiFq2* result, EccPointJacobiFq2 const* in) {
71 Fq2Elem a;
72 Fq2Elem b;
73 // Z3 = 2Z1
74 Fq2Add(&(result->Z), &(in->Z), &(in->Z));
75 // Z3 = 2*Z1*Y1
76 Fq2Mul(&(result->Z), &(result->Z), &(in->Y));
77 // A = X1^2
78 Fq2Square(&a, &(in->X));
79 // B = 2(X1^2)
80 Fq2Add(&b, &a, &a);
81 // B = 3(X1^2)
82 Fq2Add(&b, &b, &a);
83 // A = Y1^2
84 Fq2Square(&a, &(in->Y));
85 // A = 2*(Y1^2)
86 Fq2Add(&a, &a, &a);
87 // Y3 = 4*(Y1^4)
88 Fq2Square(&(result->Y), &a);
89 // Y3 = 8*(Y1^4)
90 Fq2Add(&(result->Y), &(result->Y), &(result->Y));
91 // A = 4(Y1^2)
92 Fq2Add(&a, &a, &a);
93 // A = 4(Y1^2)*X1
94 Fq2Mul(&a, &a, &(in->X));
95 // X3 = B^2
96 Fq2Square(&(result->X), &b);
97 // X3 = (B^2) - A
98 Fq2Sub(&(result->X), &(result->X), &a);
99 // X3 = (B^2) - 2A
100 Fq2Sub(&(result->X), &(result->X), &a);
101 // A = A - X3
102 Fq2Sub(&a, &a, &(result->X));
103 // A = B*(A-X3)
104 Fq2Mul(&a, &a, &b);
105 // Y3 = B*(A-X3) - 8*(Y1^4)
106 Fq2Sub(&(result->Y), &a, &(result->Y));
107 }
108
EFq2Add(EccPointJacobiFq2 * result,EccPointJacobiFq2 const * left,EccPointJacobiFq2 const * right)109 void EFq2Add(EccPointJacobiFq2* result, EccPointJacobiFq2 const* left,
110 EccPointJacobiFq2 const* right) {
111 Fq2Elem A;
112 Fq2Elem B;
113 Fq2Elem C;
114 Fq2Elem D;
115 Fq2Elem W;
116 Fq2Elem V;
117
118 if (Fq2IsZero(&left->Z)) {
119 // If P = O, set R = Q and return
120 EFq2Cp(result, right);
121 return;
122 }
123 if (Fq2IsZero(&right->Z)) {
124 // If Q = O, set R = P and return.
125 EFq2Cp(result, left);
126 return;
127 }
128 // A = P.X * Q.Z^2
129 Fq2Square(&C, &right->Z);
130 Fq2Mul(&A, &left->X, &C);
131 // B = Q.X * P.Z^2
132 Fq2Square(&D, &left->Z);
133 Fq2Mul(&B, &right->X, &D);
134 // C = P.Y * Q.Z^3
135 Fq2Mul(&C, &right->Z, &C);
136 Fq2Mul(&C, &left->Y, &C);
137 // D = Q.Y * P.Z^3
138 Fq2Mul(&D, &left->Z, &D);
139 Fq2Mul(&D, &right->Y, &D);
140 // W = B - A
141 Fq2Sub(&W, &B, &A);
142 // V = D - C
143 Fq2Sub(&V, &D, &C);
144 if (Fq2IsZero(&W)) {
145 if (Fq2IsZero(&V)) {
146 EFq2Dbl(result, left);
147 return;
148 } else {
149 EFq2Inf(result);
150 return;
151 }
152 }
153 // R.Z = P.Z * Q.Z * W
154 Fq2Mul(&result->Z, &left->Z, &right->Z);
155 Fq2Mul(&result->Z, &result->Z, &W);
156 // R.X = V^2 - (A + B) * W^2
157 Fq2Square(&result->X, &V);
158 Fq2Add(&B, &A, &B);
159 // Before squaring W save (C * W) to use in compitation of R.Y
160 Fq2Mul(&C, &C, &W);
161 Fq2Square(&W, &W);
162 Fq2Mul(&B, &B, &W);
163 Fq2Sub(&result->X, &result->X, &B);
164 // R.Y = V * (A * W^2 - R.X) - C * W^3
165 Fq2Mul(&A, &A, &W);
166 Fq2Sub(&A, &A, &result->X);
167 Fq2Mul(&result->Y, &V, &A);
168 Fq2Mul(&C, &C, &W);
169 Fq2Sub(&result->Y, &result->Y, &C);
170 }
171
EFq2Neg(EccPointJacobiFq2 * result,EccPointJacobiFq2 const * in)172 void EFq2Neg(EccPointJacobiFq2* result, EccPointJacobiFq2 const* in) {
173 Fq2Cp(&result->X, &in->X);
174 Fq2Neg(&result->Y, &in->Y);
175 Fq2Cp(&result->Z, &in->Z);
176 }
177
EFq2MulSSCM(EccPointJacobiFq2 * result,EccPointJacobiFq2 const * left,FpElem const * right)178 void EFq2MulSSCM(EccPointJacobiFq2* result, EccPointJacobiFq2 const* left,
179 FpElem const* right) {
180 int position;
181 EccPointJacobiFq2 nv;
182 EccPointJacobiFq2 mv;
183 EFq2Inf(&nv);
184 EFq2Cp(&mv, left);
185 for (position = 32 * NUM_ECC_DIGITS - 1; position >= 0; position--) {
186 EFq2Dbl(&nv, &nv);
187 EFq2Add(&mv, left, &nv);
188 EFq2CondSet(&nv, &mv, &nv,
189 (int)(VliTestBit(&right->limbs, (uint32_t)position)));
190 }
191 EFq2Cp(result, &nv);
192 }
193
EFq2Eq(EccPointJacobiFq2 const * left,EccPointJacobiFq2 const * right)194 int EFq2Eq(EccPointJacobiFq2 const* left, EccPointJacobiFq2 const* right) {
195 Fq2Elem t1;
196 Fq2Elem t2;
197 Fq2Elem t3;
198 Fq2Elem t4;
199
200 if (EFq2IsInf(left) && EFq2IsInf(right)) {
201 return 1;
202 }
203 // if either left or right equals to inf return 0
204 if (EFq2IsInf(left) || EFq2IsInf(right)) {
205 return 0;
206 }
207 Fq2Square(&t1, &(left->Z));
208 Fq2Square(&t2, &(right->Z));
209 Fq2Mul(&t3, &t1, &(right->X));
210 Fq2Mul(&t4, &t2, &(left->X));
211 Fq2Mul(&t1, &t1, &(left->Z));
212 Fq2Mul(&t2, &t2, &(right->Z));
213 Fq2Mul(&t1, &t1, &(right->Y));
214 Fq2Mul(&t2, &t2, &(left->Y));
215 return Fq2Eq(&t1, &t2) && Fq2Eq(&t3, &t4);
216 }
217
EFq2OnCurve(EccPointFq2 const * in)218 int EFq2OnCurve(EccPointFq2 const* in) {
219 // test that Y^2 mod q == (X^3 + a*Z^4*X + b'*Z^6) mod q
220 // This simplifies to: Y^2 mod q == (X^3 + b') mod q
221 // since: Z = 1
222 // a = 0
223 // b = 3
224 Fq2Elem t1;
225 Fq2Elem t2;
226 FqElem three;
227 // Fq2xi
228 Fq2Elem bp = {{{{0x00000002, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
229 0x00000000, 0x00000000, 0x00000000}}},
230 {{{0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
231 0x00000000, 0x00000000, 0x00000000}}}};
232 Fq2Elem const* x = &in->x;
233 Fq2Elem const* y = &in->y;
234
235 // b' = b * inv(x1)
236 FqSet(&three, 3);
237 Fq2Inv(&bp, &bp);
238 Fq2MulScalar(&bp, &bp, &three);
239
240 // set t2 = X^3
241 Fq2Square(&t1, x);
242 Fq2Mul(&t2, x, &t1);
243 // set t2 = X^3 + b'
244 Fq2Add(&t2, &t2, &bp);
245
246 // set t1 = Y^2
247 Fq2Square(&t1, y);
248
249 // set t1 = Y^2 - (X^3 + b')
250 Fq2Sub(&t1, &t1, &t2);
251 // return if t1 is zero
252 return Fq2IsZero(&t1);
253 }
254