1 /*
2 * MIRACL E(F_p^2) support functions
3 * mrecn2.c
4 *
5 */
6
7 #include <stdlib.h>
8 #include "miracl.h"
9 #ifdef MR_STATIC
10 #include <string.h>
11 #endif
12
zzn2_div2_i(zzn2 * w)13 static inline void zzn2_div2_i(zzn2 *w)
14 {
15 moddiv2(w->a->w);
16 w->a->len=2;
17 moddiv2(w->b->w);
18 w->b->len=2;
19 }
20
zzn2_tim2_i(zzn2 * w)21 static inline void zzn2_tim2_i(zzn2 *w)
22 {
23 #ifdef MR_COUNT_OPS
24 fpa+=2;
25 #endif
26
27 modtim2(w->a->w);
28 modtim2(w->b->w);
29 w->a->len=2;
30 w->b->len=2;
31 }
32
zzn2_tim3_i(zzn2 * w)33 static inline void zzn2_tim3_i(zzn2 *w)
34 {
35 #ifdef MR_COUNT_OPS
36 fpa+=4;
37 #endif
38
39 modtim3(w->a->w);
40 modtim3(w->b->w);
41 w->a->len=2;
42 w->b->len=2;
43 }
44
zzn2_copy_i(zzn2 * x,zzn2 * w)45 static inline void zzn2_copy_i(zzn2 *x,zzn2 *w)
46 {
47 if (x==w) return;
48
49 w->a->len=x->a->len;
50 w->a->w[0]=x->a->w[0];
51 w->a->w[1]=x->a->w[1];
52 w->b->len=x->b->len;
53 w->b->w[0]=x->b->w[0];
54 w->b->w[1]=x->b->w[1];
55
56 }
57
zzn2_add_i(zzn2 * x,zzn2 * y,zzn2 * w)58 static inline void zzn2_add_i(zzn2 *x,zzn2 *y,zzn2 *w)
59 {
60
61 #ifdef MR_COUNT_OPS
62 fpa+=2;
63 #endif
64
65 modadd(x->a->w,y->a->w,w->a->w);
66 modadd(x->b->w,y->b->w,w->b->w);
67 w->a->len=2;
68 w->b->len=2;
69 }
70
zzn2_sub_i(zzn2 * x,zzn2 * y,zzn2 * w)71 static inline void zzn2_sub_i(zzn2 *x,zzn2 *y,zzn2 *w)
72 {
73 #ifdef MR_COUNT_OPS
74 fpa+=2;
75 #endif
76 modsub(x->a->w,y->a->w,w->a->w);
77 modsub(x->b->w,y->b->w,w->b->w);
78 w->a->len=2;
79 w->b->len=2;
80 }
81
zzn2_timesi_i(zzn2 * u)82 static inline void zzn2_timesi_i(zzn2 *u)
83 {
84 mr_small w1[2];
85 w1[0]=u->a->w[0];
86 w1[1]=u->a->w[1];
87
88 u->a->w[0]=u->b->w[0];
89 u->a->w[1]=u->b->w[1];
90
91 modneg(u->a->w);
92
93 u->b->w[0]=w1[0];
94 u->b->w[1]=w1[1];
95 }
96
zzn2_txx_i(zzn2 * u)97 static inline void zzn2_txx_i(zzn2 *u)
98 {
99 /* multiply w by t^2 where x^2-t is irreducible polynomial for ZZn4
100
101 for p=5 mod 8 t=sqrt(sqrt(-2)), qnr=-2
102 for p=3 mod 8 t=sqrt(1+sqrt(-1)), qnr=-1
103 for p=7 mod 8 and p=2,3 mod 5 t=sqrt(2+sqrt(-1)), qnr=-1 */
104 zzn2 t;
105 struct bigtype aa,bb;
106 big a,b;
107 mr_small w3[2],w4[2];
108 a=&aa;
109 b=&bb;
110 a->len=2;
111 b->len=2;
112 a->w=w3;
113 b->w=w4;
114 t.a=a;
115 t.b=b;
116 zzn2_copy_i(u,&t);
117 zzn2_timesi_i(u);
118 zzn2_add_i(u,&t,u);
119 zzn2_add_i(u,&t,u);
120 u->a->len=2;
121 u->b->len=2;
122 }
123
zzn2_pmul_i(int i,zzn2 * x)124 static inline void zzn2_pmul_i(int i,zzn2 *x)
125 {
126 modpmul(i,x->a->w);
127 modpmul(i,x->b->w);
128 }
129
zzn2_sqr_i(zzn2 * x,zzn2 * w)130 static inline void zzn2_sqr_i(zzn2 *x,zzn2 *w)
131 {
132 static mr_small w1[2],w2[2];
133 #ifdef MR_COUNT_OPS
134 fpa+=3;
135 fpc+=2;
136 #endif
137 modadd(x->a->w,x->b->w,w1);
138 modsub(x->a->w,x->b->w,w2);
139 modmult(x->a->w,x->b->w,w->b->w);
140 modmult(w1,w2,w->a->w); // routine that calculates (a+b)(a-b) ??
141 modtim2(w->b->w);
142 w->a->len=2;
143 w->b->len=2;
144 }
145
zzn2_dblsub_i(zzn2 * x,zzn2 * y,zzn2 * w)146 static inline void zzn2_dblsub_i(zzn2 *x,zzn2 *y,zzn2 *w)
147 {
148 #ifdef MR_COUNT_OPS
149 fpa+=4;
150 #endif
151 moddblsub(w->a->w,x->a->w,y->a->w);
152 moddblsub(w->b->w,x->b->w,y->b->w);
153 w->a->len=2;
154 w->b->len=2;
155 }
156
zzn2_mul_i(zzn2 * x,zzn2 * y,zzn2 * w)157 static inline void zzn2_mul_i(zzn2 *x,zzn2 *y,zzn2 *w)
158 {
159 static mr_small w1[2],w2[2],w5[2];
160 #ifdef MR_COUNT_OPS
161 fpa+=5;
162 fpc+=3;
163 #endif
164 /*#pragma omp parallel sections
165 {
166 #pragma omp section */
167 modmult(x->a->w,y->a->w,w1);
168 /* #pragma omp section */
169 modmult(x->b->w,y->b->w,w2);
170 /*}*/
171
172 modadd(x->a->w,x->b->w,w5);
173 modadd(y->a->w,y->b->w,w->b->w);
174 modmult(w->b->w,w5,w->b->w);
175 moddblsub(w->b->w,w1,w2); /* w->b->w - w1 -w2 */
176
177 modsub(w1,w2,w->a->w);
178
179 w->a->len=2;
180 w->b->len=2;
181 }
182
zzn2_inv_i(_MIPD_ zzn2 * w)183 void zzn2_inv_i(_MIPD_ zzn2 *w)
184 {
185 #ifdef MR_OS_THREADS
186 miracl *mr_mip=get_mip();
187 #endif
188
189 if (mr_mip->ERNUM) return;
190 #ifdef MR_COUNT_OPS
191 fpc+=4;
192 fpa+=1;
193 #endif
194 MR_IN(163)
195 modsqr(w->a->w,mr_mip->w1->w);
196 modsqr(w->b->w,mr_mip->w2->w);
197 modadd(mr_mip->w1->w,mr_mip->w2->w,mr_mip->w1->w);
198 mr_mip->w1->len=2;
199
200 /* redc(_MIPP_ mr_mip->w1,mr_mip->w6); */
201 copy(mr_mip->w1,mr_mip->w6);
202
203 xgcd(_MIPP_ mr_mip->w6,mr_mip->modulus,mr_mip->w6,mr_mip->w6,mr_mip->w6);
204
205 /* nres(_MIPP_ mr_mip->w6,mr_mip->w6); */
206
207 modmult(w->a->w,mr_mip->w6->w,w->a->w);
208 modneg(mr_mip->w6->w);
209 modmult(w->b->w,mr_mip->w6->w,w->b->w);
210 MR_OUT
211 }
212
nres_sqroot(_MIPD_ big x,big w)213 BOOL nres_sqroot(_MIPD_ big x,big w)
214 { /* w=sqrt(x) mod p. This depends on p being prime! */
215 int i,t,js;
216 #ifdef MR_COUNT_OPS
217 fpc+=125;
218 #endif
219 #ifdef MR_OS_THREADS
220 miracl *mr_mip=get_mip();
221 #endif
222 if (mr_mip->ERNUM) return FALSE;
223
224 copy(x,w);
225 if (size(w)==0) return TRUE;
226
227
228 copy(w,mr_mip->w1);
229 for (i=0;i<25;i++)
230 {
231 modsqr(w->w,w->w);
232 modsqr(w->w,w->w);
233 modsqr(w->w,w->w);
234 modsqr(w->w,w->w);
235 modsqr(w->w,w->w);
236 }
237 w->len=2;
238
239 modsqr(w->w,mr_mip->w2->w);
240 mr_mip->w2->len=2;
241 if (compare(mr_mip->w1,mr_mip->w2)!=0) {zero(w);return FALSE;}
242
243
244 return TRUE;
245
246 }
247
zzn2_sqrt(_MIPD_ zzn2 * u,zzn2 * w)248 BOOL zzn2_sqrt(_MIPD_ zzn2 *u,zzn2 *w)
249 { /* sqrt(a+ib) = sqrt(a+sqrt(a*a-n*b*b)/2)+ib/(2*sqrt(a+sqrt(a*a-n*b*b)/2))
250 where i*i=n */
251 #ifdef MR_OS_THREADS
252 miracl *mr_mip=get_mip();
253 #endif
254 #ifdef MR_COUNT_OPS
255 fpc+=2;
256 fpa+=1;
257 #endif
258 if (mr_mip->ERNUM) return FALSE;
259
260 zzn2_copy(u,w);
261 if (zzn2_iszero(w)) return TRUE;
262
263 MR_IN(204)
264
265 modsqr(w->b->w,mr_mip->w7->w);
266 modsqr(w->a->w,mr_mip->w1->w);
267 modadd(mr_mip->w1->w,mr_mip->w7->w,mr_mip->w7->w);
268 mr_mip->w7->len=2;
269
270 // nres_modmult(_MIPP_ w->b,w->b,mr_mip->w7);
271 // nres_modmult(_MIPP_ w->a,w->a,mr_mip->w1);
272 // nres_modadd(_MIPP_ mr_mip->w7,mr_mip->w1,mr_mip->w7);
273
274 if (!nres_sqroot(_MIPP_ mr_mip->w7,mr_mip->w7)) /* s=w7 */
275 {
276 zzn2_zero(w);
277 MR_OUT
278 return FALSE;
279 }
280 #ifdef MR_COUNT_OPS
281 fpa+=1;
282 #endif
283 modadd(w->a->w,mr_mip->w7->w,mr_mip->w15->w);
284 moddiv2(mr_mip->w15->w);
285 mr_mip->w15->len=2;
286
287 // nres_modadd(_MIPP_ w->a,mr_mip->w7,mr_mip->w15);
288 // nres_div2(_MIPP_ mr_mip->w15,mr_mip->w15);
289
290 if (!nres_sqroot(_MIPP_ mr_mip->w15,mr_mip->w15))
291 {
292 #ifdef MR_COUNT_OPS
293 fpa+=1;
294 #endif
295 modsub(w->a->w,mr_mip->w7->w,mr_mip->w15->w);
296 moddiv2(mr_mip->w15->w);
297 mr_mip->w15->len=2;
298
299
300 // nres_modsub(_MIPP_ w->a,mr_mip->w7,mr_mip->w15);
301 // nres_div2(_MIPP_ mr_mip->w15,mr_mip->w15);
302 if (!nres_sqroot(_MIPP_ mr_mip->w15,mr_mip->w15))
303 {
304 zzn2_zero(w);
305 MR_OUT
306 return FALSE;
307 }
308 // else printf("BBBBBBBBBBBBBBBBBB\n");
309 }
310 // else printf("AAAAAAAAAAAAAAAAAAA\n");
311 #ifdef MR_COUNT_OPS
312 fpa+=1;
313 #endif
314 copy(mr_mip->w15,w->a);
315 modadd(mr_mip->w15->w,mr_mip->w15->w,mr_mip->w15->w);
316 nres_moddiv(_MIPP_ w->b,mr_mip->w15,w->b);
317
318 MR_OUT
319 return TRUE;
320 }
321
322 /*
323 BOOL zzn2_multi_inverse(_MIPD_ int m,zzn2 *x,zzn2 *w)
324 {
325 int i;
326 zzn2 t1,t2;
327 #ifdef MR_OS_THREADS
328 miracl *mr_mip=get_mip();
329 #endif
330 if (m==0) return TRUE;
331 if (m<0) return FALSE;
332 MR_IN(214)
333
334 if (x==w)
335 {
336 mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
337 MR_OUT
338 return FALSE;
339 }
340
341 if (m==1)
342 {
343 zzn2_copy_i(&x[0],&w[0]);
344 zzn2_inv_i(_MIPP_ &w[0]);
345
346 MR_OUT
347 return TRUE;
348 }
349
350 zzn2_from_int(_MIPP_ 1,&w[0]);
351 zzn2_copy_i(&x[0],&w[1]);
352
353 for (i=2;i<m;i++)
354 {
355 if (zzn2_isunity(_MIPP_ &x[i-1]))
356 zzn2_copy_i(&w[i-1],&w[i]);
357 else
358 zzn2_mul_i(&w[i-1],&x[i-1],&w[i]);
359 }
360
361 t1.a=mr_mip->w8;
362 t1.b=mr_mip->w9;
363 t2.a=mr_mip->w10;
364 t2.b=mr_mip->w11;
365
366 zzn2_mul_i(&w[m-1],&x[m-1],&t1);
367 if (zzn2_iszero(&t1))
368 {
369 mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
370 MR_OUT
371 return FALSE;
372 }
373
374 zzn2_inv_i(_MIPP_ &t1);
375
376 zzn2_copy_i(&x[m-1],&t2);
377 zzn2_mul_i(&w[m-1],&t1,&w[m-1]);
378
379 for (i=m-2;;i--)
380 {
381 if (i==0)
382 {
383 zzn2_mul_i(&t2,&t1,&w[0]);
384 break;
385 }
386 zzn2_mul_i(&w[i],&t2,&w[i]);
387 zzn2_mul_i(&w[i],&t1,&w[i]);
388 if (!zzn2_isunity(_MIPP_ &x[i])) zzn2_mul_i(&t2,&x[i],&t2);
389 }
390
391 MR_OUT
392 return TRUE;
393 }
394
395 */
396
ecn2_iszero(ecn2 * a)397 BOOL ecn2_iszero(ecn2 *a)
398 {
399 if (a->marker==MR_EPOINT_INFINITY) return TRUE;
400 return FALSE;
401 }
402
ecn2_copy(ecn2 * a,ecn2 * b)403 void ecn2_copy(ecn2 *a,ecn2 *b)
404 {
405 zzn2_copy_i(&(a->x),&(b->x));
406 zzn2_copy_i(&(a->y),&(b->y));
407 #ifndef MR_AFFINE_ONLY
408 if (a->marker==MR_EPOINT_GENERAL) zzn2_copy_i(&(a->z),&(b->z));
409 #endif
410 b->marker=a->marker;
411 }
412
ecn2_zero(ecn2 * a)413 void ecn2_zero(ecn2 *a)
414 {
415 zzn2_zero(&(a->x)); zzn2_zero(&(a->y));
416 #ifndef MR_AFFINE_ONLY
417 if (a->marker==MR_EPOINT_GENERAL) zzn2_zero(&(a->z));
418 #endif
419 a->marker=MR_EPOINT_INFINITY;
420 }
421
ecn2_compare(_MIPD_ ecn2 * a,ecn2 * b)422 BOOL ecn2_compare(_MIPD_ ecn2 *a,ecn2 *b)
423 {
424 #ifdef MR_OS_THREADS
425 miracl *mr_mip=get_mip();
426 #endif
427 if (mr_mip->ERNUM) return FALSE;
428
429 MR_IN(193)
430 ecn2_norm(_MIPP_ a);
431 ecn2_norm(_MIPP_ b);
432 MR_OUT
433 if (zzn2_compare(&(a->x),&(b->x)) && zzn2_compare(&(a->y),&(b->y)) && a->marker==b->marker) return TRUE;
434 return FALSE;
435 }
436
ecn2_norm(_MIPD_ ecn2 * a)437 void ecn2_norm(_MIPD_ ecn2 *a)
438 {
439 zzn2 t;
440 #ifdef MR_OS_THREADS
441 miracl *mr_mip=get_mip();
442 #endif
443 #ifndef MR_AFFINE_ONLY
444 if (mr_mip->ERNUM) return;
445 if (a->marker!=MR_EPOINT_GENERAL) return;
446
447 MR_IN(194)
448
449 zzn2_inv_i(_MIPP_ &(a->z));
450
451 t.a=mr_mip->w3;
452 t.b=mr_mip->w4;
453 zzn2_copy_i(&(a->z),&t);
454
455 zzn2_sqr_i( &(a->z),&(a->z));
456 zzn2_mul_i( &(a->x),&(a->z),&(a->x));
457 zzn2_mul_i( &(a->z),&t,&(a->z));
458 zzn2_mul_i( &(a->y),&(a->z),&(a->y));
459 zzn2_from_int(_MIPP_ 1,&(a->z));
460 a->marker=MR_EPOINT_NORMALIZED;
461
462 MR_OUT
463 #endif
464 }
465
ecn2_get(_MIPD_ ecn2 * e,zzn2 * x,zzn2 * y,zzn2 * z)466 void ecn2_get(_MIPD_ ecn2 *e,zzn2 *x,zzn2 *y,zzn2 *z)
467 {
468 zzn2_copy_i(&(e->x),x);
469 zzn2_copy_i(&(e->y),y);
470 #ifndef MR_AFFINE_ONLY
471 if (e->marker==MR_EPOINT_GENERAL) zzn2_copy_i(&(e->z),z);
472 else zzn2_from_zzn(mr_mip->one,z);
473 #endif
474 }
475
ecn2_getxy(ecn2 * e,zzn2 * x,zzn2 * y)476 void ecn2_getxy(ecn2 *e,zzn2 *x,zzn2 *y)
477 {
478 zzn2_copy_i(&(e->x),x);
479 zzn2_copy_i(&(e->y),y);
480 }
481
ecn2_getx(ecn2 * e,zzn2 * x)482 void ecn2_getx(ecn2 *e,zzn2 *x)
483 {
484 zzn2_copy_i(&(e->x),x);
485 }
486
zzn2_conj_i(zzn2 * x,zzn2 * w)487 inline void zzn2_conj_i(zzn2 *x,zzn2 *w)
488 {
489 zzn2_copy_i(x,w);
490 modneg(w->b->w);
491 }
492
ecn2_psi(_MIPD_ zzn2 * psi,ecn2 * P)493 void ecn2_psi(_MIPD_ zzn2 *psi,ecn2 *P)
494 {
495 ecn2_norm(_MIPP_ P);
496 zzn2_conj_i(&(P->x),&(P->x));
497 zzn2_conj_i(&(P->y),&(P->y));
498 zzn2_mul_i(&(P->x),&psi[0],&(P->x));
499 zzn2_mul_i(&(P->y),&psi[1],&(P->y));
500
501 }
502
503 #ifndef MR_AFFINE_ONLY
ecn2_getz(_MIPD_ ecn2 * e,zzn2 * z)504 void ecn2_getz(_MIPD_ ecn2 *e,zzn2 *z)
505 {
506 if (e->marker==MR_EPOINT_GENERAL) zzn2_copy_i(&(e->z),z);
507 else zzn2_from_zzn(mr_mip->one,z);
508 }
509 #endif
510
ecn2_rhs(_MIPD_ zzn2 * x,zzn2 * rhs)511 void ecn2_rhs(_MIPD_ zzn2 *x,zzn2 *rhs)
512 { /* calculate RHS of elliptic curve equation */
513 BOOL twist;
514 zzn2 A,B;
515 #ifdef MR_OS_THREADS
516 miracl *mr_mip=get_mip();
517 #endif
518 if (mr_mip->ERNUM) return;
519 twist=mr_mip->TWIST;
520
521 MR_IN(202)
522
523 A.a=mr_mip->w10;
524 A.b=mr_mip->w11;
525 B.a=mr_mip->w12;
526 B.b=mr_mip->w13;
527
528 if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&A);
529 else zzn2_from_zzn(mr_mip->A,&A);
530
531 if (mr_abs(mr_mip->Bsize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Bsize,&B);
532 else zzn2_from_zzn(mr_mip->B,&B);
533
534 if (twist)
535 {
536 if (mr_mip->Asize==0 || mr_mip->Bsize==0)
537 {
538 if (mr_mip->Asize==0)
539 {
540 zzn2_txd(_MIPP_ &B);
541 }
542 if (mr_mip->Bsize==0)
543 {
544 zzn2_mul_i( &A,x,&B);
545 zzn2_txd(_MIPP_ &B);
546 }
547 zzn2_negate(_MIPP_ &B,&B);
548 }
549 else
550 {
551 zzn2_txx_i(&B);
552 zzn2_txx_i(&B);
553 zzn2_txx_i(&B);
554 zzn2_mul_i( &A,x,&A);
555 zzn2_txx_i(&A);
556 zzn2_txx_i(&A);
557 zzn2_add_i(&B,&A,&B);
558 }
559 }
560 else
561 {
562 zzn2_mul_i( &A,x,&A);
563 zzn2_add_i(&B,&A,&B);
564 }
565
566 zzn2_sqr_i( x,&A);
567 zzn2_mul_i( &A,x,&A);
568 zzn2_add_i(&B,&A,rhs);
569
570 MR_OUT
571 }
572
ecn2_set(_MIPD_ zzn2 * x,zzn2 * y,ecn2 * e)573 BOOL ecn2_set(_MIPD_ zzn2 *x,zzn2 *y,ecn2 *e)
574 {
575 zzn2 lhs,rhs;
576 #ifdef MR_OS_THREADS
577 miracl *mr_mip=get_mip();
578 #endif
579 if (mr_mip->ERNUM) return FALSE;
580
581 MR_IN(195)
582
583 lhs.a=mr_mip->w10;
584 lhs.b=mr_mip->w11;
585 rhs.a=mr_mip->w12;
586 rhs.b=mr_mip->w13;
587
588 ecn2_rhs(_MIPP_ x,&rhs);
589
590 zzn2_sqr_i( y,&lhs);
591
592 if (!zzn2_compare(&lhs,&rhs))
593 {
594 MR_OUT
595 return FALSE;
596 }
597
598 zzn2_copy_i(x,&(e->x));
599 zzn2_copy_i(y,&(e->y));
600
601 e->marker=MR_EPOINT_NORMALIZED;
602
603 MR_OUT
604 return TRUE;
605 }
606
607 #ifndef MR_NOSUPPORT_COMPRESSION
608
ecn2_setx(_MIPD_ zzn2 * x,ecn2 * e)609 BOOL ecn2_setx(_MIPD_ zzn2 *x,ecn2 *e)
610 {
611 zzn2 rhs;
612 #ifdef MR_OS_THREADS
613 miracl *mr_mip=get_mip();
614 #endif
615 if (mr_mip->ERNUM) return FALSE;
616
617 MR_IN(201)
618
619 rhs.a=mr_mip->w12;
620 rhs.b=mr_mip->w13;
621
622 ecn2_rhs(_MIPP_ x,&rhs);
623
624 if (!zzn2_iszero(&rhs))
625 {
626 if (!zzn2_sqrt(_MIPP_ &rhs,&rhs))
627 {
628 MR_OUT
629 return FALSE;
630 }
631 }
632
633 zzn2_copy_i(x,&(e->x));
634 zzn2_copy_i(&rhs,&(e->y));
635
636 e->marker=MR_EPOINT_NORMALIZED;
637
638 MR_OUT
639 return TRUE;
640 }
641
642 #endif
643
644 #ifndef MR_AFFINE_ONLY
ecn2_setxyz(zzn2 * x,zzn2 * y,zzn2 * z,ecn2 * e)645 void ecn2_setxyz(zzn2 *x,zzn2 *y,zzn2 *z,ecn2 *e)
646 {
647 zzn2_copy_i(x,&(e->x));
648 zzn2_copy_i(y,&(e->y));
649 zzn2_copy_i(z,&(e->z));
650 e->marker=MR_EPOINT_GENERAL;
651 }
652 #endif
653
ecn2_negate(_MIPD_ ecn2 * u,ecn2 * w)654 void ecn2_negate(_MIPD_ ecn2 *u,ecn2 *w)
655 {
656 ecn2_copy(u,w);
657 if (!w->marker!=MR_EPOINT_INFINITY)
658 zzn2_negate(_MIPP_ &(w->y),&(w->y));
659 }
660 /*
661 BOOL ecn2_add2(_MIPD_ ecn2 *Q,ecn2 *P,zzn2 *lam,zzn2 *ex1)
662 {
663 BOOL Doubling;
664 #ifdef MR_OS_THREADS
665 miracl *mr_mip=get_mip();
666 #endif
667
668 Doubling=ecn2_add3(_MIPP_ Q,P,lam,ex1,NULL);
669
670 return Doubling;
671 }
672
673 BOOL ecn2_add1(_MIPD_ ecn2 *Q,ecn2 *P,zzn2 *lam)
674 {
675 BOOL Doubling;
676 #ifdef MR_OS_THREADS
677 miracl *mr_mip=get_mip();
678 #endif
679 Doubling=ecn2_add3(_MIPP_ Q,P,lam,NULL,NULL);
680
681 return Doubling;
682 }
683 */
684
ecn2_sub(_MIPD_ ecn2 * Q,ecn2 * P)685 BOOL ecn2_sub(_MIPD_ ecn2 *Q,ecn2 *P)
686 {
687 BOOL Doubling;
688 #ifdef MR_OS_THREADS
689 miracl *mr_mip=get_mip();
690 #endif
691
692 ecn2_negate(_MIPP_ Q,Q);
693
694 Doubling=ecn2_add(_MIPP_ Q,P);
695
696 ecn2_negate(_MIPP_ Q,Q);
697
698 return Doubling;
699 }
700
701 /*
702 static void zzn2_print(_MIPD_ char *label, zzn2 *x)
703 {
704 char s1[1024], s2[1024];
705 big a, b;
706
707 #ifdef MR_STATIC
708 char mem_big[MR_BIG_RESERVE(2)];
709 memset(mem_big, 0, MR_BIG_RESERVE(2));
710 a=mirvar_mem(_MIPP_ mem_big,0);
711 b=mirvar_mem(_MIPP_ mem_big,1);
712 #else
713 a = mirvar(_MIPP_ 0);
714 b = mirvar(_MIPP_ 0);
715 #endif
716 redc(_MIPP_ x->a, a); otstr(_MIPP_ a, s1);
717 redc(_MIPP_ x->b, b); otstr(_MIPP_ b, s2);
718
719 printf("%s: [%s,%s]\n", label, s1, s2);
720 #ifndef MR_STATIC
721 mr_free(a); mr_free(b);
722 #endif
723 }
724
725 static void nres_print(_MIPD_ char *label, big x)
726 {
727 char s[1024];
728 big a;
729
730 a = mirvar(_MIPP_ 0);
731
732 redc(_MIPP_ x, a);
733 otstr(_MIPP_ a, s);
734
735 printf("%s: %s\n", label, s);
736
737 mr_free(a);
738 }
739 */
740
ecn2_add_sub(_MIPD_ ecn2 * P,ecn2 * Q,ecn2 * PP,ecn2 * PM)741 BOOL ecn2_add_sub(_MIPD_ ecn2 *P,ecn2 *Q,ecn2 *PP,ecn2 *PM)
742 { /* PP=P+Q, PM=P-Q. Assumes P and Q are both normalized, and P!=Q */
743 #ifdef MR_OS_THREADS
744 miracl *mr_mip=get_mip();
745 #endif
746 zzn2 t1,t2,lam;
747
748 if (mr_mip->ERNUM) return FALSE;
749
750 MR_IN(211)
751
752 if (P->marker==MR_EPOINT_GENERAL || P->marker==MR_EPOINT_GENERAL)
753 { /* Sorry, some restrictions.. */
754 mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
755 MR_OUT
756 return FALSE;
757 }
758
759 if (zzn2_compare(&(P->x),&(Q->x)))
760 { /* P=Q or P=-Q - shouldn't happen */
761 ecn2_copy(P,PP);
762 ecn2_add(_MIPP_ Q,PP);
763 ecn2_copy(P,PM);
764 ecn2_sub(_MIPP_ Q,PM);
765
766 MR_OUT
767 return TRUE;
768 }
769
770 t1.a = mr_mip->w8;
771 t1.b = mr_mip->w9;
772 t2.a = mr_mip->w10;
773 t2.b = mr_mip->w11;
774 lam.a = mr_mip->w12;
775 lam.b = mr_mip->w13;
776
777 zzn2_copy_i(&(P->x),&t2);
778 zzn2_sub_i(&t2,&(Q->x),&t2);
779 zzn2_inv_i(_MIPP_ &t2); /* only one inverse required */
780 zzn2_add_i(&(P->x),&(Q->x),&(PP->x));
781 zzn2_copy_i(&(PP->x),&(PM->x));
782
783 zzn2_copy_i(&(P->y),&t1);
784 zzn2_sub_i(&t1,&(Q->y),&t1);
785 zzn2_copy_i(&t1,&lam);
786 zzn2_mul_i( &lam,&t2,&lam);
787 zzn2_copy_i(&lam,&t1);
788 zzn2_sqr_i( &t1,&t1);
789 zzn2_sub_i(&t1,&(PP->x),&(PP->x));
790 zzn2_copy_i(&(Q->x),&(PP->y));
791 zzn2_sub_i(&(PP->y),&(PP->x),&(PP->y));
792 zzn2_mul_i( &(PP->y),&lam,&(PP->y));
793 zzn2_sub_i(&(PP->y),&(Q->y),&(PP->y));
794
795 zzn2_copy_i(&(P->y),&t1);
796 zzn2_add_i(&t1,&(Q->y),&t1);
797 zzn2_copy_i(&t1,&lam);
798 zzn2_mul_i( &lam,&t2,&lam);
799 zzn2_copy_i(&lam,&t1);
800 zzn2_sqr_i( &t1,&t1);
801 zzn2_sub_i(&t1,&(PM->x),&(PM->x));
802 zzn2_copy_i(&(Q->x),&(PM->y));
803 zzn2_sub_i(&(PM->y),&(PM->x),&(PM->y));
804 zzn2_mul_i( &(PM->y),&lam,&(PM->y));
805 zzn2_add_i(&(PM->y),&(Q->y),&(PM->y));
806
807 PP->marker=MR_EPOINT_NORMALIZED;
808 PM->marker=MR_EPOINT_NORMALIZED;
809
810 MR_OUT
811 return TRUE;
812 }
813
ecn2_add(_MIPD_ ecn2 * Q,ecn2 * P)814 BOOL ecn2_add(_MIPD_ ecn2 *Q,ecn2 *P)
815 { /* P+=Q */
816 BOOL Doubling=FALSE;
817 BOOL twist;
818 int iA;
819 zzn2 t1,t2,t3,lam;
820
821 #ifdef MR_OS_THREADS
822 miracl *mr_mip=get_mip();
823 #endif
824
825 t1.a = mr_mip->w8;
826 t1.b = mr_mip->w9;
827 t2.a = mr_mip->w10;
828 t2.b = mr_mip->w11;
829 t3.a = mr_mip->w12;
830 t3.b = mr_mip->w13;
831 lam.a = mr_mip->w14;
832 lam.b = mr_mip->w15;
833
834
835 twist=mr_mip->TWIST;
836 if (mr_mip->ERNUM) return FALSE;
837
838 if (P->marker==MR_EPOINT_INFINITY)
839 {
840 ecn2_copy(Q,P);
841 return Doubling;
842 }
843 if (Q->marker==MR_EPOINT_INFINITY) return Doubling;
844
845 MR_IN(205)
846
847 if (Q!=P && Q->marker==MR_EPOINT_GENERAL)
848 { /* Sorry, this code is optimized for mixed addition only */
849 mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
850 MR_OUT
851 return Doubling;
852 }
853 #ifndef MR_AFFINE_ONLY
854 if (mr_mip->coord==MR_AFFINE)
855 {
856 #endif
857 if (!zzn2_compare(&(P->x),&(Q->x)))
858 {
859 zzn2_copy_i(&(P->y),&t1);
860 zzn2_sub_i(&t1,&(Q->y),&t1);
861 zzn2_copy_i(&(P->x),&t2);
862 zzn2_sub_i(&t2,&(Q->x),&t2);
863 zzn2_copy_i(&t1,&lam);
864 zzn2_inv_i(_MIPP_ &t2);
865 zzn2_mul_i( &lam,&t2,&lam);
866
867 zzn2_add_i(&(P->x),&(Q->x),&(P->x));
868 zzn2_copy_i(&lam,&t1);
869 zzn2_sqr_i( &t1,&t1);
870 zzn2_sub_i(&t1,&(P->x),&(P->x));
871
872 zzn2_copy_i(&(Q->x),&(P->y));
873 zzn2_sub_i(&(P->y),&(P->x),&(P->y));
874 zzn2_mul_i( &(P->y),&lam,&(P->y));
875 zzn2_sub_i(&(P->y),&(Q->y),&(P->y));
876 }
877 else
878 {
879 if (!zzn2_compare(&(P->y),&(Q->y)) || zzn2_iszero(&(P->y)))
880 {
881 ecn2_zero(P);
882 zzn2_from_int(_MIPP_ 1,&lam);
883 MR_OUT
884 return Doubling;
885 }
886 zzn2_copy_i(&(P->x),&t1);
887 zzn2_copy_i(&(P->x),&t2);
888 zzn2_copy_i(&(P->x),&lam);
889 zzn2_sqr_i( &lam,&lam);
890
891 zzn2_copy_i(&lam,&t3);
892 zzn2_tim2_i(&t3);
893 zzn2_add_i(&lam,&t3,&lam);
894
895 if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&t3);
896 else zzn2_from_zzn(mr_mip->A,&t3);
897
898 if (twist)
899 {
900 zzn2_txx_i(&t3);
901 zzn2_txx_i(&t3);
902 }
903 zzn2_add_i(&lam,&t3,&lam);
904 zzn2_copy_i(&(P->y),&t3);
905 zzn2_tim2_i(&t3);
906 zzn2_inv_i(_MIPP_ &t3);
907 zzn2_mul_i( &lam,&t3,&lam);
908
909 zzn2_add_i(&t2,&(P->x),&t2);
910 zzn2_copy_i(&lam,&(P->x));
911 zzn2_sqr_i( &(P->x),&(P->x));
912 zzn2_sub_i(&(P->x),&t2,&(P->x));
913 zzn2_sub_i(&t1,&(P->x),&t1);
914 zzn2_mul_i( &t1,&lam,&t1);
915 zzn2_sub_i(&t1,&(P->y),&(P->y));
916 }
917 #ifndef MR_AFFINE_ONLY
918 zzn2_from_int(_MIPP_ 1,&(P->z));
919 #endif
920 P->marker=MR_EPOINT_NORMALIZED;
921 MR_OUT
922 return Doubling;
923 #ifndef MR_AFFINE_ONLY
924 }
925
926 if (Q==P) Doubling=TRUE;
927
928 if (!Doubling)
929 {
930 if (P->marker!=MR_EPOINT_NORMALIZED)
931 {
932 zzn2_sqr_i(&(P->z),&t1);
933 zzn2_mul_i(&t1,&(P->z),&t2);
934 zzn2_mul_i(&t1,&(Q->x),&t1);
935 zzn2_mul_i(&t2,&(Q->y),&t2);
936 // zzn2_sqr_i( &(P->z),&t1); /* 1S */
937 // zzn2_mul_i( &t3,&t1,&t3); /* 1M */
938 // zzn2_mul_i( &t1,&(P->z),&t1); /* 1M */
939 // zzn2_mul_i( &Yzzz,&t1,&Yzzz); /* 1M */
940 }
941 else
942 {
943 zzn2_copy(&(Q->x),&t1);
944 zzn2_copy(&(Q->y),&t2);
945 }
946 if (zzn2_compare(&t1,&(P->x))) /*?*/
947 {
948 if (!zzn2_compare(&t2,&(P->y)) || zzn2_iszero(&(P->y)))
949 {
950 ecn2_zero(P);
951 zzn2_from_int(_MIPP_ 1,&lam);
952 MR_OUT
953 return Doubling;
954 }
955 else Doubling=TRUE;
956 }
957 }
958
959 if (!Doubling)
960 { /* Addition */
961 zzn2_sub_i(&t1,&(P->x),&t1);
962 zzn2_sub_i(&t2,&(P->y),&t2);
963 if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy_i(&t1,&(P->z));
964 else zzn2_mul_i(&(P->z),&t1,&(P->z));
965 zzn2_sqr_i(&t1,&t3);
966 zzn2_mul_i(&t3,&t1,&lam);
967 zzn2_mul_i(&t3,&(P->x),&t3);
968 zzn2_copy_i(&t3,&t1);
969 zzn2_tim2_i(&t1);
970 zzn2_sqr_i(&t2,&(P->x));
971 zzn2_dblsub_i(&t1,&lam,&(P->x));
972 zzn2_sub_i(&t3,&(P->x),&t3);
973 zzn2_mul_i(&t3,&t2,&t3);
974 zzn2_mul_i(&lam,&(P->y),&lam);
975 zzn2_sub_i(&t3,&lam,&(P->y));
976 }
977 else
978 { /* doubling */
979 if (P->marker==MR_EPOINT_NORMALIZED) zzn2_from_int(_MIPP_ 1,&t1);
980 else zzn2_sqr_i(&(P->z),&t1);
981 if (twist) zzn2_txx_i(&t1);
982 zzn2_sub_i(&(P->x),&t1,&t2);
983 zzn2_add_i(&t1,&(P->x),&t1);
984 zzn2_mul_i(&t2,&t1,&t2);
985 zzn2_tim3_i(&t2);
986
987 zzn2_tim2_i(&(P->y));
988 if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy_i(&(P->y),&(P->z));
989 else zzn2_mul_i(&(P->z),&(P->y),&(P->z));
990 zzn2_sqr_i(&(P->y),&(P->y));
991 zzn2_mul_i(&(P->y),&(P->x),&t3);
992 zzn2_sqr_i(&(P->y),&(P->y));
993 zzn2_div2_i(&(P->y));
994 zzn2_sqr_i(&t2,&(P->x));
995 zzn2_copy_i(&t3,&t1);
996 zzn2_tim2_i(&t1);
997 zzn2_sub_i(&(P->x),&t1,&(P->x));
998 zzn2_sub_i(&t3,&(P->x),&t1);
999 zzn2_mul_i(&t1,&t2,&t1);
1000 zzn2_sub_i(&t1,&(P->y),&(P->y));
1001 }
1002
1003 P->marker=MR_EPOINT_GENERAL;
1004 MR_OUT
1005 return Doubling;
1006 #endif
1007 }
1008
calc_n(int w)1009 static int calc_n(int w)
1010 { /* number of precomputed values needed for given window size */
1011 if (w==3) return 3;
1012 if (w==4) return 5;
1013 if (w==5) return 11;
1014 if (w==6) return 41;
1015 return 0;
1016 }
1017
1018 /* Dahmen, Okeya and Schepers "Affine Precomputation with Sole Inversion in Elliptic Curve Cryptography" */
1019 /* Precomputes table into T. Assumes first P has been copied to P[0], then calculates 3P, 5P, 7P etc. into T */
1020
1021 #define MR_DOS_2 (14+4*MR_STR_SZ_2P)
1022
ecn2_dos(_MIPD_ int win,ecn2 * PT)1023 static void ecn2_dos(_MIPD_ int win,ecn2 *PT)
1024 {
1025 BOOL twist;
1026 int i,j,sz;
1027 zzn2 A,B,C,D,E,T,W,d[MR_STR_SZ_2P],e[MR_STR_SZ_2P];
1028 #ifdef MR_OS_THREADS
1029 miracl *mr_mip=get_mip();
1030 #endif
1031
1032 #ifndef MR_STATIC
1033 char *mem = memalloc(_MIPP_ MR_DOS_2);
1034 #else
1035 char mem[MR_BIG_RESERVE(MR_DOS_2)];
1036 memset(mem, 0, MR_BIG_RESERVE(MR_DOS_2));
1037 #endif
1038
1039 twist=mr_mip->TWIST;
1040 j=0;
1041 sz=calc_n(win);
1042
1043 A.a= mirvar_mem(_MIPP_ mem, j++);
1044 A.b= mirvar_mem(_MIPP_ mem, j++);
1045 B.a= mirvar_mem(_MIPP_ mem, j++);
1046 B.b= mirvar_mem(_MIPP_ mem, j++);
1047 C.a= mirvar_mem(_MIPP_ mem, j++);
1048 C.b= mirvar_mem(_MIPP_ mem, j++);
1049 D.a= mirvar_mem(_MIPP_ mem, j++);
1050 D.b= mirvar_mem(_MIPP_ mem, j++);
1051 E.a= mirvar_mem(_MIPP_ mem, j++);
1052 E.b= mirvar_mem(_MIPP_ mem, j++);
1053 T.a= mirvar_mem(_MIPP_ mem, j++);
1054 T.b= mirvar_mem(_MIPP_ mem, j++);
1055 W.a= mirvar_mem(_MIPP_ mem, j++);
1056 W.b= mirvar_mem(_MIPP_ mem, j++);
1057
1058 for (i=0;i<sz;i++)
1059 {
1060 d[i].a= mirvar_mem(_MIPP_ mem, j++);
1061 d[i].b= mirvar_mem(_MIPP_ mem, j++);
1062 e[i].a= mirvar_mem(_MIPP_ mem, j++);
1063 e[i].b= mirvar_mem(_MIPP_ mem, j++);
1064 }
1065
1066 zzn2_add_i(&(PT[0].y),&(PT[0].y),&d[0]); /* 1. d_0=2.y */
1067 zzn2_sqr_i(&d[0],&C); /* 2. C=d_0^2 */
1068
1069 zzn2_sqr_i(&(PT[0].x),&T);
1070 zzn2_add_i(&T,&T,&A);
1071 zzn2_add_i(&T,&A,&T);
1072
1073 if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&A);
1074 else zzn2_from_zzn(mr_mip->A,&A);
1075
1076 if (twist)
1077 {
1078 zzn2_txx_i(&A);
1079 zzn2_txx_i(&A);
1080 }
1081 zzn2_add_i(&A,&T,&A); /* 3. A=3x^2+a */
1082 zzn2_copy_i(&A,&W);
1083
1084 zzn2_add_i(&C,&C,&B);
1085 zzn2_add_i(&B,&C,&B);
1086 zzn2_mul_i(&B,&(PT[0].x),&B); /* 4. B=3C.x */
1087
1088 zzn2_sqr_i(&A,&d[1]);
1089 zzn2_sub_i(&d[1],&B,&d[1]); /* 5. d_1=A^2-B */
1090
1091 zzn2_sqr_i(&d[1],&E); /* 6. E=d_1^2 */
1092
1093 zzn2_mul_i(&B,&E,&B); /* 7. B=E.B */
1094
1095 zzn2_sqr_i(&C,&C); /* 8. C=C^2 */
1096
1097 zzn2_mul_i(&E,&d[1],&D); /* 9. D=E.d_1 */
1098
1099 zzn2_mul_i(&A,&d[1],&A);
1100 zzn2_add_i(&A,&C,&A);
1101 zzn2_negate(_MIPP_ &A,&A); /* 10. A=-d_1*A-C */
1102
1103 zzn2_add_i(&D,&D,&T);
1104 zzn2_sqr_i(&A,&d[2]);
1105 zzn2_sub_i(&d[2],&T,&d[2]);
1106 zzn2_sub_i(&d[2],&B,&d[2]); /* 11. d_2=A^2-2D-B */
1107
1108 if (sz>3)
1109 {
1110 zzn2_sqr_i(&d[2],&E); /* 12. E=d_2^2 */
1111
1112 zzn2_add_i(&T,&D,&T);
1113 zzn2_add_i(&T,&B,&T);
1114 zzn2_mul_i(&T,&E,&B); /* 13. B=E(B+3D) */
1115
1116 zzn2_add_i(&A,&A,&T);
1117 zzn2_add_i(&C,&T,&C);
1118 zzn2_mul_i(&C,&D,&C); /* 14. C=D(2A+C) */
1119
1120 zzn2_mul_i(&d[2],&E,&D); /* 15. D=E.d_2 */
1121
1122 zzn2_mul_i(&A,&d[2],&A);
1123 zzn2_add_i(&A,&C,&A);
1124 zzn2_negate(_MIPP_ &A,&A); /* 16. A=-d_2*A-C */
1125
1126
1127 zzn2_sqr_i(&A,&d[3]);
1128 zzn2_sub_i(&d[3],&D,&d[3]);
1129 zzn2_sub_i(&d[3],&B,&d[3]); /* 17. d_3=A^2-D-B */
1130
1131 for (i=4;i<sz;i++)
1132 {
1133 zzn2_sqr_i(&d[i-1],&E); /* 19. E=d(i-1)^2 */
1134 zzn2_mul_i(&B,&E,&B); /* 20. B=E.B */
1135 zzn2_mul_i(&C,&D,&C); /* 21. C=D.C */
1136 zzn2_mul_i(&E,&d[i-1],&D); /* 22. D=E.d(i-1) */
1137
1138 zzn2_mul_i(&A,&d[i-1],&A);
1139 zzn2_add_i(&A,&C,&A);
1140 zzn2_negate(_MIPP_ &A,&A); /* 23. A=-d(i-1)*A-C */
1141
1142 zzn2_sqr_i(&A,&d[i]);
1143 zzn2_sub_i(&d[i],&D,&d[i]);
1144 zzn2_sub_i(&d[i],&B,&d[i]); /* 24. d(i)=A^2-D-B */
1145 }
1146 }
1147
1148 zzn2_copy_i(&d[0],&e[0]);
1149 for (i=1;i<sz;i++)
1150 zzn2_mul_i(&e[i-1],&d[i],&e[i]);
1151
1152 zzn2_copy_i(&e[sz-1],&A);
1153 zzn2_inv_i(_MIPP_ &A);
1154
1155 for (i=sz-1;i>0;i--)
1156 {
1157 zzn2_copy_i(&d[i],&B);
1158 zzn2_mul_i(&e[i-1],&A,&d[i]);
1159 zzn2_mul_i(&A,&B,&A);
1160 }
1161 zzn2_copy_i(&A,&d[0]);
1162
1163 for (i=1;i<sz;i++)
1164 {
1165 zzn2_sqr_i(&e[i-1],&T);
1166 zzn2_mul_i(&d[i],&T,&d[i]); /** */
1167 }
1168
1169 zzn2_mul_i(&W,&d[0],&W);
1170 zzn2_sqr_i(&W,&A);
1171 zzn2_sub_i(&A,&(PT[0].x),&A);
1172 zzn2_sub_i(&A,&(PT[0].x),&A);
1173 zzn2_sub_i(&(PT[0].x),&A,&B);
1174 zzn2_mul_i(&B,&W,&B);
1175 zzn2_sub_i(&B,&(PT[0].y),&B);
1176
1177 zzn2_sub_i(&B,&(PT[0].y),&T);
1178 zzn2_mul_i(&T,&d[1],&T);
1179
1180 zzn2_sqr_i(&T,&(PT[1].x));
1181 zzn2_sub_i(&(PT[1].x),&A,&(PT[1].x));
1182 zzn2_sub_i(&(PT[1].x),&(PT[0].x),&(PT[1].x));
1183
1184 zzn2_sub_i(&A,&(PT[1].x),&(PT[1].y));
1185 zzn2_mul_i(&(PT[1].y),&T,&(PT[1].y));
1186 zzn2_sub_i(&(PT[1].y),&B,&(PT[1].y));
1187
1188 for (i=2;i<sz;i++)
1189 {
1190 zzn2_sub_i(&(PT[i-1].y),&B,&T);
1191 zzn2_mul_i(&T,&d[i],&T);
1192
1193 zzn2_sqr_i(&T,&(PT[i].x));
1194 zzn2_sub_i(&(PT[i].x),&A,&(PT[i].x));
1195 zzn2_sub_i(&(PT[i].x),&(PT[i-1].x),&(PT[i].x));
1196
1197 zzn2_sub_i(&A,&(PT[i].x),&(PT[i].y));
1198 zzn2_mul_i(&(PT[i].y),&T,&(PT[i].y));
1199 zzn2_sub_i(&(PT[i].y),&B,&(PT[i].y));
1200 }
1201 for (i=0;i<sz;i++) PT[i].marker=MR_EPOINT_NORMALIZED;
1202
1203 #ifndef MR_STATIC
1204 memkill(_MIPP_ mem, MR_DOS_2);
1205 #else
1206 memset(mem, 0, MR_BIG_RESERVE(MR_DOS_2));
1207 #endif
1208 }
1209
1210 #ifndef MR_DOUBLE_BIG
1211 #define MR_MUL_RESERVE (1+4*MR_STR_SZ_2)
1212 #else
1213 #define MR_MUL_RESERVE (2+4*MR_STR_SZ_2)
1214 #endif
1215
ecn2_mul(_MIPD_ big k,ecn2 * P)1216 int ecn2_mul(_MIPD_ big k,ecn2 *P)
1217 {
1218 int i,j,nb,n,nbs,nzs,nadds;
1219 big h;
1220 ecn2 T[MR_STR_SZ_2];
1221 #ifdef MR_OS_THREADS
1222 miracl *mr_mip=get_mip();
1223 #endif
1224
1225 #ifndef MR_STATIC
1226 char *mem = memalloc(_MIPP_ MR_MUL_RESERVE);
1227 #else
1228 char mem[MR_BIG_RESERVE(MR_MUL_RESERVE)];
1229 memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
1230 #endif
1231
1232 j=0;
1233 #ifndef MR_DOUBLE_BIG
1234 h=mirvar_mem(_MIPP_ mem, j++);
1235 #else
1236 h=mirvar_mem(_MIPP_ mem, j); j+=2;
1237 #endif
1238 for (i=0;i<MR_STR_SZ_2;i++)
1239 {
1240 T[i].x.a= mirvar_mem(_MIPP_ mem, j++);
1241 T[i].x.b= mirvar_mem(_MIPP_ mem, j++);
1242 T[i].y.a= mirvar_mem(_MIPP_ mem, j++);
1243 T[i].y.b= mirvar_mem(_MIPP_ mem, j++);
1244 }
1245
1246 MR_IN(207)
1247
1248 ecn2_norm(_MIPP_ P);
1249
1250 nadds=0;
1251 premult(_MIPP_ k,3,h);
1252 ecn2_copy(P,&T[0]);
1253 ecn2_dos(_MIPP_ MR_WIN_SZ_2,T);
1254 nb=logb2(_MIPP_ h);
1255
1256 for (i=nb-2;i>=1;)
1257 {
1258 if (mr_mip->user!=NULL) (*mr_mip->user)();
1259 n=mr_naf_window(_MIPP_ k,h,i,&nbs,&nzs,MR_WIN_SZ_2);
1260
1261 for (j=0;j<nbs;j++) ecn2_add(_MIPP_ P,P);
1262
1263 if (n>0) {nadds++; ecn2_add(_MIPP_ &T[n/2],P);}
1264 if (n<0) {nadds++; ecn2_sub(_MIPP_ &T[(-n)/2],P);}
1265 i-=nbs;
1266 if (nzs)
1267 {
1268 for (j=0;j<nzs;j++) ecn2_add(_MIPP_ P,P);
1269 i-=nzs;
1270 }
1271 }
1272
1273 ecn2_norm(_MIPP_ P);
1274
1275 MR_OUT
1276
1277 #ifndef MR_STATIC
1278 memkill(_MIPP_ mem, MR_MUL_RESERVE);
1279 #else
1280 memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
1281 #endif
1282 return nadds;
1283 }
1284
1285 /* Double addition, using Joint Sparse Form */
1286 /* R=aP+bQ */
1287
1288 #define MR_MUL2_JSF_RESERVE 20
1289
ecn2_mul2_jsf(_MIPD_ big a,ecn2 * P,big b,ecn2 * Q,ecn2 * R)1290 int ecn2_mul2_jsf(_MIPD_ big a,ecn2 *P,big b,ecn2 *Q,ecn2 *R)
1291 {
1292 int e1,h1,e2,h2,bb,nadds;
1293 ecn2 P1,P2,PS,PD;
1294 big c,d,e,f;
1295 #ifdef MR_OS_THREADS
1296 miracl *mr_mip=get_mip();
1297 #endif
1298
1299 #ifndef MR_STATIC
1300 char *mem = memalloc(_MIPP_ MR_MUL2_JSF_RESERVE);
1301 #else
1302 char mem[MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE)];
1303 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
1304 #endif
1305
1306 c = mirvar_mem(_MIPP_ mem, 0);
1307 d = mirvar_mem(_MIPP_ mem, 1);
1308 e = mirvar_mem(_MIPP_ mem, 2);
1309 f = mirvar_mem(_MIPP_ mem, 3);
1310 P1.x.a= mirvar_mem(_MIPP_ mem, 4);
1311 P1.x.b= mirvar_mem(_MIPP_ mem, 5);
1312 P1.y.a= mirvar_mem(_MIPP_ mem, 6);
1313 P1.y.b= mirvar_mem(_MIPP_ mem, 7);
1314 P2.x.a= mirvar_mem(_MIPP_ mem, 8);
1315 P2.x.b= mirvar_mem(_MIPP_ mem, 9);
1316 P2.y.a= mirvar_mem(_MIPP_ mem, 10);
1317 P2.y.b= mirvar_mem(_MIPP_ mem, 11);
1318 PS.x.a= mirvar_mem(_MIPP_ mem, 12);
1319 PS.x.b= mirvar_mem(_MIPP_ mem, 13);
1320 PS.y.a= mirvar_mem(_MIPP_ mem, 14);
1321 PS.y.b= mirvar_mem(_MIPP_ mem, 15);
1322 PD.x.a= mirvar_mem(_MIPP_ mem, 16);
1323 PD.x.b= mirvar_mem(_MIPP_ mem, 17);
1324 PD.y.a= mirvar_mem(_MIPP_ mem, 18);
1325 PD.y.b= mirvar_mem(_MIPP_ mem, 19);
1326
1327 MR_IN(206)
1328
1329 ecn2_norm(_MIPP_ Q);
1330 ecn2_copy(Q,&P2);
1331
1332 copy(b,d);
1333 if (size(d)<0)
1334 {
1335 negify(d,d);
1336 ecn2_negate(_MIPP_ &P2,&P2);
1337 }
1338
1339 ecn2_norm(_MIPP_ P);
1340 ecn2_copy(P,&P1);
1341
1342 copy(a,c);
1343 if (size(c)<0)
1344 {
1345 negify(c,c);
1346 ecn2_negate(_MIPP_ &P1,&P1);
1347 }
1348
1349 mr_jsf(_MIPP_ d,c,e,d,f,c); /* calculate joint sparse form */
1350
1351 if (compare(e,f)>0) bb=logb2(_MIPP_ e)-1;
1352 else bb=logb2(_MIPP_ f)-1;
1353
1354 ecn2_add_sub(_MIPP_ &P1,&P2,&PS,&PD);
1355 ecn2_zero(R);
1356 nadds=0;
1357 while (bb>=0)
1358 { /* add/subtract method */
1359 if (mr_mip->user!=NULL) (*mr_mip->user)();
1360 ecn2_add(_MIPP_ R,R);
1361 e1=h1=e2=h2=0;
1362
1363 if (mr_testbit(_MIPP_ d,bb)) e2=1;
1364 if (mr_testbit(_MIPP_ e,bb)) h2=1;
1365 if (mr_testbit(_MIPP_ c,bb)) e1=1;
1366 if (mr_testbit(_MIPP_ f,bb)) h1=1;
1367
1368 if (e1!=h1)
1369 {
1370 if (e2==h2)
1371 {
1372 if (h1==1) {ecn2_add(_MIPP_ &P1,R); nadds++;}
1373 else {ecn2_sub(_MIPP_ &P1,R); nadds++;}
1374 }
1375 else
1376 {
1377 if (h1==1)
1378 {
1379 if (h2==1) {ecn2_add(_MIPP_ &PS,R); nadds++;}
1380 else {ecn2_add(_MIPP_ &PD,R); nadds++;}
1381 }
1382 else
1383 {
1384 if (h2==1) {ecn2_sub(_MIPP_ &PD,R); nadds++;}
1385 else {ecn2_sub(_MIPP_ &PS,R); nadds++;}
1386 }
1387 }
1388 }
1389 else if (e2!=h2)
1390 {
1391 if (h2==1) {ecn2_add(_MIPP_ &P2,R); nadds++;}
1392 else {ecn2_sub(_MIPP_ &P2,R); nadds++;}
1393 }
1394 bb-=1;
1395 }
1396 ecn2_norm(_MIPP_ R);
1397
1398 MR_OUT
1399 #ifndef MR_STATIC
1400 memkill(_MIPP_ mem, MR_MUL2_JSF_RESERVE);
1401 #else
1402 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
1403 #endif
1404 return nadds;
1405
1406 }
1407
1408 /* General purpose multi-exponentiation engine, using inter-leaving algorithm. Calculate aP+bQ+cR+dS...
1409 Inputs are divided into two groups of sizes wa<4 and wb<4. For the first group if the points are fixed the
1410 first precomputed Table Ta[] may be taken from ROM. For the second group if the points are variable Tb[j] will
1411 have to computed online. Each group has its own window size, wina (=5?) and winb (=4?) respectively. The values
1412 a,b,c.. are provided in ma[] and mb[], and 3.a,3.b,3.c (as required by the NAF) are provided in ma3[] and
1413 mb3[]. If only one group is required, set wb=0 and pass NULL pointers.
1414 */
1415
ecn2_muln_engine(_MIPD_ int wa,int wina,int wb,int winb,big * ma,big * ma3,big * mb,big * mb3,ecn2 * Ta,ecn2 * Tb,ecn2 * R)1416 int ecn2_muln_engine(_MIPD_ int wa,int wina,int wb,int winb,big *ma,big *ma3,big *mb,big *mb3,ecn2 *Ta,ecn2 *Tb,ecn2 *R)
1417 { /* general purpose interleaving algorithm engine for multi-exp */
1418 int i,j,tba[4],pba[4],na[4],sa[4],tbb[4],pbb[4],nb[4],sb[4],nbits,nbs,nzs;
1419 int sza,szb,nadds;
1420 #ifdef MR_OS_THREADS
1421 miracl *mr_mip=get_mip();
1422 #endif
1423
1424 sza=calc_n(wina);
1425 szb=calc_n(winb);
1426
1427 ecn2_zero(R);
1428
1429 nbits=0;
1430 for (i=0;i<wa;i++) {sa[i]=exsign(ma[i]); tba[i]=0; j=logb2(_MIPP_ ma3[i]); if (j>nbits) nbits=j; }
1431 for (i=0;i<wb;i++) {sb[i]=exsign(mb[i]); tbb[i]=0; j=logb2(_MIPP_ mb3[i]); if (j>nbits) nbits=j; }
1432
1433 nadds=0;
1434 for (i=nbits-1;i>=1;i--)
1435 {
1436 if (mr_mip->user!=NULL) (*mr_mip->user)();
1437 if (R->marker!=MR_EPOINT_INFINITY) ecn2_add(_MIPP_ R,R);
1438 for (j=0;j<wa;j++)
1439 { /* deal with the first group */
1440 if (tba[j]==0)
1441 {
1442 na[j]=mr_naf_window(_MIPP_ ma[j],ma3[j],i,&nbs,&nzs,wina);
1443 tba[j]=nbs+nzs;
1444 pba[j]=nbs;
1445 }
1446 tba[j]--; pba[j]--;
1447 if (pba[j]==0)
1448 {
1449 if (sa[j]==PLUS)
1450 {
1451 if (na[j]>0) {ecn2_add(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
1452 if (na[j]<0) {ecn2_sub(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
1453 }
1454 else
1455 {
1456 if (na[j]>0) {ecn2_sub(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
1457 if (na[j]<0) {ecn2_add(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
1458 }
1459 }
1460 }
1461 for (j=0;j<wb;j++)
1462 { /* deal with the second group */
1463 if (tbb[j]==0)
1464 {
1465 nb[j]=mr_naf_window(_MIPP_ mb[j],mb3[j],i,&nbs,&nzs,winb);
1466 tbb[j]=nbs+nzs;
1467 pbb[j]=nbs;
1468 }
1469 tbb[j]--; pbb[j]--;
1470 if (pbb[j]==0)
1471 {
1472 if (sb[j]==PLUS)
1473 {
1474 if (nb[j]>0) {ecn2_add(_MIPP_ &Tb[j*szb+nb[j]/2],R); nadds++;}
1475 if (nb[j]<0) {ecn2_sub(_MIPP_ &Tb[j*szb+(-nb[j])/2],R); nadds++;}
1476 }
1477 else
1478 {
1479 if (nb[j]>0) {ecn2_sub(_MIPP_ &Tb[j*szb+nb[j]/2],R); nadds++;}
1480 if (nb[j]<0) {ecn2_add(_MIPP_ &Tb[j*szb+(-nb[j])/2],R); nadds++;}
1481 }
1482 }
1483 }
1484 }
1485 ecn2_norm(_MIPP_ R);
1486 return nadds;
1487 }
1488
1489 /* Routines to support Galbraith, Lin, Scott (GLS) method for ECC */
1490 /* requires an endomorphism psi */
1491
1492 /* *********************** */
1493
1494 /* Precompute T - first half from i.P, second half from i.psi(P) */
1495
ecn2_precomp_gls(_MIPD_ int win,ecn2 * P,zzn2 * psi,ecn2 * T)1496 void ecn2_precomp_gls(_MIPD_ int win,ecn2 *P,zzn2 *psi,ecn2 *T)
1497 {
1498 int i,j,sz;
1499
1500 #ifdef MR_OS_THREADS
1501 miracl *mr_mip=get_mip();
1502 #endif
1503
1504 j=0;
1505 sz=calc_n(win);
1506
1507 MR_IN(219)
1508
1509 ecn2_norm(_MIPP_ P);
1510 ecn2_copy(P,&T[0]);
1511
1512 ecn2_dos(_MIPP_ win,T); /* precompute table */
1513
1514 for (i=sz;i<sz+sz;i++)
1515 {
1516 ecn2_copy(&T[i-sz],&T[i]);
1517 ecn2_psi(_MIPP_ psi,&T[i]);
1518 }
1519
1520 MR_OUT
1521 }
1522
1523 /* Calculate a[0].P+a[1].psi(P) using interleaving method */
1524
1525 #define MR_MUL2_GLS_RESERVE (2+2*MR_STR_SZ_2*4)
1526
ecn2_mul2_gls(_MIPD_ big * a,ecn2 * P,zzn2 * psi,ecn2 * R)1527 int ecn2_mul2_gls(_MIPD_ big *a,ecn2 *P,zzn2 *psi,ecn2 *R)
1528 {
1529 int i,j,nadds;
1530 ecn2 T[2*MR_STR_SZ_2];
1531 big a3[2];
1532 #ifdef MR_OS_THREADS
1533 miracl *mr_mip=get_mip();
1534 #endif
1535
1536 #ifndef MR_STATIC
1537 char *mem = memalloc(_MIPP_ MR_MUL2_GLS_RESERVE);
1538 #else
1539 char mem[MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE)];
1540 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE));
1541 #endif
1542
1543 for (j=i=0;i<2;i++)
1544 a3[i]=mirvar_mem(_MIPP_ mem, j++);
1545
1546 for (i=0;i<2*MR_STR_SZ_2;i++)
1547 {
1548 T[i].x.a=mirvar_mem(_MIPP_ mem, j++);
1549 T[i].x.b=mirvar_mem(_MIPP_ mem, j++);
1550 T[i].y.a=mirvar_mem(_MIPP_ mem, j++);
1551 T[i].y.b=mirvar_mem(_MIPP_ mem, j++);
1552 T[i].marker=MR_EPOINT_INFINITY;
1553 }
1554 MR_IN(220)
1555
1556 ecn2_precomp_gls(_MIPP_ MR_WIN_SZ_2,P,psi,T);
1557
1558 for (i=0;i<2;i++) premult(_MIPP_ a[i],3,a3[i]); /* calculate for NAF */
1559
1560 nadds=ecn2_muln_engine(_MIPP_ 0,0,2,MR_WIN_SZ_2,NULL,NULL,a,a3,NULL,T,R);
1561
1562 ecn2_norm(_MIPP_ R);
1563
1564 MR_OUT
1565
1566 #ifndef MR_STATIC
1567 memkill(_MIPP_ mem, MR_MUL2_GLS_RESERVE);
1568 #else
1569 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE));
1570 #endif
1571 return nadds;
1572 }
1573
1574 /* Calculates a[0]*P+a[1]*psi(P) + b[0]*Q+b[1]*psi(Q)
1575 where P is fixed, and precomputations are already done off-line into FT
1576 using ecn2_precomp_gls. Useful for signature verification */
1577
1578 #define MR_MUL4_GLS_V_RESERVE (4+2*MR_STR_SZ_2*4)
1579
ecn2_mul4_gls_v(_MIPD_ big * a,ecn2 * FT,big * b,ecn2 * Q,zzn2 * psi,ecn2 * R)1580 int ecn2_mul4_gls_v(_MIPD_ big *a,ecn2 *FT,big *b,ecn2 *Q,zzn2 *psi,ecn2 *R)
1581 {
1582 int i,j,nadds;
1583 ecn2 VT[2*MR_STR_SZ_2];
1584 big a3[2],b3[2];
1585 #ifdef MR_OS_THREADS
1586 miracl *mr_mip=get_mip();
1587 #endif
1588
1589 #ifndef MR_STATIC
1590 char *mem = memalloc(_MIPP_ MR_MUL4_GLS_V_RESERVE);
1591 #else
1592 char mem[MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE)];
1593 memset(mem, 0, MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE));
1594 #endif
1595 j=0;
1596 for (i=0;i<2;i++)
1597 {
1598 a3[i]=mirvar_mem(_MIPP_ mem, j++);
1599 b3[i]=mirvar_mem(_MIPP_ mem, j++);
1600 }
1601 for (i=0;i<2*MR_STR_SZ_2;i++)
1602 {
1603 VT[i].x.a=mirvar_mem(_MIPP_ mem, j++);
1604 VT[i].x.b=mirvar_mem(_MIPP_ mem, j++);
1605 VT[i].y.a=mirvar_mem(_MIPP_ mem, j++);
1606 VT[i].y.b=mirvar_mem(_MIPP_ mem, j++);
1607 VT[i].marker=MR_EPOINT_INFINITY;
1608 }
1609
1610 MR_IN(217)
1611
1612 ecn2_precomp_gls(_MIPP_ MR_WIN_SZ_2,Q,psi,VT); /* precompute for the variable points */
1613 for (i=0;i<2;i++)
1614 { /* needed for NAF */
1615 premult(_MIPP_ a[i],3,a3[i]);
1616 premult(_MIPP_ b[i],3,b3[i]);
1617 }
1618 nadds=ecn2_muln_engine(_MIPP_ 2,MR_WIN_SZ_2P,2,MR_WIN_SZ_2,a,a3,b,b3,FT,VT,R);
1619 ecn2_norm(_MIPP_ R);
1620
1621 MR_OUT
1622
1623 #ifndef MR_STATIC
1624 memkill(_MIPP_ mem, MR_MUL4_GLS_V_RESERVE);
1625 #else
1626 memset(mem, 0, MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE));
1627 #endif
1628 return nadds;
1629 }
1630
1631 /* Calculate a.P+b.Q using interleaving method. P is fixed and FT is precomputed from it */
1632
ecn2_precomp(_MIPD_ int win,ecn2 * P,ecn2 * T)1633 void ecn2_precomp(_MIPD_ int win,ecn2 *P,ecn2 *T)
1634 {
1635 int sz;
1636
1637 #ifdef MR_OS_THREADS
1638 miracl *mr_mip=get_mip();
1639 #endif
1640
1641 sz=calc_n(win);
1642
1643 MR_IN(216)
1644
1645 ecn2_norm(_MIPP_ P);
1646 ecn2_copy(P,&T[0]);
1647 ecn2_dos(_MIPP_ win,T);
1648
1649 MR_OUT
1650 }
1651
1652 #ifndef MR_DOUBLE_BIG
1653 #define MR_MUL2_RESERVE (2+2*MR_STR_SZ_2*4)
1654 #else
1655 #define MR_MUL2_RESERVE (4+2*MR_STR_SZ_2*4)
1656 #endif
1657
ecn2_mul2(_MIPD_ big a,ecn2 * FT,big b,ecn2 * Q,ecn2 * R)1658 int ecn2_mul2(_MIPD_ big a,ecn2 *FT,big b,ecn2 *Q,ecn2 *R)
1659 {
1660 int i,j,nadds;
1661 ecn2 T[2*MR_STR_SZ_2];
1662 big a3,b3;
1663 #ifdef MR_OS_THREADS
1664 miracl *mr_mip=get_mip();
1665 #endif
1666
1667 #ifndef MR_STATIC
1668 char *mem = memalloc(_MIPP_ MR_MUL2_RESERVE);
1669 #else
1670 char mem[MR_BIG_RESERVE(MR_MUL2_RESERVE)];
1671 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_RESERVE));
1672 #endif
1673
1674 j=0;
1675 #ifndef MR_DOUBLE_BIG
1676 a3=mirvar_mem(_MIPP_ mem, j++);
1677 b3=mirvar_mem(_MIPP_ mem, j++);
1678 #else
1679 a3=mirvar_mem(_MIPP_ mem, j); j+=2;
1680 b3=mirvar_mem(_MIPP_ mem, j); j+=2;
1681 #endif
1682 for (i=0;i<2*MR_STR_SZ_2;i++)
1683 {
1684 T[i].x.a=mirvar_mem(_MIPP_ mem, j++);
1685 T[i].x.b=mirvar_mem(_MIPP_ mem, j++);
1686 T[i].y.a=mirvar_mem(_MIPP_ mem, j++);
1687 T[i].y.b=mirvar_mem(_MIPP_ mem, j++);
1688 T[i].marker=MR_EPOINT_INFINITY;
1689 }
1690
1691 MR_IN(218)
1692
1693 ecn2_precomp(_MIPP_ MR_WIN_SZ_2,Q,T);
1694
1695 premult(_MIPP_ a,3,a3);
1696 premult(_MIPP_ b,3,b3);
1697
1698 nadds=ecn2_muln_engine(_MIPP_ 1,MR_WIN_SZ_2P,1,MR_WIN_SZ_2,&a,&a3,&b,&b3,FT,T,R);
1699
1700 ecn2_norm(_MIPP_ R);
1701
1702 MR_OUT
1703
1704 #ifndef MR_STATIC
1705 memkill(_MIPP_ mem, MR_MUL2_RESERVE);
1706 #else
1707 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_RESERVE));
1708 #endif
1709 return nadds;
1710 }
1711
1712
1713 #ifndef MR_STATIC
1714
ecn2_brick_init(_MIPD_ ebrick * B,zzn2 * x,zzn2 * y,big a,big b,big n,int window,int nb)1715 BOOL ecn2_brick_init(_MIPD_ ebrick *B,zzn2 *x,zzn2 *y,big a,big b,big n,int window,int nb)
1716 { /* Uses Montgomery arithmetic internally *
1717 * (x,y) is the fixed base *
1718 * a,b and n are parameters and modulus of the curve *
1719 * window is the window size in bits and *
1720 * nb is the maximum number of bits in the multiplier */
1721 int i,j,k,t,bp,len,bptr;
1722 ecn2 *table;
1723 ecn2 w;
1724
1725 #ifdef MR_OS_THREADS
1726 miracl *mr_mip=get_mip();
1727 #endif
1728
1729 if (nb<2 || window<1 || window>nb || mr_mip->ERNUM) return FALSE;
1730
1731 t=MR_ROUNDUP(nb,window);
1732
1733 if (t<2) return FALSE;
1734
1735 MR_IN(221)
1736
1737 #ifndef MR_ALWAYS_BINARY
1738 if (mr_mip->base != mr_mip->base2)
1739 {
1740 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
1741 MR_OUT
1742 return FALSE;
1743 }
1744 #endif
1745
1746 B->window=window;
1747 B->max=nb;
1748 table=mr_alloc(_MIPP_ (1<<window),sizeof(ecn2));
1749 if (table==NULL)
1750 {
1751 mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);
1752 MR_OUT
1753 return FALSE;
1754 }
1755 B->a=mirvar(_MIPP_ 0);
1756 B->b=mirvar(_MIPP_ 0);
1757 B->n=mirvar(_MIPP_ 0);
1758 copy(a,B->a);
1759 copy(b,B->b);
1760 copy(n,B->n);
1761
1762 ecurve_init(_MIPP_ a,b,n,MR_AFFINE);
1763 mr_mip->TWIST=TRUE;
1764
1765 w.x.a=mirvar(_MIPP_ 0);
1766 w.x.b=mirvar(_MIPP_ 0);
1767 w.y.a=mirvar(_MIPP_ 0);
1768 w.y.b=mirvar(_MIPP_ 0);
1769 w.marker=MR_EPOINT_INFINITY;
1770 ecn2_set(_MIPP_ x,y,&w);
1771
1772 table[0].x.a=mirvar(_MIPP_ 0);
1773 table[0].x.b=mirvar(_MIPP_ 0);
1774 table[0].y.a=mirvar(_MIPP_ 0);
1775 table[0].y.b=mirvar(_MIPP_ 0);
1776 table[0].marker=MR_EPOINT_INFINITY;
1777 table[1].x.a=mirvar(_MIPP_ 0);
1778 table[1].x.b=mirvar(_MIPP_ 0);
1779 table[1].y.a=mirvar(_MIPP_ 0);
1780 table[1].y.b=mirvar(_MIPP_ 0);
1781 table[1].marker=MR_EPOINT_INFINITY;
1782
1783 ecn2_copy(&w,&table[1]);
1784 for (j=0;j<t;j++)
1785 ecn2_add(_MIPP_ &w,&w);
1786
1787 k=1;
1788 for (i=2;i<(1<<window);i++)
1789 {
1790 table[i].x.a=mirvar(_MIPP_ 0);
1791 table[i].x.b=mirvar(_MIPP_ 0);
1792 table[i].y.a=mirvar(_MIPP_ 0);
1793 table[i].y.b=mirvar(_MIPP_ 0);
1794 table[i].marker=MR_EPOINT_INFINITY;
1795 if (i==(1<<k))
1796 {
1797 k++;
1798 ecn2_copy(&w,&table[i]);
1799
1800 for (j=0;j<t;j++)
1801 ecn2_add(_MIPP_ &w,&w);
1802 continue;
1803 }
1804 bp=1;
1805 for (j=0;j<k;j++)
1806 {
1807 if (i&bp)
1808 ecn2_add(_MIPP_ &table[1<<j],&table[i]);
1809 bp<<=1;
1810 }
1811 }
1812 mr_free(w.x.a);
1813 mr_free(w.x.b);
1814 mr_free(w.y.a);
1815 mr_free(w.y.b);
1816
1817 /* create the table */
1818
1819 len=n->len;
1820 bptr=0;
1821 B->table=mr_alloc(_MIPP_ 4*len*(1<<window),sizeof(mr_small));
1822
1823 for (i=0;i<(1<<window);i++)
1824 {
1825 for (j=0;j<len;j++) B->table[bptr++]=table[i].x.a->w[j];
1826 for (j=0;j<len;j++) B->table[bptr++]=table[i].x.b->w[j];
1827
1828 for (j=0;j<len;j++) B->table[bptr++]=table[i].y.a->w[j];
1829 for (j=0;j<len;j++) B->table[bptr++]=table[i].y.b->w[j];
1830
1831 mr_free(table[i].x.a);
1832 mr_free(table[i].x.b);
1833 mr_free(table[i].y.a);
1834 mr_free(table[i].y.b);
1835 }
1836
1837 mr_free(table);
1838
1839 MR_OUT
1840 return TRUE;
1841 }
1842
ecn2_brick_end(ebrick * B)1843 void ecn2_brick_end(ebrick *B)
1844 {
1845 mirkill(B->n);
1846 mirkill(B->b);
1847 mirkill(B->a);
1848 mr_free(B->table);
1849 }
1850
1851 #else
1852
1853 /* use precomputated table in ROM */
1854
ecn2_brick_init(ebrick * B,const mr_small * rom,big a,big b,big n,int window,int nb)1855 void ecn2_brick_init(ebrick *B,const mr_small* rom,big a,big b,big n,int window,int nb)
1856 {
1857 B->table=rom;
1858 B->a=a; /* just pass a pointer */
1859 B->b=b;
1860 B->n=n;
1861 B->window=window; /* 2^4=16 stored values */
1862 B->max=nb;
1863 }
1864
1865 #endif
1866
1867 /*
1868 void ecn2_mul_brick(_MIPD_ ebrick *B,big e,zzn2 *x,zzn2 *y)
1869 {
1870 int i,j,t,len,maxsize,promptr;
1871 ecn2 w,z;
1872
1873 #ifdef MR_STATIC
1874 char mem[MR_BIG_RESERVE(10)];
1875 #else
1876 char *mem;
1877 #endif
1878 #ifdef MR_OS_THREADS
1879 miracl *mr_mip=get_mip();
1880 #endif
1881
1882 if (size(e)<0) mr_berror(_MIPP_ MR_ERR_NEG_POWER);
1883 t=MR_ROUNDUP(B->max,B->window);
1884
1885 MR_IN(116)
1886
1887 #ifndef MR_ALWAYS_BINARY
1888 if (mr_mip->base != mr_mip->base2)
1889 {
1890 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
1891 MR_OUT
1892 return;
1893 }
1894 #endif
1895
1896 if (logb2(_MIPP_ e) > B->max)
1897 {
1898 mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
1899 MR_OUT
1900 return;
1901 }
1902
1903 ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
1904 mr_mip->TWIST=TRUE;
1905
1906 #ifdef MR_STATIC
1907 memset(mem,0,MR_BIG_RESERVE(10));
1908 #else
1909 mem=memalloc(_MIPP_ 10);
1910 #endif
1911
1912 w.x.a=mirvar_mem(_MIPP_ mem, 0);
1913 w.x.b=mirvar_mem(_MIPP_ mem, 1);
1914 w.y.a=mirvar_mem(_MIPP_ mem, 2);
1915 w.y.b=mirvar_mem(_MIPP_ mem, 3);
1916 w.z.a=mirvar_mem(_MIPP_ mem, 4);
1917 w.z.b=mirvar_mem(_MIPP_ mem, 5);
1918 w.marker=MR_EPOINT_INFINITY;
1919 z.x.a=mirvar_mem(_MIPP_ mem, 6);
1920 z.x.b=mirvar_mem(_MIPP_ mem, 7);
1921 z.y.a=mirvar_mem(_MIPP_ mem, 8);
1922 z.y.b=mirvar_mem(_MIPP_ mem, 9);
1923 z.marker=MR_EPOINT_INFINITY;
1924
1925 len=B->n->len;
1926 maxsize=4*(1<<B->window)*len;
1927
1928 for (i=t-1;i>=0;i--)
1929 {
1930 j=recode(_MIPP_ e,t,B->window,i);
1931 ecn2_add(_MIPP_ &w,&w);
1932 if (j>0)
1933 {
1934 promptr=4*j*len;
1935 init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
1936 init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
1937 init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
1938 init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
1939 z.marker=MR_EPOINT_NORMALIZED;
1940 ecn2_add(_MIPP_ &z,&w);
1941 }
1942 }
1943 ecn2_norm(_MIPP_ &w);
1944 ecn2_getxy(&w,x,y);
1945 #ifndef MR_STATIC
1946 memkill(_MIPP_ mem,10);
1947 #else
1948 memset(mem,0,MR_BIG_RESERVE(10));
1949 #endif
1950 MR_OUT
1951 }
1952 */
1953
ecn2_mul_brick_gls(_MIPD_ ebrick * B,big * e,zzn2 * psi,zzn2 * x,zzn2 * y)1954 void ecn2_mul_brick_gls(_MIPD_ ebrick *B,big *e,zzn2 *psi,zzn2 *x,zzn2 *y)
1955 {
1956 int i,j,k,t,len,maxsize,promptr,se[2];
1957 ecn2 w,z;
1958
1959 #ifdef MR_STATIC
1960 char mem[MR_BIG_RESERVE(10)];
1961 #else
1962 char *mem;
1963 #endif
1964 #ifdef MR_OS_THREADS
1965 miracl *mr_mip=get_mip();
1966 #endif
1967
1968 for (k=0;k<2;k++) se[k]=exsign(e[k]);
1969
1970 t=MR_ROUNDUP(B->max,B->window);
1971
1972 MR_IN(222)
1973
1974 #ifndef MR_ALWAYS_BINARY
1975 if (mr_mip->base != mr_mip->base2)
1976 {
1977 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
1978 MR_OUT
1979 return;
1980 }
1981 #endif
1982
1983 if (logb2(_MIPP_ e[0])>B->max || logb2(_MIPP_ e[1])>B->max)
1984 {
1985 mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
1986 MR_OUT
1987 return;
1988 }
1989
1990 ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
1991 mr_mip->TWIST=TRUE;
1992
1993 #ifdef MR_STATIC
1994 memset(mem,0,MR_BIG_RESERVE(10));
1995 #else
1996 mem=memalloc(_MIPP_ 10);
1997 #endif
1998
1999 z.x.a=mirvar_mem(_MIPP_ mem, 0);
2000 z.x.b=mirvar_mem(_MIPP_ mem, 1);
2001 z.y.a=mirvar_mem(_MIPP_ mem, 2);
2002 z.y.b=mirvar_mem(_MIPP_ mem, 3);
2003 z.marker=MR_EPOINT_INFINITY;
2004
2005 w.x.a=mirvar_mem(_MIPP_ mem, 4);
2006 w.x.b=mirvar_mem(_MIPP_ mem, 5);
2007 w.y.a=mirvar_mem(_MIPP_ mem, 6);
2008 w.y.b=mirvar_mem(_MIPP_ mem, 7);
2009 #ifndef MR_AFFINE_ONLY
2010 w.z.a=mirvar_mem(_MIPP_ mem, 8);
2011 w.z.b=mirvar_mem(_MIPP_ mem, 9);
2012 #endif
2013 w.marker=MR_EPOINT_INFINITY;
2014
2015 len=B->n->len;
2016 maxsize=4*(1<<B->window)*len;
2017
2018 for (i=t-1;i>=0;i--)
2019 {
2020 ecn2_add(_MIPP_ &w,&w);
2021 for (k=0;k<2;k++)
2022 {
2023 j=recode(_MIPP_ e[k],t,B->window,i);
2024 if (j>0)
2025 {
2026 promptr=4*j*len;
2027 init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
2028 init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
2029 init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
2030 init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
2031 z.marker=MR_EPOINT_NORMALIZED;
2032 if (k==1) ecn2_psi(_MIPP_ psi,&z);
2033 if (se[k]==PLUS) ecn2_add(_MIPP_ &z,&w);
2034 else ecn2_sub(_MIPP_ &z,&w);
2035 }
2036 }
2037 }
2038 ecn2_norm(_MIPP_ &w);
2039 ecn2_getxy(&w,x,y);
2040 #ifndef MR_STATIC
2041 memkill(_MIPP_ mem,10);
2042 #else
2043 memset(mem,0,MR_BIG_RESERVE(10));
2044 #endif
2045 MR_OUT
2046 }
2047
2048