1
2 /***************************************************************************
3 *
4 Copyright 2012 CertiVox IOM Ltd. *
5 *
6 This file is part of CertiVox MIRACL Crypto SDK. *
7 *
8 The CertiVox MIRACL Crypto SDK provides developers with an *
9 extensive and efficient set of cryptographic functions. *
10 For further information about its features and functionalities please *
11 refer to http://www.certivox.com *
12 *
13 * The CertiVox MIRACL Crypto SDK is free software: you can *
14 redistribute it and/or modify it under the terms of the *
15 GNU Affero General Public License as published by the *
16 Free Software Foundation, either version 3 of the License, *
17 or (at your option) any later version. *
18 *
19 * The CertiVox MIRACL Crypto SDK is distributed in the hope *
20 that it will be useful, but WITHOUT ANY WARRANTY; without even the *
21 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *
22 See the GNU Affero General Public License for more details. *
23 *
24 * You should have received a copy of the GNU Affero General Public *
25 License along with CertiVox MIRACL Crypto SDK. *
26 If not, see <http://www.gnu.org/licenses/>. *
27 *
28 You can be released from the requirements of the license by purchasing *
29 a commercial license. Buying such a license is mandatory as soon as you *
30 develop commercial activities involving the CertiVox MIRACL Crypto SDK *
31 without disclosing the source code of your own applications, or shipping *
32 the CertiVox MIRACL Crypto SDK with a closed source product. *
33 *
34 ***************************************************************************/
35 /*
36 * MIRACL F_p^2 support functions
37 * mrzzn2.c
38 */
39
40 #include <stdlib.h>
41 #include "miracl.h"
42
43 #ifdef MR_COUNT_OPS
44 extern int fpmq,fpsq,fpaq;
45 #endif
46
zzn2_iszero(zzn2 * x)47 BOOL zzn2_iszero(zzn2 *x)
48 {
49 if (size(x->a)==0 && size(x->b)==0) return TRUE;
50 return FALSE;
51 }
52
zzn2_isunity(_MIPD_ zzn2 * x)53 BOOL zzn2_isunity(_MIPD_ zzn2 *x)
54 {
55 #ifdef MR_OS_THREADS
56 miracl *mr_mip=get_mip();
57 #endif
58 if (mr_mip->ERNUM || size(x->b)!=0) return FALSE;
59
60 if (compare(x->a,mr_mip->one)==0) return TRUE;
61 return FALSE;
62
63 }
64
zzn2_compare(zzn2 * x,zzn2 * y)65 BOOL zzn2_compare(zzn2 *x,zzn2 *y)
66 {
67 if (mr_compare(x->a,y->a)==0 && mr_compare(x->b,y->b)==0) return TRUE;
68 return FALSE;
69 }
70
zzn2_from_int(_MIPD_ int i,zzn2 * w)71 void zzn2_from_int(_MIPD_ int i,zzn2 *w)
72 {
73 #ifdef MR_OS_THREADS
74 miracl *mr_mip=get_mip();
75 #endif
76 if (mr_mip->ERNUM) return;
77
78 MR_IN(156)
79 if (i==1)
80 {
81 copy(mr_mip->one,w->a);
82 }
83 else
84 {
85 convert(_MIPP_ i,mr_mip->w1);
86 nres(_MIPP_ mr_mip->w1,w->a);
87 }
88 zero(w->b);
89 MR_OUT
90 }
91
zzn2_from_ints(_MIPD_ int i,int j,zzn2 * w)92 void zzn2_from_ints(_MIPD_ int i,int j,zzn2 *w)
93 {
94 #ifdef MR_OS_THREADS
95 miracl *mr_mip=get_mip();
96 #endif
97 if (mr_mip->ERNUM) return;
98
99 MR_IN(168)
100 convert(_MIPP_ i,mr_mip->w1);
101 nres(_MIPP_ mr_mip->w1,w->a);
102 convert(_MIPP_ j,mr_mip->w1);
103 nres(_MIPP_ mr_mip->w1,w->b);
104
105 MR_OUT
106 }
107
zzn2_from_zzns(big x,big y,zzn2 * w)108 void zzn2_from_zzns(big x,big y,zzn2 *w)
109 {
110 copy(x,w->a);
111 copy(y,w->b);
112 }
113
zzn2_from_bigs(_MIPD_ big x,big y,zzn2 * w)114 void zzn2_from_bigs(_MIPD_ big x,big y, zzn2 *w)
115 {
116 #ifdef MR_OS_THREADS
117 miracl *mr_mip=get_mip();
118 #endif
119 if (mr_mip->ERNUM) return;
120
121 MR_IN(166)
122 nres(_MIPP_ x,w->a);
123 nres(_MIPP_ y,w->b);
124 MR_OUT
125 }
126
zzn2_from_zzn(big x,zzn2 * w)127 void zzn2_from_zzn(big x,zzn2 *w)
128 {
129 copy(x,w->a);
130 zero(w->b);
131 }
132
zzn2_from_big(_MIPD_ big x,zzn2 * w)133 void zzn2_from_big(_MIPD_ big x, zzn2 *w)
134 {
135 #ifdef MR_OS_THREADS
136 miracl *mr_mip=get_mip();
137 #endif
138 if (mr_mip->ERNUM) return;
139
140 MR_IN(167)
141 nres(_MIPP_ x,w->a);
142 zero(w->b);
143 MR_OUT
144 }
145
zzn2_copy(zzn2 * x,zzn2 * w)146 void zzn2_copy(zzn2 *x,zzn2 *w)
147 {
148 if (x==w) return;
149 copy(x->a,w->a);
150 copy(x->b,w->b);
151 }
152
zzn2_zero(zzn2 * w)153 void zzn2_zero(zzn2 *w)
154 {
155 zero(w->a);
156 zero(w->b);
157 }
158
zzn2_negate(_MIPD_ zzn2 * x,zzn2 * w)159 void zzn2_negate(_MIPD_ zzn2 *x,zzn2 *w)
160 {
161 #ifdef MR_OS_THREADS
162 miracl *mr_mip=get_mip();
163 #endif
164 if (mr_mip->ERNUM) return;
165 MR_IN(157)
166 zzn2_copy(x,w);
167 nres_negate(_MIPP_ w->a,w->a);
168 nres_negate(_MIPP_ w->b,w->b);
169 MR_OUT
170 }
171
zzn2_conj(_MIPD_ zzn2 * x,zzn2 * w)172 void zzn2_conj(_MIPD_ zzn2 *x,zzn2 *w)
173 {
174 #ifdef MR_OS_THREADS
175 miracl *mr_mip=get_mip();
176 #endif
177 MR_IN(158)
178 if (mr_mip->ERNUM) return;
179 zzn2_copy(x,w);
180 nres_negate(_MIPP_ w->b,w->b);
181 MR_OUT
182 }
183
zzn2_add(_MIPD_ zzn2 * x,zzn2 * y,zzn2 * w)184 void zzn2_add(_MIPD_ zzn2 *x,zzn2 *y,zzn2 *w)
185 {
186 #ifdef MR_OS_THREADS
187 miracl *mr_mip=get_mip();
188 #endif
189 if (mr_mip->ERNUM) return;
190 #ifdef MR_COUNT_OPS
191 fpaq++;
192 #endif
193 MR_IN(159)
194 nres_modadd(_MIPP_ x->a,y->a,w->a);
195 nres_modadd(_MIPP_ x->b,y->b,w->b);
196 MR_OUT
197 }
198
zzn2_sadd(_MIPD_ zzn2 * x,big y,zzn2 * w)199 void zzn2_sadd(_MIPD_ zzn2 *x,big y,zzn2 *w)
200 {
201 #ifdef MR_OS_THREADS
202 miracl *mr_mip=get_mip();
203 #endif
204 if (mr_mip->ERNUM) return;
205 MR_IN(169)
206 nres_modadd(_MIPP_ x->a,y,w->a);
207 MR_OUT
208 }
209
zzn2_sub(_MIPD_ zzn2 * x,zzn2 * y,zzn2 * w)210 void zzn2_sub(_MIPD_ zzn2 *x,zzn2 *y,zzn2 *w)
211 {
212 #ifdef MR_OS_THREADS
213 miracl *mr_mip=get_mip();
214 #endif
215 if (mr_mip->ERNUM) return;
216 #ifdef MR_COUNT_OPS
217 fpaq++;
218 #endif
219 MR_IN(160)
220 nres_modsub(_MIPP_ x->a,y->a,w->a);
221 nres_modsub(_MIPP_ x->b,y->b,w->b);
222 MR_OUT
223 }
224
zzn2_ssub(_MIPD_ zzn2 * x,big y,zzn2 * w)225 void zzn2_ssub(_MIPD_ zzn2 *x,big y,zzn2 *w)
226 {
227 #ifdef MR_OS_THREADS
228 miracl *mr_mip=get_mip();
229 #endif
230 if (mr_mip->ERNUM) return;
231
232 MR_IN(170)
233 nres_modsub(_MIPP_ x->a,y,w->a);
234 MR_OUT
235 }
236
zzn2_smul(_MIPD_ zzn2 * x,big y,zzn2 * w)237 void zzn2_smul(_MIPD_ zzn2 *x,big y,zzn2 *w)
238 {
239 #ifdef MR_OS_THREADS
240 miracl *mr_mip=get_mip();
241 #endif
242 if (mr_mip->ERNUM) return;
243 MR_IN(161)
244 if (size(x->a)!=0) nres_modmult(_MIPP_ x->a,y,w->a);
245 else zero(w->a);
246 if (size(x->b)!=0) nres_modmult(_MIPP_ x->b,y,w->b);
247 else zero(w->b);
248 MR_OUT
249 }
250
zzn2_imul(_MIPD_ zzn2 * x,int y,zzn2 * w)251 void zzn2_imul(_MIPD_ zzn2 *x,int y,zzn2 *w)
252 {
253 #ifdef MR_OS_THREADS
254 miracl *mr_mip=get_mip();
255 #endif
256 if (mr_mip->ERNUM) return;
257 MR_IN(152)
258 if (size(x->a)!=0) nres_premult(_MIPP_ x->a,y,w->a);
259 else zero(w->a);
260 if (size(x->b)!=0) nres_premult(_MIPP_ x->b,y,w->b);
261 else zero(w->b);
262 MR_OUT
263 }
264
zzn2_sqr(_MIPD_ zzn2 * x,zzn2 * w)265 void zzn2_sqr(_MIPD_ zzn2 *x,zzn2 *w)
266 {
267 #ifdef MR_OS_THREADS
268 miracl *mr_mip=get_mip();
269 #endif
270
271 if (mr_mip->ERNUM) return;
272 #ifdef MR_COUNT_OPS
273 fpsq++;
274 #endif
275 MR_IN(210)
276
277 nres_complex(_MIPP_ x->a,x->b,w->a,w->b);
278
279 MR_OUT
280 }
281
zzn2_mul(_MIPD_ zzn2 * x,zzn2 * y,zzn2 * w)282 void zzn2_mul(_MIPD_ zzn2 *x,zzn2 *y,zzn2 *w)
283 {
284 #ifdef MR_OS_THREADS
285 miracl *mr_mip=get_mip();
286 #endif
287
288 if (mr_mip->ERNUM) return;
289 if (x==y) {zzn2_sqr(_MIPP_ x,w); return; }
290 MR_IN(162)
291 /* Uses w1, w2, and w5 */
292
293 if (zzn2_iszero(x) || zzn2_iszero(y)) zzn2_zero(w);
294 else
295 {
296 #ifdef MR_COUNT_OPS
297 fpmq++;
298 #endif
299 #ifndef MR_NO_LAZY_REDUCTION
300 if (x->a->len!=0 && x->b->len!=0 && y->a->len!=0 && y->b->len!=0)
301 nres_lazy(_MIPP_ x->a,x->b,y->a,y->b,w->a,w->b);
302 else
303 {
304 #endif
305 nres_modmult(_MIPP_ x->a,y->a,mr_mip->w1);
306 nres_modmult(_MIPP_ x->b,y->b,mr_mip->w2);
307 nres_modadd(_MIPP_ x->a,x->b,mr_mip->w5);
308 nres_modadd(_MIPP_ y->a,y->b,w->b);
309 nres_modmult(_MIPP_ w->b,mr_mip->w5,w->b);
310 nres_modsub(_MIPP_ w->b,mr_mip->w1,w->b);
311 nres_modsub(_MIPP_ w->b,mr_mip->w2,w->b);
312 nres_modsub(_MIPP_ mr_mip->w1,mr_mip->w2,w->a);
313 if (mr_mip->qnr==-2)
314 nres_modsub(_MIPP_ w->a,mr_mip->w2,w->a);
315 #ifndef MR_NO_LAZY_REDUCTION
316 }
317 #endif
318 }
319 MR_OUT
320 }
321
322
323 /*
324 void zzn2_print(_MIPD_ char *label, zzn2 *x)
325 {
326 char s1[1024], s2[1024];
327 big a, b;
328
329 #ifdef MR_STATIC
330 char mem_big[MR_BIG_RESERVE(2)];
331 memset(mem_big, 0, MR_BIG_RESERVE(2));
332 a=mirvar_mem(_MIPP_ mem_big,0);
333 b=mirvar_mem(_MIPP_ mem_big,1);
334 #else
335 a = mirvar(_MIPP_ 0);
336 b = mirvar(_MIPP_ 0);
337 #endif
338 redc(_MIPP_ x->a, a); otstr(_MIPP_ a, s1);
339 redc(_MIPP_ x->b, b); otstr(_MIPP_ b, s2);
340
341 printf("%s: [%s,%s]\n", label, s1, s2);
342 #ifndef MR_STATIC
343 mr_free(a); mr_free(b);
344 #endif
345 }
346
347 static void nres_print(_MIPD_ char *label, big x)
348 {
349 char s[1024];
350 big a;
351 #ifdef MR_STATIC
352 char mem_big[MR_BIG_RESERVE(1)];
353 memset(mem_big, 0, MR_BIG_RESERVE(1));
354 a=mirvar_mem(_MIPP_ mem_big,0);
355 #else
356 a = mirvar(_MIPP_ 0);
357 #endif
358
359 redc(_MIPP_ x, a);
360 otstr(_MIPP_ a, s);
361
362 printf("%s: %s\n", label, s);
363 #ifndef MR_STATIC
364 mr_free(a);
365 #endif
366 }
367
368 */
zzn2_inv(_MIPD_ zzn2 * w)369 void zzn2_inv(_MIPD_ zzn2 *w)
370 {
371 #ifdef MR_OS_THREADS
372 miracl *mr_mip=get_mip();
373 #endif
374 if (mr_mip->ERNUM) return;
375 MR_IN(163)
376 nres_modmult(_MIPP_ w->a,w->a,mr_mip->w1);
377 nres_modmult(_MIPP_ w->b,w->b,mr_mip->w2);
378 nres_modadd(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w1);
379
380 if (mr_mip->qnr==-2)
381 nres_modadd(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w1);
382 redc(_MIPP_ mr_mip->w1,mr_mip->w6);
383
384 invmodp(_MIPP_ mr_mip->w6,mr_mip->modulus,mr_mip->w6);
385
386 nres(_MIPP_ mr_mip->w6,mr_mip->w6);
387
388 nres_modmult(_MIPP_ w->a,mr_mip->w6,w->a);
389 nres_negate(_MIPP_ mr_mip->w6,mr_mip->w6);
390 nres_modmult(_MIPP_ w->b,mr_mip->w6,w->b);
391 MR_OUT
392 }
393
394 /* divide zzn2 by 2 */
395
zzn2_div2(_MIPD_ zzn2 * w)396 void zzn2_div2(_MIPD_ zzn2 *w)
397 {
398 #ifdef MR_OS_THREADS
399 miracl *mr_mip=get_mip();
400 #endif
401 if (mr_mip->ERNUM) return;
402 MR_IN(173)
403
404 nres_div2(_MIPP_ w->a,w->a);
405 nres_div2(_MIPP_ w->b,w->b);
406
407 MR_OUT
408 }
409
410 /* divide zzn2 by 3 */
411
zzn2_div3(_MIPD_ zzn2 * w)412 void zzn2_div3(_MIPD_ zzn2 *w)
413 {
414 #ifdef MR_OS_THREADS
415 miracl *mr_mip=get_mip();
416 #endif
417 if (mr_mip->ERNUM) return;
418 MR_IN(200)
419
420 nres_div3(_MIPP_ w->a,w->a);
421 nres_div3(_MIPP_ w->b,w->b);
422
423 MR_OUT
424 }
425
426 /* divide zzn2 by 5 */
427
zzn2_div5(_MIPD_ zzn2 * w)428 void zzn2_div5(_MIPD_ zzn2 *w)
429 {
430 #ifdef MR_OS_THREADS
431 miracl *mr_mip=get_mip();
432 #endif
433 if (mr_mip->ERNUM) return;
434 MR_IN(209)
435
436 nres_div5(_MIPP_ w->a,w->a);
437 nres_div5(_MIPP_ w->b,w->b);
438
439 MR_OUT
440 }
441
442 /* multiply zzn2 by i */
443
zzn2_timesi(_MIPD_ zzn2 * u)444 void zzn2_timesi(_MIPD_ zzn2 *u)
445 {
446 #ifdef MR_OS_THREADS
447 miracl *mr_mip=get_mip();
448 #endif
449 if (mr_mip->ERNUM) return;
450 MR_IN(164)
451 copy(u->a,mr_mip->w1);
452 nres_negate(_MIPP_ u->b,u->a);
453 if (mr_mip->qnr==-2)
454 nres_modadd(_MIPP_ u->a,u->a,u->a);
455
456 copy(mr_mip->w1,u->b);
457 MR_OUT
458 }
459
zzn2_txx(_MIPD_ zzn2 * u)460 void zzn2_txx(_MIPD_ zzn2 *u)
461 {
462 /* multiply w by t^2 where x^2-t is irreducible polynomial for ZZn4
463
464 for p=5 mod 8 t=sqrt(sqrt(-2)), qnr=-2
465 for p=3 mod 8 t=sqrt(1+sqrt(-1)), qnr=-1
466 for p=7 mod 8 and p=2,3 mod 5 t=sqrt(2+sqrt(-1)), qnr=-1 */
467 zzn2 t;
468 #ifdef MR_OS_THREADS
469 miracl *mr_mip=get_mip();
470 #endif
471 if (mr_mip->ERNUM) return;
472 MR_IN(196)
473
474 switch (mr_mip->pmod8)
475 {
476 case 5:
477 zzn2_timesi(_MIPP_ u);
478 break;
479 case 3:
480 t.a=mr_mip->w3;
481 t.b=mr_mip->w4;
482 zzn2_copy(u,&t);
483 zzn2_timesi(_MIPP_ u);
484 zzn2_add(_MIPP_ u,&t,u);
485 break;
486 case 7:
487 t.a=mr_mip->w3;
488 t.b=mr_mip->w4;
489 zzn2_copy(u,&t);
490 zzn2_timesi(_MIPP_ u);
491 zzn2_add(_MIPP_ u,&t,u);
492 zzn2_add(_MIPP_ u,&t,u);
493 break;
494 default: break;
495 }
496 MR_OUT
497 }
498
zzn2_txd(_MIPD_ zzn2 * u)499 void zzn2_txd(_MIPD_ zzn2 *u)
500 { /* divide w by t^2 where x^2-t is irreducible polynomial for ZZn4
501
502 for p=5 mod 8 t=sqrt(sqrt(-2)), qnr=-2
503 for p=3 mod 8 t=sqrt(1+sqrt(-1)), qnr=-1
504 for p=7 mod 8 and p=2,3 mod 5 t=sqrt(2+sqrt(-1)), qnr=-1 */
505 zzn2 t;
506 #ifdef MR_OS_THREADS
507 miracl *mr_mip=get_mip();
508 #endif
509 if (mr_mip->ERNUM) return;
510 MR_IN(197)
511 t.a=mr_mip->w3;
512 t.b=mr_mip->w4;
513 switch (mr_mip->pmod8)
514 {
515 case 5:
516 copy(u->b,t.a);
517 nres_div2(_MIPP_ u->a,t.b);
518 nres_negate(_MIPP_ t.b,t.b);
519 zzn2_copy(&t,u);
520 break;
521 case 3:
522 nres_modadd(_MIPP_ u->a,u->b,t.a);
523 nres_modsub(_MIPP_ u->b,u->a,t.b);
524 zzn2_div2(_MIPP_ &t);
525 zzn2_copy(&t,u);
526 break;
527 case 7:
528 nres_modadd(_MIPP_ u->a,u->a,t.a);
529 nres_modadd(_MIPP_ t.a,u->b,t.a);
530 nres_modadd(_MIPP_ u->b,u->b,t.b);
531 nres_modsub(_MIPP_ t.b,u->a,t.b);
532 zzn2_div5(_MIPP_ &t);
533 zzn2_copy(&t,u);
534 /*
535 nres_modadd(_MIPP_ u->a,u->b,t.a);
536 nres_modadd(_MIPP_ t.a,u->b,t.a);
537 nres_modsub(_MIPP_ u->b,u->a,t.b);
538 zzn2_div3(_MIPP_ &t);
539 zzn2_copy(&t,u);
540 */
541 break;
542 default: break;
543 }
544
545 MR_OUT
546 }
547
548
549 /*
550 static void zzn2_print(_MIPD_ char *label, zzn2 *x)
551 {
552 char s1[1024], s2[1024];
553 big a, b;
554
555
556 a = mirvar(_MIPP_ 0);
557 b = mirvar(_MIPP_ 0);
558
559 redc(_MIPP_ x->a, a); otstr(_MIPP_ a, s1);
560 redc(_MIPP_ x->b, b); otstr(_MIPP_ b, s2);
561
562 printf("%s: [%s,%s]\n", label, s1, s2);
563
564 mr_free(a); mr_free(b);
565
566 }
567
568 static void nres_print(_MIPD_ char *label, big x)
569 {
570 char s[1024];
571 big a;
572
573 a = mirvar(_MIPP_ 0);
574
575 redc(_MIPP_ x, a);
576 otstr(_MIPP_ a, s);
577
578 printf("%s: %s\n", label, s);
579
580 mr_free(a);
581 }
582
583 */
584
585 /* Lucas-style ladder exponentiation - for ZZn4 exponentiation
586
587 void zzn2_powl(_MIPD_ zzn2 *x,big e,zzn2 *w)
588 {
589 #ifdef MR_OS_THREADS
590 miracl *mr_mip=get_mip();
591 #endif
592 int i,s;
593 zzn2 t1,t3,t4;
594 if (mr_mip->ERNUM) return;
595 MR_IN(165)
596 t1.a=mr_mip->w3;
597 t1.b=mr_mip->w4;
598 t3.a=mr_mip->w8;
599 t3.b=mr_mip->w9;
600 t4.a=mr_mip->w10;
601 t4.b=mr_mip->w11;
602
603 zzn2_from_int(_MIPP_ 1,&t1);
604
605 s=size(e);
606 if (s==0)
607 {
608 zzn2_copy(&t1,w);
609 return;
610 }
611 zzn2_copy(x,w);
612 if (s==1 || s==(-1)) return;
613
614 i=logb2(_MIPP_ e)-1;
615
616 zzn2_copy(w,&t3);
617 zzn2_sqr(_MIPP_ w,&t4);
618 zzn2_add(_MIPP_ &t4,&t4,&t4);
619 zzn2_sub(_MIPP_ &t4,&t1,&t4);
620
621 while (i-- && !mr_mip->ERNUM)
622 {
623 if (mr_testbit(_MIPP_ e,i))
624 {
625 zzn2_mul(_MIPP_ &t3,&t4,&t3);
626 zzn2_add(_MIPP_ &t3,&t3,&t3);
627 zzn2_sub(_MIPP_ &t3,w,&t3);
628 zzn2_sqr(_MIPP_ &t4,&t4);
629 zzn2_add(_MIPP_ &t4,&t4,&t4);
630 zzn2_sub(_MIPP_ &t4,&t1,&t4);
631 }
632 else
633 {
634 zzn2_mul(_MIPP_ &t4,&t3,&t4);
635 zzn2_add(_MIPP_ &t4,&t4,&t4);
636 zzn2_sub(_MIPP_ &t4,w,&t4);
637 zzn2_sqr(_MIPP_ &t3,&t3);
638 zzn2_add(_MIPP_ &t3,&t3,&t3);
639 zzn2_sub(_MIPP_ &t3,&t1,&t3);
640 }
641
642 }
643 zzn2_copy(&t4,w);
644 MR_OUT
645 }
646 */
647