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 EFq math
17 /*! \file */
18 
19 #include "epid/member/tiny/math/efq.h"
20 #include "epid/member/tiny/math/fq.h"
21 #include "epid/member/tiny/math/hashwrap.h"
22 #include "epid/member/tiny/math/mathtypes.h"
23 #include "epid/member/tiny/math/serialize.h"
24 #include "epid/member/tiny/math/vli.h"
25 #include "epid/member/tiny/stdlib/tiny_stdlib.h"
26 
EFqMakePoint(EccPointFq * output,FqElem * in)27 static int EFqMakePoint(EccPointFq* output, FqElem* in) {
28   FqElem fq_sqrt = {0};
29   FqElem fq_tmp = {0};
30   FqSet(&fq_tmp, 3);
31   FqSquare(&fq_sqrt, in);
32   FqMul(&fq_sqrt, &fq_sqrt, in);
33   FqAdd(&fq_sqrt, &fq_sqrt, &fq_tmp);
34   if (!FqSqrt(&output->y, &fq_sqrt)) {
35     return 0;
36   }
37   FqCp(&output->x, in);
38 
39   return 1;
40 }
41 
EFqMulSSCM(EccPointJacobiFq * result,EccPointJacobiFq const * base,FpElem const * exp)42 void EFqMulSSCM(EccPointJacobiFq* result, EccPointJacobiFq const* base,
43                 FpElem const* exp) {
44   EccPointJacobiFq efqj_1;
45   EccPointJacobiFq efqj_2;
46 
47   uint32_t position;
48   EFqInf(&efqj_1);
49   EFqJCp(&efqj_2, base);
50   for (position = 32 * NUM_ECC_DIGITS; position > 0; --position) {
51     EFqDbl(&efqj_1, &efqj_1);
52     EFqAdd(&efqj_2, base, &efqj_1);
53     EFqCondSet(&efqj_1, &efqj_2, &efqj_1,
54                VliTestBit(&(exp->limbs), position - 1));
55   }
56   EFqJCp(result, &efqj_1);
57 }
58 
EFqAffineExp(EccPointFq * result,EccPointFq const * base,FpElem const * exp)59 int EFqAffineExp(EccPointFq* result, EccPointFq const* base,
60                  FpElem const* exp) {
61   EccPointJacobiFq efqj;
62   EFqFromAffine(&efqj, base);
63   EFqMulSSCM(&efqj, &efqj, exp);
64   return EFqToAffine(result, &efqj);
65 }
66 
EFqAffineMultiExp(EccPointFq * result,EccPointFq const * base0,FpElem const * exp0,EccPointFq const * base1,FpElem const * exp1)67 int EFqAffineMultiExp(EccPointFq* result, EccPointFq const* base0,
68                       FpElem const* exp0, EccPointFq const* base1,
69                       FpElem const* exp1) {
70   EccPointJacobiFq efqj_base0;
71   EccPointJacobiFq efqj_base1;
72   EFqFromAffine(&efqj_base0, base0);
73   EFqFromAffine(&efqj_base1, base1);
74   EFqMultiExp(&efqj_base0, &efqj_base0, exp0, &efqj_base1, exp1);
75   return EFqToAffine(result, &efqj_base0);
76 }
77 
EFqMultiExp(EccPointJacobiFq * result,EccPointJacobiFq const * base0,FpElem const * exp0,EccPointJacobiFq const * base1,FpElem const * exp1)78 void EFqMultiExp(EccPointJacobiFq* result, EccPointJacobiFq const* base0,
79                  FpElem const* exp0, EccPointJacobiFq const* base1,
80                  FpElem const* exp1) {
81   EccPointJacobiFq efqj_base0;
82   EccPointJacobiFq efqj_a;
83   EccPointJacobiFq efqj_b;
84   int i, j;
85 
86   EFqAdd(&efqj_base0, base0, base1);
87   EFqInf(&efqj_a);
88   for (i = NUM_ECC_DIGITS - 1; i >= 0; i--) {
89     for (j = 31; j >= 0; j--) {
90       EFqAdd(&efqj_a, &efqj_a, &efqj_a);
91       EFqInf(&efqj_b);
92       EFqJCp(&efqj_b, base0);
93 
94       EFqCondSet(&efqj_b, base1, &efqj_b,
95                  (int)((exp1->limbs.word[i] >> j) & (0x1)));
96 
97       EFqCondSet(&efqj_b, &efqj_base0, &efqj_b,
98                  (int)((exp0->limbs.word[i] >> j) & (exp1->limbs.word[i] >> j) &
99                        (0x1)));
100 
101       EFqAdd(&efqj_b, &efqj_a, &efqj_b);
102 
103       EFqCondSet(&efqj_a, &efqj_b, &efqj_a, (int)(((exp0->limbs.word[i] >> j) |
104                                                    (exp1->limbs.word[i] >> j)) &
105                                                   (0x1)));
106     }
107   }
108   EFqJCp(result, &efqj_a);
109 }
110 
EFqAffineAdd(EccPointFq * result,EccPointFq const * left,EccPointFq const * right)111 int EFqAffineAdd(EccPointFq* result, EccPointFq const* left,
112                  EccPointFq const* right) {
113   EccPointJacobiFq efqj_a;
114   EccPointJacobiFq efqj_b;
115   if (EFqEqAffine(left, right)) return EFqAffineDbl(result, left);
116 
117   EFqFromAffine(&efqj_a, left);
118   EFqFromAffine(&efqj_b, right);
119   EFqAdd(&efqj_a, &efqj_a, &efqj_b);
120 
121   return EFqToAffine(result, &efqj_a);
122 }
123 
EFqAffineDbl(EccPointFq * result,EccPointFq const * in)124 int EFqAffineDbl(EccPointFq* result, EccPointFq const* in) {
125   EccPointJacobiFq efqj_a;
126   EFqFromAffine(&efqj_a, in);
127   EFqAdd(&efqj_a, &efqj_a, &efqj_a);
128 
129   return EFqToAffine(result, &efqj_a);
130 }
131 
EFqDbl(EccPointJacobiFq * result,EccPointJacobiFq const * in)132 void EFqDbl(EccPointJacobiFq* result, EccPointJacobiFq const* in) {
133   FqElem fq_a;
134   FqElem fq_b;
135 
136   FqAdd(&(result->Z), &(in->Z), &(in->Z));
137   FqMul(&(result->Z), &(result->Z), &(in->Y));
138   FqSquare(&fq_a, &(in->X));
139   FqAdd(&fq_b, &fq_a, &fq_a);
140   FqAdd(&fq_b, &fq_b, &fq_a);
141   FqSquare(&fq_a, &(in->Y));
142   FqAdd(&fq_a, &fq_a, &fq_a);
143   FqSquare(&(result->Y), &fq_a);
144   FqAdd(&(result->Y), &(result->Y), &(result->Y));
145   FqAdd(&fq_a, &fq_a, &fq_a);
146   FqMul(&fq_a, &fq_a, &(in->X));
147   FqSquare(&(result->X), &fq_b);
148   FqSub(&(result->X), &(result->X), &fq_a);
149   FqSub(&(result->X), &(result->X), &fq_a);
150   FqSub(&fq_a, &fq_a, &(result->X));
151   FqMul(&fq_a, &fq_a, &fq_b);
152   FqSub(&(result->Y), &fq_a, &(result->Y));
153 }
154 
EFqAdd(EccPointJacobiFq * result,EccPointJacobiFq const * left,EccPointJacobiFq const * right)155 void EFqAdd(EccPointJacobiFq* result, EccPointJacobiFq const* left,
156             EccPointJacobiFq const* right) {
157   FqElem fq0;
158   FqElem fq1;
159   FqElem fq2;
160   FqElem fq3;
161   FqElem fq4;
162   FqElem fq5;
163 
164   if (FqIsZero(&(left->Z))) {
165     EFqJCp(result, right);
166     return;
167   }
168   if (FqIsZero(&(right->Z))) {
169     EFqJCp(result, left);
170     return;
171   }
172 
173   FqSquare(&fq2, &(right->Z));
174   FqSquare(&fq3, &(left->Z));
175   // P.X * Q.Z^2
176   FqMul(&fq0, &(left->X), &fq2);
177   // Q.X * P.Z^2
178   FqMul(&fq1, &(right->X), &fq3);
179   // Q.X*P.Z^2 - P*X+Q*Z^2
180   FqSub(&fq5, &fq1, &fq0);
181   FqMul(&fq3, &(right->Y), &fq3);
182   // P.Y * Q.Z^3
183   FqMul(&fq3, &(left->Z), &fq3);
184   FqMul(&fq2, &(left->Y), &fq2);
185   // Q.Y * P.Z^3
186   FqMul(&fq2, &(right->Z), &fq2);
187   FqSub(&fq4, &fq3, &fq2);
188 
189   if (FqIsZero(&fq5)) {
190     if (FqIsZero(&fq4)) {
191       EFqDbl(result, left);
192       return;
193     } else {
194       EFqInf(result);
195       return;
196     }
197   }
198   FqMul(&(result->Z), &(left->Z), &(right->Z));
199   FqMul(&(result->Z), &(result->Z), &fq5);
200   // Q.X*P.Z^2 + P*X+Q*Z^2
201   FqAdd(&fq1, &fq0, &fq1);
202   FqMul(&fq2, &fq2, &fq5);
203   FqSquare(&fq5, &fq5);
204   FqMul(&fq1, &fq1, &fq5);
205   FqSquare(&(result->X), &fq4);
206   FqSub(&(result->X), &(result->X), &fq1);
207   FqMul(&fq2, &fq2, &fq5);
208   FqMul(&fq0, &fq0, &fq5);
209   FqSub(&fq0, &fq0, &(result->X));
210   FqMul(&(result->Y), &fq4, &fq0);
211   FqSub(&(result->Y), &(result->Y), &fq2);
212 }
213 
EFqRand(EccPointFq * result,BitSupplier rnd_func,void * rnd_param)214 int EFqRand(EccPointFq* result, BitSupplier rnd_func, void* rnd_param) {
215   FqElem fq;
216   do {
217     if (!FqRand(&fq, rnd_func, rnd_param)) {
218       return 0;
219     }
220   } while (!EFqMakePoint(result, &fq));
221   return 1;
222 }
223 
EFqSet(EccPointJacobiFq * result,FqElem const * x,FqElem const * y)224 void EFqSet(EccPointJacobiFq* result, FqElem const* x, FqElem const* y) {
225   FqCp(&result->X, x);
226   FqCp(&result->Y, y);
227   FqSet(&result->Z, 1);
228 }
229 
EFqIsInf(EccPointJacobiFq const * in)230 int EFqIsInf(EccPointJacobiFq const* in) {
231   return FqIsZero(&in->X) && FqIsZero(&in->Z) && (!FqIsZero(&in->Y));
232 }
233 
EFqFromAffine(EccPointJacobiFq * result,EccPointFq const * in)234 void EFqFromAffine(EccPointJacobiFq* result, EccPointFq const* in) {
235   FqCp(&result->X, &in->x);
236   FqCp(&result->Y, &in->y);
237   FqSet(&result->Z, 1);
238 }
239 
EFqToAffine(EccPointFq * result,EccPointJacobiFq const * in)240 int EFqToAffine(EccPointFq* result, EccPointJacobiFq const* in) {
241   FqElem fq_inv;
242   if (EFqIsInf(in)) {
243     return 0;
244   }
245   FqInv(&fq_inv, &in->Z);
246   FqMul(&result->x, &in->X, &fq_inv);
247   FqMul(&result->x, &result->x, &fq_inv);
248   FqMul(&result->y, &in->Y, &fq_inv);
249   FqMul(&result->y, &result->y, &fq_inv);
250   FqMul(&result->y, &result->y, &fq_inv);
251 
252   return 1;
253 }
254 
EFqNeg(EccPointJacobiFq * result,EccPointJacobiFq const * in)255 void EFqNeg(EccPointJacobiFq* result, EccPointJacobiFq const* in) {
256   FqCp(&result->X, &in->X);
257   FqNeg(&result->Y, &in->Y);
258   FqCp(&result->Z, &in->Z);
259 }
260 
EFqEq(EccPointJacobiFq const * left,EccPointJacobiFq const * right)261 int EFqEq(EccPointJacobiFq const* left, EccPointJacobiFq const* right) {
262   FqElem fq1;
263   FqElem fq2;
264   FqElem fq3;
265   FqElem fq4;
266   if (EFqIsInf(left) && EFqIsInf(right)) {
267     return 1;
268   }
269   if (EFqIsInf(left) || EFqIsInf(right)) {
270     return 0;
271   }
272   // Z1^2
273   FqSquare(&fq1, &left->Z);
274   // Z2^2
275   FqSquare(&fq2, &right->Z);
276   // (Z1^2)*X2
277   FqMul(&fq3, &fq1, &right->X);
278   // (Z2^2)*X1
279   FqMul(&fq4, &fq2, &left->X);
280   // Z1^3
281   FqMul(&fq1, &fq1, &left->Z);
282   // Z2^3
283   FqMul(&fq2, &fq2, &right->Z);
284   // (Z1^3)*Y2
285   FqMul(&fq1, &fq1, &right->Y);
286   // (Z2^3)*Y1
287   FqMul(&fq2, &fq2, &left->Y);
288   // (Z1^2)*X2 == (Z2^2)*X1  &&  (Z1^3)*Y2 == (Z2^3)*Y1
289   return FqEq(&fq1, &fq2) && FqEq(&fq3, &fq4);
290 }
291 
EFqHash(EccPointFq * result,unsigned char const * msg,size_t len,HashAlg hashalg)292 int EFqHash(EccPointFq* result, unsigned char const* msg, size_t len,
293             HashAlg hashalg) {
294   tiny_sha hash_context;
295   FqElem three;
296   FqElem tmp;
297   uint32_t hash_salt = 0;
298   uint32_t buf = 0;
299   sha_digest hash_buf;
300   // 1/q in Fq
301   FqElem montgomery_r = {
302       0x512ccfed, 0x2cd6d224, 0xed67f57d, 0xf3239a04,
303       0x118e5b60, 0xb91a0da1, 0x00030f32, 0,
304   };
305   if ((kSha512 != hashalg) && (kSha256 != hashalg)) {
306     return 0;
307   }
308   FqSet(&three, 3);
309 
310   for (hash_salt = 0; hash_salt < 0xFFFFFFFF; ++hash_salt) {
311     tinysha_init(hashalg, &hash_context);
312 
313     Uint32Serialize((OctStr32*)&buf, hash_salt);
314     tinysha_update(&hash_context, &buf, sizeof(buf));
315     tinysha_update(&hash_context, msg, len);
316 
317     tinysha_final(hash_buf.digest, &hash_context);
318 
319     FqFromHash(&result->x, hash_buf.digest, tinysha_digest_size(&hash_context));
320     FqSquare(&tmp, &result->x);
321     FqMul(&tmp, &tmp, &result->x);
322     FqAdd(&tmp, &tmp, &three);
323     if (FqSqrt(&result->y, &tmp)) {
324       FqNeg(&tmp, &result->y);
325       // Verify and Non-tiny member use montgomery representation to determine
326       // if negation is needed: this is to be compatible with them
327       FqMul(&montgomery_r, &result->y, &montgomery_r);
328       FqCondSet(&result->y, &tmp, &result->y, montgomery_r.limbs.word[0] & 1);
329       return 1;
330     }
331   }
332   return 0;
333 }
334 
EFqCp(EccPointFq * result,EccPointFq const * in)335 void EFqCp(EccPointFq* result, EccPointFq const* in) {
336   FqCp(&result->x, &in->x);
337   FqCp(&result->y, &in->y);
338 }
339 
EFqEqAffine(EccPointFq const * left,EccPointFq const * right)340 int EFqEqAffine(EccPointFq const* left, EccPointFq const* right) {
341   return FqEq(&left->x, &right->x) && FqEq(&left->y, &right->y);
342 }
343 
EFqCondSet(EccPointJacobiFq * result,EccPointJacobiFq const * true_val,EccPointJacobiFq const * false_val,int truth_val)344 void EFqCondSet(EccPointJacobiFq* result, EccPointJacobiFq const* true_val,
345                 EccPointJacobiFq const* false_val, int truth_val) {
346   FqCondSet(&result->X, &true_val->X, &false_val->X, truth_val);
347   FqCondSet(&result->Y, &true_val->Y, &false_val->Y, truth_val);
348   FqCondSet(&result->Z, &true_val->Z, &false_val->Z, truth_val);
349 }
350 
EFqJCp(EccPointJacobiFq * result,EccPointJacobiFq const * in)351 void EFqJCp(EccPointJacobiFq* result, EccPointJacobiFq const* in) {
352   FqCp(&result->X, &in->X);
353   FqCp(&result->Y, &in->Y);
354   FqCp(&result->Z, &in->Z);
355 }
356 
EFqInf(EccPointJacobiFq * result)357 void EFqInf(EccPointJacobiFq* result) {
358   FqSet(&result->X, 0);
359   FqSet(&result->Y, 1);
360   FqSet(&result->Z, 0);
361 }
362 
EFqOnCurve(EccPointFq const * in)363 int EFqOnCurve(EccPointFq const* in) {
364   // test that Y^2 mod q == (X^3 + a*Z^4*X + b*Z^6) mod q
365   // This simplifies to: Y^2 mod q == (X^3 + 3) mod q
366   //      since: Z = 1
367   //             a = 0
368   //             b = 3
369   FqElem t1;
370   FqElem t2;
371   FqSquare(&t1, &in->x);
372   FqMul(&t2, &in->x, &t1);
373   FqSquare(&t1, &in->y);
374   FqSub(&t1, &t1, &t2);
375   t1.limbs.word[0] -= 3;  // check equal to curve b
376                           // this operation will not always
377                           // result in the same value as T1 - 3
378                           // however it will always result in a correct
379                           // value for the zero check below
380   return FqIsZero(&t1);
381 }
382 
EFqJOnCurve(EccPointJacobiFq const * in)383 int EFqJOnCurve(EccPointJacobiFq const* in) {
384   FqElem fq1;
385   FqElem fq2;
386 
387   FqSquare(&fq1, &in->Z);
388   FqSquare(&fq2, &fq1);
389   FqMul(&fq2, &fq2, &fq1);  // T2 = Z^6
390   FqAdd(&fq1, &fq2, &fq2);
391   FqAdd(&fq1, &fq1, &fq2);  // T1 = 3 * Z^6
392   FqSquare(&fq2, &in->X);
393   FqMul(&fq2, &fq2, &in->X);  // T2 = X^3
394   FqAdd(&fq1, &fq1, &fq2);    // T1 = X^3 + 3 Z^6
395   FqSquare(&fq2, &in->Y);
396   FqMul(&fq1, &fq1, &in->Z);
397   FqMul(&fq2, &fq2, &in->Z);
398   return FqEq(&fq1, &fq2);  // check Y^2 = X^3 + 3 Z^6
399 }
400 
EFqJRand(EccPointJacobiFq * result,BitSupplier rnd_func,void * rnd_param)401 int EFqJRand(EccPointJacobiFq* result, BitSupplier rnd_func, void* rnd_param) {
402   FqElem fq;
403   do {
404     if (!FqRand(&fq, rnd_func, rnd_param)) {
405       return 0;
406     }
407   } while (!EFqMakePoint((EccPointFq*)result, &fq));
408 
409   FqSet(&result->Z, 1);
410 
411   return 1;
412 }
413