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 E(F_p^2) support functions
37 * mrecn2.c
38 */
39
40 #include <stdlib.h>
41 #include "miracl.h"
42 #ifdef MR_STATIC
43 #include <string.h>
44 #endif
45
46 #ifndef MR_EDWARDS
47
ecn2_iszero(ecn2 * a)48 BOOL ecn2_iszero(ecn2 *a)
49 {
50 if (a->marker==MR_EPOINT_INFINITY) return TRUE;
51 return FALSE;
52 }
53
ecn2_copy(ecn2 * a,ecn2 * b)54 void ecn2_copy(ecn2 *a,ecn2 *b)
55 {
56 zzn2_copy(&(a->x),&(b->x));
57 zzn2_copy(&(a->y),&(b->y));
58 #ifndef MR_AFFINE_ONLY
59 if (a->marker==MR_EPOINT_GENERAL) zzn2_copy(&(a->z),&(b->z));
60 #endif
61 b->marker=a->marker;
62 }
63
ecn2_zero(ecn2 * a)64 void ecn2_zero(ecn2 *a)
65 {
66 zzn2_zero(&(a->x)); zzn2_zero(&(a->y));
67 #ifndef MR_AFFINE_ONLY
68 if (a->marker==MR_EPOINT_GENERAL) zzn2_zero(&(a->z));
69 #endif
70 a->marker=MR_EPOINT_INFINITY;
71 }
72
ecn2_compare(_MIPD_ ecn2 * a,ecn2 * b)73 BOOL ecn2_compare(_MIPD_ ecn2 *a,ecn2 *b)
74 {
75 #ifdef MR_OS_THREADS
76 miracl *mr_mip=get_mip();
77 #endif
78 if (mr_mip->ERNUM) return FALSE;
79
80 MR_IN(193)
81 ecn2_norm(_MIPP_ a);
82 ecn2_norm(_MIPP_ b);
83 MR_OUT
84 if (zzn2_compare(&(a->x),&(b->x)) && zzn2_compare(&(a->y),&(b->y)) && a->marker==b->marker) return TRUE;
85 return FALSE;
86 }
87
ecn2_norm(_MIPD_ ecn2 * a)88 void ecn2_norm(_MIPD_ ecn2 *a)
89 {
90 zzn2 t;
91 #ifdef MR_OS_THREADS
92 miracl *mr_mip=get_mip();
93 #endif
94 #ifndef MR_AFFINE_ONLY
95 if (mr_mip->ERNUM) return;
96 if (a->marker!=MR_EPOINT_GENERAL) return;
97
98 MR_IN(194)
99
100 zzn2_inv(_MIPP_ &(a->z));
101
102 t.a=mr_mip->w3;
103 t.b=mr_mip->w4;
104 zzn2_copy(&(a->z),&t);
105
106 zzn2_sqr(_MIPP_ &(a->z),&(a->z));
107 zzn2_mul(_MIPP_ &(a->x),&(a->z),&(a->x));
108 zzn2_mul(_MIPP_ &(a->z),&t,&(a->z));
109 zzn2_mul(_MIPP_ &(a->y),&(a->z),&(a->y));
110 zzn2_from_zzn(mr_mip->one,&(a->z));
111 a->marker=MR_EPOINT_NORMALIZED;
112
113 MR_OUT
114 #endif
115 }
116
ecn2_get(_MIPD_ ecn2 * e,zzn2 * x,zzn2 * y,zzn2 * z)117 void ecn2_get(_MIPD_ ecn2 *e,zzn2 *x,zzn2 *y,zzn2 *z)
118 {
119 #ifdef MR_OS_THREADS
120 miracl *mr_mip=get_mip();
121 #endif
122
123 zzn2_copy(&(e->x),x);
124 zzn2_copy(&(e->y),y);
125 #ifndef MR_AFFINE_ONLY
126 if (e->marker==MR_EPOINT_GENERAL) zzn2_copy(&(e->z),z);
127 else zzn2_from_zzn(mr_mip->one,z);
128 #endif
129 }
130
ecn2_getxy(ecn2 * e,zzn2 * x,zzn2 * y)131 void ecn2_getxy(ecn2 *e,zzn2 *x,zzn2 *y)
132 {
133 zzn2_copy(&(e->x),x);
134 zzn2_copy(&(e->y),y);
135 }
136
ecn2_getx(ecn2 * e,zzn2 * x)137 void ecn2_getx(ecn2 *e,zzn2 *x)
138 {
139 zzn2_copy(&(e->x),x);
140 }
141
ecn2_psi(_MIPD_ zzn2 * psi,ecn2 * P)142 void ecn2_psi(_MIPD_ zzn2 *psi,ecn2 *P)
143 { /* apply GLS morphism to P */
144 #ifdef MR_OS_THREADS
145 miracl *mr_mip=get_mip();
146 #endif
147
148 MR_IN(212)
149 ecn2_norm(_MIPP_ P);
150 zzn2_conj(_MIPP_ &(P->x),&(P->x));
151 zzn2_conj(_MIPP_ &(P->y),&(P->y));
152 zzn2_mul(_MIPP_ &(P->x),&psi[0],&(P->x));
153 zzn2_mul(_MIPP_ &(P->y),&psi[1],&(P->y));
154
155 MR_OUT
156 }
157
158 #ifndef MR_AFFINE_ONLY
ecn2_getz(_MIPD_ ecn2 * e,zzn2 * z)159 void ecn2_getz(_MIPD_ ecn2 *e,zzn2 *z)
160 {
161 #ifdef MR_OS_THREADS
162 miracl *mr_mip=get_mip();
163 #endif
164
165 if (e->marker==MR_EPOINT_GENERAL) zzn2_copy(&(e->z),z);
166 else zzn2_from_zzn(mr_mip->one,z);
167 }
168 #endif
169
ecn2_rhs(_MIPD_ zzn2 * x,zzn2 * rhs)170 void ecn2_rhs(_MIPD_ zzn2 *x,zzn2 *rhs)
171 { /* calculate RHS of elliptic curve equation */
172 int twist;
173 zzn2 A,B;
174 #ifdef MR_OS_THREADS
175 miracl *mr_mip=get_mip();
176 #endif
177 if (mr_mip->ERNUM) return;
178 twist=mr_mip->TWIST;
179
180 MR_IN(202)
181
182 A.a=mr_mip->w10;
183 A.b=mr_mip->w11;
184 B.a=mr_mip->w12;
185 B.b=mr_mip->w13;
186
187 if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&A);
188 else zzn2_from_zzn(mr_mip->A,&A);
189
190 if (mr_abs(mr_mip->Bsize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Bsize,&B);
191 else zzn2_from_zzn(mr_mip->B,&B);
192
193 if (twist)
194 { /* assume its the quartic or sextic twist, if such is possible */
195 if (twist==MR_QUARTIC_M)
196 {
197 zzn2_mul(_MIPP_ &A,x,&B);
198 zzn2_txx(_MIPP_ &B);
199 }
200 if (twist==MR_QUARTIC_D)
201 {
202 zzn2_mul(_MIPP_ &A,x,&B);
203 zzn2_txd(_MIPP_ &B);
204 }
205 if (twist==MR_SEXTIC_M)
206 {
207 zzn2_txx(_MIPP_ &B);
208 }
209 if (twist==MR_SEXTIC_D)
210 {
211 zzn2_txd(_MIPP_ &B);
212 }
213 if (twist==MR_QUADRATIC)
214 {
215 zzn2_txx(_MIPP_ &B);
216 zzn2_txx(_MIPP_ &B);
217 zzn2_txx(_MIPP_ &B);
218
219 zzn2_mul(_MIPP_ &A,x,&A);
220 zzn2_txx(_MIPP_ &A);
221 zzn2_txx(_MIPP_ &A);
222 zzn2_add(_MIPP_ &B,&A,&B);
223
224 }
225 /*
226 if (mr_mip->Asize==0 || mr_mip->Bsize==0)
227 {
228 if (mr_mip->Asize==0)
229 { // CM Discriminant D=3 - its the sextic twist (Hope I got the right one!). This works for BN curves
230 zzn2_txd(_MIPP_ &B);
231 }
232 if (mr_mip->Bsize==0)
233 { // CM Discriminant D=1 - its the quartic twist.
234 zzn2_mul(_MIPP_ &A,x,&B);
235 zzn2_txx(_MIPP_ &B);
236 }
237 }
238 else
239 { // its the quadratic twist
240
241 zzn2_txx(_MIPP_ &B);
242 zzn2_txx(_MIPP_ &B);
243 zzn2_txx(_MIPP_ &B);
244
245 zzn2_mul(_MIPP_ &A,x,&A);
246 zzn2_txx(_MIPP_ &A);
247 zzn2_txx(_MIPP_ &A);
248 zzn2_add(_MIPP_ &B,&A,&B);
249
250 }
251 */
252 }
253 else
254 {
255 zzn2_mul(_MIPP_ &A,x,&A);
256 zzn2_add(_MIPP_ &B,&A,&B);
257 }
258
259 zzn2_sqr(_MIPP_ x,&A);
260 zzn2_mul(_MIPP_ &A,x,&A);
261 zzn2_add(_MIPP_ &B,&A,rhs);
262
263 MR_OUT
264 }
265
ecn2_set(_MIPD_ zzn2 * x,zzn2 * y,ecn2 * e)266 BOOL ecn2_set(_MIPD_ zzn2 *x,zzn2 *y,ecn2 *e)
267 {
268 zzn2 lhs,rhs;
269 #ifdef MR_OS_THREADS
270 miracl *mr_mip=get_mip();
271 #endif
272 if (mr_mip->ERNUM) return FALSE;
273
274 MR_IN(195)
275
276 lhs.a=mr_mip->w10;
277 lhs.b=mr_mip->w11;
278 rhs.a=mr_mip->w12;
279 rhs.b=mr_mip->w13;
280
281 ecn2_rhs(_MIPP_ x,&rhs);
282
283 zzn2_sqr(_MIPP_ y,&lhs);
284
285 if (!zzn2_compare(&lhs,&rhs))
286 {
287 MR_OUT
288 return FALSE;
289 }
290
291 zzn2_copy(x,&(e->x));
292 zzn2_copy(y,&(e->y));
293
294 e->marker=MR_EPOINT_NORMALIZED;
295
296 MR_OUT
297 return TRUE;
298 }
299
300 #ifndef MR_NOSUPPORT_COMPRESSION
301
302
ecn2_setx(_MIPD_ zzn2 * x,ecn2 * e)303 BOOL ecn2_setx(_MIPD_ zzn2 *x,ecn2 *e)
304 {
305 zzn2 rhs;
306 #ifdef MR_OS_THREADS
307 miracl *mr_mip=get_mip();
308 #endif
309 if (mr_mip->ERNUM) return FALSE;
310
311 MR_IN(201)
312
313 rhs.a=mr_mip->w12;
314 rhs.b=mr_mip->w13;
315
316 ecn2_rhs(_MIPP_ x,&rhs);
317 if (!zzn2_iszero(&rhs))
318 {
319 if (!zzn2_qr(_MIPP_ &rhs))
320 {
321 MR_OUT
322 return FALSE;
323 }
324 zzn2_sqrt(_MIPP_ &rhs,&rhs);
325 }
326
327 zzn2_copy(x,&(e->x));
328 zzn2_copy(&rhs,&(e->y));
329
330 e->marker=MR_EPOINT_NORMALIZED;
331
332 MR_OUT
333 return TRUE;
334 }
335
336 #endif
337
338 #ifndef MR_AFFINE_ONLY
ecn2_setxyz(_MIPD_ zzn2 * x,zzn2 * y,zzn2 * z,ecn2 * e)339 void ecn2_setxyz(_MIPD_ zzn2 *x,zzn2 *y,zzn2 *z,ecn2 *e)
340 {
341 zzn2_copy(x,&(e->x));
342 zzn2_copy(y,&(e->y));
343 zzn2_copy(z,&(e->z));
344
345
346 if (zzn2_isunity(_MIPP_ z)) e->marker=MR_EPOINT_NORMALIZED;
347 else e->marker=MR_EPOINT_GENERAL;
348 }
349 #endif
350
351 /* Normalise an array of points of length m<MR_MAX_M_T_S - requires a zzn2 workspace array of length m */
352
ecn2_multi_norm(_MIPD_ int m,zzn2 * work,ecn2 * p)353 BOOL ecn2_multi_norm(_MIPD_ int m,zzn2 *work,ecn2 *p)
354 {
355
356 #ifdef MR_OS_THREADS
357 miracl *mr_mip=get_mip();
358 #endif
359
360 #ifndef MR_AFFINE_ONLY
361 int i;
362 zzn2 one,t;
363 zzn2 w[MR_MAX_M_T_S];
364 if (mr_mip->coord==MR_AFFINE) return TRUE;
365 if (mr_mip->ERNUM) return FALSE;
366 if (m>MR_MAX_M_T_S) return FALSE;
367
368 MR_IN(215)
369
370 one.a=mr_mip->w12;
371 one.b=mr_mip->w13;
372 t.a=mr_mip->w14;
373 t.b=mr_mip->w15;
374
375 zzn2_from_int(_MIPP_ 1,&one);
376
377 for (i=0;i<m;i++)
378 {
379 if (p[i].marker==MR_EPOINT_NORMALIZED) w[i]=one;
380 else w[i]=p[i].z;
381 }
382
383 if (!zzn2_multi_inverse(_MIPP_ m,w,work))
384 {
385 MR_OUT
386 return FALSE;
387 }
388
389 for (i=0;i<m;i++)
390 {
391 p[i].marker=MR_EPOINT_NORMALIZED;
392 if (!zzn2_isunity(_MIPP_ &work[i]))
393 {
394 zzn2_sqr(_MIPP_ &work[i],&t);
395 zzn2_mul(_MIPP_ &(p[i].x),&t,&(p[i].x));
396 zzn2_mul(_MIPP_ &t,&work[i],&t);
397 zzn2_mul(_MIPP_ &(p[i].y),&t,&(p[i].y));
398 }
399 }
400 MR_OUT
401 #endif
402 return TRUE;
403 }
404
ecn2_negate(_MIPD_ ecn2 * u,ecn2 * w)405 void ecn2_negate(_MIPD_ ecn2 *u,ecn2 *w)
406 {
407 #ifdef MR_OS_THREADS
408 miracl *mr_mip=get_mip();
409 #endif
410
411 ecn2_copy(u,w);
412 if (w->marker!=MR_EPOINT_INFINITY)
413 zzn2_negate(_MIPP_ &(w->y),&(w->y));
414 }
415
ecn2_add2(_MIPD_ ecn2 * Q,ecn2 * P,zzn2 * lam,zzn2 * ex1)416 BOOL ecn2_add2(_MIPD_ ecn2 *Q,ecn2 *P,zzn2 *lam,zzn2 *ex1)
417 {
418 BOOL Doubling;
419 #ifdef MR_OS_THREADS
420 miracl *mr_mip=get_mip();
421 #endif
422
423 Doubling=ecn2_add3(_MIPP_ Q,P,lam,ex1,NULL);
424
425 return Doubling;
426 }
427
ecn2_add1(_MIPD_ ecn2 * Q,ecn2 * P,zzn2 * lam)428 BOOL ecn2_add1(_MIPD_ ecn2 *Q,ecn2 *P,zzn2 *lam)
429 {
430 BOOL Doubling;
431 #ifdef MR_OS_THREADS
432 miracl *mr_mip=get_mip();
433 #endif
434 Doubling=ecn2_add3(_MIPP_ Q,P,lam,NULL,NULL);
435
436 return Doubling;
437 }
438
ecn2_add(_MIPD_ ecn2 * Q,ecn2 * P)439 BOOL ecn2_add(_MIPD_ ecn2 *Q,ecn2 *P)
440 {
441 BOOL Doubling;
442 #ifdef MR_OS_THREADS
443 miracl *mr_mip=get_mip();
444 #endif
445 zzn2 lam;
446
447 lam.a = mr_mip->w14;
448 lam.b = mr_mip->w15;
449
450 Doubling=ecn2_add3(_MIPP_ Q,P,&lam,NULL,NULL);
451
452 return Doubling;
453 }
454
ecn2_sub(_MIPD_ ecn2 * Q,ecn2 * P)455 BOOL ecn2_sub(_MIPD_ ecn2 *Q,ecn2 *P)
456 {
457 BOOL Doubling;
458 #ifdef MR_OS_THREADS
459 miracl *mr_mip=get_mip();
460 #endif
461 zzn2 lam;
462
463 lam.a = mr_mip->w14;
464 lam.b = mr_mip->w15;
465
466 ecn2_negate(_MIPP_ Q,Q);
467
468 Doubling=ecn2_add3(_MIPP_ Q,P,&lam,NULL,NULL);
469
470 ecn2_negate(_MIPP_ Q,Q);
471
472 return Doubling;
473 }
474
ecn2_add_sub(_MIPD_ ecn2 * P,ecn2 * Q,ecn2 * PP,ecn2 * PM)475 BOOL ecn2_add_sub(_MIPD_ ecn2 *P,ecn2 *Q,ecn2 *PP,ecn2 *PM)
476 { /* PP=P+Q, PM=P-Q. Assumes P and Q are both normalized, and P!=Q */
477 #ifdef MR_OS_THREADS
478 miracl *mr_mip=get_mip();
479 #endif
480 zzn2 t1,t2,lam;
481
482 if (mr_mip->ERNUM) return FALSE;
483
484 if (P->marker==MR_EPOINT_GENERAL || Q->marker==MR_EPOINT_GENERAL)
485 { /* Sorry, some restrictions.. */
486 mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
487 MR_OUT
488 return FALSE;
489 }
490
491 if (zzn2_compare(&(P->x),&(Q->x)))
492 { /* P=Q or P=-Q - shouldn't happen */
493 ecn2_copy(P,PP);
494 ecn2_add(_MIPP_ Q,PP);
495 ecn2_copy(P,PM);
496 ecn2_sub(_MIPP_ Q,PM);
497
498 MR_OUT
499 return TRUE;
500 }
501
502 t1.a = mr_mip->w8;
503 t1.b = mr_mip->w9;
504 t2.a = mr_mip->w10;
505 t2.b = mr_mip->w11;
506 lam.a = mr_mip->w12;
507 lam.b = mr_mip->w13;
508
509 zzn2_copy(&(P->x),&t2);
510 zzn2_sub(_MIPP_ &t2,&(Q->x),&t2);
511 zzn2_inv(_MIPP_ &t2); /* only one inverse required */
512 zzn2_add(_MIPP_ &(P->x),&(Q->x),&(PP->x));
513 zzn2_copy(&(PP->x),&(PM->x));
514
515 zzn2_copy(&(P->y),&t1);
516 zzn2_sub(_MIPP_ &t1,&(Q->y),&t1);
517 zzn2_copy(&t1,&lam);
518 zzn2_mul(_MIPP_ &lam,&t2,&lam);
519 zzn2_copy(&lam,&t1);
520 zzn2_sqr(_MIPP_ &t1,&t1);
521 zzn2_sub(_MIPP_ &t1,&(PP->x),&(PP->x));
522 zzn2_copy(&(Q->x),&(PP->y));
523 zzn2_sub(_MIPP_ &(PP->y),&(PP->x),&(PP->y));
524 zzn2_mul(_MIPP_ &(PP->y),&lam,&(PP->y));
525 zzn2_sub(_MIPP_ &(PP->y),&(Q->y),&(PP->y));
526
527 zzn2_copy(&(P->y),&t1);
528 zzn2_add(_MIPP_ &t1,&(Q->y),&t1);
529 zzn2_copy(&t1,&lam);
530 zzn2_mul(_MIPP_ &lam,&t2,&lam);
531 zzn2_copy(&lam,&t1);
532 zzn2_sqr(_MIPP_ &t1,&t1);
533 zzn2_sub(_MIPP_ &t1,&(PM->x),&(PM->x));
534 zzn2_copy(&(Q->x),&(PM->y));
535 zzn2_sub(_MIPP_ &(PM->y),&(PM->x),&(PM->y));
536 zzn2_mul(_MIPP_ &(PM->y),&lam,&(PM->y));
537 zzn2_add(_MIPP_ &(PM->y),&(Q->y),&(PM->y));
538
539 PP->marker=MR_EPOINT_NORMALIZED;
540 PM->marker=MR_EPOINT_NORMALIZED;
541
542 return TRUE;
543 }
544
ecn2_add3(_MIPD_ ecn2 * Q,ecn2 * P,zzn2 * lam,zzn2 * ex1,zzn2 * ex2)545 BOOL ecn2_add3(_MIPD_ ecn2 *Q,ecn2 *P,zzn2 *lam,zzn2 *ex1,zzn2 *ex2)
546 { /* P+=Q */
547 BOOL Doubling=FALSE;
548 int twist;
549 int iA;
550 zzn2 t1,t2,t3;
551 zzn2 Yzzz;
552
553 #ifdef MR_OS_THREADS
554 miracl *mr_mip=get_mip();
555 #endif
556
557 t1.a = mr_mip->w8;
558 t1.b = mr_mip->w9;
559 t2.a = mr_mip->w10;
560 t2.b = mr_mip->w11;
561 t3.a = mr_mip->w12;
562 t3.b = mr_mip->w13;
563 Yzzz.a = mr_mip->w3;
564 Yzzz.b = mr_mip->w4;
565
566 twist=mr_mip->TWIST;
567 if (mr_mip->ERNUM) return FALSE;
568
569 if (P->marker==MR_EPOINT_INFINITY)
570 {
571 ecn2_copy(Q,P);
572 return Doubling;
573 }
574 if (Q->marker==MR_EPOINT_INFINITY) return Doubling;
575
576 MR_IN(205)
577
578 if (Q!=P && Q->marker==MR_EPOINT_GENERAL)
579 { /* Sorry, this code is optimized for mixed addition only */
580 mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
581 MR_OUT
582 return Doubling;
583 }
584 #ifndef MR_AFFINE_ONLY
585 if (mr_mip->coord==MR_AFFINE)
586 {
587 #endif
588 if (!zzn2_compare(&(P->x),&(Q->x)))
589 {
590 zzn2_copy(&(P->y),&t1);
591 zzn2_sub(_MIPP_ &t1,&(Q->y),&t1);
592 zzn2_copy(&(P->x),&t2);
593 zzn2_sub(_MIPP_ &t2,&(Q->x),&t2);
594 zzn2_copy(&t1,lam);
595 zzn2_inv(_MIPP_ &t2);
596 zzn2_mul(_MIPP_ lam,&t2,lam);
597
598 zzn2_add(_MIPP_ &(P->x),&(Q->x),&(P->x));
599 zzn2_copy(lam,&t1);
600 zzn2_sqr(_MIPP_ &t1,&t1);
601 zzn2_sub(_MIPP_ &t1,&(P->x),&(P->x));
602
603 zzn2_copy(&(Q->x),&(P->y));
604 zzn2_sub(_MIPP_ &(P->y),&(P->x),&(P->y));
605 zzn2_mul(_MIPP_ &(P->y),lam,&(P->y));
606 zzn2_sub(_MIPP_ &(P->y),&(Q->y),&(P->y));
607 }
608 else
609 {
610 if (!zzn2_compare(&(P->y),&(Q->y)) || zzn2_iszero(&(P->y)))
611 {
612 ecn2_zero(P);
613 zzn2_from_int(_MIPP_ 1,lam);
614 MR_OUT
615 return Doubling;
616 }
617 zzn2_copy(&(P->x),&t1);
618 zzn2_copy(&(P->x),&t2);
619 zzn2_copy(&(P->x),lam);
620 zzn2_sqr(_MIPP_ lam,lam);
621 zzn2_add(_MIPP_ lam,lam,&t3);
622 zzn2_add(_MIPP_ lam,&t3,lam);
623
624 if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&t3);
625 else zzn2_from_zzn(mr_mip->A,&t3);
626
627 if (twist)
628 {
629 if (twist==MR_QUARTIC_M)
630 {
631 zzn2_txx(_MIPP_ &t3);
632 }
633 if (twist==MR_QUARTIC_D)
634 {
635 zzn2_txd(_MIPP_ &t3);
636 }
637 if (twist==MR_QUADRATIC)
638 {
639 zzn2_txx(_MIPP_ &t3);
640 zzn2_txx(_MIPP_ &t3);
641 }
642 /*
643 if (mr_mip->Bsize==0)
644 { // assume its the quartic twist
645 zzn2_txx(_MIPP_ &t3);
646 }
647 else
648 {
649 zzn2_txx(_MIPP_ &t3);
650 zzn2_txx(_MIPP_ &t3);
651 }
652 */
653 }
654 zzn2_add(_MIPP_ lam,&t3,lam);
655 zzn2_add(_MIPP_ &(P->y),&(P->y),&t3);
656 zzn2_inv(_MIPP_ &t3);
657 zzn2_mul(_MIPP_ lam,&t3,lam);
658
659 zzn2_add(_MIPP_ &t2,&(P->x),&t2);
660 zzn2_copy(lam,&(P->x));
661 zzn2_sqr(_MIPP_ &(P->x),&(P->x));
662 zzn2_sub(_MIPP_ &(P->x),&t2,&(P->x));
663 zzn2_sub(_MIPP_ &t1,&(P->x),&t1);
664 zzn2_mul(_MIPP_ &t1,lam,&t1);
665 zzn2_sub(_MIPP_ &t1,&(P->y),&(P->y));
666 }
667
668 P->marker=MR_EPOINT_NORMALIZED;
669 MR_OUT
670 return Doubling;
671 #ifndef MR_AFFINE_ONLY
672 }
673
674 if (Q==P) Doubling=TRUE;
675
676 zzn2_copy(&(Q->x),&t3);
677 zzn2_copy(&(Q->y),&Yzzz);
678
679 if (!Doubling)
680 {
681 if (P->marker!=MR_EPOINT_NORMALIZED)
682 {
683 zzn2_sqr(_MIPP_ &(P->z),&t1); /* 1S */
684 zzn2_mul(_MIPP_ &t3,&t1,&t3); /* 1M */
685 zzn2_mul(_MIPP_ &t1,&(P->z),&t1); /* 1M */
686 zzn2_mul(_MIPP_ &Yzzz,&t1,&Yzzz); /* 1M */
687 }
688 if (zzn2_compare(&t3,&(P->x)))
689 {
690 if (!zzn2_compare(&Yzzz,&(P->y)) || zzn2_iszero(&(P->y)))
691 {
692 ecn2_zero(P);
693 zzn2_from_int(_MIPP_ 1,lam);
694 MR_OUT
695 return Doubling;
696 }
697 else Doubling=TRUE;
698 }
699 }
700 if (!Doubling)
701 { /* Addition */
702 zzn2_sub(_MIPP_ &t3,&(P->x),&t3);
703 zzn2_sub(_MIPP_ &Yzzz,&(P->y),lam);
704 if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy(&t3,&(P->z));
705 else zzn2_mul(_MIPP_ &(P->z),&t3,&(P->z)); /* 1M */
706 zzn2_sqr(_MIPP_ &t3,&t1); /* 1S */
707 zzn2_mul(_MIPP_ &t1,&t3,&Yzzz); /* 1M */
708 zzn2_mul(_MIPP_ &t1,&(P->x),&t1); /* 1M */
709 zzn2_copy(&t1,&t3);
710 zzn2_add(_MIPP_ &t3,&t3,&t3);
711 zzn2_sqr(_MIPP_ lam,&(P->x)); /* 1S */
712 zzn2_sub(_MIPP_ &(P->x),&t3,&(P->x));
713 zzn2_sub(_MIPP_ &(P->x),&Yzzz,&(P->x));
714 zzn2_sub(_MIPP_ &t1,&(P->x),&t1);
715 zzn2_mul(_MIPP_ &t1,lam,&t1); /* 1M */
716 zzn2_mul(_MIPP_ &Yzzz,&(P->y),&Yzzz); /* 1M */
717 zzn2_sub(_MIPP_ &t1,&Yzzz,&(P->y));
718
719 /*
720 zzn2_sub(_MIPP_ &(P->x),&t3,&t1);
721 zzn2_sub(_MIPP_ &(P->y),&Yzzz,lam);
722 if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy(&t1,&(P->z));
723 else zzn2_mul(_MIPP_ &(P->z),&t1,&(P->z));
724 zzn2_sqr(_MIPP_ &t1,&t2);
725 zzn2_add(_MIPP_ &(P->x),&t3,&t3);
726 zzn2_mul(_MIPP_ &t3,&t2,&t3);
727 zzn2_sqr(_MIPP_ lam,&(P->x));
728 zzn2_sub(_MIPP_ &(P->x),&t3,&(P->x));
729
730 zzn2_mul(_MIPP_ &t2,&t1,&t2);
731 zzn2_add(_MIPP_ &(P->x),&(P->x),&t1);
732 zzn2_sub(_MIPP_ &t3,&t1,&t3);
733 zzn2_mul(_MIPP_ &t3,lam,&t3);
734
735 zzn2_add(_MIPP_ &(P->y),&Yzzz,&t1);
736
737 zzn2_mul(_MIPP_ &t2,&t1,&t2);
738 zzn2_sub(_MIPP_ &t3,&t2,&(P->y));
739 zzn2_div2(_MIPP_ &(P->y));
740 */
741 }
742 else
743 { /* doubling */
744 zzn2_sqr(_MIPP_ &(P->y),&t3); /* 1S */
745
746 iA=mr_mip->Asize;
747 if (iA!=0)
748 {
749 if (P->marker==MR_EPOINT_NORMALIZED) zzn2_from_int(_MIPP_ 1,&t1);
750 else zzn2_sqr(_MIPP_ &(P->z),&t1); /* 1S */
751 if (ex2!=NULL) zzn2_copy(&t1,ex2);
752
753 if (iA==-3 && twist<=MR_QUADRATIC)
754 {
755 if (twist==MR_QUADRATIC) zzn2_txx(_MIPP_ &t1); /* quadratic twist */
756 zzn2_sub(_MIPP_ &(P->x),&t1,lam);
757 zzn2_add(_MIPP_ &t1,&(P->x),&t1);
758 zzn2_mul(_MIPP_ lam,&t1,lam); /* 1M */
759 zzn2_add(_MIPP_ lam,lam,&t2);
760 zzn2_add(_MIPP_ lam,&t2,lam);
761 }
762 else
763 {
764 zzn2_sqr(_MIPP_ &(P->x),lam); /* 1S */
765 zzn2_add(_MIPP_ lam,lam,&t2);
766 zzn2_add(_MIPP_ lam,&t2,lam);
767
768 if (twist==MR_QUADRATIC) zzn2_txx(_MIPP_ &t1); /* quadratic twist */
769 zzn2_sqr(_MIPP_ &t1,&t1); /* 1S */
770 if (twist==MR_QUARTIC_M) zzn2_txx(_MIPP_ &t1); /* quartic twist */
771 if (twist==MR_QUARTIC_D) zzn2_txd(_MIPP_ &t1); /* quartic twist */
772 if (iA!=1)
773 { /* optimized for iA=1 case */
774 if (iA<MR_TOOBIG) zzn2_imul(_MIPP_ &t1,iA,&t1);
775 else zzn2_smul(_MIPP_ &t1,mr_mip->A,&t1);
776 }
777 zzn2_add(_MIPP_ lam,&t1,lam);
778 }
779 }
780 else
781 {
782 zzn2_sqr(_MIPP_ &(P->x),lam); /* 1S */
783 zzn2_add(_MIPP_ lam,lam,&t2);
784 zzn2_add(_MIPP_ lam,&t2,lam);
785 }
786 zzn2_mul(_MIPP_ &(P->x),&t3,&t1); /* 1M */
787 zzn2_add(_MIPP_ &t1,&t1,&t1);
788 zzn2_add(_MIPP_ &t1,&t1,&t1);
789 zzn2_sqr(_MIPP_ lam,&(P->x)); /* 1S */
790 zzn2_add(_MIPP_ &t1,&t1,&t2);
791 zzn2_sub(_MIPP_ &(P->x),&t2,&(P->x));
792 if (P->marker==MR_EPOINT_NORMALIZED) zzn2_copy(&(P->y),&(P->z));
793 else zzn2_mul(_MIPP_ &(P->z),&(P->y),&(P->z)); /* 1M */
794 zzn2_add(_MIPP_ &(P->z),&(P->z),&(P->z));
795 zzn2_add(_MIPP_ &t3,&t3,&t3);
796 if (ex1!=NULL) zzn2_copy(&t3,ex1);
797 zzn2_sqr(_MIPP_ &t3,&t3); /* 1S */
798 zzn2_add(_MIPP_ &t3,&t3,&t3);
799 zzn2_sub(_MIPP_ &t1,&(P->x),&t1);
800 zzn2_mul(_MIPP_ lam,&t1,&(P->y)); /* 1M */
801 zzn2_sub(_MIPP_ &(P->y),&t3,&(P->y));
802 }
803
804 P->marker=MR_EPOINT_GENERAL;
805 MR_OUT
806 return Doubling;
807 #endif
808 }
809
810 /* Dahmen, Okeya and Schepers "Affine Precomputation with Sole Inversion in Elliptic Curve Cryptography" */
811 /* Precomputes table into T. Assumes first P has been copied to P[0], then calculates 3P, 5P, 7P etc. into T */
812
813 #define MR_PRE_2 (14+4*MR_MAX_M_T_S)
814
ecn2_pre(_MIPD_ int sz,BOOL norm,ecn2 * PT)815 static void ecn2_pre(_MIPD_ int sz,BOOL norm,ecn2 *PT)
816 {
817 int twist;
818 int i,j;
819 zzn2 A,B,C,D,E,T,W;
820
821 #ifdef MR_OS_THREADS
822 miracl *mr_mip=get_mip();
823 #endif
824
825 #ifndef MR_STATIC
826 zzn2 *d=(zzn2 *)mr_alloc(_MIPP_ sz,sizeof(zzn2));
827 zzn2 *e=(zzn2 *)mr_alloc(_MIPP_ sz,sizeof(zzn2));
828 char *mem = (char *)memalloc(_MIPP_ 14+4*sz);
829 #else
830 zzn2 d[MR_MAX_M_T_S],e[MR_MAX_M_T_S];
831 char mem[MR_BIG_RESERVE(MR_PRE_2)];
832 memset(mem, 0, MR_BIG_RESERVE(MR_PRE_2));
833 #endif
834
835 twist=mr_mip->TWIST;
836 j=0;
837
838 A.a= mirvar_mem(_MIPP_ mem, j++);
839 A.b= mirvar_mem(_MIPP_ mem, j++);
840 B.a= mirvar_mem(_MIPP_ mem, j++);
841 B.b= mirvar_mem(_MIPP_ mem, j++);
842 C.a= mirvar_mem(_MIPP_ mem, j++);
843 C.b= mirvar_mem(_MIPP_ mem, j++);
844 D.a= mirvar_mem(_MIPP_ mem, j++);
845 D.b= mirvar_mem(_MIPP_ mem, j++);
846 E.a= mirvar_mem(_MIPP_ mem, j++);
847 E.b= mirvar_mem(_MIPP_ mem, j++);
848 T.a= mirvar_mem(_MIPP_ mem, j++);
849 T.b= mirvar_mem(_MIPP_ mem, j++);
850 W.a= mirvar_mem(_MIPP_ mem, j++);
851 W.b= mirvar_mem(_MIPP_ mem, j++);
852
853 for (i=0;i<sz;i++)
854 {
855 d[i].a= mirvar_mem(_MIPP_ mem, j++);
856 d[i].b= mirvar_mem(_MIPP_ mem, j++);
857 e[i].a= mirvar_mem(_MIPP_ mem, j++);
858 e[i].b= mirvar_mem(_MIPP_ mem, j++);
859 }
860
861 zzn2_add(_MIPP_ &(PT[0].y),&(PT[0].y),&d[0]); /* 1. d_0=2.y */
862 zzn2_sqr(_MIPP_ &d[0],&C); /* 2. C=d_0^2 */
863
864 zzn2_sqr(_MIPP_ &(PT[0].x),&T);
865 zzn2_add(_MIPP_ &T,&T,&A);
866 zzn2_add(_MIPP_ &T,&A,&T);
867
868 if (mr_abs(mr_mip->Asize)<MR_TOOBIG) zzn2_from_int(_MIPP_ mr_mip->Asize,&A);
869 else zzn2_from_zzn(mr_mip->A,&A);
870
871 if (twist)
872 {
873 if (twist==MR_QUARTIC_M)
874 {
875 zzn2_txx(_MIPP_ &A);
876 }
877 if (twist==MR_QUARTIC_D)
878 {
879 zzn2_txd(_MIPP_ &A);
880 }
881 if (twist==MR_QUADRATIC)
882 {
883 zzn2_txx(_MIPP_ &A);
884 zzn2_txx(_MIPP_ &A);
885 }
886 /*
887 if (mr_mip->Bsize==0)
888 { // assume its the quartic twist
889 zzn2_txx(_MIPP_ &A);
890 }
891 else
892 {
893 zzn2_txx(_MIPP_ &A);
894 zzn2_txx(_MIPP_ &A);
895 }
896 */
897 }
898 zzn2_add(_MIPP_ &A,&T,&A); /* 3. A=3x^2+a */
899 zzn2_copy(&A,&W);
900
901 zzn2_add(_MIPP_ &C,&C,&B);
902 zzn2_add(_MIPP_ &B,&C,&B);
903 zzn2_mul(_MIPP_ &B,&(PT[0].x),&B); /* 4. B=3C.x */
904
905 zzn2_sqr(_MIPP_ &A,&d[1]);
906 zzn2_sub(_MIPP_ &d[1],&B,&d[1]); /* 5. d_1=A^2-B */
907
908 zzn2_sqr(_MIPP_ &d[1],&E); /* 6. E=d_1^2 */
909
910 zzn2_mul(_MIPP_ &B,&E,&B); /* 7. B=E.B */
911
912 zzn2_sqr(_MIPP_ &C,&C); /* 8. C=C^2 */
913
914 zzn2_mul(_MIPP_ &E,&d[1],&D); /* 9. D=E.d_1 */
915
916 zzn2_mul(_MIPP_ &A,&d[1],&A);
917 zzn2_add(_MIPP_ &A,&C,&A);
918 zzn2_negate(_MIPP_ &A,&A); /* 10. A=-d_1*A-C */
919
920 zzn2_add(_MIPP_ &D,&D,&T);
921 zzn2_sqr(_MIPP_ &A,&d[2]);
922 zzn2_sub(_MIPP_ &d[2],&T,&d[2]);
923 zzn2_sub(_MIPP_ &d[2],&B,&d[2]); /* 11. d_2=A^2-2D-B */
924
925 if (sz>3)
926 {
927 zzn2_sqr(_MIPP_ &d[2],&E); /* 12. E=d_2^2 */
928
929 zzn2_add(_MIPP_ &T,&D,&T);
930 zzn2_add(_MIPP_ &T,&B,&T);
931 zzn2_mul(_MIPP_ &T,&E,&B); /* 13. B=E(B+3D) */
932
933 zzn2_add(_MIPP_ &A,&A,&T);
934 zzn2_add(_MIPP_ &C,&T,&C);
935 zzn2_mul(_MIPP_ &C,&D,&C); /* 14. C=D(2A+C) */
936
937 zzn2_mul(_MIPP_ &d[2],&E,&D); /* 15. D=E.d_2 */
938
939 zzn2_mul(_MIPP_ &A,&d[2],&A);
940 zzn2_add(_MIPP_ &A,&C,&A);
941 zzn2_negate(_MIPP_ &A,&A); /* 16. A=-d_2*A-C */
942
943
944 zzn2_sqr(_MIPP_ &A,&d[3]);
945 zzn2_sub(_MIPP_ &d[3],&D,&d[3]);
946 zzn2_sub(_MIPP_ &d[3],&B,&d[3]); /* 17. d_3=A^2-D-B */
947
948 for (i=4;i<sz;i++)
949 {
950 zzn2_sqr(_MIPP_ &d[i-1],&E); /* 19. E=d(i-1)^2 */
951 zzn2_mul(_MIPP_ &B,&E,&B); /* 20. B=E.B */
952 zzn2_mul(_MIPP_ &C,&D,&C); /* 21. C=D.C */
953 zzn2_mul(_MIPP_ &E,&d[i-1],&D); /* 22. D=E.d(i-1) */
954
955 zzn2_mul(_MIPP_ &A,&d[i-1],&A);
956 zzn2_add(_MIPP_ &A,&C,&A);
957 zzn2_negate(_MIPP_ &A,&A); /* 23. A=-d(i-1)*A-C */
958
959 zzn2_sqr(_MIPP_ &A,&d[i]);
960 zzn2_sub(_MIPP_ &d[i],&D,&d[i]);
961 zzn2_sub(_MIPP_ &d[i],&B,&d[i]); /* 24. d(i)=A^2-D-B */
962 }
963 }
964
965 zzn2_copy(&d[0],&e[0]);
966 for (i=1;i<sz;i++)
967 zzn2_mul(_MIPP_ &e[i-1],&d[i],&e[i]);
968
969 zzn2_copy(&e[sz-1],&A);
970 zzn2_inv(_MIPP_ &A);
971
972 for (i=sz-1;i>0;i--)
973 {
974 zzn2_copy(&d[i],&B);
975 zzn2_mul(_MIPP_ &e[i-1],&A,&d[i]);
976 zzn2_mul(_MIPP_ &A,&B,&A);
977 }
978 zzn2_copy(&A,&d[0]);
979
980 for (i=1;i<sz;i++)
981 {
982 zzn2_sqr(_MIPP_ &e[i-1],&T);
983 zzn2_mul(_MIPP_ &d[i],&T,&d[i]); /** */
984 }
985
986 zzn2_mul(_MIPP_ &W,&d[0],&W);
987 zzn2_sqr(_MIPP_ &W,&A);
988 zzn2_sub(_MIPP_ &A,&(PT[0].x),&A);
989 zzn2_sub(_MIPP_ &A,&(PT[0].x),&A);
990 zzn2_sub(_MIPP_ &(PT[0].x),&A,&B);
991 zzn2_mul(_MIPP_ &B,&W,&B);
992 zzn2_sub(_MIPP_ &B,&(PT[0].y),&B);
993
994 zzn2_sub(_MIPP_ &B,&(PT[0].y),&T);
995 zzn2_mul(_MIPP_ &T,&d[1],&T);
996
997 zzn2_sqr(_MIPP_ &T,&(PT[1].x));
998 zzn2_sub(_MIPP_ &(PT[1].x),&A,&(PT[1].x));
999 zzn2_sub(_MIPP_ &(PT[1].x),&(PT[0].x),&(PT[1].x));
1000
1001 zzn2_sub(_MIPP_ &A,&(PT[1].x),&(PT[1].y));
1002 zzn2_mul(_MIPP_ &(PT[1].y),&T,&(PT[1].y));
1003 zzn2_sub(_MIPP_ &(PT[1].y),&B,&(PT[1].y));
1004
1005 for (i=2;i<sz;i++)
1006 {
1007 zzn2_sub(_MIPP_ &(PT[i-1].y),&B,&T);
1008 zzn2_mul(_MIPP_ &T,&d[i],&T);
1009
1010 zzn2_sqr(_MIPP_ &T,&(PT[i].x));
1011 zzn2_sub(_MIPP_ &(PT[i].x),&A,&(PT[i].x));
1012 zzn2_sub(_MIPP_ &(PT[i].x),&(PT[i-1].x),&(PT[i].x));
1013
1014 zzn2_sub(_MIPP_ &A,&(PT[i].x),&(PT[i].y));
1015 zzn2_mul(_MIPP_ &(PT[i].y),&T,&(PT[i].y));
1016 zzn2_sub(_MIPP_ &(PT[i].y),&B,&(PT[i].y));
1017 }
1018 for (i=0;i<sz;i++) PT[i].marker=MR_EPOINT_NORMALIZED;
1019
1020 #ifndef MR_STATIC
1021 memkill(_MIPP_ mem, 14+4*sz);
1022 mr_free(d); mr_free(e);
1023 #else
1024 memset(mem, 0, MR_BIG_RESERVE(MR_PRE_2));
1025 #endif
1026 }
1027
1028 #ifndef MR_DOUBLE_BIG
1029 #define MR_MUL_RESERVE (1+4*MR_ECC_STORE_N2)
1030 #else
1031 #define MR_MUL_RESERVE (2+4*MR_ECC_STORE_N2)
1032 #endif
1033
ecn2_mul(_MIPD_ big k,ecn2 * P)1034 int ecn2_mul(_MIPD_ big k,ecn2 *P)
1035 {
1036 int i,j,nb,n,nbs,nzs,nadds;
1037 BOOL neg;
1038 big h;
1039 ecn2 T[MR_ECC_STORE_N2];
1040 #ifdef MR_OS_THREADS
1041 miracl *mr_mip=get_mip();
1042 #endif
1043
1044 #ifndef MR_STATIC
1045 char *mem = (char *)memalloc(_MIPP_ MR_MUL_RESERVE);
1046 #else
1047 char mem[MR_BIG_RESERVE(MR_MUL_RESERVE)];
1048 memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
1049 #endif
1050
1051 j=0;
1052 #ifndef MR_DOUBLE_BIG
1053 h=mirvar_mem(_MIPP_ mem, j++);
1054 #else
1055 h=mirvar_mem(_MIPP_ mem, j); j+=2;
1056 #endif
1057 for (i=0;i<MR_ECC_STORE_N2;i++)
1058 {
1059 T[i].x.a= mirvar_mem(_MIPP_ mem, j++);
1060 T[i].x.b= mirvar_mem(_MIPP_ mem, j++);
1061 T[i].y.a= mirvar_mem(_MIPP_ mem, j++);
1062 T[i].y.b= mirvar_mem(_MIPP_ mem, j++);
1063 }
1064
1065 MR_IN(207)
1066
1067 ecn2_norm(_MIPP_ P);
1068
1069 nadds=0;
1070
1071 neg=FALSE;
1072 if (size(k)<0)
1073 {
1074 negify(k,k);
1075 ecn2_negate(_MIPP_ P,&T[0]);
1076 neg=TRUE;
1077 }
1078 else ecn2_copy(P,&T[0]);
1079
1080 premult(_MIPP_ k,3,h);
1081
1082 nb=logb2(_MIPP_ h);
1083 ecn2_pre(_MIPP_ MR_ECC_STORE_N2,TRUE,T);
1084
1085 ecn2_zero(P);
1086
1087 for (i=nb-1;i>=1;)
1088 {
1089 if (mr_mip->user!=NULL) (*mr_mip->user)();
1090 n=mr_naf_window(_MIPP_ k,h,i,&nbs,&nzs,MR_ECC_STORE_N2);
1091
1092 for (j=0;j<nbs;j++) ecn2_add(_MIPP_ P,P);
1093
1094 if (n>0) {nadds++; ecn2_add(_MIPP_ &T[n/2],P);}
1095 if (n<0) {nadds++; ecn2_sub(_MIPP_ &T[(-n)/2],P);}
1096 i-=nbs;
1097 if (nzs)
1098 {
1099 for (j=0;j<nzs;j++) ecn2_add(_MIPP_ P,P);
1100 i-=nzs;
1101 }
1102 }
1103 if (neg) negify(k,k);
1104
1105 ecn2_norm(_MIPP_ P);
1106 MR_OUT
1107
1108 #ifndef MR_STATIC
1109 memkill(_MIPP_ mem, MR_MUL_RESERVE);
1110 #else
1111 memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
1112 #endif
1113 return nadds;
1114 }
1115
1116 /* Double addition, using Joint Sparse Form */
1117 /* R=aP+bQ */
1118
1119 #ifndef MR_NO_ECC_MULTIADD
1120
1121 #define MR_MUL2_JSF_RESERVE 20
1122
ecn2_mul2_jsf(_MIPD_ big a,ecn2 * P,big b,ecn2 * Q,ecn2 * R)1123 int ecn2_mul2_jsf(_MIPD_ big a,ecn2 *P,big b,ecn2 *Q,ecn2 *R)
1124 {
1125 int e1,h1,e2,h2,bb,nadds;
1126 ecn2 P1,P2,PS,PD;
1127 big c,d,e,f;
1128 #ifdef MR_OS_THREADS
1129 miracl *mr_mip=get_mip();
1130 #endif
1131
1132 #ifndef MR_STATIC
1133 char *mem = (char *)memalloc(_MIPP_ MR_MUL2_JSF_RESERVE);
1134 #else
1135 char mem[MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE)];
1136 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
1137 #endif
1138
1139 c = mirvar_mem(_MIPP_ mem, 0);
1140 d = mirvar_mem(_MIPP_ mem, 1);
1141 e = mirvar_mem(_MIPP_ mem, 2);
1142 f = mirvar_mem(_MIPP_ mem, 3);
1143 P1.x.a= mirvar_mem(_MIPP_ mem, 4);
1144 P1.x.b= mirvar_mem(_MIPP_ mem, 5);
1145 P1.y.a= mirvar_mem(_MIPP_ mem, 6);
1146 P1.y.b= mirvar_mem(_MIPP_ mem, 7);
1147 P2.x.a= mirvar_mem(_MIPP_ mem, 8);
1148 P2.x.b= mirvar_mem(_MIPP_ mem, 9);
1149 P2.y.a= mirvar_mem(_MIPP_ mem, 10);
1150 P2.y.b= mirvar_mem(_MIPP_ mem, 11);
1151 PS.x.a= mirvar_mem(_MIPP_ mem, 12);
1152 PS.x.b= mirvar_mem(_MIPP_ mem, 13);
1153 PS.y.a= mirvar_mem(_MIPP_ mem, 14);
1154 PS.y.b= mirvar_mem(_MIPP_ mem, 15);
1155 PD.x.a= mirvar_mem(_MIPP_ mem, 16);
1156 PD.x.b= mirvar_mem(_MIPP_ mem, 17);
1157 PD.y.a= mirvar_mem(_MIPP_ mem, 18);
1158 PD.y.b= mirvar_mem(_MIPP_ mem, 19);
1159
1160 MR_IN(206)
1161
1162 ecn2_norm(_MIPP_ Q);
1163 ecn2_copy(Q,&P2);
1164
1165 copy(b,d);
1166 if (size(d)<0)
1167 {
1168 negify(d,d);
1169 ecn2_negate(_MIPP_ &P2,&P2);
1170 }
1171
1172 ecn2_norm(_MIPP_ P);
1173 ecn2_copy(P,&P1);
1174
1175 copy(a,c);
1176 if (size(c)<0)
1177 {
1178 negify(c,c);
1179 ecn2_negate(_MIPP_ &P1,&P1);
1180 }
1181
1182 mr_jsf(_MIPP_ d,c,e,d,f,c); /* calculate joint sparse form */
1183
1184 if (compare(e,f)>0) bb=logb2(_MIPP_ e)-1;
1185 else bb=logb2(_MIPP_ f)-1;
1186
1187 ecn2_add_sub(_MIPP_ &P1,&P2,&PS,&PD);
1188 ecn2_zero(R);
1189 nadds=0;
1190
1191 while (bb>=0)
1192 { /* add/subtract method */
1193 if (mr_mip->user!=NULL) (*mr_mip->user)();
1194 ecn2_add(_MIPP_ R,R);
1195 e1=h1=e2=h2=0;
1196
1197 if (mr_testbit(_MIPP_ d,bb)) e2=1;
1198 if (mr_testbit(_MIPP_ e,bb)) h2=1;
1199 if (mr_testbit(_MIPP_ c,bb)) e1=1;
1200 if (mr_testbit(_MIPP_ f,bb)) h1=1;
1201
1202 if (e1!=h1)
1203 {
1204 if (e2==h2)
1205 {
1206 if (h1==1) {ecn2_add(_MIPP_ &P1,R); nadds++;}
1207 else {ecn2_sub(_MIPP_ &P1,R); nadds++;}
1208 }
1209 else
1210 {
1211 if (h1==1)
1212 {
1213 if (h2==1) {ecn2_add(_MIPP_ &PS,R); nadds++;}
1214 else {ecn2_add(_MIPP_ &PD,R); nadds++;}
1215 }
1216 else
1217 {
1218 if (h2==1) {ecn2_sub(_MIPP_ &PD,R); nadds++;}
1219 else {ecn2_sub(_MIPP_ &PS,R); nadds++;}
1220 }
1221 }
1222 }
1223 else if (e2!=h2)
1224 {
1225 if (h2==1) {ecn2_add(_MIPP_ &P2,R); nadds++;}
1226 else {ecn2_sub(_MIPP_ &P2,R); nadds++;}
1227 }
1228 bb-=1;
1229 }
1230 ecn2_norm(_MIPP_ R);
1231
1232 MR_OUT
1233 #ifndef MR_STATIC
1234 memkill(_MIPP_ mem, MR_MUL2_JSF_RESERVE);
1235 #else
1236 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
1237 #endif
1238 return nadds;
1239
1240 }
1241
1242 /* General purpose multi-exponentiation engine, using inter-leaving algorithm. Calculate aP+bQ+cR+dS...
1243 Inputs are divided into two groups of sizes wa<4 and wb<4. For the first group if the points are fixed the
1244 first precomputed Table Ta[] may be taken from ROM. For the second group if the points are variable Tb[j] will
1245 have to computed online. Each group has its own precomputed store size, sza (=8?) and szb (=20?) respectively.
1246 The values a,b,c.. are provided in ma[] and mb[], and 3.a,3.b,3.c (as required by the NAF) are provided in
1247 ma3[] and mb3[]. If only one group is required, set wb=0 and pass NULL pointers.
1248 */
1249
ecn2_muln_engine(_MIPD_ int wa,int sza,int wb,int szb,big * ma,big * ma3,big * mb,big * mb3,ecn2 * Ta,ecn2 * Tb,ecn2 * R)1250 int ecn2_muln_engine(_MIPD_ int wa,int sza,int wb,int szb,big *ma,big *ma3,big *mb,big *mb3,ecn2 *Ta,ecn2 *Tb,ecn2 *R)
1251 { /* general purpose interleaving algorithm engine for multi-exp */
1252 int i,j,tba[4],pba[4],na[4],sa[4],tbb[4],pbb[4],nb[4],sb[4],nbits,nbs,nzs;
1253 int nadds;
1254 #ifdef MR_OS_THREADS
1255 miracl *mr_mip=get_mip();
1256 #endif
1257
1258 ecn2_zero(R);
1259
1260 nbits=0;
1261 for (i=0;i<wa;i++) {sa[i]=exsign(ma[i]); tba[i]=0; j=logb2(_MIPP_ ma3[i]); if (j>nbits) nbits=j; }
1262 for (i=0;i<wb;i++) {sb[i]=exsign(mb[i]); tbb[i]=0; j=logb2(_MIPP_ mb3[i]); if (j>nbits) nbits=j; }
1263
1264 nadds=0;
1265 for (i=nbits-1;i>=1;i--)
1266 {
1267 if (mr_mip->user!=NULL) (*mr_mip->user)();
1268 if (R->marker!=MR_EPOINT_INFINITY) ecn2_add(_MIPP_ R,R);
1269 for (j=0;j<wa;j++)
1270 { /* deal with the first group */
1271 if (tba[j]==0)
1272 {
1273 na[j]=mr_naf_window(_MIPP_ ma[j],ma3[j],i,&nbs,&nzs,sza);
1274 tba[j]=nbs+nzs;
1275 pba[j]=nbs;
1276 }
1277 tba[j]--; pba[j]--;
1278 if (pba[j]==0)
1279 {
1280 if (sa[j]==PLUS)
1281 {
1282 if (na[j]>0) {ecn2_add(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
1283 if (na[j]<0) {ecn2_sub(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
1284 }
1285 else
1286 {
1287 if (na[j]>0) {ecn2_sub(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
1288 if (na[j]<0) {ecn2_add(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
1289 }
1290 }
1291 }
1292 for (j=0;j<wb;j++)
1293 { /* deal with the second group */
1294 if (tbb[j]==0)
1295 {
1296 nb[j]=mr_naf_window(_MIPP_ mb[j],mb3[j],i,&nbs,&nzs,szb);
1297 tbb[j]=nbs+nzs;
1298 pbb[j]=nbs;
1299 }
1300 tbb[j]--; pbb[j]--;
1301 if (pbb[j]==0)
1302 {
1303 if (sb[j]==PLUS)
1304 {
1305 if (nb[j]>0) {ecn2_add(_MIPP_ &Tb[j*szb+nb[j]/2],R); nadds++;}
1306 if (nb[j]<0) {ecn2_sub(_MIPP_ &Tb[j*szb+(-nb[j])/2],R); nadds++;}
1307 }
1308 else
1309 {
1310 if (nb[j]>0) {ecn2_sub(_MIPP_ &Tb[j*szb+nb[j]/2],R); nadds++;}
1311 if (nb[j]<0) {ecn2_add(_MIPP_ &Tb[j*szb+(-nb[j])/2],R); nadds++;}
1312 }
1313 }
1314 }
1315 }
1316 ecn2_norm(_MIPP_ R);
1317 return nadds;
1318 }
1319
1320 /* Routines to support Galbraith, Lin, Scott (GLS) method for ECC */
1321 /* requires an endomorphism psi */
1322
1323 /* *********************** */
1324
1325 /* Precompute T - first half from i.P, second half from i.psi(P) */
1326
ecn2_precomp_gls(_MIPD_ int sz,BOOL norm,ecn2 * P,zzn2 * psi,ecn2 * T)1327 void ecn2_precomp_gls(_MIPD_ int sz,BOOL norm,ecn2 *P,zzn2 *psi,ecn2 *T)
1328 {
1329 int i,j;
1330
1331 #ifdef MR_OS_THREADS
1332 miracl *mr_mip=get_mip();
1333 #endif
1334
1335 j=0;
1336
1337 MR_IN(219)
1338
1339 ecn2_norm(_MIPP_ P);
1340 ecn2_copy(P,&T[0]);
1341
1342 ecn2_pre(_MIPP_ sz,norm,T); /* precompute table */
1343
1344 for (i=sz;i<sz+sz;i++)
1345 {
1346 ecn2_copy(&T[i-sz],&T[i]);
1347 ecn2_psi(_MIPP_ psi,&T[i]);
1348 }
1349
1350 MR_OUT
1351 }
1352
1353 #ifndef MR_NO_ECC_MULTIADD
1354
1355 /* Calculate a[0].P+a[1].psi(P) using interleaving method */
1356
1357 #define MR_MUL2_GLS_RESERVE (2+2*MR_ECC_STORE_N2*4)
1358
ecn2_mul2_gls(_MIPD_ big * a,ecn2 * P,zzn2 * psi,ecn2 * R)1359 int ecn2_mul2_gls(_MIPD_ big *a,ecn2 *P,zzn2 *psi,ecn2 *R)
1360 {
1361 int i,j,nadds;
1362 ecn2 T[2*MR_ECC_STORE_N2];
1363 big a3[2];
1364 #ifdef MR_OS_THREADS
1365 miracl *mr_mip=get_mip();
1366 #endif
1367
1368 #ifndef MR_STATIC
1369 char *mem = (char *)memalloc(_MIPP_ MR_MUL2_GLS_RESERVE);
1370 #else
1371 char mem[MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE)];
1372 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE));
1373 #endif
1374
1375 for (j=i=0;i<2;i++)
1376 a3[i]=mirvar_mem(_MIPP_ mem, j++);
1377
1378 for (i=0;i<2*MR_ECC_STORE_N2;i++)
1379 {
1380 T[i].x.a=mirvar_mem(_MIPP_ mem, j++);
1381 T[i].x.b=mirvar_mem(_MIPP_ mem, j++);
1382 T[i].y.a=mirvar_mem(_MIPP_ mem, j++);
1383 T[i].y.b=mirvar_mem(_MIPP_ mem, j++);
1384 T[i].marker=MR_EPOINT_INFINITY;
1385 }
1386 MR_IN(220)
1387
1388 ecn2_precomp_gls(_MIPP_ MR_ECC_STORE_N2,TRUE,P,psi,T);
1389
1390 for (i=0;i<2;i++) premult(_MIPP_ a[i],3,a3[i]); /* calculate for NAF */
1391
1392 nadds=ecn2_muln_engine(_MIPP_ 0,0,2,MR_ECC_STORE_N2,NULL,NULL,a,a3,NULL,T,R);
1393
1394 ecn2_norm(_MIPP_ R);
1395
1396 MR_OUT
1397
1398 #ifndef MR_STATIC
1399 memkill(_MIPP_ mem, MR_MUL2_GLS_RESERVE);
1400 #else
1401 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE));
1402 #endif
1403 return nadds;
1404 }
1405
1406 /* Calculates a[0]*P+a[1]*psi(P) + b[0]*Q+b[1]*psi(Q)
1407 where P is fixed, and precomputations are already done off-line into FT
1408 using ecn2_precomp_gls. Useful for signature verification */
1409
1410 #define MR_MUL4_GLS_V_RESERVE (4+2*MR_ECC_STORE_N2*4)
1411
ecn2_mul4_gls_v(_MIPD_ big * a,int ns,ecn2 * FT,big * b,ecn2 * Q,zzn2 * psi,ecn2 * R)1412 int ecn2_mul4_gls_v(_MIPD_ big *a,int ns,ecn2 *FT,big *b,ecn2 *Q,zzn2 *psi,ecn2 *R)
1413 {
1414 int i,j,nadds;
1415 ecn2 VT[2*MR_ECC_STORE_N2];
1416 big a3[2],b3[2];
1417 #ifdef MR_OS_THREADS
1418 miracl *mr_mip=get_mip();
1419 #endif
1420
1421 #ifndef MR_STATIC
1422 char *mem = (char *)memalloc(_MIPP_ MR_MUL4_GLS_V_RESERVE);
1423 #else
1424 char mem[MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE)];
1425 memset(mem, 0, MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE));
1426 #endif
1427 j=0;
1428 for (i=0;i<2;i++)
1429 {
1430 a3[i]=mirvar_mem(_MIPP_ mem, j++);
1431 b3[i]=mirvar_mem(_MIPP_ mem, j++);
1432 }
1433 for (i=0;i<2*MR_ECC_STORE_N2;i++)
1434 {
1435 VT[i].x.a=mirvar_mem(_MIPP_ mem, j++);
1436 VT[i].x.b=mirvar_mem(_MIPP_ mem, j++);
1437 VT[i].y.a=mirvar_mem(_MIPP_ mem, j++);
1438 VT[i].y.b=mirvar_mem(_MIPP_ mem, j++);
1439 VT[i].marker=MR_EPOINT_INFINITY;
1440 }
1441
1442 MR_IN(217)
1443
1444 ecn2_precomp_gls(_MIPP_ MR_ECC_STORE_N2,TRUE,Q,psi,VT); /* precompute for the variable points */
1445 for (i=0;i<2;i++)
1446 { /* needed for NAF */
1447 premult(_MIPP_ a[i],3,a3[i]);
1448 premult(_MIPP_ b[i],3,b3[i]);
1449 }
1450 nadds=ecn2_muln_engine(_MIPP_ 2,ns,2,MR_ECC_STORE_N2,a,a3,b,b3,FT,VT,R);
1451 ecn2_norm(_MIPP_ R);
1452
1453 MR_OUT
1454
1455 #ifndef MR_STATIC
1456 memkill(_MIPP_ mem, MR_MUL4_GLS_V_RESERVE);
1457 #else
1458 memset(mem, 0, MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE));
1459 #endif
1460 return nadds;
1461 }
1462
1463 /* Calculate a.P+b.Q using interleaving method. P is fixed and FT is precomputed from it */
1464
ecn2_precomp(_MIPD_ int sz,BOOL norm,ecn2 * P,ecn2 * T)1465 void ecn2_precomp(_MIPD_ int sz,BOOL norm,ecn2 *P,ecn2 *T)
1466 {
1467 #ifdef MR_OS_THREADS
1468 miracl *mr_mip=get_mip();
1469 #endif
1470
1471 MR_IN(216)
1472
1473 ecn2_norm(_MIPP_ P);
1474 ecn2_copy(P,&T[0]);
1475 ecn2_pre(_MIPP_ sz,norm,T);
1476
1477 MR_OUT
1478 }
1479
1480 #ifndef MR_DOUBLE_BIG
1481 #define MR_MUL2_RESERVE (2+2*MR_ECC_STORE_N2*4)
1482 #else
1483 #define MR_MUL2_RESERVE (4+2*MR_ECC_STORE_N2*4)
1484 #endif
1485
ecn2_mul2(_MIPD_ big a,int ns,ecn2 * FT,big b,ecn2 * Q,ecn2 * R)1486 int ecn2_mul2(_MIPD_ big a,int ns,ecn2 *FT,big b,ecn2 *Q,ecn2 *R)
1487 {
1488 int i,j,nadds;
1489 ecn2 T[2*MR_ECC_STORE_N2];
1490 big a3,b3;
1491 #ifdef MR_OS_THREADS
1492 miracl *mr_mip=get_mip();
1493 #endif
1494
1495 #ifndef MR_STATIC
1496 char *mem = (char *)memalloc(_MIPP_ MR_MUL2_RESERVE);
1497 #else
1498 char mem[MR_BIG_RESERVE(MR_MUL2_RESERVE)];
1499 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_RESERVE));
1500 #endif
1501
1502 j=0;
1503 #ifndef MR_DOUBLE_BIG
1504 a3=mirvar_mem(_MIPP_ mem, j++);
1505 b3=mirvar_mem(_MIPP_ mem, j++);
1506 #else
1507 a3=mirvar_mem(_MIPP_ mem, j); j+=2;
1508 b3=mirvar_mem(_MIPP_ mem, j); j+=2;
1509 #endif
1510 for (i=0;i<2*MR_ECC_STORE_N2;i++)
1511 {
1512 T[i].x.a=mirvar_mem(_MIPP_ mem, j++);
1513 T[i].x.b=mirvar_mem(_MIPP_ mem, j++);
1514 T[i].y.a=mirvar_mem(_MIPP_ mem, j++);
1515 T[i].y.b=mirvar_mem(_MIPP_ mem, j++);
1516 T[i].marker=MR_EPOINT_INFINITY;
1517 }
1518
1519 MR_IN(218)
1520
1521 ecn2_precomp(_MIPP_ MR_ECC_STORE_N2,TRUE,Q,T);
1522
1523 premult(_MIPP_ a,3,a3);
1524 premult(_MIPP_ b,3,b3);
1525
1526 nadds=ecn2_muln_engine(_MIPP_ 1,ns,1,MR_ECC_STORE_N2,&a,&a3,&b,&b3,FT,T,R);
1527
1528 ecn2_norm(_MIPP_ R);
1529
1530 MR_OUT
1531
1532 #ifndef MR_STATIC
1533 memkill(_MIPP_ mem, MR_MUL2_RESERVE);
1534 #else
1535 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_RESERVE));
1536 #endif
1537 return nadds;
1538 }
1539 #endif
1540 #endif
1541
1542 #ifndef MR_STATIC
1543
ecn2_brick_init(_MIPD_ ebrick * B,zzn2 * x,zzn2 * y,big a,big b,big n,int window,int nb)1544 BOOL ecn2_brick_init(_MIPD_ ebrick *B,zzn2 *x,zzn2 *y,big a,big b,big n,int window,int nb)
1545 { /* Uses Montgomery arithmetic internally *
1546 * (x,y) is the fixed base *
1547 * a,b and n are parameters and modulus of the curve *
1548 * window is the window size in bits and *
1549 * nb is the maximum number of bits in the multiplier */
1550 int i,j,k,t,bp,len,bptr,is;
1551 ecn2 *table;
1552 ecn2 w;
1553
1554 #ifdef MR_OS_THREADS
1555 miracl *mr_mip=get_mip();
1556 #endif
1557
1558 if (nb<2 || window<1 || window>nb || mr_mip->ERNUM) return FALSE;
1559
1560 t=MR_ROUNDUP(nb,window);
1561
1562 if (t<2) return FALSE;
1563
1564 MR_IN(221)
1565
1566 #ifndef MR_ALWAYS_BINARY
1567 if (mr_mip->base != mr_mip->base2)
1568 {
1569 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
1570 MR_OUT
1571 return FALSE;
1572 }
1573 #endif
1574
1575 B->window=window;
1576 B->max=nb;
1577 table=(ecn2 *)mr_alloc(_MIPP_ (1<<window),sizeof(ecn2));
1578 if (table==NULL)
1579 {
1580 mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);
1581 MR_OUT
1582 return FALSE;
1583 }
1584 B->a=mirvar(_MIPP_ 0);
1585 B->b=mirvar(_MIPP_ 0);
1586 B->n=mirvar(_MIPP_ 0);
1587 copy(a,B->a);
1588 copy(b,B->b);
1589 copy(n,B->n);
1590
1591 ecurve_init(_MIPP_ a,b,n,MR_AFFINE);
1592 mr_mip->TWIST=MR_QUADRATIC;
1593
1594 w.x.a=mirvar(_MIPP_ 0);
1595 w.x.b=mirvar(_MIPP_ 0);
1596 w.y.a=mirvar(_MIPP_ 0);
1597 w.y.b=mirvar(_MIPP_ 0);
1598 w.marker=MR_EPOINT_INFINITY;
1599 ecn2_set(_MIPP_ x,y,&w);
1600
1601 table[0].x.a=mirvar(_MIPP_ 0);
1602 table[0].x.b=mirvar(_MIPP_ 0);
1603 table[0].y.a=mirvar(_MIPP_ 0);
1604 table[0].y.b=mirvar(_MIPP_ 0);
1605 table[0].marker=MR_EPOINT_INFINITY;
1606 table[1].x.a=mirvar(_MIPP_ 0);
1607 table[1].x.b=mirvar(_MIPP_ 0);
1608 table[1].y.a=mirvar(_MIPP_ 0);
1609 table[1].y.b=mirvar(_MIPP_ 0);
1610 table[1].marker=MR_EPOINT_INFINITY;
1611
1612 ecn2_copy(&w,&table[1]);
1613 for (j=0;j<t;j++)
1614 ecn2_add(_MIPP_ &w,&w);
1615
1616 k=1;
1617 for (i=2;i<(1<<window);i++)
1618 {
1619 table[i].x.a=mirvar(_MIPP_ 0);
1620 table[i].x.b=mirvar(_MIPP_ 0);
1621 table[i].y.a=mirvar(_MIPP_ 0);
1622 table[i].y.b=mirvar(_MIPP_ 0);
1623 table[i].marker=MR_EPOINT_INFINITY;
1624 if (i==(1<<k))
1625 {
1626 k++;
1627 ecn2_copy(&w,&table[i]);
1628
1629 for (j=0;j<t;j++)
1630 ecn2_add(_MIPP_ &w,&w);
1631 continue;
1632 }
1633 bp=1;
1634 for (j=0;j<k;j++)
1635 {
1636 if (i&bp)
1637 {
1638 is=1<<j;
1639 ecn2_add(_MIPP_ &table[is],&table[i]);
1640 }
1641 bp<<=1;
1642 }
1643 }
1644 mr_free(w.x.a);
1645 mr_free(w.x.b);
1646 mr_free(w.y.a);
1647 mr_free(w.y.b);
1648
1649 /* create the table */
1650
1651 len=n->len;
1652 bptr=0;
1653 B->table=(mr_small *)mr_alloc(_MIPP_ 4*len*(1<<window),sizeof(mr_small));
1654
1655 for (i=0;i<(1<<window);i++)
1656 {
1657 for (j=0;j<len;j++) B->table[bptr++]=table[i].x.a->w[j];
1658 for (j=0;j<len;j++) B->table[bptr++]=table[i].x.b->w[j];
1659
1660 for (j=0;j<len;j++) B->table[bptr++]=table[i].y.a->w[j];
1661 for (j=0;j<len;j++) B->table[bptr++]=table[i].y.b->w[j];
1662
1663 mr_free(table[i].x.a);
1664 mr_free(table[i].x.b);
1665 mr_free(table[i].y.a);
1666 mr_free(table[i].y.b);
1667 }
1668
1669 mr_free(table);
1670
1671 MR_OUT
1672 return TRUE;
1673 }
1674
ecn2_brick_end(ebrick * B)1675 void ecn2_brick_end(ebrick *B)
1676 {
1677 mirkill(B->n);
1678 mirkill(B->b);
1679 mirkill(B->a);
1680 mr_free(B->table);
1681 }
1682
1683 #else
1684
1685 /* use precomputated table in ROM */
1686
ecn2_brick_init(ebrick * B,const mr_small * rom,big a,big b,big n,int window,int nb)1687 void ecn2_brick_init(ebrick *B,const mr_small* rom,big a,big b,big n,int window,int nb)
1688 {
1689 B->table=rom;
1690 B->a=a; /* just pass a pointer */
1691 B->b=b;
1692 B->n=n;
1693 B->window=window; /* 2^4=16 stored values */
1694 B->max=nb;
1695 }
1696
1697 #endif
1698
1699 /*
1700 void ecn2_mul_brick(_MIPD_ ebrick *B,big e,zzn2 *x,zzn2 *y)
1701 {
1702 int i,j,t,len,maxsize,promptr;
1703 ecn2 w,z;
1704
1705 #ifdef MR_STATIC
1706 char mem[MR_BIG_RESERVE(10)];
1707 #else
1708 char *mem;
1709 #endif
1710 #ifdef MR_OS_THREADS
1711 miracl *mr_mip=get_mip();
1712 #endif
1713
1714 if (size(e)<0) mr_berror(_MIPP_ MR_ERR_NEG_POWER);
1715 t=MR_ROUNDUP(B->max,B->window);
1716
1717 MR_IN(116)
1718
1719 #ifndef MR_ALWAYS_BINARY
1720 if (mr_mip->base != mr_mip->base2)
1721 {
1722 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
1723 MR_OUT
1724 return;
1725 }
1726 #endif
1727
1728 if (logb2(_MIPP_ e) > B->max)
1729 {
1730 mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
1731 MR_OUT
1732 return;
1733 }
1734
1735 ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
1736 mr_mip->TWIST=MR_QUADRATIC;
1737
1738 #ifdef MR_STATIC
1739 memset(mem,0,MR_BIG_RESERVE(10));
1740 #else
1741 mem=memalloc(_MIPP_ 10);
1742 #endif
1743
1744 w.x.a=mirvar_mem(_MIPP_ mem, 0);
1745 w.x.b=mirvar_mem(_MIPP_ mem, 1);
1746 w.y.a=mirvar_mem(_MIPP_ mem, 2);
1747 w.y.b=mirvar_mem(_MIPP_ mem, 3);
1748 w.z.a=mirvar_mem(_MIPP_ mem, 4);
1749 w.z.b=mirvar_mem(_MIPP_ mem, 5);
1750 w.marker=MR_EPOINT_INFINITY;
1751 z.x.a=mirvar_mem(_MIPP_ mem, 6);
1752 z.x.b=mirvar_mem(_MIPP_ mem, 7);
1753 z.y.a=mirvar_mem(_MIPP_ mem, 8);
1754 z.y.b=mirvar_mem(_MIPP_ mem, 9);
1755 z.marker=MR_EPOINT_INFINITY;
1756
1757 len=B->n->len;
1758 maxsize=4*(1<<B->window)*len;
1759
1760 for (i=t-1;i>=0;i--)
1761 {
1762 j=recode(_MIPP_ e,t,B->window,i);
1763 ecn2_add(_MIPP_ &w,&w);
1764 if (j>0)
1765 {
1766 promptr=4*j*len;
1767 init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
1768 init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
1769 init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
1770 init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
1771 z.marker=MR_EPOINT_NORMALIZED;
1772 ecn2_add(_MIPP_ &z,&w);
1773 }
1774 }
1775 ecn2_norm(_MIPP_ &w);
1776 ecn2_getxy(&w,x,y);
1777 #ifndef MR_STATIC
1778 memkill(_MIPP_ mem,10);
1779 #else
1780 memset(mem,0,MR_BIG_RESERVE(10));
1781 #endif
1782 MR_OUT
1783 }
1784 */
1785
ecn2_mul_brick_gls(_MIPD_ ebrick * B,big * e,zzn2 * psi,zzn2 * x,zzn2 * y)1786 void ecn2_mul_brick_gls(_MIPD_ ebrick *B,big *e,zzn2 *psi,zzn2 *x,zzn2 *y)
1787 {
1788 int i,j,k,t,len,maxsize,promptr,se[2];
1789 ecn2 w,z;
1790
1791 #ifdef MR_STATIC
1792 char mem[MR_BIG_RESERVE(10)];
1793 #else
1794 char *mem;
1795 #endif
1796 #ifdef MR_OS_THREADS
1797 miracl *mr_mip=get_mip();
1798 #endif
1799
1800 for (k=0;k<2;k++) se[k]=exsign(e[k]);
1801
1802 t=MR_ROUNDUP(B->max,B->window);
1803
1804 MR_IN(222)
1805
1806 #ifndef MR_ALWAYS_BINARY
1807 if (mr_mip->base != mr_mip->base2)
1808 {
1809 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
1810 MR_OUT
1811 return;
1812 }
1813 #endif
1814
1815 if (logb2(_MIPP_ e[0])>B->max || logb2(_MIPP_ e[1])>B->max)
1816 {
1817 mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
1818 MR_OUT
1819 return;
1820 }
1821
1822 ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
1823 mr_mip->TWIST=MR_QUADRATIC;
1824
1825 #ifdef MR_STATIC
1826 memset(mem,0,MR_BIG_RESERVE(10));
1827 #else
1828 mem=(char *)memalloc(_MIPP_ 10);
1829 #endif
1830
1831 z.x.a=mirvar_mem(_MIPP_ mem, 0);
1832 z.x.b=mirvar_mem(_MIPP_ mem, 1);
1833 z.y.a=mirvar_mem(_MIPP_ mem, 2);
1834 z.y.b=mirvar_mem(_MIPP_ mem, 3);
1835 z.marker=MR_EPOINT_INFINITY;
1836
1837 w.x.a=mirvar_mem(_MIPP_ mem, 4);
1838 w.x.b=mirvar_mem(_MIPP_ mem, 5);
1839 w.y.a=mirvar_mem(_MIPP_ mem, 6);
1840 w.y.b=mirvar_mem(_MIPP_ mem, 7);
1841 #ifndef MR_AFFINE_ONLY
1842 w.z.a=mirvar_mem(_MIPP_ mem, 8);
1843 w.z.b=mirvar_mem(_MIPP_ mem, 9);
1844 #endif
1845 w.marker=MR_EPOINT_INFINITY;
1846
1847 len=B->n->len;
1848 maxsize=4*(1<<B->window)*len;
1849
1850 for (i=t-1;i>=0;i--)
1851 {
1852 ecn2_add(_MIPP_ &w,&w);
1853 for (k=0;k<2;k++)
1854 {
1855 j=recode(_MIPP_ e[k],t,B->window,i);
1856 if (j>0)
1857 {
1858 promptr=4*j*len;
1859 init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
1860 init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
1861 init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
1862 init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
1863 z.marker=MR_EPOINT_NORMALIZED;
1864 if (k==1) ecn2_psi(_MIPP_ psi,&z);
1865 if (se[k]==PLUS) ecn2_add(_MIPP_ &z,&w);
1866 else ecn2_sub(_MIPP_ &z,&w);
1867 }
1868 }
1869 }
1870 ecn2_norm(_MIPP_ &w);
1871 ecn2_getxy(&w,x,y);
1872 #ifndef MR_STATIC
1873 memkill(_MIPP_ mem,10);
1874 #else
1875 memset(mem,0,MR_BIG_RESERVE(10));
1876 #endif
1877 MR_OUT
1878 }
1879
1880 #else
1881
1882 /* Now for curves in Inverted Twisted Edwards Form */
1883
ecn2_iszero(ecn2 * a)1884 BOOL ecn2_iszero(ecn2 *a)
1885 {
1886 if (a->marker==MR_EPOINT_INFINITY) return TRUE;
1887 return FALSE;
1888 }
1889
ecn2_copy(ecn2 * a,ecn2 * b)1890 void ecn2_copy(ecn2 *a,ecn2 *b)
1891 {
1892 zzn2_copy(&(a->x),&(b->x));
1893 zzn2_copy(&(a->y),&(b->y));
1894 if (a->marker==MR_EPOINT_GENERAL) zzn2_copy(&(a->z),&(b->z));
1895 b->marker=a->marker;
1896 }
1897
ecn2_zero(ecn2 * a)1898 void ecn2_zero(ecn2 *a)
1899 {
1900 zzn2_zero(&(a->x));
1901 zzn2_zero(&(a->y));
1902 if (a->marker==MR_EPOINT_GENERAL) zzn2_zero(&(a->z));
1903 a->marker=MR_EPOINT_INFINITY;
1904 }
1905
ecn2_compare(_MIPD_ ecn2 * a,ecn2 * b)1906 BOOL ecn2_compare(_MIPD_ ecn2 *a,ecn2 *b)
1907 {
1908 #ifdef MR_OS_THREADS
1909 miracl *mr_mip=get_mip();
1910 #endif
1911 if (mr_mip->ERNUM) return FALSE;
1912
1913 MR_IN(193)
1914 ecn2_norm(_MIPP_ a);
1915 ecn2_norm(_MIPP_ b);
1916 MR_OUT
1917 if (zzn2_compare(&(a->x),&(b->x)) && zzn2_compare(&(a->y),&(b->y)) && a->marker==b->marker) return TRUE;
1918 return FALSE;
1919 }
1920
ecn2_norm(_MIPD_ ecn2 * a)1921 void ecn2_norm(_MIPD_ ecn2 *a)
1922 {
1923 #ifdef MR_OS_THREADS
1924 miracl *mr_mip=get_mip();
1925 #endif
1926
1927 if (mr_mip->ERNUM) return;
1928 if (a->marker!=MR_EPOINT_GENERAL) return;
1929
1930 MR_IN(194)
1931
1932 zzn2_inv(_MIPP_ &(a->z));
1933
1934 zzn2_mul(_MIPP_ &(a->x),&(a->z),&(a->x));
1935 zzn2_mul(_MIPP_ &(a->y),&(a->z),&(a->y));
1936 zzn2_from_zzn(mr_mip->one,&(a->z));
1937 a->marker=MR_EPOINT_NORMALIZED;
1938
1939 MR_OUT
1940
1941 }
1942
ecn2_get(_MIPD_ ecn2 * e,zzn2 * x,zzn2 * y,zzn2 * z)1943 void ecn2_get(_MIPD_ ecn2 *e,zzn2 *x,zzn2 *y,zzn2 *z)
1944 {
1945 #ifdef MR_OS_THREADS
1946 miracl *mr_mip=get_mip();
1947 #endif
1948
1949 zzn2_copy(&(e->x),x);
1950 zzn2_copy(&(e->y),y);
1951 if (e->marker==MR_EPOINT_GENERAL) zzn2_copy(&(e->z),z);
1952 else zzn2_from_zzn(mr_mip->one,z);
1953 }
1954
ecn2_getxy(ecn2 * e,zzn2 * x,zzn2 * y)1955 void ecn2_getxy(ecn2 *e,zzn2 *x,zzn2 *y)
1956 {
1957 zzn2_copy(&(e->x),x);
1958 zzn2_copy(&(e->y),y);
1959 }
1960
ecn2_getx(ecn2 * e,zzn2 * x)1961 void ecn2_getx(ecn2 *e,zzn2 *x)
1962 {
1963 zzn2_copy(&(e->x),x);
1964 }
1965
ecn2_getz(_MIPD_ ecn2 * e,zzn2 * z)1966 void ecn2_getz(_MIPD_ ecn2 *e,zzn2 *z)
1967 {
1968 #ifdef MR_OS_THREADS
1969 miracl *mr_mip=get_mip();
1970 #endif
1971 if (e->marker==MR_EPOINT_GENERAL) zzn2_copy(&(e->z),z);
1972 else zzn2_from_zzn(mr_mip->one,z);
1973 }
1974
ecn2_psi(_MIPD_ zzn2 * psi,ecn2 * P)1975 void ecn2_psi(_MIPD_ zzn2 *psi,ecn2 *P)
1976 { /* apply GLS morphism to P */
1977 #ifdef MR_OS_THREADS
1978 miracl *mr_mip=get_mip();
1979 #endif
1980
1981 MR_IN(212)
1982 zzn2_conj(_MIPP_ &(P->x),&(P->x));
1983 zzn2_conj(_MIPP_ &(P->y),&(P->y));
1984 if (P->marker==MR_EPOINT_GENERAL)
1985 zzn2_conj(_MIPP_ &(P->z),&(P->z));
1986 zzn2_mul(_MIPP_ &(P->x),&psi[0],&(P->x));
1987
1988 MR_OUT
1989 }
1990 /*
1991 static void out_zzn2(zzn2 *x)
1992 {
1993 redc(x->a,x->a);
1994 redc(x->b,x->b);
1995 cotnum(x->a,stdout);
1996 cotnum(x->b,stdout);
1997 nres(x->a,x->a);
1998 nres(x->b,x->b);
1999 }
2000 */
2001
2002 /* find RHS=(x^2-B)/(x^2-A) */
2003
ecn2_rhs(_MIPD_ zzn2 * x,zzn2 * rhs)2004 void ecn2_rhs(_MIPD_ zzn2 *x,zzn2 *rhs)
2005 { /* calculate RHS of elliptic curve equation */
2006 int twist;
2007 zzn2 A,B;
2008 #ifdef MR_OS_THREADS
2009 miracl *mr_mip=get_mip();
2010 #endif
2011 if (mr_mip->ERNUM) return;
2012 twist=mr_mip->TWIST;
2013
2014 MR_IN(202)
2015
2016 A.a=mr_mip->w8;
2017 A.b=mr_mip->w9;
2018 B.a=mr_mip->w10;
2019 B.b=mr_mip->w11;
2020
2021 zzn2_from_zzn(mr_mip->A,&A);
2022 zzn2_from_zzn(mr_mip->B,&B);
2023
2024 if (twist==MR_QUADRATIC)
2025 { /* quadratic twist */
2026 zzn2_txx(_MIPP_ &A);
2027 zzn2_txx(_MIPP_ &B);
2028 }
2029
2030 zzn2_sqr(_MIPP_ x,rhs);
2031
2032 zzn2_sub(_MIPP_ rhs,&B,&B);
2033
2034 zzn2_sub(_MIPP_ rhs,&A,&A);
2035
2036 zzn2_inv(_MIPP_ &A);
2037 zzn2_mul(_MIPP_ &A,&B,rhs);
2038
2039 MR_OUT
2040 }
2041
ecn2_set(_MIPD_ zzn2 * x,zzn2 * y,ecn2 * e)2042 BOOL ecn2_set(_MIPD_ zzn2 *x,zzn2 *y,ecn2 *e)
2043 {
2044 zzn2 lhs,rhs;
2045 #ifdef MR_OS_THREADS
2046 miracl *mr_mip=get_mip();
2047 #endif
2048 if (mr_mip->ERNUM) return FALSE;
2049
2050 MR_IN(195)
2051
2052 lhs.a=mr_mip->w12;
2053 lhs.b=mr_mip->w13;
2054 rhs.a=mr_mip->w14;
2055 rhs.b=mr_mip->w15;
2056
2057 ecn2_rhs(_MIPP_ x,&rhs);
2058
2059 zzn2_sqr(_MIPP_ y,&lhs);
2060
2061 if (!zzn2_compare(&lhs,&rhs))
2062 {
2063 MR_OUT
2064 return FALSE;
2065 }
2066
2067 zzn2_copy(x,&(e->x));
2068 zzn2_copy(y,&(e->y));
2069
2070 e->marker=MR_EPOINT_NORMALIZED;
2071
2072 MR_OUT
2073 return TRUE;
2074 }
2075
2076 #ifndef MR_NOSUPPORT_COMPRESSION
2077
ecn2_setx(_MIPD_ zzn2 * x,ecn2 * e)2078 BOOL ecn2_setx(_MIPD_ zzn2 *x,ecn2 *e)
2079 {
2080 zzn2 rhs;
2081 #ifdef MR_OS_THREADS
2082 miracl *mr_mip=get_mip();
2083 #endif
2084 if (mr_mip->ERNUM) return FALSE;
2085
2086 MR_IN(201)
2087
2088 rhs.a=mr_mip->w12;
2089 rhs.b=mr_mip->w13;
2090
2091 ecn2_rhs(_MIPP_ x,&rhs);
2092
2093 if (!zzn2_iszero(&rhs))
2094 {
2095 if (!zzn2_qr(_MIPP_ &rhs))
2096 {
2097 MR_OUT
2098 return FALSE;
2099 }
2100 zzn2_sqrt(_MIPP_ &rhs,&rhs);
2101 }
2102
2103 zzn2_copy(x,&(e->x));
2104 zzn2_copy(&rhs,&(e->y));
2105
2106 e->marker=MR_EPOINT_NORMALIZED;
2107
2108 MR_OUT
2109 return TRUE;
2110 }
2111
2112 #endif
2113
ecn2_setxyz(zzn2 * x,zzn2 * y,zzn2 * z,ecn2 * e)2114 void ecn2_setxyz(zzn2 *x,zzn2 *y,zzn2 *z,ecn2 *e)
2115 {
2116 zzn2_copy(x,&(e->x));
2117 zzn2_copy(y,&(e->y));
2118 zzn2_copy(z,&(e->z));
2119 e->marker=MR_EPOINT_GENERAL;
2120 }
2121
2122 /* Normalise an array of points of length m<MR_MAX_M_T_S - requires a zzn2 workspace array of length m */
2123
ecn2_multi_norm(_MIPD_ int m,zzn2 * work,ecn2 * p)2124 BOOL ecn2_multi_norm(_MIPD_ int m,zzn2 *work,ecn2 *p)
2125 {
2126
2127 #ifdef MR_OS_THREADS
2128 miracl *mr_mip=get_mip();
2129 #endif
2130
2131 int i;
2132 zzn2 one;
2133 zzn2 w[MR_MAX_M_T_S];
2134 if (mr_mip->ERNUM) return FALSE;
2135 if (m>MR_MAX_M_T_S) return FALSE;
2136
2137 MR_IN(215)
2138
2139 one.a=mr_mip->w12;
2140 one.b=mr_mip->w13;
2141
2142 zzn2_from_zzn(mr_mip->one,&one);
2143
2144 for (i=0;i<m;i++)
2145 {
2146 if (p[i].marker==MR_EPOINT_NORMALIZED) w[i]=one;
2147 else w[i]=p[i].z;
2148 }
2149
2150 if (!zzn2_multi_inverse(_MIPP_ m,w,work))
2151 {
2152 MR_OUT
2153 return FALSE;
2154 }
2155
2156 for (i=0;i<m;i++)
2157 {
2158 p[i].marker=MR_EPOINT_NORMALIZED;
2159 zzn2_mul(_MIPP_ &(p[i].x),&work[i],&(p[i].x));
2160 zzn2_mul(_MIPP_ &(p[i].y),&work[i],&(p[i].y));
2161 zzn2_from_zzn(mr_mip->one,&(p[i].z));
2162 }
2163 MR_OUT
2164
2165 return TRUE;
2166 }
2167
ecn2_add(_MIPD_ ecn2 * Q,ecn2 * P)2168 BOOL ecn2_add(_MIPD_ ecn2 *Q,ecn2 *P)
2169 { /* P+=Q */
2170 BOOL Doubling=FALSE;
2171 int twist;
2172 zzn2 t2,t3,t4;
2173
2174 #ifdef MR_OS_THREADS
2175 miracl *mr_mip=get_mip();
2176 #endif
2177
2178 t2.a = mr_mip->w8;
2179 t2.b = mr_mip->w9;
2180 t3.a = mr_mip->w10;
2181 t3.b = mr_mip->w11;
2182 t4.a = mr_mip->w12;
2183 t4.b = mr_mip->w13;
2184
2185 twist=mr_mip->TWIST;
2186 if (mr_mip->ERNUM) return FALSE;
2187
2188 if (P->marker==MR_EPOINT_INFINITY)
2189 {
2190 ecn2_copy(Q,P);
2191 return Doubling;
2192 }
2193 if (Q->marker==MR_EPOINT_INFINITY) return Doubling;
2194
2195 if (Q==P)
2196 {
2197 Doubling=TRUE;
2198 if (P->marker==MR_EPOINT_INFINITY)
2199 { /* 2 times infinity == infinity ! */
2200 return Doubling;
2201 }
2202 }
2203
2204 MR_IN(205)
2205
2206 if (!Doubling)
2207 { /* Addition */
2208 zzn2_add(_MIPP_ &(Q->x),&(Q->y),&t2);
2209 zzn2_add(_MIPP_ &(P->x),&(P->y),&t4);
2210 zzn2_mul(_MIPP_ &t4,&t2,&t4); /* I = t4 = (x1+y1)(x2+y2) */
2211 if (Q->marker!=MR_EPOINT_NORMALIZED)
2212 {
2213 if (P->marker==MR_EPOINT_NORMALIZED)
2214 zzn2_copy(&(Q->z),&(P->z));
2215 else
2216 zzn2_mul(_MIPP_ &(Q->z),&(P->z),&(P->z)); /* Z = z1*z2 */
2217 }
2218 else
2219 {
2220 if (P->marker==MR_EPOINT_NORMALIZED)
2221 zzn2_from_zzn(mr_mip->one,&(P->z));
2222 }
2223 zzn2_sqr(_MIPP_ &(P->z),&t2); /* P->z = z1.z2 */
2224 if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)
2225 zzn2_smul(_MIPP_ &t2,mr_mip->B,&t2);
2226 else
2227 zzn2_imul(_MIPP_ &t2,mr_mip->Bsize,&t2);
2228 if (twist==MR_QUADRATIC) zzn2_txx(_MIPP_ &t2); /* B = t2 = d*A^2 */
2229 zzn2_mul(_MIPP_ &(P->x),&(Q->x),&(P->x)); /* X = x1*x2 */
2230 zzn2_mul(_MIPP_ &(P->y),&(Q->y),&(P->y)); /* Y = y1*y2 */
2231 zzn2_sub(_MIPP_ &t4,&(P->x),&t4);
2232 zzn2_sub(_MIPP_ &t4,&(P->y),&t4); /* I = (x1+y1)(x2+y2)-X-Y */
2233 zzn2_mul(_MIPP_ &(P->x),&(P->y),&t3); /* E = t3 = X*Y */
2234 if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
2235 zzn2_smul(_MIPP_ &(P->y),mr_mip->A,&(P->y));
2236 else
2237 zzn2_imul(_MIPP_ &(P->y),mr_mip->Asize,&(P->y));
2238 if (twist==MR_QUADRATIC) zzn2_txx(_MIPP_ &(P->y)); /* Y=aY */
2239 zzn2_sub(_MIPP_ &(P->x),&(P->y),&(P->x)); /* X=X-aY */
2240 zzn2_mul(_MIPP_ &(P->z),&(P->x),&(P->z));
2241 zzn2_mul(_MIPP_ &(P->z),&t4,&(P->z));
2242 zzn2_sub(_MIPP_ &t3,&t2,&(P->y));
2243 zzn2_mul(_MIPP_ &(P->y),&t4,&(P->y));
2244 zzn2_add(_MIPP_ &t3,&t2,&t4);
2245 zzn2_mul(_MIPP_ &(P->x),&t4,&(P->x));
2246 }
2247 else
2248 { /* doubling */
2249 zzn2_add(_MIPP_ &(P->x),&(P->y),&t2);
2250 zzn2_sqr(_MIPP_ &t2,&t2);
2251 zzn2_sqr(_MIPP_ &(P->x),&(P->x));
2252 zzn2_sqr(_MIPP_ &(P->y),&(P->y));
2253 zzn2_sub(_MIPP_ &t2,&(P->x),&t2);
2254 zzn2_sub(_MIPP_ &t2,&(P->y),&t2); /* E=(X+Y)^2-X^2-Y^2 */
2255
2256 if (P->marker!=MR_EPOINT_NORMALIZED)
2257 zzn2_sqr(_MIPP_ &(P->z),&(P->z));
2258 else
2259 zzn2_from_zzn(mr_mip->one,&(P->z));
2260
2261 zzn2_add(_MIPP_ &(P->z),&(P->z),&(P->z));
2262 if (mr_abs(mr_mip->Bsize)==MR_TOOBIG)
2263 zzn2_smul(_MIPP_ &(P->z),mr_mip->B,&(P->z));
2264 else
2265 zzn2_imul(_MIPP_ &(P->z),mr_mip->Bsize,&(P->z));
2266 if (twist==MR_QUADRATIC) zzn2_txx(_MIPP_ &(P->z));
2267 if (mr_abs(mr_mip->Asize)==MR_TOOBIG)
2268 zzn2_smul(_MIPP_ &(P->y),mr_mip->A,&(P->y));
2269 else
2270 zzn2_imul(_MIPP_ &(P->y),mr_mip->Asize,&(P->y));
2271 if (twist==MR_QUADRATIC) zzn2_txx(_MIPP_ &(P->y));
2272 zzn2_add(_MIPP_ &(P->x),&(P->y),&t3);
2273 zzn2_sub(_MIPP_ &(P->x),&(P->y),&t4);
2274 zzn2_mul(_MIPP_ &t3,&t4,&(P->x));
2275
2276 zzn2_sub(_MIPP_ &t3,&(P->z),&t3);
2277 zzn2_mul(_MIPP_ &t2,&t3,&(P->y));
2278 zzn2_mul(_MIPP_ &t2,&t4,&(P->z));
2279 }
2280
2281 if (zzn2_iszero(&(P->z)))
2282 {
2283 zzn2_from_zzn(mr_mip->one,&(P->x));
2284 zzn2_zero(&(P->y));
2285 P->marker=MR_EPOINT_INFINITY;
2286 }
2287 else P->marker=MR_EPOINT_GENERAL;
2288
2289 MR_OUT
2290 return Doubling;
2291 }
2292
ecn2_negate(_MIPD_ ecn2 * u,ecn2 * w)2293 void ecn2_negate(_MIPD_ ecn2 *u,ecn2 *w)
2294 {
2295 #ifdef MR_OS_THREADS
2296 miracl *mr_mip=get_mip();
2297 #endif
2298
2299 ecn2_copy(u,w);
2300 if (w->marker!=MR_EPOINT_INFINITY)
2301 zzn2_negate(_MIPP_ &(w->x),&(w->x));
2302 }
2303
2304
ecn2_sub(_MIPD_ ecn2 * Q,ecn2 * P)2305 BOOL ecn2_sub(_MIPD_ ecn2 *Q,ecn2 *P)
2306 {
2307 BOOL Doubling;
2308 #ifdef MR_OS_THREADS
2309 miracl *mr_mip=get_mip();
2310 #endif
2311 zzn2 lam;
2312
2313 lam.a = mr_mip->w14;
2314 lam.b = mr_mip->w15;
2315
2316 ecn2_negate(_MIPP_ Q,Q);
2317
2318 Doubling=ecn2_add(_MIPP_ Q,P);
2319
2320 ecn2_negate(_MIPP_ Q,Q);
2321
2322 return Doubling;
2323 }
2324
2325 /*
2326
2327 BOOL ecn2_add_sub(_MIPD_ ecn2 *P,ecn2 *Q,ecn2 *PP,ecn2 *PM)
2328 { PP=P+Q, PM=P-Q. Assumes P and Q are both normalized, and P!=Q
2329 #ifdef MR_OS_THREADS
2330 miracl *mr_mip=get_mip();
2331 #endif
2332 zzn2 t1,t2,lam;
2333
2334 if (mr_mip->ERNUM) return FALSE;
2335
2336 PP->marker=MR_EPOINT_NORMALIZED;
2337 PM->marker=MR_EPOINT_NORMALIZED;
2338
2339 return TRUE;
2340 }
2341
2342 */
2343
2344 /* Precomputation of 3P, 5P, 7P etc. into PT. Assume PT[0] contains P */
2345
2346 #define MR_PRE_2 (6+2*MR_MAX_M_T_S)
2347
ecn2_pre(_MIPD_ int sz,BOOL norm,ecn2 * PT)2348 static void ecn2_pre(_MIPD_ int sz,BOOL norm,ecn2 *PT)
2349 {
2350 int i,j;
2351 ecn2 P2;
2352 #ifdef MR_OS_THREADS
2353 miracl *mr_mip=get_mip();
2354 #endif
2355
2356 #ifndef MR_STATIC
2357 zzn2 *work=(zzn2 *)mr_alloc(_MIPP_ sz,sizeof(zzn2));
2358 char *mem = memalloc(_MIPP_ 6+2*sz);
2359 #else
2360 zzn2 work[MR_MAX_M_T_S];
2361 char mem[MR_BIG_RESERVE(MR_PRE_2)];
2362 memset(mem, 0, MR_BIG_RESERVE(MR_PRE_2));
2363 #endif
2364 j=0;
2365 P2.x.a=mirvar_mem(_MIPP_ mem, j++);
2366 P2.x.b=mirvar_mem(_MIPP_ mem, j++);
2367 P2.y.a=mirvar_mem(_MIPP_ mem, j++);
2368 P2.y.b=mirvar_mem(_MIPP_ mem, j++);
2369 P2.z.a=mirvar_mem(_MIPP_ mem, j++);
2370 P2.z.b=mirvar_mem(_MIPP_ mem, j++);
2371
2372 for (i=0;i<sz;i++)
2373 {
2374 work[i].a= mirvar_mem(_MIPP_ mem, j++);
2375 work[i].b= mirvar_mem(_MIPP_ mem, j++);
2376 }
2377
2378 ecn2_copy(&PT[0],&P2);
2379 ecn2_add(_MIPP_ &P2,&P2);
2380 for (i=1;i<sz;i++)
2381 {
2382 ecn2_copy(&PT[i-1],&PT[i]);
2383 ecn2_add(_MIPP_ &P2,&PT[i]);
2384
2385 }
2386 if (norm) ecn2_multi_norm(_MIPP_ sz,work,PT);
2387
2388 #ifndef MR_STATIC
2389 memkill(_MIPP_ mem, 6+2*sz);
2390 mr_free(work);
2391 #else
2392 memset(mem, 0, MR_BIG_RESERVE(MR_PRE_2));
2393 #endif
2394 }
2395
2396 #ifndef MR_DOUBLE_BIG
2397 #define MR_MUL_RESERVE (1+6*MR_ECC_STORE_N2)
2398 #else
2399 #define MR_MUL_RESERVE (2+6*MR_ECC_STORE_N2)
2400 #endif
2401
ecn2_mul(_MIPD_ big k,ecn2 * P)2402 int ecn2_mul(_MIPD_ big k,ecn2 *P)
2403 {
2404 int i,j,nb,n,nbs,nzs,nadds;
2405 big h;
2406 BOOL neg;
2407 ecn2 T[MR_ECC_STORE_N2];
2408 #ifdef MR_OS_THREADS
2409 miracl *mr_mip=get_mip();
2410 #endif
2411
2412 #ifndef MR_STATIC
2413 char *mem = memalloc(_MIPP_ MR_MUL_RESERVE);
2414 #else
2415 char mem[MR_BIG_RESERVE(MR_MUL_RESERVE)];
2416 memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
2417 #endif
2418
2419 j=0;
2420 #ifndef MR_DOUBLE_BIG
2421 h=mirvar_mem(_MIPP_ mem, j++);
2422 #else
2423 h=mirvar_mem(_MIPP_ mem, j); j+=2;
2424 #endif
2425 for (i=0;i<MR_ECC_STORE_N2;i++)
2426 {
2427 T[i].x.a= mirvar_mem(_MIPP_ mem, j++);
2428 T[i].x.b= mirvar_mem(_MIPP_ mem, j++);
2429 T[i].y.a= mirvar_mem(_MIPP_ mem, j++);
2430 T[i].y.b= mirvar_mem(_MIPP_ mem, j++);
2431 T[i].z.a= mirvar_mem(_MIPP_ mem, j++);
2432 T[i].z.b= mirvar_mem(_MIPP_ mem, j++);
2433 }
2434
2435 MR_IN(207)
2436
2437 ecn2_norm(_MIPP_ P);
2438
2439 nadds=0;
2440
2441 neg=FALSE;
2442 if (size(k)<0)
2443 {
2444 negify(k,k);
2445 ecn2_negate(_MIPP_ P,&T[0]);
2446 neg=TRUE;
2447 }
2448 else ecn2_copy(P,&T[0]);
2449
2450 premult(_MIPP_ k,3,h);
2451
2452 ecn2_pre(_MIPP_ MR_ECC_STORE_N2,FALSE,T);
2453 nb=logb2(_MIPP_ h);
2454
2455 ecn2_zero(P);
2456
2457 for (i=nb-1;i>=1;)
2458 {
2459 if (mr_mip->user!=NULL) (*mr_mip->user)();
2460 n=mr_naf_window(_MIPP_ k,h,i,&nbs,&nzs,MR_ECC_STORE_N2);
2461
2462 for (j=0;j<nbs;j++) ecn2_add(_MIPP_ P,P);
2463
2464 if (n>0) {nadds++; ecn2_add(_MIPP_ &T[n/2],P);}
2465 if (n<0) {nadds++; ecn2_sub(_MIPP_ &T[(-n)/2],P);}
2466 i-=nbs;
2467 if (nzs)
2468 {
2469 for (j=0;j<nzs;j++) ecn2_add(_MIPP_ P,P);
2470 i-=nzs;
2471 }
2472 }
2473 if (neg) negify(k,k);
2474
2475 ecn2_norm(_MIPP_ P);
2476 MR_OUT
2477
2478 #ifndef MR_STATIC
2479 memkill(_MIPP_ mem, MR_MUL_RESERVE);
2480 #else
2481 memset(mem, 0, MR_BIG_RESERVE(MR_MUL_RESERVE));
2482 #endif
2483 return nadds;
2484 }
2485
2486 /* Double addition, using Joint Sparse Form */
2487 /* R=aP+bQ */
2488
2489 #define MR_MUL2_JSF_RESERVE 24
2490
ecn2_mul2_jsf(_MIPD_ big a,ecn2 * P,big b,ecn2 * Q,ecn2 * R)2491 int ecn2_mul2_jsf(_MIPD_ big a,ecn2 *P,big b,ecn2 *Q,ecn2 *R)
2492 {
2493 int e1,h1,e2,h2,bb,nadds;
2494 ecn2 P1,P2,PS,PD;
2495 big c,d,e,f;
2496 #ifdef MR_OS_THREADS
2497 miracl *mr_mip=get_mip();
2498 #endif
2499
2500 #ifndef MR_STATIC
2501 char *mem = memalloc(_MIPP_ MR_MUL2_JSF_RESERVE);
2502 #else
2503 char mem[MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE)];
2504 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
2505 #endif
2506
2507 c = mirvar_mem(_MIPP_ mem, 0);
2508 d = mirvar_mem(_MIPP_ mem, 1);
2509 e = mirvar_mem(_MIPP_ mem, 2);
2510 f = mirvar_mem(_MIPP_ mem, 3);
2511 P1.x.a= mirvar_mem(_MIPP_ mem, 4);
2512 P1.x.b= mirvar_mem(_MIPP_ mem, 5);
2513 P1.y.a= mirvar_mem(_MIPP_ mem, 6);
2514 P1.y.b= mirvar_mem(_MIPP_ mem, 7);
2515 P2.x.a= mirvar_mem(_MIPP_ mem, 8);
2516 P2.x.b= mirvar_mem(_MIPP_ mem, 9);
2517 P2.y.a= mirvar_mem(_MIPP_ mem, 10);
2518 P2.y.b= mirvar_mem(_MIPP_ mem, 11);
2519 PS.x.a= mirvar_mem(_MIPP_ mem, 12);
2520 PS.x.b= mirvar_mem(_MIPP_ mem, 13);
2521 PS.y.a= mirvar_mem(_MIPP_ mem, 14);
2522 PS.y.b= mirvar_mem(_MIPP_ mem, 15);
2523 PS.z.a= mirvar_mem(_MIPP_ mem, 16);
2524 PS.z.b= mirvar_mem(_MIPP_ mem, 17);
2525 PD.x.a= mirvar_mem(_MIPP_ mem, 18);
2526 PD.x.b= mirvar_mem(_MIPP_ mem, 19);
2527 PD.y.a= mirvar_mem(_MIPP_ mem, 20);
2528 PD.y.b= mirvar_mem(_MIPP_ mem, 21);
2529 PD.z.a= mirvar_mem(_MIPP_ mem, 22);
2530 PD.z.b= mirvar_mem(_MIPP_ mem, 23);
2531
2532 MR_IN(206)
2533
2534 ecn2_norm(_MIPP_ Q);
2535 ecn2_copy(Q,&P2);
2536
2537 copy(b,d);
2538 if (size(d)<0)
2539 {
2540 negify(d,d);
2541 ecn2_negate(_MIPP_ &P2,&P2);
2542 }
2543
2544 ecn2_norm(_MIPP_ P);
2545 ecn2_copy(P,&P1);
2546
2547 copy(a,c);
2548 if (size(c)<0)
2549 {
2550 negify(c,c);
2551 ecn2_negate(_MIPP_ &P1,&P1);
2552 }
2553
2554 mr_jsf(_MIPP_ d,c,e,d,f,c); /* calculate joint sparse form */
2555
2556 if (compare(e,f)>0) bb=logb2(_MIPP_ e)-1;
2557 else bb=logb2(_MIPP_ f)-1;
2558
2559 /*ecn2_add_sub(_MIPP_ &P1,&P2,&PS,&PD);*/
2560
2561 ecn2_copy(&P1,&PS);
2562 ecn2_copy(&P1,&PD);
2563 ecn2_add(_MIPP_ &P2,&PS);
2564 ecn2_sub(_MIPP_ &P2,&PD);
2565
2566 ecn2_zero(R);
2567 nadds=0;
2568
2569 while (bb>=0)
2570 { /* add/subtract method */
2571 if (mr_mip->user!=NULL) (*mr_mip->user)();
2572 ecn2_add(_MIPP_ R,R);
2573 e1=h1=e2=h2=0;
2574
2575 if (mr_testbit(_MIPP_ d,bb)) e2=1;
2576 if (mr_testbit(_MIPP_ e,bb)) h2=1;
2577 if (mr_testbit(_MIPP_ c,bb)) e1=1;
2578 if (mr_testbit(_MIPP_ f,bb)) h1=1;
2579
2580 if (e1!=h1)
2581 {
2582 if (e2==h2)
2583 {
2584 if (h1==1) {ecn2_add(_MIPP_ &P1,R); nadds++;}
2585 else {ecn2_sub(_MIPP_ &P1,R); nadds++;}
2586 }
2587 else
2588 {
2589 if (h1==1)
2590 {
2591 if (h2==1) {ecn2_add(_MIPP_ &PS,R); nadds++;}
2592 else {ecn2_add(_MIPP_ &PD,R); nadds++;}
2593 }
2594 else
2595 {
2596 if (h2==1) {ecn2_sub(_MIPP_ &PD,R); nadds++;}
2597 else {ecn2_sub(_MIPP_ &PS,R); nadds++;}
2598 }
2599 }
2600 }
2601 else if (e2!=h2)
2602 {
2603 if (h2==1) {ecn2_add(_MIPP_ &P2,R); nadds++;}
2604 else {ecn2_sub(_MIPP_ &P2,R); nadds++;}
2605 }
2606 bb-=1;
2607 }
2608 ecn2_norm(_MIPP_ R);
2609
2610 MR_OUT
2611 #ifndef MR_STATIC
2612 memkill(_MIPP_ mem, MR_MUL2_JSF_RESERVE);
2613 #else
2614 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_JSF_RESERVE));
2615 #endif
2616 return nadds;
2617
2618 }
2619
2620 /* General purpose multi-exponentiation engine, using inter-leaving algorithm. Calculate aP+bQ+cR+dS...
2621 Inputs are divided into two groups of sizes wa<4 and wb<4. For the first group if the points are fixed the
2622 first precomputed Table Ta[] may be taken from ROM. For the second group if the points are variable Tb[j] will
2623 have to computed online. Each group has its own precomputed store size, sza (=8?) and szb (=20?) respectively.
2624 The values a,b,c.. are provided in ma[] and mb[], and 3.a,3.b,3.c (as required by the NAF) are provided in
2625 ma3[] and mb3[]. If only one group is required, set wb=0 and pass NULL pointers.
2626 */
2627
ecn2_muln_engine(_MIPD_ int wa,int sza,int wb,int szb,big * ma,big * ma3,big * mb,big * mb3,ecn2 * Ta,ecn2 * Tb,ecn2 * R)2628 int ecn2_muln_engine(_MIPD_ int wa,int sza,int wb,int szb,big *ma,big *ma3,big *mb,big *mb3,ecn2 *Ta,ecn2 *Tb,ecn2 *R)
2629 { /* general purpose interleaving algorithm engine for multi-exp */
2630 int i,j,tba[4],pba[4],na[4],sa[4],tbb[4],pbb[4],nb[4],sb[4],nbits,nbs,nzs;
2631 int nadds;
2632 #ifdef MR_OS_THREADS
2633 miracl *mr_mip=get_mip();
2634 #endif
2635
2636 ecn2_zero(R);
2637
2638 nbits=0;
2639 for (i=0;i<wa;i++) {sa[i]=exsign(ma[i]); tba[i]=0; j=logb2(_MIPP_ ma3[i]); if (j>nbits) nbits=j; }
2640 for (i=0;i<wb;i++) {sb[i]=exsign(mb[i]); tbb[i]=0; j=logb2(_MIPP_ mb3[i]); if (j>nbits) nbits=j; }
2641
2642 nadds=0;
2643 for (i=nbits-1;i>=1;i--)
2644 {
2645 if (mr_mip->user!=NULL) (*mr_mip->user)();
2646 if (R->marker!=MR_EPOINT_INFINITY) ecn2_add(_MIPP_ R,R);
2647 for (j=0;j<wa;j++)
2648 { /* deal with the first group */
2649 if (tba[j]==0)
2650 {
2651 na[j]=mr_naf_window(_MIPP_ ma[j],ma3[j],i,&nbs,&nzs,sza);
2652 tba[j]=nbs+nzs;
2653 pba[j]=nbs;
2654 }
2655 tba[j]--; pba[j]--;
2656 if (pba[j]==0)
2657 {
2658 if (sa[j]==PLUS)
2659 {
2660 if (na[j]>0) {ecn2_add(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
2661 if (na[j]<0) {ecn2_sub(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
2662 }
2663 else
2664 {
2665 if (na[j]>0) {ecn2_sub(_MIPP_ &Ta[j*sza+na[j]/2],R); nadds++;}
2666 if (na[j]<0) {ecn2_add(_MIPP_ &Ta[j*sza+(-na[j])/2],R); nadds++;}
2667 }
2668 }
2669 }
2670 for (j=0;j<wb;j++)
2671 { /* deal with the second group */
2672 if (tbb[j]==0)
2673 {
2674 nb[j]=mr_naf_window(_MIPP_ mb[j],mb3[j],i,&nbs,&nzs,szb);
2675 tbb[j]=nbs+nzs;
2676 pbb[j]=nbs;
2677 }
2678 tbb[j]--; pbb[j]--;
2679 if (pbb[j]==0)
2680 {
2681 if (sb[j]==PLUS)
2682 {
2683 if (nb[j]>0) {ecn2_add(_MIPP_ &Tb[j*szb+nb[j]/2],R); nadds++;}
2684 if (nb[j]<0) {ecn2_sub(_MIPP_ &Tb[j*szb+(-nb[j])/2],R); nadds++;}
2685 }
2686 else
2687 {
2688 if (nb[j]>0) {ecn2_sub(_MIPP_ &Tb[j*szb+nb[j]/2],R); nadds++;}
2689 if (nb[j]<0) {ecn2_add(_MIPP_ &Tb[j*szb+(-nb[j])/2],R); nadds++;}
2690 }
2691 }
2692 }
2693 }
2694 ecn2_norm(_MIPP_ R);
2695 return nadds;
2696 }
2697
2698 /* Routines to support Galbraith, Lin, Scott (GLS) method for ECC */
2699 /* requires an endomorphism psi */
2700
2701 /* *********************** */
2702
2703 /* Precompute T - first half from i.P, second half from i.psi(P) */
2704 /* norm=TRUE if the table is to be normalised - which it should be */
2705 /* if it is to be calculated off-line */
2706
ecn2_precomp_gls(_MIPD_ int sz,BOOL norm,ecn2 * P,zzn2 * psi,ecn2 * T)2707 void ecn2_precomp_gls(_MIPD_ int sz,BOOL norm,ecn2 *P,zzn2 *psi,ecn2 *T)
2708 {
2709 int i,j;
2710
2711 #ifdef MR_OS_THREADS
2712 miracl *mr_mip=get_mip();
2713 #endif
2714
2715 j=0;
2716
2717 MR_IN(219)
2718
2719 ecn2_norm(_MIPP_ P);
2720 ecn2_copy(P,&T[0]);
2721
2722 ecn2_pre(_MIPP_ sz,norm,T); /* precompute table */
2723 for (i=sz;i<sz+sz;i++)
2724 {
2725 ecn2_copy(&T[i-sz],&T[i]);
2726 ecn2_psi(_MIPP_ psi,&T[i]);
2727 }
2728
2729 MR_OUT
2730 }
2731
2732 /* Calculate a[0].P+a[1].psi(P) using interleaving method */
2733
2734 #define MR_MUL2_GLS_RESERVE (2+2*MR_ECC_STORE_N2*6)
2735
ecn2_mul2_gls(_MIPD_ big * a,ecn2 * P,zzn2 * psi,ecn2 * R)2736 int ecn2_mul2_gls(_MIPD_ big *a,ecn2 *P,zzn2 *psi,ecn2 *R)
2737 {
2738 int i,j,nadds;
2739 ecn2 T[2*MR_ECC_STORE_N2];
2740 big a3[2];
2741 #ifdef MR_OS_THREADS
2742 miracl *mr_mip=get_mip();
2743 #endif
2744
2745 #ifndef MR_STATIC
2746 char *mem = memalloc(_MIPP_ MR_MUL2_GLS_RESERVE);
2747 #else
2748 char mem[MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE)];
2749 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE));
2750 #endif
2751
2752 for (j=i=0;i<2;i++)
2753 a3[i]=mirvar_mem(_MIPP_ mem, j++);
2754
2755 for (i=0;i<2*MR_ECC_STORE_N2;i++)
2756 {
2757 T[i].x.a=mirvar_mem(_MIPP_ mem, j++);
2758 T[i].x.b=mirvar_mem(_MIPP_ mem, j++);
2759 T[i].y.a=mirvar_mem(_MIPP_ mem, j++);
2760 T[i].y.b=mirvar_mem(_MIPP_ mem, j++);
2761 T[i].z.a=mirvar_mem(_MIPP_ mem, j++);
2762 T[i].z.b=mirvar_mem(_MIPP_ mem, j++);
2763 T[i].marker=MR_EPOINT_INFINITY;
2764 }
2765 MR_IN(220)
2766
2767 ecn2_precomp_gls(_MIPP_ MR_ECC_STORE_N2,FALSE,P,psi,T);
2768
2769 for (i=0;i<2;i++) premult(_MIPP_ a[i],3,a3[i]); /* calculate for NAF */
2770
2771 nadds=ecn2_muln_engine(_MIPP_ 0,0,2,MR_ECC_STORE_N2,NULL,NULL,a,a3,NULL,T,R);
2772
2773 ecn2_norm(_MIPP_ R);
2774
2775 MR_OUT
2776
2777 #ifndef MR_STATIC
2778 memkill(_MIPP_ mem, MR_MUL2_GLS_RESERVE);
2779 #else
2780 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_GLS_RESERVE));
2781 #endif
2782 return nadds;
2783 }
2784
2785 /* Calculates a[0]*P+a[1]*psi(P) + b[0]*Q+b[1]*psi(Q)
2786 where P is fixed, and precomputations are already done off-line into FT
2787 using ecn2_precomp_gls. Useful for signature verification */
2788
2789 #define MR_MUL4_GLS_V_RESERVE (4+2*MR_ECC_STORE_N2*6)
2790
ecn2_mul4_gls_v(_MIPD_ big * a,int ns,ecn2 * FT,big * b,ecn2 * Q,zzn2 * psi,ecn2 * R)2791 int ecn2_mul4_gls_v(_MIPD_ big *a,int ns,ecn2 *FT,big *b,ecn2 *Q,zzn2 *psi,ecn2 *R)
2792 {
2793 int i,j,nadds;
2794 ecn2 VT[2*MR_ECC_STORE_N2];
2795 big a3[2],b3[2];
2796 #ifdef MR_OS_THREADS
2797 miracl *mr_mip=get_mip();
2798 #endif
2799
2800 #ifndef MR_STATIC
2801 char *mem = memalloc(_MIPP_ MR_MUL4_GLS_V_RESERVE);
2802 #else
2803 char mem[MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE)];
2804 memset(mem, 0, MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE));
2805 #endif
2806 j=0;
2807 for (i=0;i<2;i++)
2808 {
2809 a3[i]=mirvar_mem(_MIPP_ mem, j++);
2810 b3[i]=mirvar_mem(_MIPP_ mem, j++);
2811 }
2812 for (i=0;i<2*MR_ECC_STORE_N2;i++)
2813 {
2814 VT[i].x.a=mirvar_mem(_MIPP_ mem, j++);
2815 VT[i].x.b=mirvar_mem(_MIPP_ mem, j++);
2816 VT[i].y.a=mirvar_mem(_MIPP_ mem, j++);
2817 VT[i].y.b=mirvar_mem(_MIPP_ mem, j++);
2818 VT[i].z.a=mirvar_mem(_MIPP_ mem, j++);
2819 VT[i].z.b=mirvar_mem(_MIPP_ mem, j++);
2820 VT[i].marker=MR_EPOINT_INFINITY;
2821 }
2822
2823 MR_IN(217)
2824
2825 ecn2_precomp_gls(_MIPP_ MR_ECC_STORE_N2,FALSE,Q,psi,VT); /* precompute for the variable points */
2826 for (i=0;i<2;i++)
2827 { /* needed for NAF */
2828 premult(_MIPP_ a[i],3,a3[i]);
2829 premult(_MIPP_ b[i],3,b3[i]);
2830 }
2831 nadds=ecn2_muln_engine(_MIPP_ 2,ns,2,MR_ECC_STORE_N2,a,a3,b,b3,FT,VT,R);
2832 ecn2_norm(_MIPP_ R);
2833
2834 MR_OUT
2835
2836 #ifndef MR_STATIC
2837 memkill(_MIPP_ mem, MR_MUL4_GLS_V_RESERVE);
2838 #else
2839 memset(mem, 0, MR_BIG_RESERVE(MR_MUL4_GLS_V_RESERVE));
2840 #endif
2841 return nadds;
2842 }
2843
2844 /* Calculate a.P+b.Q using interleaving method. P is fixed and T is precomputed from it */
2845
ecn2_precomp(_MIPD_ int sz,BOOL norm,ecn2 * P,ecn2 * T)2846 void ecn2_precomp(_MIPD_ int sz,BOOL norm,ecn2 *P,ecn2 *T)
2847 {
2848 #ifdef MR_OS_THREADS
2849 miracl *mr_mip=get_mip();
2850 #endif
2851
2852 MR_IN(216)
2853
2854 ecn2_norm(_MIPP_ P);
2855 ecn2_copy(P,&T[0]);
2856 ecn2_pre(_MIPP_ sz,norm,T);
2857
2858 MR_OUT
2859 }
2860
2861 #ifndef MR_DOUBLE_BIG
2862 #define MR_MUL2_RESERVE (2+2*MR_ECC_STORE_N2*6)
2863 #else
2864 #define MR_MUL2_RESERVE (4+2*MR_ECC_STORE_N2*6)
2865 #endif
2866
ecn2_mul2(_MIPD_ big a,int ns,ecn2 * FT,big b,ecn2 * Q,ecn2 * R)2867 int ecn2_mul2(_MIPD_ big a,int ns,ecn2 *FT,big b,ecn2 *Q,ecn2 *R)
2868 {
2869 int i,j,nadds;
2870 ecn2 T[2*MR_ECC_STORE_N2];
2871 big a3,b3;
2872 #ifdef MR_OS_THREADS
2873 miracl *mr_mip=get_mip();
2874 #endif
2875
2876 #ifndef MR_STATIC
2877 char *mem = memalloc(_MIPP_ MR_MUL2_RESERVE);
2878 #else
2879 char mem[MR_BIG_RESERVE(MR_MUL2_RESERVE)];
2880 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_RESERVE));
2881 #endif
2882
2883 j=0;
2884 #ifndef MR_DOUBLE_BIG
2885 a3=mirvar_mem(_MIPP_ mem, j++);
2886 b3=mirvar_mem(_MIPP_ mem, j++);
2887 #else
2888 a3=mirvar_mem(_MIPP_ mem, j); j+=2;
2889 b3=mirvar_mem(_MIPP_ mem, j); j+=2;
2890 #endif
2891 for (i=0;i<2*MR_ECC_STORE_N2;i++)
2892 {
2893 T[i].x.a=mirvar_mem(_MIPP_ mem, j++);
2894 T[i].x.b=mirvar_mem(_MIPP_ mem, j++);
2895 T[i].y.a=mirvar_mem(_MIPP_ mem, j++);
2896 T[i].y.b=mirvar_mem(_MIPP_ mem, j++);
2897 T[i].z.a=mirvar_mem(_MIPP_ mem, j++);
2898 T[i].z.b=mirvar_mem(_MIPP_ mem, j++);
2899 T[i].marker=MR_EPOINT_INFINITY;
2900 }
2901
2902 MR_IN(218)
2903
2904 ecn2_precomp(_MIPP_ MR_ECC_STORE_N2,FALSE,Q,T);
2905
2906 premult(_MIPP_ a,3,a3);
2907 premult(_MIPP_ b,3,b3);
2908
2909 nadds=ecn2_muln_engine(_MIPP_ 1,ns,1,MR_ECC_STORE_N2,&a,&a3,&b,&b3,FT,T,R);
2910
2911 ecn2_norm(_MIPP_ R);
2912
2913 MR_OUT
2914
2915 #ifndef MR_STATIC
2916 memkill(_MIPP_ mem, MR_MUL2_RESERVE);
2917 #else
2918 memset(mem, 0, MR_BIG_RESERVE(MR_MUL2_RESERVE));
2919 #endif
2920 return nadds;
2921 }
2922
2923
2924 #ifndef MR_STATIC
2925
ecn2_brick_init(_MIPD_ ebrick * B,zzn2 * x,zzn2 * y,big a,big b,big n,int window,int nb)2926 BOOL ecn2_brick_init(_MIPD_ ebrick *B,zzn2 *x,zzn2 *y,big a,big b,big n,int window,int nb)
2927 { /* Uses Montgomery arithmetic internally *
2928 * (x,y) is the fixed base *
2929 * a,b and n are parameters and modulus of the curve *
2930 * window is the window size in bits and *
2931 * nb is the maximum number of bits in the multiplier */
2932 int i,j,k,t,bp,len,bptr;
2933 ecn2 *table;
2934 ecn2 w;
2935
2936 #ifdef MR_OS_THREADS
2937 miracl *mr_mip=get_mip();
2938 #endif
2939 if (nb<2 || window<1 || window>nb || mr_mip->ERNUM) return FALSE;
2940
2941 t=MR_ROUNDUP(nb,window);
2942 if (t<2) return FALSE;
2943
2944 MR_IN(221)
2945
2946 #ifndef MR_ALWAYS_BINARY
2947 if (mr_mip->base != mr_mip->base2)
2948 {
2949 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
2950 MR_OUT
2951 return FALSE;
2952 }
2953 #endif
2954
2955 B->window=window;
2956 B->max=nb;
2957 table=mr_alloc(_MIPP_ (1<<window),sizeof(ecn2));
2958 if (table==NULL)
2959 {
2960 mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);
2961 MR_OUT
2962 return FALSE;
2963 }
2964 B->a=mirvar(_MIPP_ 0);
2965 B->b=mirvar(_MIPP_ 0);
2966 B->n=mirvar(_MIPP_ 0);
2967 copy(a,B->a);
2968 copy(b,B->b);
2969 copy(n,B->n);
2970
2971 ecurve_init(_MIPP_ a,b,n,MR_BEST);
2972 mr_mip->TWIST=MR_QUADRATIC;
2973
2974 w.x.a=mirvar(_MIPP_ 0);
2975 w.x.b=mirvar(_MIPP_ 0);
2976 w.y.a=mirvar(_MIPP_ 0);
2977 w.y.b=mirvar(_MIPP_ 0);
2978 w.z.a=mirvar(_MIPP_ 0);
2979 w.z.b=mirvar(_MIPP_ 0);
2980
2981 w.marker=MR_EPOINT_INFINITY;
2982 ecn2_set(_MIPP_ x,y,&w);
2983
2984 table[0].x.a=mirvar(_MIPP_ 0);
2985 table[0].x.b=mirvar(_MIPP_ 0);
2986 table[0].y.a=mirvar(_MIPP_ 0);
2987 table[0].y.b=mirvar(_MIPP_ 0);
2988 table[0].z.a=mirvar(_MIPP_ 0);
2989 table[0].z.b=mirvar(_MIPP_ 0);
2990 table[0].marker=MR_EPOINT_INFINITY;
2991 table[1].x.a=mirvar(_MIPP_ 0);
2992 table[1].x.b=mirvar(_MIPP_ 0);
2993 table[1].y.a=mirvar(_MIPP_ 0);
2994 table[1].y.b=mirvar(_MIPP_ 0);
2995 table[1].z.a=mirvar(_MIPP_ 0);
2996 table[1].z.b=mirvar(_MIPP_ 0);
2997 table[1].marker=MR_EPOINT_INFINITY;
2998
2999 ecn2_copy(&w,&table[1]);
3000 for (j=0;j<t;j++)
3001 ecn2_add(_MIPP_ &w,&w);
3002
3003 k=1;
3004 for (i=2;i<(1<<window);i++)
3005 {
3006 table[i].x.a=mirvar(_MIPP_ 0);
3007 table[i].x.b=mirvar(_MIPP_ 0);
3008 table[i].y.a=mirvar(_MIPP_ 0);
3009 table[i].y.b=mirvar(_MIPP_ 0);
3010 table[i].z.a=mirvar(_MIPP_ 0);
3011 table[i].z.b=mirvar(_MIPP_ 0);
3012 table[i].marker=MR_EPOINT_INFINITY;
3013 if (i==(1<<k))
3014 {
3015 k++;
3016 ecn2_norm(_MIPP_ &w);
3017 ecn2_copy(&w,&table[i]);
3018
3019 for (j=0;j<t;j++)
3020 ecn2_add(_MIPP_ &w,&w);
3021 continue;
3022 }
3023 bp=1;
3024 for (j=0;j<k;j++)
3025 {
3026 if (i&bp)
3027 ecn2_add(_MIPP_ &table[1<<j],&table[i]);
3028 bp<<=1;
3029 }
3030 ecn2_norm(_MIPP_ &table[i]);
3031 }
3032 mr_free(w.x.a);
3033 mr_free(w.x.b);
3034 mr_free(w.y.a);
3035 mr_free(w.y.b);
3036 mr_free(w.z.a);
3037 mr_free(w.z.b);
3038
3039 /* create the table */
3040
3041 len=n->len;
3042 bptr=0;
3043 B->table=mr_alloc(_MIPP_ 4*len*(1<<window),sizeof(mr_small));
3044
3045 for (i=0;i<(1<<window);i++)
3046 {
3047 for (j=0;j<len;j++) B->table[bptr++]=table[i].x.a->w[j];
3048 for (j=0;j<len;j++) B->table[bptr++]=table[i].x.b->w[j];
3049
3050 for (j=0;j<len;j++) B->table[bptr++]=table[i].y.a->w[j];
3051 for (j=0;j<len;j++) B->table[bptr++]=table[i].y.b->w[j];
3052
3053 mr_free(table[i].x.a);
3054 mr_free(table[i].x.b);
3055 mr_free(table[i].y.a);
3056 mr_free(table[i].y.b);
3057 mr_free(table[i].z.a);
3058 mr_free(table[i].z.b);
3059 }
3060
3061 mr_free(table);
3062
3063 MR_OUT
3064 return TRUE;
3065 }
3066
ecn2_brick_end(ebrick * B)3067 void ecn2_brick_end(ebrick *B)
3068 {
3069 mirkill(B->n);
3070 mirkill(B->b);
3071 mirkill(B->a);
3072 mr_free(B->table);
3073 }
3074
3075 #else
3076
3077 /* use precomputated table in ROM */
3078
ecn2_brick_init(ebrick * B,const mr_small * rom,big a,big b,big n,int window,int nb)3079 void ecn2_brick_init(ebrick *B,const mr_small* rom,big a,big b,big n,int window,int nb)
3080 {
3081 B->table=rom;
3082 B->a=a; /* just pass a pointer */
3083 B->b=b;
3084 B->n=n;
3085 B->window=window; /* 2^4=16 stored values */
3086 B->max=nb;
3087 }
3088
3089 #endif
3090
3091 /*
3092 void ecn2_mul_brick(_MIPD_ ebrick *B,big e,zzn2 *x,zzn2 *y)
3093 {
3094 int i,j,t,len,maxsize,promptr;
3095 ecn2 w,z;
3096
3097 #ifdef MR_STATIC
3098 char mem[MR_BIG_RESERVE(10)];
3099 #else
3100 char *mem;
3101 #endif
3102 #ifdef MR_OS_THREADS
3103 miracl *mr_mip=get_mip();
3104 #endif
3105
3106 if (size(e)<0) mr_berror(_MIPP_ MR_ERR_NEG_POWER);
3107 t=MR_ROUNDUP(B->max,B->window);
3108
3109 MR_IN(116)
3110
3111 #ifndef MR_ALWAYS_BINARY
3112 if (mr_mip->base != mr_mip->base2)
3113 {
3114 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
3115 MR_OUT
3116 return;
3117 }
3118 #endif
3119
3120 if (logb2(_MIPP_ e) > B->max)
3121 {
3122 mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
3123 MR_OUT
3124 return;
3125 }
3126
3127 ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
3128 mr_mip->TWIST=MR_QUADRATIC;
3129
3130 #ifdef MR_STATIC
3131 memset(mem,0,MR_BIG_RESERVE(10));
3132 #else
3133 mem=memalloc(_MIPP_ 10);
3134 #endif
3135
3136 w.x.a=mirvar_mem(_MIPP_ mem, 0);
3137 w.x.b=mirvar_mem(_MIPP_ mem, 1);
3138 w.y.a=mirvar_mem(_MIPP_ mem, 2);
3139 w.y.b=mirvar_mem(_MIPP_ mem, 3);
3140 w.z.a=mirvar_mem(_MIPP_ mem, 4);
3141 w.z.b=mirvar_mem(_MIPP_ mem, 5);
3142 w.marker=MR_EPOINT_INFINITY;
3143 z.x.a=mirvar_mem(_MIPP_ mem, 6);
3144 z.x.b=mirvar_mem(_MIPP_ mem, 7);
3145 z.y.a=mirvar_mem(_MIPP_ mem, 8);
3146 z.y.b=mirvar_mem(_MIPP_ mem, 9);
3147 z.marker=MR_EPOINT_INFINITY;
3148
3149 len=B->n->len;
3150 maxsize=4*(1<<B->window)*len;
3151
3152 for (i=t-1;i>=0;i--)
3153 {
3154 j=recode(_MIPP_ e,t,B->window,i);
3155 ecn2_add(_MIPP_ &w,&w);
3156 if (j>0)
3157 {
3158 promptr=4*j*len;
3159 init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
3160 init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
3161 init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
3162 init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
3163 z.marker=MR_EPOINT_NORMALIZED;
3164 ecn2_add(_MIPP_ &z,&w);
3165 }
3166 }
3167 ecn2_norm(_MIPP_ &w);
3168 ecn2_getxy(&w,x,y);
3169 #ifndef MR_STATIC
3170 memkill(_MIPP_ mem,10);
3171 #else
3172 memset(mem,0,MR_BIG_RESERVE(10));
3173 #endif
3174 MR_OUT
3175 }
3176 */
3177
ecn2_mul_brick_gls(_MIPD_ ebrick * B,big * e,zzn2 * psi,zzn2 * x,zzn2 * y)3178 void ecn2_mul_brick_gls(_MIPD_ ebrick *B,big *e,zzn2 *psi,zzn2 *x,zzn2 *y)
3179 {
3180 int i,j,k,t,len,maxsize,promptr,se[2];
3181 ecn2 w,z;
3182
3183 #ifdef MR_STATIC
3184 char mem[MR_BIG_RESERVE(10)];
3185 #else
3186 char *mem;
3187 #endif
3188 #ifdef MR_OS_THREADS
3189 miracl *mr_mip=get_mip();
3190 #endif
3191
3192 for (k=0;k<2;k++) se[k]=exsign(e[k]);
3193
3194 t=MR_ROUNDUP(B->max,B->window);
3195
3196 MR_IN(222)
3197
3198 #ifndef MR_ALWAYS_BINARY
3199 if (mr_mip->base != mr_mip->base2)
3200 {
3201 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
3202 MR_OUT
3203 return;
3204 }
3205 #endif
3206
3207 if (logb2(_MIPP_ e[0])>B->max || logb2(_MIPP_ e[1])>B->max)
3208 {
3209 mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
3210 MR_OUT
3211 return;
3212 }
3213
3214 ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
3215 mr_mip->TWIST=MR_QUADRATIC;
3216
3217 #ifdef MR_STATIC
3218 memset(mem,0,MR_BIG_RESERVE(10));
3219 #else
3220 mem=memalloc(_MIPP_ 10);
3221 #endif
3222
3223 z.x.a=mirvar_mem(_MIPP_ mem, 0);
3224 z.x.b=mirvar_mem(_MIPP_ mem, 1);
3225 z.y.a=mirvar_mem(_MIPP_ mem, 2);
3226 z.y.b=mirvar_mem(_MIPP_ mem, 3);
3227 z.marker=MR_EPOINT_INFINITY;
3228
3229 w.x.a=mirvar_mem(_MIPP_ mem, 4);
3230 w.x.b=mirvar_mem(_MIPP_ mem, 5);
3231 w.y.a=mirvar_mem(_MIPP_ mem, 6);
3232 w.y.b=mirvar_mem(_MIPP_ mem, 7);
3233 w.z.a=mirvar_mem(_MIPP_ mem, 8);
3234 w.z.b=mirvar_mem(_MIPP_ mem, 9);
3235 w.marker=MR_EPOINT_INFINITY;
3236
3237 len=B->n->len;
3238 maxsize=4*(1<<B->window)*len;
3239
3240 for (i=t-1;i>=0;i--)
3241 {
3242 ecn2_add(_MIPP_ &w,&w);
3243 for (k=0;k<2;k++)
3244 {
3245 j=recode(_MIPP_ e[k],t,B->window,i);
3246 if (j>0)
3247 {
3248 promptr=4*j*len;
3249 init_big_from_rom(z.x.a,len,B->table,maxsize,&promptr);
3250 init_big_from_rom(z.x.b,len,B->table,maxsize,&promptr);
3251 init_big_from_rom(z.y.a,len,B->table,maxsize,&promptr);
3252 init_big_from_rom(z.y.b,len,B->table,maxsize,&promptr);
3253 z.marker=MR_EPOINT_NORMALIZED;
3254 if (k==1) ecn2_psi(_MIPP_ psi,&z);
3255 if (se[k]==PLUS) ecn2_add(_MIPP_ &z,&w);
3256 else ecn2_sub(_MIPP_ &z,&w);
3257 }
3258 }
3259 }
3260 ecn2_norm(_MIPP_ &w);
3261 ecn2_getxy(&w,x,y);
3262 #ifndef MR_STATIC
3263 memkill(_MIPP_ mem,10);
3264 #else
3265 memset(mem,0,MR_BIG_RESERVE(10));
3266 #endif
3267 MR_OUT
3268 }
3269
3270 #endif
3271
3272 #ifndef MR_NO_ECC_MULTIADD
3273 #ifndef MR_STATIC
3274
ecn2_multn(_MIPD_ int n,big * e,ecn2 * P,ecn2 * R)3275 void ecn2_multn(_MIPD_ int n,big *e,ecn2 *P,ecn2 *R)
3276 { /* R=e[0]*P[0]+e[1]*P[1]+ .... e[n-1]*P[n-1] */
3277 int i,j,k,l,nb,ea,c;
3278 int m=1<<n;
3279 ecn2 *G;
3280 zzn2 *work;
3281 #ifdef MR_OS_THREADS
3282 miracl *mr_mip=get_mip();
3283 #endif
3284 char *mem=(char *)memalloc(_MIPP_ 8*(m-1));
3285 if (mr_mip->ERNUM) return;
3286
3287 MR_IN(223)
3288
3289 G= (ecn2 *)mr_alloc(_MIPP_ m,sizeof(ecn2));
3290 work=(zzn2 *)mr_alloc(_MIPP_ m,sizeof(zzn2));
3291
3292 l=0;
3293 for (k=1;k<m;k++)
3294 {
3295 G[k].x.a=mirvar_mem(_MIPP_ mem, l++);
3296 G[k].x.b=mirvar_mem(_MIPP_ mem, l++);
3297 G[k].y.a=mirvar_mem(_MIPP_ mem, l++);
3298 G[k].y.b=mirvar_mem(_MIPP_ mem, l++);
3299 G[k].z.a=mirvar_mem(_MIPP_ mem, l++);
3300 G[k].z.b=mirvar_mem(_MIPP_ mem, l++);
3301 G[k].marker=MR_EPOINT_INFINITY;
3302
3303 i=k; j=1; c=0; while (i>=(2*j)) {j*=2; c++;}
3304 if (i>j) ecn2_copy(&G[i-j],&G[k]);
3305 ecn2_add(_MIPP_ &P[c],&G[k]);
3306 }
3307
3308 for (i=0;i<m-1;i++)
3309 {
3310 work[i].a=mirvar_mem(_MIPP_ mem, l++);
3311 work[i].b=mirvar_mem(_MIPP_ mem, l++);
3312 }
3313
3314 ecn2_multi_norm(_MIPP_ m-1,work,&G[1]);
3315
3316 nb=0;
3317 for (j=0;j<n;j++) if ((k=logb2(_MIPP_ e[j])) > nb) nb=k;
3318
3319 ecn2_zero(R);
3320
3321 #ifndef MR_ALWAYS_BINARY
3322 if (mr_mip->base==mr_mip->base2)
3323 {
3324 #endif
3325 for (i=nb-1;i>=0;i--)
3326 {
3327 if (mr_mip->user!=NULL) (*mr_mip->user)();
3328 ea=0;
3329 k=1;
3330 for (j=0;j<n;j++)
3331 {
3332 if (mr_testbit(_MIPP_ e[j],i)) ea+=k;
3333 k<<=1;
3334 }
3335 ecn2_add(_MIPP_ R,R);
3336 if (ea!=0) ecn2_add(_MIPP_ &G[ea],R);
3337 }
3338 #ifndef MR_ALWAYS_BINARY
3339 }
3340 else mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
3341 #endif
3342
3343 memkill(_MIPP_ mem,8*(m-1));
3344 mr_free(work);
3345 mr_free(G);
3346 MR_OUT
3347 }
3348
3349 #endif
3350 #endif
3351