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 *
37 * MIRACL Core module - contains initialisation code and general purpose
38 * utilities
39 * mrcore.c
40 *
41 * Space can be saved by removing unneeded functions (mr_and ?)
42 *
43 */
44
45 #include "miracl.h"
46 #include <stdlib.h>
47 #include <string.h>
48
49
50 #ifdef MR_FP
51 #include <math.h>
52 #endif
53
54
55 /*** Multi-Threaded Support ***/
56
57 #ifndef MR_GENERIC_MT
58
59 #ifdef MR_OPENMP_MT
60 #include <omp.h>
61
62 #define MR_MIP_EXISTS
63
64 miracl *mr_mip;
65 #pragma omp threadprivate(mr_mip)
66
get_mip()67 miracl *get_mip()
68 {
69 return mr_mip;
70 }
71
mr_init_threading()72 void mr_init_threading()
73 {
74 }
75
mr_end_threading()76 void mr_end_threading()
77 {
78 }
79
80 #endif
81
82 #ifdef MR_WINDOWS_MT
83 #include <windows.h>
84 DWORD mr_key;
85
get_mip()86 miracl *get_mip()
87 {
88 return (miracl *)TlsGetValue(mr_key);
89 }
90
mr_init_threading()91 void mr_init_threading()
92 {
93 mr_key=TlsAlloc();
94 }
95
mr_end_threading()96 void mr_end_threading()
97 {
98 TlsFree(mr_key);
99 }
100
101 #endif
102
103 #ifdef MR_UNIX_MT
104 #include <pthread.h>
105 pthread_key_t mr_key;
106
get_mip()107 miracl *get_mip()
108 {
109 return (miracl *)pthread_getspecific(mr_key);
110 }
111
mr_init_threading()112 void mr_init_threading()
113 {
114 pthread_key_create(&mr_key,(void(*)(void *))NULL);
115 }
116
mr_end_threading()117 void mr_end_threading()
118 {
119 pthread_key_delete(mr_key);
120 }
121 #endif
122
123 #ifndef MR_WINDOWS_MT
124 #ifndef MR_UNIX_MT
125 #ifndef MR_OPENMP_MT
126 #ifdef MR_STATIC
127 miracl mip;
128 miracl *mr_mip=&mip;
129 #else
130 miracl *mr_mip=NULL; /* MIRACL's one and only global variable */
131 #endif
132 #define MR_MIP_EXISTS
get_mip()133 miracl *get_mip()
134 {
135 return (miracl *)mr_mip;
136 }
137 #endif
138 #endif
139 #endif
140
141 #ifdef MR_MIP_EXISTS
set_mip(miracl * mip)142 void set_mip(miracl *mip)
143 {
144 mr_mip=mip;
145 }
146 #endif
147
148 #endif
149
150 /* See Advanced Windows by Jeffrey Richter, Chapter 12 for methods for
151 creating different instances of this global for each executing thread
152 when using Windows '95/NT
153 */
154
155 #ifdef MR_STATIC
156
157 #if MIRACL==8
158
159 static const int mr_small_primes[]=
160 {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
161 107,109,113,127,0};
162
163 #else
164
165 static const int mr_small_primes[]=
166 {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
167 107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,
168 223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
169 337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,
170 457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,
171 593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
172 719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
173 857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
174 997,0};
175
176 #endif
177
178 #endif
179
180 #ifndef MR_STRIPPED_DOWN
181 #ifndef MR_NO_STANDARD_IO
182
183 static char *names[] =
184 {(char *)"your program",(char *)"innum",(char *)"otnum",(char *)"jack",(char *)"normalise",
185 (char *)"multiply",(char *)"divide",(char *)"incr",(char *)"decr",(char *)"premult",
186 (char *)"subdiv",(char *)"fdsize",(char *)"egcd",(char *)"cbase",
187 (char *)"cinnum",(char *)"cotnum",(char *)"nroot",(char *)"power",
188 (char *)"powmod",(char *)"bigdig",(char *)"bigrand",(char *)"nxprime",(char *)"isprime",
189 (char *)"mirvar",(char *)"mad",(char *)"multi_inverse",(char *)"putdig",
190 (char *)"add",(char *)"subtract",(char *)"mirsys",(char *)"xgcd",
191 (char *)"fpack",(char *)"dconv",(char *)"mr_shift",(char *)"mround",(char *)"fmul",
192 (char *)"fdiv",(char *)"fadd",(char *)"fsub",(char *)"fcomp",(char *)"fconv",
193 (char *)"frecip",(char *)"fpmul",(char *)"fincr",(char *)"",(char *)"ftrunc",
194 (char *)"frand",(char *)"sftbit",(char *)"build",(char *)"logb2",(char *)"expint",
195 (char *)"fpower",(char *)"froot",(char *)"fpi",(char *)"fexp",(char *)"flog",(char *)"fpowf",
196 (char *)"ftan",(char *)"fatan",(char *)"fsin",(char *)"fasin",(char *)"fcos",(char *)"facos",
197 (char *)"ftanh",(char *)"fatanh",(char *)"fsinh",(char *)"fasinh",(char *)"fcosh",
198 (char *)"facosh",(char *)"flop",(char *)"gprime",(char *)"powltr",(char *)"fft_mult",
199 (char *)"crt_init",(char *)"crt",(char *)"otstr",(char *)"instr",(char *)"cotstr",(char *)"cinstr",(char *)"powmod2",
200 (char *)"prepare_monty",(char *)"nres",(char *)"redc",(char *)"nres_modmult",(char *)"nres_powmod",
201 (char *)"nres_moddiv",(char *)"nres_powltr",(char *)"divisible",(char *)"remain",
202 (char *)"fmodulo",(char *)"nres_modadd",(char *)"nres_modsub",(char *)"nres_negate",
203 (char *)"ecurve_init",(char *)"ecurve_add",(char *)"ecurve_mult",
204 (char *)"epoint_init",(char *)"epoint_set",(char *)"epoint_get",(char *)"nres_powmod2",
205 (char *)"nres_sqroot",(char *)"sqroot",(char *)"nres_premult",(char *)"ecurve_mult2",
206 (char *)"ecurve_sub",(char *)"trial_division",(char *)"nxsafeprime",(char *)"nres_lucas",(char *)"lucas",
207 (char *)"brick_init",(char *)"pow_brick",(char *)"set_user_function",
208 (char *)"nres_powmodn",(char *)"powmodn",(char *)"ecurve_multn",
209 (char *)"ebrick_init",(char *)"mul_brick",(char *)"epoint_norm",(char *)"nres_multi_inverse",(char *)"",
210 (char *)"nres_dotprod",(char *)"epoint_negate",(char *)"ecurve_multi_add",
211 (char *)"ecurve2_init",(char *)"",(char *)"epoint2_set",(char *)"epoint2_norm",(char *)"epoint2_get",
212 (char *)"epoint2_comp",(char *)"ecurve2_add",(char *)"epoint2_negate",(char *)"ecurve2_sub",
213 (char *)"ecurve2_multi_add",(char *)"ecurve2_mult",(char *)"ecurve2_multn",(char *)"ecurve2_mult2",
214 (char *)"ebrick2_init",(char *)"mul2_brick",(char *)"prepare_basis",(char *)"strong_bigrand",
215 (char *)"bytes_to_big",(char *)"big_to_bytes",(char *)"set_io_buffer_size",
216 (char *)"epoint_getxyz",(char *)"epoint_double_add",(char *)"nres_double_inverse",
217 (char *)"double_inverse",(char *)"epoint_x",(char *)"hamming",(char *)"expb2",(char *)"bigbits",
218 (char *)"nres_lazy",(char *)"zzn2_imul",(char *)"nres_double_modadd",(char *)"nres_double_modsub",
219 /*155*/(char *)"",(char *)"zzn2_from_int",(char *)"zzn2_negate",(char *)"zzn2_conj",(char *)"zzn2_add",
220 (char *)"zzn2_sub",(char *)"zzn2_smul",(char *)"zzn2_mul",(char *)"zzn2_inv",(char *)"zzn2_timesi",(char *)"zzn2_powl",
221 (char *)"zzn2_from_bigs",(char *)"zzn2_from_big",(char *)"zzn2_from_ints",
222 (char *)"zzn2_sadd",(char *)"zzn2_ssub",(char *)"zzn2_times_irp",(char *)"zzn2_div2",
223 (char *)"zzn3_from_int",(char *)"zzn3_from_ints",(char *)"zzn3_from_bigs",
224 (char *)"zzn3_from_big",(char *)"zzn3_negate",(char *)"zzn3_powq",(char *)"zzn3_init",
225 (char *)"zzn3_add",(char *)"zzn3_sadd",(char *)"zzn3_sub",(char *)"zzn3_ssub",(char *)"zzn3_smul",
226 (char *)"zzn3_imul",(char *)"zzn3_mul",(char *)"zzn3_inv",(char *)"zzn3_div2",(char *)"zzn3_timesi",
227 (char *)"epoint_multi_norm",(char *)"mr_jsf",(char *)"epoint2_multi_norm",
228 (char *)"ecn2_compare",(char *)"ecn2_norm",(char *)"ecn2_set",(char *)"zzn2_txx",
229 (char *)"zzn2_txd",(char *)"nres_div2",(char *)"nres_div3",(char *)"zzn2_div3",
230 (char *)"ecn2_setx",(char *)"ecn2_rhs",(char *)"zzn2_qr",(char *)"zzn2_sqrt",(char *)"ecn2_add",(char *)"ecn2_mul2_jsf",(char *)"ecn2_mul",
231 (char *)"nres_div5",(char *)"zzn2_div5",(char *)"zzn2_sqr",(char *)"ecn2_add_sub",(char *)"ecn2_psi",(char *)"invmodp",
232 (char *)"zzn2_multi_inverse",(char *)"ecn2_multi_norm",(char *)"ecn2_precomp",(char *)"ecn2_mul4_gls_v",
233 (char *)"ecn2_mul2",(char *)"ecn2_precomp_gls",(char *)"ecn2_mul2_gls",
234 (char *)"ecn2_brick_init",(char *)"ecn2_mul_brick_gls",(char *)"ecn2_multn",(char *)"zzn3_timesi2",
235 (char *)"nres_complex"};
236
237 /* 0 - 225 (226 in all) */
238
239 #endif
240 #endif
241
242 #ifdef MR_NOASM
243
244 /* C only versions of muldiv/muldvd/muldvd2/muldvm */
245 /* Note that mr_large should be twice the size of mr_small */
246
muldiv(mr_small a,mr_small b,mr_small c,mr_small m,mr_small * rp)247 mr_small muldiv(mr_small a,mr_small b,mr_small c,mr_small m,mr_small *rp)
248 {
249 mr_small q;
250 mr_large ldres,p=(mr_large)a*b+c;
251 q=(mr_small)(MR_LROUND(p/m));
252 *rp=(mr_small)(p-(mr_large)q*m);
253 return q;
254 }
255
256 #ifdef MR_FP_ROUNDING
257
imuldiv(mr_small a,mr_small b,mr_small c,mr_small m,mr_large im,mr_small * rp)258 mr_small imuldiv(mr_small a,mr_small b,mr_small c,mr_small m,mr_large im,mr_small *rp)
259 {
260 mr_small q;
261 mr_large ldres,p=(mr_large)a*b+c;
262 q=(mr_small)MR_LROUND(p*im);
263 *rp=(mr_small)(p-(mr_large)q*m);
264 return q;
265 }
266
267 #endif
268
269 #ifndef MR_NOFULLWIDTH
270
muldvm(mr_small a,mr_small c,mr_small m,mr_small * rp)271 mr_small muldvm(mr_small a,mr_small c,mr_small m,mr_small *rp)
272 {
273 mr_small q;
274 union doubleword dble;
275 dble.h[MR_BOT]=c;
276 dble.h[MR_TOP]=a;
277
278 q=(mr_small)(dble.d/m);
279 *rp=(mr_small)(dble.d-(mr_large)q*m);
280 return q;
281 }
282
muldvd(mr_small a,mr_small b,mr_small c,mr_small * rp)283 mr_small muldvd(mr_small a,mr_small b,mr_small c,mr_small *rp)
284 {
285 union doubleword dble;
286 dble.d=(mr_large)a*b+c;
287
288 *rp=dble.h[MR_BOT];
289 return dble.h[MR_TOP];
290 }
291
muldvd2(mr_small a,mr_small b,mr_small * c,mr_small * rp)292 void muldvd2(mr_small a,mr_small b,mr_small *c,mr_small *rp)
293 {
294 union doubleword dble;
295 dble.d=(mr_large)a*b+*c+*rp;
296 *rp=dble.h[MR_BOT];
297 *c=dble.h[MR_TOP];
298 }
299
300 #endif
301 #endif
302
303 #ifdef MR_NOFULLWIDTH
304
305 /* no FULLWIDTH working, so supply dummies */
306
307 /*
308
309 mr_small muldvd(mr_small a,mr_small b,mr_small c,mr_small *rp)
310 {
311 return (mr_small)0;
312 }
313
314 mr_small muldvm(mr_small a,mr_small c,mr_small m,mr_small *rp)
315 {
316 return (mr_small)0;
317 }
318
319 void muldvd2(mr_small a,mr_small b,mr_small *c,mr_small *rp)
320 {
321 }
322
323 */
324
325 #endif
326
327 #ifndef MR_NO_STANDARD_IO
328
mputs(char * s)329 static void mputs(char *s)
330 { /* output a string */
331 int i=0;
332 while (s[i]!=0) fputc((int)s[i++],stdout);
333 }
334 #endif
335
mr_berror(_MIPD_ int nerr)336 void mr_berror(_MIPD_ int nerr)
337 { /* Big number error routine */
338 #ifndef MR_STRIPPED_DOWN
339 int i;
340 #endif
341
342 #ifdef MR_OS_THREADS
343 miracl *mr_mip=get_mip();
344 #endif
345
346 if (mr_mip->ERCON)
347 {
348 mr_mip->ERNUM=nerr;
349 return;
350 }
351 #ifndef MR_NO_STANDARD_IO
352
353 #ifndef MR_STRIPPED_DOWN
354 mputs((char *)"\nMIRACL error from routine ");
355 if (mr_mip->depth<MR_MAXDEPTH) mputs(names[mr_mip->trace[mr_mip->depth]]);
356 else mputs((char *)"???");
357 fputc('\n',stdout);
358
359 for (i=mr_mip->depth-1;i>=0;i--)
360 {
361 mputs((char *)" called from ");
362 if (i<MR_MAXDEPTH) mputs(names[mr_mip->trace[i]]);
363 else mputs((char *)"???");
364 fputc('\n',stdout);
365 }
366
367 switch (nerr)
368 {
369 case 1 :
370 mputs((char *)"Number base too big for representation\n");
371 break;
372 case 2 :
373 mputs((char *)"Division by zero attempted\n");
374 break;
375 case 3 :
376 mputs((char *)"Overflow - Number too big\n");
377 break;
378 case 4 :
379 mputs((char *)"Internal result is negative\n");
380 break;
381 case 5 :
382 mputs((char *)"Input format error\n");
383 break;
384 case 6 :
385 mputs((char *)"Illegal number base\n");
386 break;
387 case 7 :
388 mputs((char *)"Illegal parameter usage\n");
389 break;
390 case 8 :
391 mputs((char *)"Out of space\n");
392 break;
393 case 9 :
394 mputs((char *)"Even root of a negative number\n");
395 break;
396 case 10:
397 mputs((char *)"Raising integer to negative power\n");
398 break;
399 case 11:
400 mputs((char *)"Attempt to take illegal root\n");
401 break;
402 case 12:
403 mputs((char *)"Integer operation attempted on Flash number\n");
404 break;
405 case 13:
406 mputs((char *)"Flash overflow\n");
407 break;
408 case 14:
409 mputs((char *)"Numbers too big\n");
410 break;
411 case 15:
412 mputs((char *)"Log of a non-positive number\n");
413 break;
414 case 16:
415 mputs((char *)"Flash to double conversion failure\n");
416 break;
417 case 17:
418 mputs((char *)"I/O buffer overflow\n");
419 break;
420 case 18:
421 mputs((char *)"MIRACL not initialised - no call to mirsys()\n");
422 break;
423 case 19:
424 mputs((char *)"Illegal modulus \n");
425 break;
426 case 20:
427 mputs((char *)"No modulus defined\n");
428 break;
429 case 21:
430 mputs((char *)"Exponent too big\n");
431 break;
432 case 22:
433 mputs((char *)"Unsupported Feature - check mirdef.h\n");
434 break;
435 case 23:
436 mputs((char *)"Specified double length type isn't double length\n");
437 break;
438 case 24:
439 mputs((char *)"Specified basis is NOT irreducible\n");
440 break;
441 case 25:
442 mputs((char *)"Unable to control Floating-point rounding\n");
443 break;
444 case 26:
445 mputs((char *)"Base must be binary (MR_ALWAYS_BINARY defined in mirdef.h ?)\n");
446 break;
447 case 27:
448 mputs((char *)"No irreducible basis defined\n");
449 break;
450 case 28:
451 mputs((char *)"Composite modulus\n");
452 break;
453 case 29:
454 mputs((char *)"Input/output error when reading from RNG device node\n");
455 break;
456 default:
457 mputs((char *)"Undefined error\n");
458 break;
459 }
460 exit(0);
461 #else
462 mputs((char *)"MIRACL error\n");
463 exit(0);
464 #endif
465
466 #endif
467 }
468
469 #ifndef MR_STRIPPED_DOWN
470
mr_track(_MIPDO_)471 void mr_track(_MIPDO_ )
472 { /* track course of program execution *
473 * through the MIRACL routines */
474
475 #ifndef MR_NO_STANDARD_IO
476
477 int i;
478 #ifdef MR_OS_THREADS
479 miracl *mr_mip=get_mip();
480 #endif
481 for (i=0;i<mr_mip->depth;i++) fputc('-',stdout);
482 fputc('>',stdout);
483 mputs(names[mr_mip->trace[mr_mip->depth]]);
484 fputc('\n',stdout);
485 #endif
486 }
487
488 #endif
489
490 #ifndef MR_NO_RAND
491
brand(_MIPDO_)492 mr_small brand(_MIPDO_ )
493 { /* Marsaglia & Zaman random number generator */
494 int i,k;
495 mr_unsign32 pdiff,t;
496 mr_small r;
497 #ifdef MR_OS_THREADS
498 miracl *mr_mip=get_mip();
499 #endif
500 if (mr_mip->lg2b>32)
501 { /* underlying type is > 32 bits. Assume <= 64 bits */
502 mr_mip->rndptr+=2;
503 if (mr_mip->rndptr<NK-1)
504 {
505 r=(mr_small)mr_mip->ira[mr_mip->rndptr];
506 r=mr_shiftbits(r,mr_mip->lg2b-32);
507 r+=(mr_small)mr_mip->ira[mr_mip->rndptr+1];
508 return r;
509 }
510 }
511 else
512 {
513 mr_mip->rndptr++;
514 if (mr_mip->rndptr<NK) return (mr_small)mr_mip->ira[mr_mip->rndptr];
515 }
516 mr_mip->rndptr=0;
517 for (i=0,k=NK-NJ;i<NK;i++,k++)
518 { /* calculate next NK values */
519 if (k==NK) k=0;
520 t=mr_mip->ira[k];
521 pdiff=t - mr_mip->ira[i] - mr_mip->borrow;
522 if (pdiff<t) mr_mip->borrow=0;
523 if (pdiff>t) mr_mip->borrow=1;
524 mr_mip->ira[i]=pdiff;
525 }
526 if (mr_mip->lg2b>32)
527 { /* double up */
528 r=(mr_small)mr_mip->ira[0];
529 r=mr_shiftbits(r,mr_mip->lg2b-32);
530 r+=(mr_small)mr_mip->ira[1];
531 return r;
532 }
533 else return (mr_small)(mr_mip->ira[0]);
534 }
535
irand(_MIPD_ mr_unsign32 seed)536 void irand(_MIPD_ mr_unsign32 seed)
537 { /* initialise random number system */
538 int i,in;
539 mr_unsign32 t,m=1L;
540 #ifdef MR_OS_THREADS
541 miracl *mr_mip=get_mip();
542 #endif
543 mr_mip->borrow=0L;
544 mr_mip->rndptr=0;
545 mr_mip->ira[0]=seed;
546 for (i=1;i<NK;i++)
547 { /* fill initialisation vector */
548 in=(NV*i)%NK;
549 mr_mip->ira[in]=m;
550 t=m;
551 m=seed-m;
552 seed=t;
553 }
554 for (i=0;i<1000;i++) brand(_MIPPO_ ); /* "warm-up" & stir the generator */
555 }
556
557 #endif
558
mr_shiftbits(mr_small x,int n)559 mr_small mr_shiftbits(mr_small x,int n)
560 {
561 #ifdef MR_FP
562 int i;
563 mr_small dres;
564 if (n==0) return x;
565 if (n>0)
566 {
567 for (i=0;i<n;i++) x=x+x;
568 return x;
569 }
570 n=-n;
571 for (i=0;i<n;i++) x=MR_DIV(x,2.0);
572 return x;
573 #else
574 if (n==0) return x;
575 if (n>0) x<<=n;
576 else x>>=(-n);
577 return x;
578 #endif
579
580 }
581
mr_setbase(_MIPD_ mr_small nb)582 mr_small mr_setbase(_MIPD_ mr_small nb)
583 { /* set base. Pack as many digits as *
584 * possible into each computer word */
585 mr_small temp;
586 #ifdef MR_FP
587 mr_small dres;
588 #endif
589 #ifndef MR_NOFULLWIDTH
590 BOOL fits;
591 int bits;
592 #ifdef MR_OS_THREADS
593 miracl *mr_mip=get_mip();
594 #endif
595 fits=FALSE;
596 bits=MIRACL;
597 while (bits>1)
598 {
599 bits/=2;
600 temp=((mr_small)1<<bits);
601 if (temp==nb)
602 {
603 fits=TRUE;
604 break;
605 }
606 if (temp<nb || (bits%2)!=0) break;
607 }
608 if (fits)
609 {
610 mr_mip->apbase=nb;
611 mr_mip->pack=MIRACL/bits;
612 mr_mip->base=0;
613 return 0;
614 }
615 #endif
616 mr_mip->apbase=nb;
617 mr_mip->pack=1;
618 mr_mip->base=nb;
619 #ifdef MR_SIMPLE_BASE
620 return 0;
621 #else
622 if (mr_mip->base==0) return 0;
623 temp=MR_DIV(MAXBASE,nb);
624 while (temp>=nb)
625 {
626 temp=MR_DIV(temp,nb);
627 mr_mip->base*=nb;
628 mr_mip->pack++;
629 }
630 #ifdef MR_FP_ROUNDING
631 mr_mip->inverse_base=mr_invert(mr_mip->base);
632 return mr_mip->inverse_base;
633 #else
634 return 0;
635 #endif
636 #endif
637 }
638
639 #ifdef MR_FLASH
640
fit(big x,big y,int f)641 BOOL fit(big x,big y,int f)
642 { /* returns TRUE if x/y would fit flash format of length f */
643 int n,d;
644 n=(int)(x->len&(MR_OBITS));
645 d=(int)(y->len&(MR_OBITS));
646 if (n==1 && x->w[0]==1) n=0;
647 if (d==1 && y->w[0]==1) d=0;
648 if (n+d<=f) return TRUE;
649 return FALSE;
650 }
651
652 #endif
653
mr_lent(flash x)654 int mr_lent(flash x)
655 { /* return length of big or flash in words */
656 mr_lentype lx;
657 lx=(x->len&(MR_OBITS));
658 #ifdef MR_FLASH
659 return (int)((lx&(MR_MSK))+((lx>>(MR_BTS))&(MR_MSK)));
660 #else
661 return (int)lx;
662 #endif
663 }
664
zero(flash x)665 void zero(flash x)
666 { /* set big/flash number to zero */
667 int i,n;
668 mr_small *g;
669 if (x==NULL) return;
670 #ifdef MR_FLASH
671 n=mr_lent(x);
672 #else
673 n=(x->len&MR_OBITS);
674 #endif
675 g=x->w;
676
677 for (i=0;i<n;i++)
678 g[i]=0;
679
680 x->len=0;
681 }
682
uconvert(_MIPD_ unsigned int n,big x)683 void uconvert(_MIPD_ unsigned int n ,big x)
684 { /* convert unsigned integer n to big number format */
685 int m;
686 #ifdef MR_FP
687 mr_small dres;
688 #endif
689 #ifdef MR_OS_THREADS
690 miracl *mr_mip=get_mip();
691 #endif
692 zero(x);
693 if (n==0) return;
694
695 m=0;
696 #ifndef MR_SIMPLE_BASE
697 if (mr_mip->base==0)
698 {
699 #endif
700 #ifndef MR_NOFULLWIDTH
701 #if MR_IBITS > MIRACL
702 while (n>0)
703 {
704 x->w[m++]=(mr_small)(n%((mr_small)1<<(MIRACL)));
705 n/=((mr_small)1<<(MIRACL));
706 }
707 #else
708 x->w[m++]=(mr_small)n;
709 #endif
710 #endif
711 #ifndef MR_SIMPLE_BASE
712 }
713 else while (n>0)
714 {
715 x->w[m++]=MR_REMAIN((mr_small)n,mr_mip->base);
716 n=(unsigned int)((mr_small)n/mr_mip->base);
717 }
718 #endif
719 x->len=m;
720 }
721
tconvert(_MIPD_ mr_utype n,big x)722 void tconvert(_MIPD_ mr_utype n,big x)
723 {
724 mr_lentype s;
725 #ifdef MR_OS_THREADS
726 miracl *mr_mip=get_mip();
727 #endif
728 if (n==0) {zero(x); return;}
729 s=0;
730 if (n<0)
731 {
732 s=MR_MSBIT;
733 n=(-n);
734 }
735 x->w[0]=n;
736 x->len=1;
737 x->len|=s;
738 }
739
convert(_MIPD_ int n,big x)740 void convert(_MIPD_ int n ,big x)
741 { /* convert signed integer n to big number format */
742 mr_lentype s;
743
744 #ifdef MR_OS_THREADS
745 miracl *mr_mip=get_mip();
746 #endif
747 if (n==0) {zero(x); return;}
748 s=0;
749 if (n<0)
750 {
751 s=MR_MSBIT;
752 n=(-n);
753 }
754 uconvert(_MIPP_ (unsigned int)n,x);
755 x->len|=s;
756 }
757
758 #ifndef MR_STATIC
759 #ifdef mr_dltype
760
dlconv(_MIPD_ mr_dltype n,big x)761 void dlconv(_MIPD_ mr_dltype n,big x)
762 { /* convert double length integer to big number format - rarely needed */
763 int m;
764 mr_lentype s;
765 #ifdef MR_FP
766 mr_small dres;
767 #endif
768 #ifdef MR_OS_THREADS
769 miracl *mr_mip=get_mip();
770 #endif
771 zero(x);
772 if (n==0) return;
773 s=0;
774 if (n<0)
775 {
776 s=MR_MSBIT;
777 n=(-n);
778 }
779 m=0;
780 #ifndef MR_SIMPLE_BASE
781 if (mr_mip->base==0)
782 {
783 #endif
784 #ifndef MR_NOFULLWIDTH
785 while (n>0)
786 {
787 x->w[m++]=(mr_small)(n%((mr_dltype)1<<(MIRACL)));
788 n/=((mr_dltype)1<<(MIRACL));
789 }
790 #endif
791 #ifndef MR_SIMPLE_BASE
792 }
793 else while (n>0)
794 {
795 x->w[m++]=(mr_small)MR_REMAIN(n,mr_mip->base);
796 n/=mr_mip->base;
797 }
798 #endif
799 x->len=(m|s);
800 }
801
802 #endif
803
ulgconv(_MIPD_ unsigned long n,big x)804 void ulgconv(_MIPD_ unsigned long n,big x)
805 { /* convert unsigned long integer to big number format - rarely needed */
806 int m;
807 #ifdef MR_FP
808 mr_small dres;
809 #endif
810 #ifdef MR_OS_THREADS
811 miracl *mr_mip=get_mip();
812 #endif
813 zero(x);
814 if (n==0) return;
815
816 m=0;
817 #ifndef MR_SIMPLE_BASE
818 if (mr_mip->base==0)
819 {
820 #endif
821 #ifndef MR_NOFULLWIDTH
822 #if MR_LBITS > MIRACL
823 while (n>0)
824 {
825 x->w[m++]=(mr_small)(n%(1L<<(MIRACL)));
826 n/=(1L<<(MIRACL));
827 }
828 #else
829 x->w[m++]=(mr_small)n;
830 #endif
831 #endif
832 #ifndef MR_SIMPLE_BASE
833 }
834 else while (n>0)
835 {
836 x->w[m++]=MR_REMAIN(n,mr_mip->base);
837 n=(unsigned long)((mr_small)n/mr_mip->base);
838 }
839 #endif
840 x->len=m;
841 }
842
lgconv(_MIPD_ long n,big x)843 void lgconv(_MIPD_ long n,big x)
844 { /* convert signed long integer to big number format - rarely needed */
845 mr_lentype s;
846
847 #ifdef MR_OS_THREADS
848 miracl *mr_mip=get_mip();
849 #endif
850 if (n==0) {zero(x); return;}
851 s=0;
852 if (n<0)
853 {
854 s=MR_MSBIT;
855 n=(-n);
856 }
857 ulgconv(_MIPP_ (unsigned long)n,x);
858
859 x->len|=s;
860 }
861
mirvar(_MIPD_ int iv)862 flash mirvar(_MIPD_ int iv)
863 { /* initialize big/flash number */
864 flash x;
865 int align;
866 char *ptr;
867 #ifdef MR_OS_THREADS
868 miracl *mr_mip=get_mip();
869 #endif
870
871 if (mr_mip->ERNUM) return NULL;
872 MR_IN(23);
873
874 if (!(mr_mip->active))
875 {
876 mr_berror(_MIPP_ MR_ERR_NO_MIRSYS);
877 MR_OUT
878 return NULL;
879 }
880
881 /* OK, now I control alignment.... */
882
883 /* Allocate space for big, the length, the pointer, and the array */
884 /* Do it all in one memory allocation - this is quicker */
885 /* Ensure that the array has correct alignment */
886
887 x=(big)mr_alloc(_MIPP_ mr_size(mr_mip->nib-1),1);
888 if (x==NULL)
889 {
890 MR_OUT
891 return x;
892 }
893
894 ptr=(char *)&x->w;
895 align=(unsigned long)(ptr+sizeof(mr_small *))%sizeof(mr_small);
896
897 x->w=(mr_small *)(ptr+sizeof(mr_small *)+sizeof(mr_small)-align);
898
899 if (iv!=0) convert(_MIPP_ iv,x);
900 MR_OUT
901 return x;
902 }
903
904 #endif
905
mirvar_mem_variable(char * mem,int index,int sz)906 flash mirvar_mem_variable(char *mem,int index,int sz)
907 {
908 flash x;
909 int align;
910 char *ptr;
911 int offset,r;
912
913 /* alignment */
914 offset=0;
915 r=(unsigned long)mem%MR_SL;
916 if (r>0) offset=MR_SL-r;
917
918 x=(big)&mem[offset+mr_size(sz)*index];
919 ptr=(char *)&x->w;
920 align=(unsigned long)(ptr+sizeof(mr_small *))%sizeof(mr_small);
921 x->w=(mr_small *)(ptr+sizeof(mr_small *)+sizeof(mr_small)-align);
922
923 return x;
924 }
925
mirvar_mem(_MIPD_ char * mem,int index)926 flash mirvar_mem(_MIPD_ char *mem,int index)
927 { /* initialize big/flash number from pre-allocated memory */
928
929 #ifdef MR_OS_THREADS
930 miracl *mr_mip=get_mip();
931 #endif
932
933 if (mr_mip->ERNUM) return NULL;
934
935 return mirvar_mem_variable(mem,index,mr_mip->nib-1);
936
937 }
938
set_user_function(_MIPD_ BOOL (* user)(void))939 void set_user_function(_MIPD_ BOOL (*user)(void))
940 {
941 #ifdef MR_OS_THREADS
942 miracl *mr_mip=get_mip();
943 #endif
944 if (mr_mip->ERNUM) return;
945
946 MR_IN(111)
947
948 if (!(mr_mip->active))
949 {
950 mr_berror(_MIPP_ MR_ERR_NO_MIRSYS);
951 MR_OUT
952 return;
953 }
954
955 mr_mip->user=user;
956
957 MR_OUT
958 }
959
960 #ifndef MR_STATIC
961
962 #ifndef MR_SIMPLE_IO
963
set_io_buffer_size(_MIPD_ int len)964 void set_io_buffer_size(_MIPD_ int len)
965 {
966 int i;
967 #ifdef MR_OS_THREADS
968 miracl *mr_mip=get_mip();
969 #endif
970 if (len<0) return;
971 MR_IN(142)
972 for (i=0;i<mr_mip->IOBSIZ;i++) mr_mip->IOBUFF[i]=0;
973 mr_free(mr_mip->IOBUFF);
974 if (len==0)
975 {
976 MR_OUT
977 return;
978 }
979 mr_mip->IOBSIZ=len;
980 mr_mip->IOBUFF=(char *)mr_alloc(_MIPP_ len+1,1);
981 mr_mip->IOBUFF[0]='\0';
982 MR_OUT
983 }
984 #endif
985
986 #endif
987
988 /* Initialise a big from ROM given its fixed length */
989
init_big_from_rom(big x,int len,const mr_small * rom,int romsize,int * romptr)990 BOOL init_big_from_rom(big x,int len,const mr_small *rom,int romsize,int *romptr)
991 {
992 int i;
993 zero(x);
994 x->len=len;
995 for (i=0;i<len;i++)
996 {
997 if (*romptr>=romsize) return FALSE;
998 #ifdef MR_AVR
999 x->w[i]=pgm_read_byte_near(&rom[*romptr]);
1000 #else
1001 x->w[i]=rom[*romptr];
1002 #endif
1003 (*romptr)++;
1004 }
1005
1006 mr_lzero(x);
1007 return TRUE;
1008 }
1009
1010 /* Initialise an elliptic curve point from ROM */
1011
init_point_from_rom(epoint * P,int len,const mr_small * rom,int romsize,int * romptr)1012 BOOL init_point_from_rom(epoint *P,int len,const mr_small *rom,int romsize,int *romptr)
1013 {
1014 if (!init_big_from_rom(P->X,len,rom,romsize,romptr)) return FALSE;
1015 if (!init_big_from_rom(P->Y,len,rom,romsize,romptr)) return FALSE;
1016 P->marker=MR_EPOINT_NORMALIZED;
1017 return TRUE;
1018 }
1019
1020 #ifdef MR_GENERIC_AND_STATIC
mirsys(miracl * mr_mip,int nd,mr_small nb)1021 miracl *mirsys(miracl *mr_mip,int nd,mr_small nb)
1022 #else
1023 miracl *mirsys(int nd,mr_small nb)
1024 #endif
1025 { /* Initialize MIRACL system to *
1026 * use numbers to base nb, and *
1027 * nd digits or (-nd) bytes long */
1028
1029 /* In these cases mr_mip is passed as the first parameter */
1030
1031 #ifdef MR_GENERIC_AND_STATIC
1032 return mirsys_basic(mr_mip,nd,nb);
1033 #endif
1034
1035 #ifdef MR_GENERIC_MT
1036 #ifndef MR_STATIC
1037 miracl *mr_mip=mr_first_alloc();
1038 return mirsys_basic(mr_mip,nd,nb);
1039 #endif
1040 #endif
1041 /* In these cases mr_mip is a "global" pointer and the mip itself is allocated from the heap.
1042 In fact mr_mip (and mip) may be thread specific if some multi-threading scheme is implemented */
1043 #ifndef MR_STATIC
1044 #ifdef MR_WINDOWS_MT
1045 miracl *mr_mip=mr_first_alloc();
1046 TlsSetValue(mr_key,mr_mip);
1047 #endif
1048
1049 #ifdef MR_UNIX_MT
1050 miracl *mr_mip=mr_first_alloc();
1051 pthread_setspecific(mr_key,mr_mip);
1052 #endif
1053
1054 #ifdef MR_OPENMP_MT
1055 mr_mip=mr_first_alloc();
1056 #endif
1057
1058 #ifndef MR_WINDOWS_MT
1059 #ifndef MR_UNIX_MT
1060 #ifndef MR_OPENMP_MT
1061 mr_mip=mr_first_alloc();
1062 #endif
1063 #endif
1064 #endif
1065 #endif
1066
1067 #ifndef MR_GENERIC_MT
1068 mr_mip=get_mip();
1069 #endif
1070 return mirsys_basic(mr_mip,nd,nb);
1071 }
1072
mirsys_basic(miracl * mr_mip,int nd,mr_small nb)1073 miracl *mirsys_basic(miracl *mr_mip,int nd,mr_small nb)
1074 {
1075 #ifndef MR_NO_RAND
1076 int i;
1077 #endif
1078
1079 mr_small b,nw;
1080 #ifdef MR_FP
1081 mr_small dres;
1082 #endif
1083
1084 if (mr_mip==NULL) return NULL;
1085
1086 #ifndef MR_STRIPPED_DOWN
1087 mr_mip->depth=0;
1088 mr_mip->trace[0]=0;
1089 mr_mip->depth++;
1090 mr_mip->trace[mr_mip->depth]=29;
1091 #endif
1092 /* digest hardware configuration */
1093
1094 #ifdef MR_NO_STANDARD_IO
1095 mr_mip->ERCON=TRUE;
1096 #else
1097 mr_mip->ERCON=FALSE;
1098 #endif
1099 #ifndef MR_STATIC
1100 mr_mip->logN=0;
1101 mr_mip->degree=0;
1102 mr_mip->chin.NP=0;
1103 #endif
1104
1105
1106 mr_mip->user=NULL;
1107 mr_mip->same=FALSE;
1108 mr_mip->first_one=FALSE;
1109 mr_mip->debug=FALSE;
1110 mr_mip->AA=0;
1111 #ifndef MR_AFFINE_ONLY
1112 mr_mip->coord=MR_NOTSET;
1113 #endif
1114
1115 #ifdef MR_NOFULLWIDTH
1116 if (nb==0)
1117 {
1118 mr_berror(_MIPP_ MR_ERR_BAD_BASE);
1119 MR_OUT
1120 return mr_mip;
1121 }
1122 #endif
1123
1124 #ifndef MR_FP
1125 #ifdef mr_dltype
1126 #ifndef MR_NOFULLWIDTH
1127 if (sizeof(mr_dltype)<2*sizeof(mr_utype))
1128 { /* double length type, isn't */
1129 mr_berror(_MIPP_ MR_ERR_NOT_DOUBLE_LEN);
1130 MR_OUT
1131 return mr_mip;
1132 }
1133 #endif
1134 #endif
1135 #endif
1136
1137 if (nb==1 || nb>MAXBASE)
1138 {
1139 mr_berror(_MIPP_ MR_ERR_BAD_BASE);
1140 MR_OUT
1141 return mr_mip;
1142 }
1143
1144 #ifdef MR_FP_ROUNDING
1145 if (mr_setbase(_MIPP_ nb)==0)
1146 { /* unable in fact to control FP rounding */
1147 mr_berror(_MIPP_ MR_ERR_NO_ROUNDING);
1148 MR_OUT
1149 return mr_mip;
1150 }
1151 #else
1152 mr_setbase(_MIPP_ nb);
1153 #endif
1154
1155 b=mr_mip->base;
1156
1157 #ifdef MR_SIMPLE_BASE
1158 if (b!=0)
1159 {
1160 mr_berror(_MIPP_ MR_ERR_BAD_BASE);
1161 MR_OUT
1162 return mr_mip;
1163 }
1164 #endif
1165
1166 mr_mip->lg2b=0;
1167 mr_mip->base2=1;
1168 #ifndef MR_SIMPLE_BASE
1169 if (b==0)
1170 {
1171 #endif
1172 mr_mip->lg2b=MIRACL;
1173 mr_mip->base2=0;
1174 #ifndef MR_SIMPLE_BASE
1175 }
1176 else while (b>1)
1177 {
1178 b=MR_DIV(b,2);
1179 mr_mip->lg2b++;
1180 mr_mip->base2*=2;
1181 }
1182 #endif
1183
1184 #ifdef MR_ALWAYS_BINARY
1185 if (mr_mip->base!=mr_mip->base2)
1186 {
1187 mr_berror(_MIPP_ MR_ERR_NOT_BINARY);
1188 MR_OUT
1189 return mr_mip;
1190 }
1191 #endif
1192
1193 /* calculate total space for bigs */
1194 /*
1195
1196 big -> |int len|small *ptr| alignment space | size in words +1| alignment up to multiple of 4 |
1197
1198
1199 */
1200 if (nd>0) nw=MR_ROUNDUP(nd,mr_mip->pack);
1201 else nw=MR_ROUNDUP(8*(-nd),mr_mip->lg2b);
1202
1203 if (nw<1) nw=1;
1204 mr_mip->nib=(int)(nw+1); /* add one extra word for small overflows */
1205
1206 #ifdef MR_STATIC
1207 if (nw>MR_STATIC)
1208 {
1209 mr_berror(_MIPP_ MR_ERR_TOO_BIG);
1210 MR_OUT
1211 return mr_mip;
1212 }
1213 #endif
1214
1215 /* mr_mip->nib=(int)(nw+1); add one extra word for small overflows */
1216
1217 #ifdef MR_FLASH
1218 mr_mip->workprec=mr_mip->nib;
1219 mr_mip->stprec=mr_mip->nib;
1220 while (mr_mip->stprec>2 && mr_mip->stprec>MR_FLASH/mr_mip->lg2b)
1221 mr_mip->stprec=(mr_mip->stprec+1)/2;
1222 if (mr_mip->stprec<2) mr_mip->stprec=2;
1223
1224 #endif
1225
1226 #ifndef MR_DOUBLE_BIG
1227 mr_mip->check=ON;
1228 #else
1229 mr_mip->check=OFF;
1230 #endif
1231
1232 #ifndef MR_SIMPLE_BASE
1233 #ifndef MR_SIMPLE_IO
1234 mr_mip->IOBASE=10; /* defaults */
1235 #endif
1236 #endif
1237 mr_mip->ERNUM=0;
1238
1239 mr_mip->NTRY=6;
1240 mr_mip->MONTY=ON;
1241 #ifdef MR_FLASH
1242 mr_mip->EXACT=TRUE;
1243 mr_mip->RPOINT=OFF;
1244 #endif
1245 #ifndef MR_STRIPPED_DOWN
1246 mr_mip->TRACER=OFF;
1247 #endif
1248
1249 #ifndef MR_SIMPLE_IO
1250 mr_mip->INPLEN=0;
1251 mr_mip->IOBSIZ=MR_DEFAULT_BUFFER_SIZE;
1252 #endif
1253
1254 #ifdef MR_STATIC
1255 mr_mip->PRIMES=mr_small_primes;
1256 #else
1257 mr_mip->PRIMES=NULL;
1258 #ifndef MR_SIMPLE_IO
1259 mr_mip->IOBUFF=(char *)mr_alloc(_MIPP_ MR_DEFAULT_BUFFER_SIZE+1,1);
1260 #endif
1261 #endif
1262 #ifndef MR_SIMPLE_IO
1263 mr_mip->IOBUFF[0]='\0';
1264 #endif
1265 mr_mip->qnr=0;
1266 mr_mip->cnr=0;
1267 mr_mip->TWIST=0;
1268 mr_mip->pmod8=0;
1269 mr_mip->pmod9=0;
1270
1271 /* quick start for rng. irand(.) should be called first before serious use.. */
1272
1273 #ifndef MR_NO_RAND
1274 mr_mip->ira[0]=0x55555555;
1275 mr_mip->ira[1]=0x12345678;
1276
1277 for (i=2;i<NK;i++)
1278 mr_mip->ira[i]=mr_mip->ira[i-1]+mr_mip->ira[i-2]+0x1379BDF1;
1279 mr_mip->rndptr=NK;
1280 mr_mip->borrow=0;
1281 #endif
1282
1283 mr_mip->nib=2*mr_mip->nib+1;
1284 #ifdef MR_FLASH
1285 if (mr_mip->nib!=(mr_mip->nib&(MR_MSK)))
1286 #else
1287 if (mr_mip->nib!=(int)(mr_mip->nib&(MR_OBITS)))
1288 #endif
1289 {
1290 mr_berror(_MIPP_ MR_ERR_TOO_BIG);
1291 mr_mip->nib=(mr_mip->nib-1)/2;
1292 MR_OUT
1293 return mr_mip;
1294 }
1295 #ifndef MR_STATIC
1296 mr_mip->workspace=(char *)memalloc(_MIPP_ MR_SPACES); /* grab workspace */
1297 #else
1298 memset(mr_mip->workspace,0,MR_BIG_RESERVE(MR_SPACES));
1299 #endif
1300
1301 mr_mip->M=0;
1302 mr_mip->fin=FALSE;
1303 mr_mip->fout=FALSE;
1304 mr_mip->active=ON;
1305
1306 mr_mip->nib=(mr_mip->nib-1)/2;
1307
1308 /* allocate memory for workspace variables */
1309
1310 #ifndef MR_DOUBLE_BIG
1311
1312 mr_mip->w0=mirvar_mem(_MIPP_ mr_mip->workspace,0); /* double length */
1313 mr_mip->w1=mirvar_mem(_MIPP_ mr_mip->workspace,2);
1314 mr_mip->w2=mirvar_mem(_MIPP_ mr_mip->workspace,3);
1315 mr_mip->w3=mirvar_mem(_MIPP_ mr_mip->workspace,4);
1316 mr_mip->w4=mirvar_mem(_MIPP_ mr_mip->workspace,5);
1317 mr_mip->w5=mirvar_mem(_MIPP_ mr_mip->workspace,6); /* double length */
1318 mr_mip->w6=mirvar_mem(_MIPP_ mr_mip->workspace,8); /* double length */
1319 mr_mip->w7=mirvar_mem(_MIPP_ mr_mip->workspace,10); /* double length */
1320 mr_mip->w8=mirvar_mem(_MIPP_ mr_mip->workspace,12);
1321 mr_mip->w9=mirvar_mem(_MIPP_ mr_mip->workspace,13);
1322 mr_mip->w10=mirvar_mem(_MIPP_ mr_mip->workspace,14);
1323 mr_mip->w11=mirvar_mem(_MIPP_ mr_mip->workspace,15);
1324 mr_mip->w12=mirvar_mem(_MIPP_ mr_mip->workspace,16);
1325 mr_mip->w13=mirvar_mem(_MIPP_ mr_mip->workspace,17);
1326 mr_mip->w14=mirvar_mem(_MIPP_ mr_mip->workspace,18);
1327 mr_mip->w15=mirvar_mem(_MIPP_ mr_mip->workspace,19);
1328 mr_mip->sru=mirvar_mem(_MIPP_ mr_mip->workspace,20);
1329 mr_mip->modulus=mirvar_mem(_MIPP_ mr_mip->workspace,21);
1330 mr_mip->pR=mirvar_mem(_MIPP_ mr_mip->workspace,22); /* double length */
1331 mr_mip->A=mirvar_mem(_MIPP_ mr_mip->workspace,24);
1332 mr_mip->B=mirvar_mem(_MIPP_ mr_mip->workspace,25);
1333 mr_mip->one=mirvar_mem(_MIPP_ mr_mip->workspace,26);
1334 #ifdef MR_KCM
1335 mr_mip->big_ndash=mirvar_mem(_MIPP_ mr_mip->workspace,27);
1336 mr_mip->ws=mirvar_mem(_MIPP_ mr_mip->workspace,28);
1337 mr_mip->wt=mirvar_mem(_MIPP_ mr_mip->workspace,29); /* double length */
1338 #endif
1339 #ifdef MR_FLASH
1340 #ifdef MR_KCM
1341 mr_mip->pi=mirvar_mem(_MIPP_ mr_mip->workspace,31);
1342 #else
1343 mr_mip->pi=mirvar_mem(_MIPP_ mr_mip->workspace,27);
1344 #endif
1345 #endif
1346
1347 #else
1348 /* w0-w7 are double normal length */
1349 mr_mip->w0=mirvar_mem(_MIPP_ mr_mip->workspace,0); /* quad length */
1350 mr_mip->w1=mirvar_mem(_MIPP_ mr_mip->workspace,4); /* double length */
1351 mr_mip->w2=mirvar_mem(_MIPP_ mr_mip->workspace,6);
1352 mr_mip->w3=mirvar_mem(_MIPP_ mr_mip->workspace,8);
1353 mr_mip->w4=mirvar_mem(_MIPP_ mr_mip->workspace,10);
1354 mr_mip->w5=mirvar_mem(_MIPP_ mr_mip->workspace,12); /* quad length */
1355 mr_mip->w6=mirvar_mem(_MIPP_ mr_mip->workspace,16); /* quad length */
1356 mr_mip->w7=mirvar_mem(_MIPP_ mr_mip->workspace,20); /* quad length */
1357 mr_mip->w8=mirvar_mem(_MIPP_ mr_mip->workspace,24);
1358
1359 mr_mip->w9=mirvar_mem(_MIPP_ mr_mip->workspace,25);
1360 mr_mip->w10=mirvar_mem(_MIPP_ mr_mip->workspace,26);
1361 mr_mip->w11=mirvar_mem(_MIPP_ mr_mip->workspace,27);
1362 mr_mip->w12=mirvar_mem(_MIPP_ mr_mip->workspace,28);
1363 mr_mip->w13=mirvar_mem(_MIPP_ mr_mip->workspace,29);
1364 mr_mip->w14=mirvar_mem(_MIPP_ mr_mip->workspace,30);
1365 mr_mip->w15=mirvar_mem(_MIPP_ mr_mip->workspace,31);
1366 mr_mip->sru=mirvar_mem(_MIPP_ mr_mip->workspace,32);
1367 mr_mip->modulus=mirvar_mem(_MIPP_ mr_mip->workspace,33);
1368 mr_mip->pR=mirvar_mem(_MIPP_ mr_mip->workspace,34); /* double length */
1369 mr_mip->A=mirvar_mem(_MIPP_ mr_mip->workspace,36);
1370 mr_mip->B=mirvar_mem(_MIPP_ mr_mip->workspace,37);
1371 mr_mip->one=mirvar_mem(_MIPP_ mr_mip->workspace,38);
1372 #ifdef MR_KCM
1373 mr_mip->big_ndash=mirvar_mem(_MIPP_ mr_mip->workspace,39);
1374 mr_mip->ws=mirvar_mem(_MIPP_ mr_mip->workspace,40);
1375 mr_mip->wt=mirvar_mem(_MIPP_ mr_mip->workspace,41); /* double length */
1376 #endif
1377 #ifdef MR_FLASH
1378 #ifdef MR_KCM
1379 mr_mip->pi=mirvar_mem(_MIPP_ mr_mip->workspace,43);
1380 #else
1381 mr_mip->pi=mirvar_mem(_MIPP_ mr_mip->workspace,39);
1382 #endif
1383 #endif
1384
1385 #endif
1386 MR_OUT
1387 return mr_mip;
1388 }
1389
1390 #ifndef MR_STATIC
1391
1392 /* allocate space for a number of bigs from the heap */
1393
memalloc(_MIPD_ int num)1394 void *memalloc(_MIPD_ int num)
1395 {
1396 #ifdef MR_OS_THREADS
1397 miracl *mr_mip=get_mip();
1398 #endif
1399 return mr_alloc(_MIPP_ mr_big_reserve(num,mr_mip->nib-1),1);
1400 }
1401
1402 #endif
1403
memkill(_MIPD_ char * mem,int len)1404 void memkill(_MIPD_ char *mem,int len)
1405 {
1406 #ifdef MR_OS_THREADS
1407 miracl *mr_mip=get_mip();
1408 #endif
1409 if (mem==NULL) return;
1410 memset(mem,0,mr_big_reserve(len,mr_mip->nib-1));
1411 #ifndef MR_STATIC
1412 mr_free(mem);
1413 #endif
1414 }
1415
1416 #ifndef MR_STATIC
1417
mirkill(big x)1418 void mirkill(big x)
1419 { /* kill a big/flash variable, that is set it to zero
1420 and free its memory */
1421 if (x==NULL) return;
1422 zero(x);
1423 mr_free(x);
1424 }
1425
1426 #endif
1427
mirexit(_MIPDO_)1428 void mirexit(_MIPDO_ )
1429 { /* clean up after miracl */
1430
1431 int i;
1432 #ifdef MR_WINDOWS_MT
1433 miracl *mr_mip=get_mip();
1434 #endif
1435 #ifdef MR_UNIX_MT
1436 miracl *mr_mip=get_mip();
1437 #endif
1438 #ifdef MR_OPENMP_MT
1439 miracl *mr_mip=get_mip();
1440 #endif
1441 mr_mip->ERCON=FALSE;
1442 mr_mip->active=OFF;
1443 memkill(_MIPP_ mr_mip->workspace,MR_SPACES);
1444 #ifndef MR_NO_RAND
1445 for (i=0;i<NK;i++) mr_mip->ira[i]=0L;
1446 #endif
1447 #ifndef MR_STATIC
1448 #ifndef MR_SIMPLE_IO
1449 set_io_buffer_size(_MIPP_ 0);
1450 #endif
1451 if (mr_mip->PRIMES!=NULL) mr_free(mr_mip->PRIMES);
1452 #else
1453 #ifndef MR_SIMPLE_IO
1454 for (i=0;i<=MR_DEFAULT_BUFFER_SIZE;i++)
1455 mr_mip->IOBUFF[i]=0;
1456 #endif
1457 #endif
1458
1459 #ifndef MR_STATIC
1460 mr_free(mr_mip);
1461 #ifdef MR_WINDOWS_MT
1462 TlsSetValue(mr_key, NULL); /* Thank you Thales */
1463 #endif
1464 #endif
1465
1466 #ifndef MR_GENERIC_MT
1467 #ifndef MR_WINDOWS_MT
1468 #ifndef MR_UNIX_MT
1469 #ifndef MR_STATIC
1470 mr_mip=NULL;
1471 #endif
1472 #endif
1473 #endif
1474 #endif
1475
1476 #ifdef MR_OPENMP_MT
1477 mr_mip=NULL;
1478 #endif
1479
1480 }
1481
exsign(flash x)1482 int exsign(flash x)
1483 { /* extract sign of big/flash number */
1484 if ((x->len&(MR_MSBIT))==0) return PLUS;
1485 else return MINUS;
1486 }
1487
insign(int s,flash x)1488 void insign(int s,flash x)
1489 { /* assert sign of big/flash number */
1490 if (x->len==0) return;
1491 if (s<0) x->len|=MR_MSBIT;
1492 else x->len&=MR_OBITS;
1493 }
1494
mr_lzero(big x)1495 void mr_lzero(big x)
1496 { /* strip leading zeros from big number */
1497 mr_lentype s;
1498 int m;
1499 s=(x->len&(MR_MSBIT));
1500 m=(int)(x->len&(MR_OBITS));
1501 while (m>0 && x->w[m-1]==0)
1502 m--;
1503 x->len=m;
1504 if (m>0) x->len|=s;
1505 }
1506
1507 #ifndef MR_SIMPLE_IO
1508
getdig(_MIPD_ big x,int i)1509 int getdig(_MIPD_ big x,int i)
1510 { /* extract a packed digit */
1511 int k;
1512 mr_small n;
1513 #ifdef MR_FP
1514 mr_small dres;
1515 #endif
1516 #ifdef MR_OS_THREADS
1517 miracl *mr_mip=get_mip();
1518 #endif
1519 i--;
1520 n=x->w[i/mr_mip->pack];
1521
1522 if (mr_mip->pack==1) return (int)n;
1523 k=i%mr_mip->pack;
1524 for (i=1;i<=k;i++)
1525 n=MR_DIV(n,mr_mip->apbase);
1526 return (int)MR_REMAIN(n,mr_mip->apbase);
1527 }
1528
numdig(_MIPD_ big x)1529 int numdig(_MIPD_ big x)
1530 { /* returns number of digits in x */
1531 int nd;
1532 #ifdef MR_OS_THREADS
1533 miracl *mr_mip=get_mip();
1534 #endif
1535
1536 if (x->len==0) return 0;
1537
1538 nd=(int)(x->len&(MR_OBITS))*mr_mip->pack;
1539 while (getdig(_MIPP_ x,nd)==0)
1540 nd--;
1541 return nd;
1542 }
1543
putdig(_MIPD_ int n,big x,int i)1544 void putdig(_MIPD_ int n,big x,int i)
1545 { /* insert a digit into a packed word */
1546 int j,k,lx;
1547 mr_small m,p;
1548 mr_lentype s;
1549 #ifdef MR_OS_THREADS
1550 miracl *mr_mip=get_mip();
1551 #endif
1552 if (mr_mip->ERNUM) return;
1553
1554 MR_IN(26)
1555
1556 s=(x->len&(MR_MSBIT));
1557 lx=(int)(x->len&(MR_OBITS));
1558 m=getdig(_MIPP_ x,i);
1559 p=n;
1560 i--;
1561 j=i/mr_mip->pack;
1562 k=i%mr_mip->pack;
1563 for (i=1;i<=k;i++)
1564 {
1565 m*=mr_mip->apbase;
1566 p*=mr_mip->apbase;
1567 }
1568 if (j>=mr_mip->nib && (mr_mip->check || j>=2*mr_mip->nib))
1569 {
1570 mr_berror(_MIPP_ MR_ERR_OVERFLOW);
1571 MR_OUT
1572 return;
1573 }
1574
1575 x->w[j]=(x->w[j]-m)+p;
1576 if (j>=lx) x->len=((j+1)|s);
1577 mr_lzero(x);
1578 MR_OUT
1579 }
1580
1581 #endif
1582
1583 #ifndef MR_FP
1584
mr_and(big x,big y,big z)1585 void mr_and(big x,big y,big z)
1586 { /* z= bitwise logical AND of x and y */
1587 int i,nx,ny,nz,nr;
1588 if (x==y)
1589 {
1590 copy(x,z);
1591 return;
1592 }
1593
1594 #ifdef MR_FLASH
1595 nx=mr_lent(x);
1596 ny=mr_lent(y);
1597 nz=mr_lent(z);
1598 #else
1599 ny=(y->len&(MR_OBITS));
1600 nx=(x->len&(MR_OBITS));
1601 nz=(z->len&(MR_OBITS));
1602 #endif
1603 if (ny<nx) nr=ny;
1604 else nr=nx;
1605 for (i=0;i<nr;i++)
1606 z->w[i]=x->w[i]&y->w[i];
1607 for (i=nr;i<nz;i++)
1608 z->w[i]=0;
1609 z->len=nr;
1610 }
1611
mr_xor(big x,big y,big z)1612 void mr_xor(big x,big y,big z)
1613 {
1614 int i,nx,ny,nz,nr;
1615 if (x==y)
1616 {
1617 copy(x,z);
1618 return;
1619 }
1620
1621 #ifdef MR_FLASH
1622 nx=mr_lent(x);
1623 ny=mr_lent(y);
1624 nz=mr_lent(z);
1625 #else
1626 ny=(y->len&(MR_OBITS));
1627 nx=(x->len&(MR_OBITS));
1628 nz=(z->len&(MR_OBITS));
1629 #endif
1630 if (ny<nx) nr=ny;
1631 else nr=nx;
1632 for (i=0;i<nr;i++)
1633 z->w[i]=x->w[i]^y->w[i];
1634 for (i=nr;i<nz;i++)
1635 z->w[i]=0;
1636 z->len=nr;
1637 }
1638
1639 #endif
1640
copy(flash x,flash y)1641 void copy(flash x,flash y)
1642 { /* copy x to y: y=x */
1643 int i,nx,ny;
1644 mr_small *gx,*gy;
1645 if (x==y || y==NULL) return;
1646
1647 if (x==NULL)
1648 {
1649 zero(y);
1650 return;
1651 }
1652
1653 #ifdef MR_FLASH
1654 ny=mr_lent(y);
1655 nx=mr_lent(x);
1656 #else
1657 ny=(y->len&(MR_OBITS));
1658 nx=(x->len&(MR_OBITS));
1659 #endif
1660
1661 gx=x->w;
1662 gy=y->w;
1663
1664 for (i=nx;i<ny;i++)
1665 gy[i]=0;
1666 for (i=0;i<nx;i++)
1667 gy[i]=gx[i];
1668 y->len=x->len;
1669
1670 }
1671
negify(flash x,flash y)1672 void negify(flash x,flash y)
1673 { /* negate a big/flash variable: y=-x */
1674 copy(x,y);
1675 if (y->len!=0) y->len^=MR_MSBIT;
1676 }
1677
absol(flash x,flash y)1678 void absol(flash x,flash y)
1679 { /* y=abs(x) */
1680 copy(x,y);
1681 y->len&=MR_OBITS;
1682 }
1683
mr_notint(flash x)1684 BOOL mr_notint(flash x)
1685 { /* returns TRUE if x is Flash */
1686 #ifdef MR_FLASH
1687 if ((((x->len&(MR_OBITS))>>(MR_BTS))&(MR_MSK))!=0) return TRUE;
1688 #endif
1689 return FALSE;
1690 }
1691
mr_shift(_MIPD_ big x,int n,big w)1692 void mr_shift(_MIPD_ big x,int n,big w)
1693 { /* set w=x.(mr_base^n) by shifting */
1694 mr_lentype s;
1695 int i,bl;
1696 mr_small *gw=w->w;
1697 #ifdef MR_OS_THREADS
1698 miracl *mr_mip=get_mip();
1699 #endif
1700 if (mr_mip->ERNUM) return;
1701 copy(x,w);
1702 if (w->len==0 || n==0) return;
1703 MR_IN(33)
1704
1705 if (mr_notint(w)) mr_berror(_MIPP_ MR_ERR_INT_OP);
1706 s=(w->len&(MR_MSBIT));
1707 bl=(int)(w->len&(MR_OBITS))+n;
1708 if (bl<=0)
1709 {
1710 zero(w);
1711 MR_OUT
1712 return;
1713 }
1714 if (bl>mr_mip->nib && mr_mip->check) mr_berror(_MIPP_ MR_ERR_OVERFLOW);
1715 if (mr_mip->ERNUM)
1716 {
1717 MR_OUT
1718 return;
1719 }
1720 if (n>0)
1721 {
1722 for (i=bl-1;i>=n;i--)
1723 gw[i]=gw[i-n];
1724 for (i=0;i<n;i++)
1725 gw[i]=0;
1726 }
1727 else
1728 {
1729 n=(-n);
1730 for (i=0;i<bl;i++)
1731 gw[i]=gw[i+n];
1732 for (i=0;i<n;i++)
1733 gw[bl+i]=0;
1734 }
1735 w->len=(bl|s);
1736 MR_OUT
1737 }
1738
size(big x)1739 int size(big x)
1740 { /* get size of big number; convert to *
1741 * integer - if possible */
1742 int n,m;
1743 mr_lentype s;
1744 if (x==NULL) return 0;
1745 s=(x->len&MR_MSBIT);
1746 m=(int)(x->len&MR_OBITS);
1747 if (m==0) return 0;
1748 if (m==1 && x->w[0]<(mr_small)MR_TOOBIG) n=(int)x->w[0];
1749 else n=MR_TOOBIG;
1750 if (s==MR_MSBIT) return (-n);
1751 return n;
1752 }
1753
mr_compare(big x,big y)1754 int mr_compare(big x,big y)
1755 { /* compare x and y: =1 if x>y =-1 if x<y *
1756 * =0 if x=y */
1757 int m,n,sig;
1758 mr_lentype sx,sy;
1759 if (x==y) return 0;
1760 sx=(x->len&MR_MSBIT);
1761 sy=(y->len&MR_MSBIT);
1762 if (sx==0) sig=PLUS;
1763 else sig=MINUS;
1764 if (sx!=sy) return sig;
1765 m=(int)(x->len&MR_OBITS);
1766 n=(int)(y->len&MR_OBITS);
1767 if (m>n) return sig;
1768 if (m<n) return -sig;
1769 while (m>0)
1770 { /* check digit by digit */
1771 m--;
1772 if (x->w[m]>y->w[m]) return sig;
1773 if (x->w[m]<y->w[m]) return -sig;
1774 }
1775 return 0;
1776 }
1777
1778 #ifdef MR_FLASH
1779
fpack(_MIPD_ big n,big d,flash x)1780 void fpack(_MIPD_ big n,big d,flash x)
1781 { /* create floating-slash number x=n/d from *
1782 * big integer numerator and denominator */
1783 mr_lentype s;
1784 int i,ld,ln;
1785 #ifdef MR_OS_THREADS
1786 miracl *mr_mip=get_mip();
1787 #endif
1788 if (mr_mip->ERNUM) return;
1789
1790 MR_IN(31)
1791
1792 ld=(int)(d->len&MR_OBITS);
1793 if (ld==0) mr_berror(_MIPP_ MR_ERR_FLASH_OVERFLOW);
1794 if (ld==1 && d->w[0]==1) ld=0;
1795 if (x==d) mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
1796 if (mr_notint(n) || mr_notint(d)) mr_berror(_MIPP_ MR_ERR_INT_OP);
1797 s=(n->len&MR_MSBIT);
1798 ln=(int)(n->len&MR_OBITS);
1799 if (ln==1 && n->w[0]==1) ln=0;
1800 if ((ld+ln>mr_mip->nib) && (mr_mip->check || ld+ln>2*mr_mip->nib))
1801 mr_berror(_MIPP_ MR_ERR_FLASH_OVERFLOW);
1802 if (mr_mip->ERNUM)
1803 {
1804 MR_OUT
1805 return;
1806 }
1807 copy(n,x);
1808 if (n->len==0)
1809 {
1810 MR_OUT
1811 return;
1812 }
1813 s^=(d->len&MR_MSBIT);
1814 if (ld==0)
1815 {
1816 if (x->len!=0) x->len|=s;
1817 MR_OUT
1818 return;
1819 }
1820 for (i=0;i<ld;i++)
1821 x->w[ln+i]=d->w[i];
1822 x->len=(s|(ln+((mr_lentype)ld<<MR_BTS)));
1823 MR_OUT
1824 }
1825
numer(_MIPD_ flash x,big y)1826 void numer(_MIPD_ flash x,big y)
1827 { /* extract numerator of x */
1828 int i,ln,ld;
1829 mr_lentype s,ly;
1830 #ifdef MR_OS_THREADS
1831 miracl *mr_mip=get_mip();
1832 #endif
1833 if (mr_mip->ERNUM) return;
1834 if (mr_notint(x))
1835 {
1836 s=(x->len&MR_MSBIT);
1837 ly=(x->len&MR_OBITS);
1838 ln=(int)(ly&MR_MSK);
1839 if (ln==0)
1840 {
1841 if(s==MR_MSBIT) convert(_MIPP_ (-1),y);
1842 else convert(_MIPP_ 1,y);
1843 return;
1844 }
1845 ld=(int)((ly>>MR_BTS)&MR_MSK);
1846 if (x!=y)
1847 {
1848 for (i=0;i<ln;i++) y->w[i]=x->w[i];
1849 for (i=ln;i<mr_lent(y);i++) y->w[i]=0;
1850 }
1851 else for (i=0;i<ld;i++) y->w[ln+i]=0;
1852 y->len=(ln|s);
1853 }
1854 else copy(x,y);
1855 }
1856
denom(_MIPD_ flash x,big y)1857 void denom(_MIPD_ flash x,big y)
1858 { /* extract denominator of x */
1859 int i,ln,ld;
1860 mr_lentype ly;
1861 #ifdef MR_OS_THREADS
1862 miracl *mr_mip=get_mip();
1863 #endif
1864 if (mr_mip->ERNUM) return;
1865 if (!mr_notint(x))
1866 {
1867 convert(_MIPP_ 1,y);
1868 return;
1869 }
1870 ly=(x->len&MR_OBITS);
1871 ln=(int)(ly&MR_MSK);
1872 ld=(int)((ly>>MR_BTS)&MR_MSK);
1873 for (i=0;i<ld;i++)
1874 y->w[i]=x->w[ln+i];
1875 if (x==y) for (i=0;i<ln;i++) y->w[ld+i]=0;
1876 else for (i=ld;i<mr_lent(y);i++) y->w[i]=0;
1877 y->len=ld;
1878 }
1879
1880 #endif
1881
igcd(unsigned int x,unsigned int y)1882 unsigned int igcd(unsigned int x,unsigned int y)
1883 { /* integer GCD, returns GCD of x and y */
1884 unsigned int r;
1885 if (y==0) return x;
1886 while ((r=x%y)!=0)
1887 x=y,y=r;
1888 return y;
1889 }
1890
lgcd(unsigned long x,unsigned long y)1891 unsigned long lgcd(unsigned long x,unsigned long y)
1892 { /* long GCD, returns GCD of x and y */
1893 unsigned long r;
1894 if (y==0) return x;
1895 while ((r=x%y)!=0)
1896 x=y,y=r;
1897 return y;
1898 }
1899
isqrt(unsigned int num,unsigned int guess)1900 unsigned int isqrt(unsigned int num,unsigned int guess)
1901 { /* square root of an integer */
1902 unsigned int sqr;
1903 unsigned int oldguess=guess;
1904 if (num==0) return 0;
1905 if (num<4) return 1;
1906
1907 for (;;)
1908 { /* Newtons iteration */
1909 /* sqr=guess+(((num/guess)-guess)/2); */
1910 sqr=((num/guess)+guess)/2;
1911 if (sqr==guess || sqr==oldguess)
1912 {
1913 if (sqr*sqr>num) sqr--;
1914 return sqr;
1915 }
1916 oldguess=guess;
1917 guess=sqr;
1918 }
1919 }
1920
mr_lsqrt(unsigned long num,unsigned long guess)1921 unsigned long mr_lsqrt(unsigned long num,unsigned long guess)
1922 { /* square root of a long */
1923 unsigned long sqr;
1924 unsigned long oldguess=guess;
1925 if (num==0) return 0;
1926 if (num<4) return 1;
1927
1928 for (;;)
1929 { /* Newtons iteration */
1930 /* sqr=guess+(((num/guess)-guess)/2); */
1931 sqr=((num/guess)+guess)/2;
1932 if (sqr==guess || sqr==oldguess)
1933 {
1934 if (sqr*sqr>num) sqr--;
1935 return sqr;
1936 }
1937 oldguess=guess;
1938 guess=sqr;
1939 }
1940 }
1941
sgcd(mr_small x,mr_small y)1942 mr_small sgcd(mr_small x,mr_small y)
1943 { /* integer GCD, returns GCD of x and y */
1944 mr_small r;
1945 #ifdef MR_FP
1946 mr_small dres;
1947 #endif
1948 if (y==(mr_small)0) return x;
1949 while ((r=MR_REMAIN(x,y))!=(mr_small)0)
1950 x=y,y=r;
1951 return y;
1952 }
1953
1954 /* routines to support sliding-windows exponentiation *
1955 * in various contexts */
1956
mr_testbit(_MIPD_ big x,int n)1957 int mr_testbit(_MIPD_ big x,int n)
1958 { /* return value of n-th bit of big */
1959 #ifdef MR_OS_THREADS
1960 miracl *mr_mip=get_mip();
1961 #endif
1962 #ifdef MR_FP
1963 mr_small m,a,dres;
1964 m=mr_shiftbits((mr_small)1,n%mr_mip->lg2b);
1965
1966 a=x->w[n/mr_mip->lg2b];
1967
1968 a=MR_DIV(a,m);
1969
1970 if ((MR_DIV(a,2.0)*2.0) != a) return 1;
1971 #else
1972 if ((x->w[n/mr_mip->lg2b] & ((mr_small)1<<(n%mr_mip->lg2b))) >0) return 1;
1973 #endif
1974 return 0;
1975 }
1976
mr_addbit(_MIPD_ big x,int n)1977 void mr_addbit(_MIPD_ big x,int n)
1978 { /* add 2^n to positive x - where you know that bit is zero. Use with care! */
1979 #ifdef MR_OS_THREADS
1980 miracl *mr_mip=get_mip();
1981 #endif
1982 mr_lentype m=n/mr_mip->lg2b;
1983 x->w[m]+=mr_shiftbits((mr_small)1,n%mr_mip->lg2b);
1984 if (x->len<m+1) x->len=m+1;
1985 }
1986
recode(_MIPD_ big e,int t,int w,int i)1987 int recode(_MIPD_ big e,int t,int w,int i)
1988 { /* recode exponent for Comb method */
1989 #ifdef MR_OS_THREADS
1990 miracl *mr_mip=get_mip();
1991 #endif
1992 int j,r;
1993 r=0;
1994 for (j=w-1;j>=0;j--)
1995 {
1996 r<<=1;
1997 r|=mr_testbit(_MIPP_ e,i+j*t);
1998 }
1999 return r;
2000 }
2001
mr_window(_MIPD_ big x,int i,int * nbs,int * nzs,int window_size)2002 int mr_window(_MIPD_ big x,int i,int *nbs,int * nzs,int window_size)
2003 { /* returns sliding window value, max. of 5 bits, *
2004 * (Note from version 5.23 this can be changed by *
2005 * setting parameter window_size. This can be *
2006 * a useful space-saver) starting at i-th bit of big x. *
2007 * nbs is number of bits processed, nzs is the number of *
2008 * additional trailing zeros detected. Returns valid bit *
2009 * pattern 1x..x1 with no two adjacent 0's. So 10101 *
2010 * will return 21 with nbs=5, nzs=0. 11001 will return 3,*
2011 * with nbs=2, nzs=2, having stopped after the first 11..*/
2012 #ifdef MR_OS_THREADS
2013 miracl *mr_mip=get_mip();
2014 #endif
2015 int j,r,w;
2016 w=window_size;
2017
2018 /* check for leading 0 bit */
2019
2020 *nbs=1;
2021 *nzs=0;
2022 if (!mr_testbit(_MIPP_ x,i)) return 0;
2023
2024 /* adjust window size if not enough bits left */
2025
2026 if (i-w+1<0) w=i+1;
2027
2028 r=1;
2029 for (j=i-1;j>i-w;j--)
2030 { /* accumulate bits. Abort if two 0's in a row */
2031 (*nbs)++;
2032 r*=2;
2033 if (mr_testbit(_MIPP_ x,j)) r+=1;
2034 if (r%4==0)
2035 { /* oops - too many zeros - shorten window */
2036 r/=4;
2037 *nbs-=2;
2038 *nzs=2;
2039 break;
2040 }
2041 }
2042 if (r%2==0)
2043 { /* remove trailing 0 */
2044 r/=2;
2045 *nzs=1;
2046 (*nbs)--;
2047 }
2048 return r;
2049 }
2050
mr_window2(_MIPD_ big x,big y,int i,int * nbs,int * nzs)2051 int mr_window2(_MIPD_ big x,big y,int i,int *nbs,int *nzs)
2052 { /* two bit window for double exponentiation */
2053 int r,w;
2054 BOOL a,b,c,d;
2055 w=2;
2056 *nbs=1;
2057 *nzs=0;
2058
2059 /* check for two leading 0's */
2060 a=mr_testbit(_MIPP_ x,i); b=mr_testbit(_MIPP_ y,i);
2061
2062 if (!a && !b) return 0;
2063 if (i<1) w=1;
2064
2065 if (a)
2066 {
2067 if (b) r=3;
2068 else r=2;
2069 }
2070 else r=1;
2071 if (w==1) return r;
2072
2073 c=mr_testbit(_MIPP_ x,i-1); d=mr_testbit(_MIPP_ y,i-1);
2074
2075 if (!c && !d)
2076 {
2077 *nzs=1;
2078 return r;
2079 }
2080
2081 *nbs=2;
2082 r*=4;
2083 if (c)
2084 {
2085 if (d) r+=3;
2086 else r+=2;
2087 }
2088 else r+=1;
2089 return r;
2090 }
2091
mr_naf_window(_MIPD_ big x,big x3,int i,int * nbs,int * nzs,int store)2092 int mr_naf_window(_MIPD_ big x,big x3,int i,int *nbs,int *nzs,int store)
2093 { /* returns sliding window value, using fractional windows *
2094 * where "store" precomputed values are precalulated and *
2095 * stored. Scanning starts at the i-th bit of x. nbs is *
2096 * the number of bits processed. nzs is number of *
2097 * additional trailing zeros detected. x and x3 (which is *
2098 * 3*x) are combined to produce the NAF (non-adjacent *
2099 * form). So if x=11011(27) and x3 is 1010001, the LSB is *
2100 * ignored and the value 100T0T (32-4-1=27) processed, *
2101 * where T is -1. Note x.P = (3x-x)/2.P. This value will *
2102 * return +7, with nbs=4 and nzs=1, having stopped after *
2103 * the first 4 bits. If it goes too far, it must backtrack *
2104 * Note in an NAF non-zero elements are never side by side, *
2105 * so 10T10T won't happen. NOTE: return value n zero or *
2106 * odd, -21 <= n <= +21 */
2107
2108 int nb,j,r,biggest;
2109
2110 /* get first bit */
2111 nb=mr_testbit(_MIPP_ x3,i)-mr_testbit(_MIPP_ x,i);
2112
2113 *nbs=1;
2114 *nzs=0;
2115 if (nb==0) return 0;
2116 if (i==0) return nb;
2117
2118 biggest=2*store-1;
2119
2120 if (nb>0) r=1;
2121 else r=(-1);
2122
2123 for (j=i-1;j>0;j--)
2124 {
2125 (*nbs)++;
2126 r*=2;
2127 nb=mr_testbit(_MIPP_ x3,j)-mr_testbit(_MIPP_ x,j);
2128 if (nb>0) r+=1;
2129 if (nb<0) r-=1;
2130 if (abs(r)>biggest) break;
2131 }
2132
2133 if (r%2!=0 && j!=0)
2134 { /* backtrack */
2135 if (nb>0) r=(r-1)/2;
2136 if (nb<0) r=(r+1)/2;
2137 (*nbs)--;
2138 }
2139
2140 while (r%2==0)
2141 { /* remove trailing zeros */
2142 r/=2;
2143 (*nzs)++;
2144 (*nbs)--;
2145 }
2146 return r;
2147 }
2148
2149 /* Some general purpose elliptic curve stuff */
2150
point_at_infinity(epoint * p)2151 BOOL point_at_infinity(epoint *p)
2152 {
2153 if (p==NULL) return FALSE;
2154 if (p->marker==MR_EPOINT_INFINITY) return TRUE;
2155 return FALSE;
2156 }
2157
2158 #ifndef MR_STATIC
2159
epoint_init(_MIPDO_)2160 epoint* epoint_init(_MIPDO_ )
2161 { /* initialise epoint to general point at infinity. */
2162 epoint *p;
2163 char *ptr;
2164
2165 #ifdef MR_OS_THREADS
2166 miracl *mr_mip=get_mip();
2167 #endif
2168 if (mr_mip->ERNUM) return NULL;
2169
2170 MR_IN(96)
2171
2172 /* Create space for whole structure in one heap access */
2173
2174 p=(epoint *)mr_alloc(_MIPP_ mr_esize(mr_mip->nib-1),1);
2175
2176 ptr=(char *)p+sizeof(epoint);
2177 p->X=mirvar_mem(_MIPP_ ptr,0);
2178 p->Y=mirvar_mem(_MIPP_ ptr,1);
2179 #ifndef MR_AFFINE_ONLY
2180 p->Z=mirvar_mem(_MIPP_ ptr,2);
2181 #endif
2182 p->marker=MR_EPOINT_INFINITY;
2183
2184 MR_OUT
2185
2186 return p;
2187 }
2188
2189 #endif
2190
epoint_init_mem_variable(_MIPD_ char * mem,int index,int sz)2191 epoint* epoint_init_mem_variable(_MIPD_ char *mem,int index,int sz)
2192 {
2193 epoint *p;
2194 char *ptr;
2195 int offset,r;
2196
2197 #ifdef MR_OS_THREADS
2198 miracl *mr_mip=get_mip();
2199 #endif
2200
2201 offset=0;
2202 r=(unsigned long)mem%MR_SL;
2203 if (r>0) offset=MR_SL-r;
2204
2205 #ifndef MR_AFFINE_ONLY
2206 if (mr_mip->coord==MR_AFFINE)
2207 p=(epoint *)&mem[offset+index*mr_esize_a(sz)];
2208 else
2209 #endif
2210 p=(epoint *)&mem[offset+index*mr_esize(sz)];
2211
2212 ptr=(char *)p+sizeof(epoint);
2213 p->X=mirvar_mem_variable(ptr,0,sz);
2214 p->Y=mirvar_mem_variable(ptr,1,sz);
2215 #ifndef MR_AFFINE_ONLY
2216 if (mr_mip->coord!=MR_AFFINE) p->Z=mirvar_mem_variable(ptr,2,sz);
2217 #endif
2218 p->marker=MR_EPOINT_INFINITY;
2219 return p;
2220 }
2221
epoint_init_mem(_MIPD_ char * mem,int index)2222 epoint* epoint_init_mem(_MIPD_ char *mem,int index)
2223 {
2224 #ifdef MR_OS_THREADS
2225 miracl *mr_mip=get_mip();
2226 #endif
2227 if (mr_mip->ERNUM) return NULL;
2228
2229 return epoint_init_mem_variable(_MIPP_ mem,index,mr_mip->nib-1);
2230 }
2231
2232 #ifndef MR_STATIC
2233
2234 /* allocate space for a number of epoints from the heap */
2235
ecp_memalloc(_MIPD_ int num)2236 void *ecp_memalloc(_MIPD_ int num)
2237 {
2238 #ifdef MR_OS_THREADS
2239 miracl *mr_mip=get_mip();
2240 #endif
2241
2242 #ifndef MR_AFFINE_ONLY
2243 if (mr_mip->coord==MR_AFFINE)
2244 return mr_alloc(_MIPP_ mr_ecp_reserve_a(num,mr_mip->nib-1),1);
2245 else
2246 #endif
2247 return mr_alloc(_MIPP_ mr_ecp_reserve(num,mr_mip->nib-1),1);
2248 }
2249
2250 #endif
2251
ecp_memkill(_MIPD_ char * mem,int num)2252 void ecp_memkill(_MIPD_ char *mem,int num)
2253 {
2254 #ifdef MR_OS_THREADS
2255 miracl *mr_mip=get_mip();
2256 #endif
2257
2258 if (mem==NULL) return;
2259
2260 #ifndef MR_AFFINE_ONLY
2261 if (mr_mip->coord==MR_AFFINE)
2262 memset(mem,0,mr_ecp_reserve_a(num,mr_mip->nib-1));
2263 else
2264 #endif
2265 memset(mem,0,mr_ecp_reserve(num,mr_mip->nib-1));
2266
2267
2268 #ifndef MR_STATIC
2269 mr_free(mem);
2270 #endif
2271 }
2272
2273 #ifndef MR_STATIC
2274
epoint_free(epoint * p)2275 void epoint_free(epoint *p)
2276 { /* clean up point */
2277
2278 if (p==NULL) return;
2279 zero(p->X);
2280 zero(p->Y);
2281 #ifndef MR_AFFINE_ONLY
2282 if (p->marker==MR_EPOINT_GENERAL) zero(p->Z);
2283 #endif
2284 mr_free(p);
2285 }
2286
2287 #endif
2288