1 /* C version of ake6mntt.cpp
2
3 Example for embedded implementation.
4
5 Should build immediately with standard mirdef.h file on a PC. For example using MS C
6
7 cl /O2 ake6mntt.c ms32.lib
8
9 To simulate performance on a PC of an 8-bit computer use
10
11 #define MR_LITTLE_ENDIAN
12 #define MIRACL 8
13 #define mr_utype char
14 #define MR_IBITS 32
15 #define MR_LBITS 32
16 #define mr_unsign32 unsigned int
17 #define mr_dltype short
18 #define MR_STATIC 20
19 #define MR_ALWAYS_BINARY
20 #define MR_STRIPPED_DOWN
21 #define MR_GENERIC_MT
22 #define MAXBASE ((mr_small)1<<(MIRACL-1))
23 #define MR_COMBA 20
24 #define MR_NOASM
25 #define MR_BITSINCHAR 8
26 #define MR_NOSUPPORT_COMPRESSION
27
28 rem Compile MIRACL modules
29 mex 20 c mrcomba
30 cl /c /O2 /W3 mrzzn3.c
31 cl /c /O2 /W3 mrcore.c
32 cl /c /O2 /W3 mrarth0.c
33 cl /c /O2 /W3 mrarth1.c
34 cl /c /O2 /W3 mrarth2.c
35 cl /c /O2 /W3 mrxgcd.c
36 cl /c /O2 /W3 mrbits.c
37 cl /c /O2 /W3 mrmonty.c
38 cl /c /O2 /W3 mrcurve.c
39 cl /c /O2 /W3 mrcomba.c
40 cl /c /O2 /W3 mrio1.c
41 cl /c /O2 /W3 mrpower.c
42
43
44 rem
45 rem Create library 'miracl.lib'
46 del miracl.lib
47
48
49 lib /OUT:miracl.lib mrxgcd.obj mrarth2.obj mrio1.obj mrcomba.obj
50 lib /OUT:miracl.lib miracl.lib mrmonty.obj mrarth1.obj mrarth0.obj mrcore.obj
51 lib /OUT:miracl.lib miracl.lib mrcurve.obj mrbits.obj mrzzn3.obj mrpower.obj
52
53 del mr*.obj
54
55 cl /O2 ake6mntt.c miracl.lib
56
57 For Atmel AVR (atmega128) use
58
59 #define MR_LITTLE_ENDIAN
60 #define MIRACL 8
61 #define mr_utype char
62 #define MR_IBITS 16
63 #define MR_LBITS 32
64 #define mr_unsign32 unsigned long
65 #define mr_dltype int
66 #define mr_qltype long
67 #define MR_STATIC 20
68 #define MR_ALWAYS_BINARY
69 #define MR_STRIPPED_DOWN
70 #define MR_GENERIC_MT
71 #define MAXBASE ((mr_small)1<<(MIRACL-1))
72 #define MR_COMBA 20
73 #define MR_NOASM
74 #define MR_BITSINCHAR 8
75 #define MR_NO_STANDARD_IO
76 #define MR_NO_FILE_IO
77 #define MR_NOSUPPORT_COMPRESSION
78 #define MR_AVR
79
80 This last line must be added manually - config.c will not do it automatically
81
82 and execute
83
84 mex 20 avr4 mrcomba
85
86 On an ARM use a header like
87
88 #define MR_LITTLE_ENDIAN
89 #define MIRACL 32
90 #define mr_utype int
91 #define MR_IBITS 32
92 #define MR_LBITS 32
93 #define mr_unsign32 unsigned int
94 #define mr_dltype long long
95 #define MR_STATIC 5
96 #define MR_ALWAYS_BINARY
97 #define MR_STRIPPED_DOWN
98 #define MR_GENERIC_MT
99 #define MAXBASE ((mr_small)1<<(MIRACL-1))
100 #define MR_COMBA 5
101 #define MR_BITSINCHAR 8
102 #define MR_NOSUPPORT_COMPRESSION
103
104 and possible
105
106 #define MR_NO_STANDARD_IO
107 #define MR_NO_FILE_IO
108
109 and execute
110
111 mex 5 arm mrcomba
112
113 */
114
115 #include <stdio.h>
116 #include <stdlib.h>
117 #include "miracl.h"
118
119 #ifdef MR_COUNT_OPS
120
121 int fpc=0;
122 int fpa=0;
123 int fpx=0;
124
125 #endif
126
127 /* Fix the contents of mnt.ecs */
128
129 #if MIRACL==64
130
131 NOT SUPPORTED
132
133 /* Note: n-residue formats are not the same for different word lengths ...*/
134
135 #endif
136
137 #if MIRACL==32
138
139 #define WORDS 5
140 #define NPW 8 /* Nibbles per Word */
141 #define ROMSZ 25
142
143 static const mr_small romp[]={
144 0x44626303,0xBB9F14CF,0x749D0195,0xA2E3DDB1,0x7DDCA613,
145 0x7D8CFD4E,0xF828D365,0xF99273D0,0x7864D1F1,0x21C3F3AC,
146 0x17D369B7,0xF44414FD,0xBA4E12DE,0xD171EED8,0x3EEE5309,
147 0xB23BE531,0x1D6BFF48,0xE93BBADB,0x45C7BB62,0xFBB94C27,
148 0xA92DB540,0x24C6F8B9,0x5913FCF1,0x9EA2B8F4,0x3AA6D7A2
149 };
150
151 /* Points - in n-residue form */
152
153 #define PROMSZ 40
154
155 static const mr_small Prom[]={
156 0xB6EF1A16,0x074251AD,0xF062F710,0xD679E3D1,0x2EEEF8B2,
157 0x8DF7059B,0x3882F3BF,0x92A4F4AA,0xE9D835E6,0x265FB32,
158 0x0,0x0,0x0,0x0,0x0,
159 0x0,0x0,0x0,0x0,0x0,
160 0x0C05C29F,0xF8512956,0xBD6A3234,0xA3C6C536,0x758EE3E4,
161 0x3282E036,0xCAC39E95,0x775F3F11,0x1E4FED9B,0x311F2F09,
162 0x5EBDAB43,0xD4EC58B7,0x406EDA4D,0x294137C6,0x57BD4583,
163 0x1B936DC6,0xD4A63AB3,0x05026F3B,0x1D4FA7B1,0x5CC7D4CC
164 };
165
166 #endif
167
168 #if MIRACL==8
169
170 #define WORDS 20
171 #define NPW 2 /* Nibbles per Word */
172 #define ROMSZ 100
173
174 #ifdef MR_AVR
175 __attribute__((__progmem__))
176 #endif
177 static const mr_small romp[]={
178 0x3,0x63,0x62,0x44,0xcf,0x14,0x9f,0xbb,0x95,0x1,0x9d,0x74,0xb1,0xdd,0xe3,0xa2,0x13,0xa6,0xdc,0x7d,
179 0x4e,0xfd,0x8c,0x7d,0x65,0xd3,0x28,0xf8,0xd0,0x73,0x92,0xf9,0xf1,0xd1,0x64,0x78,0xac,0xf3,0xc3,0x21,
180 0xb7,0x69,0xd3,0x17,0xfd,0x14,0x44,0xf4,0xde,0x12,0x4e,0xba,0xd8,0xee,0x71,0xd1,0x9,0x53,0xee,0x3e,
181 0x31,0xe5,0x3b,0xb2,0x48,0xff,0x6b,0x1d,0xdb,0xba,0x3b,0xe9,0x62,0xbb,0xc7,0x45,0x27,0x4c,0xb9,0xfb,
182 0x40,0xb5,0x2d,0xa9,0xb9,0xf8,0xc6,0x24,0xf1,0xfc,0x13,0x59,0xf4,0xb8,0xa2,0x9e,0xa2,0xd7,0xa6,0x3a};
183
184 #define PROMSZ 160
185
186 #ifdef MR_AVR
187 __attribute__((__progmem__))
188 #endif
189 static const mr_small Prom[]={
190 0x16,0x1a,0xef,0xb6,0xad,0x51,0x42,0x7,0x10,0xf7,0x62,0xf0,0xd1,0xe3,0x79,0xd6,0xb2,0xf8,0xee,0x2e,
191 0x9b,0x5,0xf7,0x8d,0xbf,0xf3,0x82,0x38,0xaa,0xf4,0xa4,0x92,0xe6,0x35,0xd8,0xe9,0x32,0xfb,0x65,0x2,
192 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
193 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
194 0x9f,0xc2,0x5,0xc,0x56,0x29,0x51,0xf8,0x34,0x32,0x6a,0xbd,0x36,0xc5,0xc6,0xa3,0xe4,0xe3,0x8e,0x75,
195 0x36,0xe0,0x82,0x32,0x95,0x9e,0xc3,0xca,0x11,0x3f,0x5f,0x77,0x9b,0xed,0x4f,0x1e,0x9,0x2f,0x1f,0x31,
196 0x43,0xab,0xbd,0x5e,0xb7,0x58,0xec,0xd4,0x4d,0xda,0x6e,0x40,0xc6,0x37,0x41,0x29,0x83,0x45,0xbd,0x57,
197 0xc6,0x6d,0x93,0x1b,0xb3,0x3a,0xa6,0xd4,0x3b,0x6f,0x2,0x5,0xb1,0xa7,0x4f,0x1d,0xcc,0xd4,0xc7,0x5c};
198
199 #endif
200
201 #define CNR 2
202 #define CF 2
203
204 /* Fp6 support functions */
205
206 typedef struct
207 {
208 zzn3 x;
209 zzn3 y;
210 BOOL unitary;
211 } zzn6;
212
213 #ifndef MR_NO_STANDARD_IO
zzn3_out(_MIPD_ char * p,zzn3 * x)214 void zzn3_out(_MIPD_ char *p,zzn3 *x)
215 {
216 printf(p); printf("\n");
217 redc(_MIPP_ x->a,x->a);
218 redc(_MIPP_ x->b,x->b);
219 redc(_MIPP_ x->c,x->c);
220 otnum(_MIPP_ x->a,stdout);
221 otnum(_MIPP_ x->b,stdout);
222 otnum(_MIPP_ x->c,stdout);
223 nres(_MIPP_ x->a,x->a);
224 nres(_MIPP_ x->b,x->b);
225 nres(_MIPP_ x->c,x->c);
226 }
227 #endif
228
zzn6_copy(zzn6 * u,zzn6 * w)229 void zzn6_copy(zzn6 *u,zzn6 *w)
230 {
231 if (u==w) return;
232 zzn3_copy(&(u->x),&(w->x));
233 zzn3_copy(&(u->y),&(w->y));
234 w->unitary=u->unitary;
235 }
236
zzn6_from_int(_MIPD_ int i,zzn6 * w)237 void zzn6_from_int(_MIPD_ int i,zzn6 *w)
238 {
239 zzn3_from_int(_MIPP_ i,&(w->x));
240 zzn3_zero(&(w->y));
241 if (i==1) w->unitary=TRUE;
242 else w->unitary=FALSE;
243 }
244
zzn6_conj(_MIPD_ zzn6 * u,zzn6 * w)245 void zzn6_conj(_MIPD_ zzn6 *u,zzn6 *w)
246 {
247 zzn6_copy(u,w);
248 zzn3_negate(_MIPP_ &(w->y),&(w->y));
249 }
250
zzn6_mul(_MIPD_ zzn6 * u,zzn6 * v,zzn6 * w)251 void zzn6_mul(_MIPD_ zzn6 *u,zzn6 *v,zzn6 *w)
252 {
253 zzn3 t1,t2,t3;
254 t1.a=mr_mip->w7;
255 t1.b=mr_mip->w8;
256 t1.c=mr_mip->w9;
257 t2.a=mr_mip->w10;
258 t2.b=mr_mip->w11;
259 t2.c=mr_mip->w12;
260 t3.a=mr_mip->w13;
261 t3.b=mr_mip->w14;
262 t3.c=mr_mip->w15;
263 if (u==v)
264 {
265 /* See Stam & Lenstra, "Efficient subgroup exponentiation in Quadratic .. Extensions", CHES 2002 */
266 if (u->unitary)
267 { /* this is a lot faster.. */
268 zzn6_copy(u,w);
269 zzn3_mul(_MIPP_ &(w->y),&(w->y),&t1);
270 zzn3_add(_MIPP_ &(w->y),&(w->x),&(w->y));
271 zzn3_mul(_MIPP_ &(w->y),&(w->y),&(w->y));
272 zzn3_sub(_MIPP_ &(w->y),&t1,&(w->y));
273 zzn3_timesi(_MIPP_ &t1);
274 zzn3_copy(&t1,&(w->x));
275 zzn3_sub(_MIPP_ &(w->y),&(w->x),&(w->y));
276 zzn3_add(_MIPP_ &(w->x),&(w->x),&(w->x));
277 zzn3_sadd(_MIPP_ &(w->x),mr_mip->one,&(w->x));
278 zzn3_ssub(_MIPP_ &(w->y),mr_mip->one,&(w->y));
279 }
280 else
281 {
282 zzn6_copy(u,w);
283 zzn3_add(_MIPP_ &(w->x),&(w->y),&t1);
284 zzn3_copy(&(w->y),&t3);
285 zzn3_timesi(_MIPP_ &t3);
286 zzn3_add(_MIPP_ &(w->x),&t3,&t2);
287 zzn3_mul(_MIPP_ &t1,&t2,&t1);
288 zzn3_mul(_MIPP_ &(w->y),&(w->x),&(w->y));
289 zzn3_sub(_MIPP_ &t1,&(w->y),&t1);
290 zzn3_copy(&(w->y),&t3);
291 zzn3_timesi(_MIPP_ &t3);
292 zzn3_sub(_MIPP_ &t1,&t3,&t1);
293 zzn3_add(_MIPP_ &(w->y),&(w->y),&(w->y));
294 zzn3_copy(&t1,&(w->x));
295 }
296 }
297 else
298 {
299 zzn3_mul(_MIPP_ &(u->x),&(v->x),&t1);
300 zzn3_mul(_MIPP_ &(u->y),&(v->y),&t2);
301 zzn3_add(_MIPP_ &(v->x),&(v->y),&t3);
302 zzn3_add(_MIPP_ &(u->x),&(u->y),&(w->y));
303 zzn3_mul(_MIPP_ &(w->y),&t3,&(w->y));
304 zzn3_sub(_MIPP_ &(w->y),&t1,&(w->y));
305 zzn3_sub(_MIPP_ &(w->y),&t2,&(w->y));
306 zzn3_copy(&t1,&(w->x));
307 zzn3_timesi(_MIPP_ &t2);
308 zzn3_add(_MIPP_ &(w->x),&t2,&(w->x));
309 if (u->unitary && v->unitary) w->unitary=TRUE;
310 else w->unitary=FALSE;
311 }
312 }
313
314 /* zzn6 powering of unitary elements */
315
zzn6_powu(_MIPD_ zzn6 * x,big k,zzn6 * u)316 void zzn6_powu(_MIPD_ zzn6 *x,big k,zzn6 *u)
317 {
318 zzn6 t[5],u2;
319 big k3;
320 int i,j,n,nb,nbw,nzs;
321 #ifndef MR_STATIC
322 char *mem=memalloc(_MIPP_ 37);
323 #else
324 char mem[MR_BIG_RESERVE(37)];
325 memset(mem,0,MR_BIG_RESERVE(37));
326 #endif
327
328 if (size(k)==0)
329 {
330 zzn6_from_int(_MIPP_ 1,u);
331 return;
332 }
333 zzn6_copy(x,u);
334 if (size(k)==1) return;
335
336 for (j=i=0;i<5;i++)
337 {
338 t[i].x.a=mirvar_mem(_MIPP_ mem,j++);
339 t[i].x.b=mirvar_mem(_MIPP_ mem,j++);
340 t[i].x.c=mirvar_mem(_MIPP_ mem,j++);
341 t[i].y.a=mirvar_mem(_MIPP_ mem,j++);
342 t[i].y.b=mirvar_mem(_MIPP_ mem,j++);
343 t[i].y.c=mirvar_mem(_MIPP_ mem,j++);
344 t[i].unitary=FALSE;
345 }
346 u2.x.a=mirvar_mem(_MIPP_ mem,j++);
347 u2.x.b=mirvar_mem(_MIPP_ mem,j++);
348 u2.x.c=mirvar_mem(_MIPP_ mem,j++);
349 u2.y.a=mirvar_mem(_MIPP_ mem,j++);
350 u2.y.b=mirvar_mem(_MIPP_ mem,j++);
351 u2.y.c=mirvar_mem(_MIPP_ mem,j++);
352 u2.unitary=FALSE;
353 k3=mirvar_mem(_MIPP_ mem,j);
354
355 premult(_MIPP_ k,3,k3);
356 zzn6_mul(_MIPP_ u,u,&u2);
357 zzn6_copy(u,&t[0]);
358
359 for (i=1;i<=4;i++)
360 zzn6_mul(_MIPP_ &u2,&t[i-1],&t[i]);
361
362 nb=logb2(_MIPP_ k3);
363
364 for (i=nb-2;i>=1;)
365 {
366 n=mr_naf_window(_MIPP_ k,k3,i,&nbw,&nzs,5);
367
368 for (j=0;j<nbw;j++) zzn6_mul(_MIPP_ u,u,u);
369 if (n>0) zzn6_mul(_MIPP_ u,&t[n/2],u);
370 if (n<0)
371 {
372 zzn6_conj(_MIPP_ &t[-n/2],&u2);
373 zzn6_mul(_MIPP_ u,&u2,u);
374 }
375 i-=nbw;
376 if (nzs)
377 {
378 for (j=0;j<nzs;j++) zzn6_mul(_MIPP_ u,u,u);
379 i-=nzs;
380 }
381 }
382
383 #ifndef MR_STATIC
384 memkill(_MIPP_ mem,37);
385 #else
386 memset(mem,0,MR_BIG_RESERVE(37));
387 #endif
388 }
389
390 /* Lucas-style ladder exponentiation */
391
zzn3_powl(_MIPD_ zzn3 * x,big e,zzn3 * w)392 void zzn3_powl(_MIPD_ zzn3 *x,big e,zzn3 *w)
393 {
394 int i,s;
395 zzn3 t1,t3,t4;
396 t1.a=mr_mip->w7;
397 t1.b=mr_mip->w8;
398 t1.c=mr_mip->w9;
399 t3.a=mr_mip->w10;
400 t3.b=mr_mip->w11;
401 t3.c=mr_mip->w12;
402 t4.a=mr_mip->w13;
403 t4.b=mr_mip->w14;
404 t4.c=mr_mip->w15;
405
406 zzn3_from_int(_MIPP_ 1,&t1);
407
408 s=size(e);
409 if (s==0)
410 {
411 zzn3_copy(&t1,w);
412 return;
413 }
414 zzn3_copy(x,w);
415 if (s==1 || s==(-1)) return;
416
417 i=logb2(_MIPP_ e)-1;
418
419 zzn3_copy(w,&t3);
420 zzn3_mul(_MIPP_ w,w,&t4);
421 zzn3_add(_MIPP_ &t4,&t4,&t4);
422 zzn3_sub(_MIPP_ &t4,&t1,&t4);
423
424 while (i--)
425 {
426 if (mr_testbit(_MIPP_ e,i))
427 {
428 zzn3_mul(_MIPP_ &t3,&t4,&t3);
429 zzn3_add(_MIPP_ &t3,&t3,&t3);
430 zzn3_sub(_MIPP_ &t3,w,&t3);
431 zzn3_mul(_MIPP_ &t4,&t4,&t4);
432 zzn3_add(_MIPP_ &t4,&t4,&t4);
433 zzn3_sub(_MIPP_ &t4,&t1,&t4);
434 }
435 else
436 {
437 zzn3_mul(_MIPP_ &t4,&t3,&t4);
438 zzn3_add(_MIPP_ &t4,&t4,&t4);
439 zzn3_sub(_MIPP_ &t4,w,&t4);
440 zzn3_mul(_MIPP_ &t3,&t3,&t3);
441 zzn3_add(_MIPP_ &t3,&t3,&t3);
442 zzn3_sub(_MIPP_ &t3,&t1,&t3);
443 }
444 }
445 zzn3_copy(&t3,w);
446 }
447
zzn6_powq(_MIPD_ zzn6 * w)448 void zzn6_powq(_MIPD_ zzn6 *w)
449 {
450 zzn3_powq(_MIPP_ &(w->x),&(w->x));
451 zzn3_powq(_MIPP_ &(w->y),&(w->y));
452 zzn3_smul(_MIPP_ &(w->y),mr_mip->sru,&(w->y));
453 }
454
zzn6_inv(_MIPD_ zzn6 * w)455 void zzn6_inv(_MIPD_ zzn6 *w)
456 {
457 zzn3 t1,t2;
458 if (w->unitary)
459 {
460 zzn6_conj(_MIPP_ w,w);
461 return;
462 }
463 t1.a=mr_mip->w7;
464 t1.b=mr_mip->w8;
465 t1.c=mr_mip->w9;
466 t2.a=mr_mip->w10;
467 t2.b=mr_mip->w11;
468 t2.c=mr_mip->w12;
469
470 zzn3_copy(&(w->x),&t1);
471 zzn3_copy(&(w->y),&t2);
472 zzn3_mul(_MIPP_ &t1,&t1,&t1);
473 zzn3_mul(_MIPP_ &t2,&t2,&t2);
474 zzn3_timesi(_MIPP_ &t2);
475 zzn3_sub(_MIPP_ &t1,&t2,&t2);
476 zzn3_inv(_MIPP_ &t2);
477 zzn3_mul(_MIPP_ &(w->x),&t2,&(w->x));
478 zzn3_negate(_MIPP_ &(w->y),&(w->y));
479 zzn3_mul(_MIPP_ &(w->y),&t2,&(w->y));
480 }
481
g(_MIPD_ epoint * A,epoint * B,zzn3 * Qx,zzn3 * Qy,zzn6 * w)482 void g(_MIPD_ epoint *A,epoint *B,zzn3 *Qx,zzn3 *Qy,zzn6 *w)
483 {
484 int type;
485 big slope;
486 zzn3 nn,dd;
487
488 copy(A->X,mr_mip->w10);
489
490 type=ecurve_add(_MIPP_ B,A);
491 if (!type)
492 {
493 zzn6_from_int(_MIPP_ 1,w);
494 return;
495 }
496 slope=mr_mip->w8; /* slope in w8 */
497
498 nn.a=mr_mip->w13;
499 nn.b=mr_mip->w14;
500 nn.c=mr_mip->w15;
501
502 dd.a=mr_mip->w5;
503 dd.b=mr_mip->w11;
504 dd.c=mr_mip->w9;
505
506 zzn3_copy(Qx,&nn);
507 zzn3_copy(Qy,&dd);
508 zzn3_negate(_MIPP_ &dd,&dd);
509
510 #ifndef MR_AFFINE_ONLY
511 if (A->marker!=MR_EPOINT_GENERAL)
512 copy(mr_mip->one,mr_mip->w12);
513 else copy(A->Z,mr_mip->w12);
514 #else
515 copy(mr_mip->one,mr_mip->w12);
516 #endif
517 if (type==MR_ADD)
518 {
519 zzn3_ssub(_MIPP_ &nn,B->X,&nn);
520 zzn3_smul(_MIPP_ &nn,slope,&nn);
521 nres_modmult(_MIPP_ mr_mip->w12,B->Y,mr_mip->w2);
522 zzn3_sadd(_MIPP_ &nn,mr_mip->w2,&nn);
523 zzn3_smul(_MIPP_ &dd,mr_mip->w12,&dd);
524 zzn3_copy(&nn,&(w->x));
525 zzn3_copy(&dd,&(w->y));
526 return;
527 }
528
529 if (type==MR_DOUBLE)
530 { /* note that ecurve_add has left useful things for us in w6 and w7! */
531 nres_modmult(_MIPP_ slope,mr_mip->w6,mr_mip->w2);
532 zzn3_smul(_MIPP_ &nn,mr_mip->w2,&nn);
533 nres_modmult(_MIPP_ slope,mr_mip->w10,slope);
534 zzn3_ssub(_MIPP_ &nn,slope,&nn);
535 zzn3_sadd(_MIPP_ &nn,mr_mip->w7,&nn);
536 nres_modmult(_MIPP_ mr_mip->w12,mr_mip->w6,mr_mip->w12);
537 zzn3_smul(_MIPP_ &dd,mr_mip->w12,&dd);
538 zzn3_copy(&nn,&(w->x));
539 zzn3_copy(&dd,&(w->y));
540 return;
541 }
542 }
543
fast_tate_pairing(_MIPD_ epoint * P,zzn3 * Qx,zzn3 * Qy,big q,big cf,zzn6 * w,zzn6 * res)544 void fast_tate_pairing(_MIPD_ epoint *P,zzn3 *Qx,zzn3 *Qy,big q,big cf,zzn6 *w,zzn6* res)
545 {
546 int i,j,n,nb,nbw,nzs;
547 epoint *t[4],*A,*P2;
548 zzn6 zn[4];
549 big work[4];
550
551 #ifndef MR_STATIC
552 char *mem=memalloc(_MIPP_ 28);
553 char *mem1=ecp_memalloc(_MIPP_ 6);
554 #else
555 char mem[MR_BIG_RESERVE(28)];
556 char mem1[MR_ECP_RESERVE(6)];
557 memset(mem,0,MR_BIG_RESERVE(28));
558 memset(mem1,0,MR_ECP_RESERVE(6));
559 #endif
560
561 for (i=0;i<4;i++)
562 t[i]=epoint_init_mem(_MIPP_ mem1,i);
563 A=epoint_init_mem(_MIPP_ mem1,4);
564 P2=epoint_init_mem(_MIPP_ mem1,5);
565
566 for (j=i=0;i<4;i++)
567 {
568 work[i]=mirvar_mem(_MIPP_ mem,j++);
569 zn[i].x.a=mirvar_mem(_MIPP_ mem,j++);
570 zn[i].x.b=mirvar_mem(_MIPP_ mem,j++);
571 zn[i].x.c=mirvar_mem(_MIPP_ mem,j++);
572 zn[i].y.a=mirvar_mem(_MIPP_ mem,j++);
573 zn[i].y.b=mirvar_mem(_MIPP_ mem,j++);
574 zn[i].y.c=mirvar_mem(_MIPP_ mem,j++);
575 zn[i].unitary=FALSE;
576 }
577
578 zzn6_from_int(_MIPP_ 1,&zn[0]);
579 epoint_copy(P,A);
580 epoint_copy(P,P2);
581 epoint_copy(P,t[0]);
582
583 g(_MIPP_ P2,P2,Qx,Qy,res);
584 epoint_norm(_MIPP_ P2);
585
586 for (i=1;i<4;i++)
587 {
588 g(_MIPP_ A,P2,Qx,Qy,w);
589 epoint_copy(A,t[i]);
590 zzn6_mul(_MIPP_ &zn[i-1],w,&zn[i]);
591 zzn6_mul(_MIPP_ &zn[i],res,&zn[i]);
592 }
593
594 epoint_multi_norm(_MIPP_ 4,work,t);
595
596 epoint_copy(P,A);
597 zzn6_from_int(_MIPP_ 1,res);
598
599 nb=logb2(_MIPP_ q);
600 for (i=nb-2;i>=0;i-=(nbw+nzs))
601 {
602 n=mr_window(_MIPP_ q,i,&nbw,&nzs,3);
603 for (j=0;j<nbw;j++)
604 {
605 zzn6_mul(_MIPP_ res,res,res);
606 g(_MIPP_ A,A,Qx,Qy,w);
607 zzn6_mul(_MIPP_ res,w,res);
608 }
609 if (n>0)
610 {
611 zzn6_mul(_MIPP_ res,&zn[n/2],res);
612 g(_MIPP_ A,t[n/2],Qx,Qy,w);
613 zzn6_mul(_MIPP_ res,w,res);
614 }
615 for (j=0;j<nzs;j++)
616 {
617 zzn6_mul(_MIPP_ res,res,res);
618 g(_MIPP_ A,A,Qx,Qy,w);
619 zzn6_mul(_MIPP_ res,w,res);
620 }
621 }
622
623 zzn6_copy(res,w);
624 zzn6_powq(_MIPP_ w);
625 zzn6_mul(_MIPP_ res,w,res);
626
627 zzn6_copy(res,w);
628 zzn6_powq(_MIPP_ w);
629 zzn6_powq(_MIPP_ w);
630 zzn6_powq(_MIPP_ w);
631
632 zzn6_inv(_MIPP_ res);
633 zzn6_mul(_MIPP_ res,w,res);
634
635 res->unitary=TRUE;
636
637 #ifndef MR_STATIC
638 memkill(_MIPP_ mem,28);
639 ecp_memkill(_MIPP_ mem1,6);
640 #else
641 memset(mem,0,MR_BIG_RESERVE(28));
642 memset(mem1,0,MR_ECP_RESERVE(6));
643 #endif
644 }
645
ecap(_MIPD_ epoint * P,zzn3 * Qx,zzn3 * Qy,big q,big cf,zzn3 * r)646 void ecap(_MIPD_ epoint *P,zzn3 *Qx,zzn3 *Qy,big q,big cf,zzn3* r)
647 {
648 zzn6 res,w;
649 #ifndef MR_STATIC
650 char *mem=memalloc(_MIPP_ 12);
651 #else
652 char mem[MR_BIG_RESERVE(12)];
653 memset(mem,0,MR_BIG_RESERVE(12));
654 #endif
655 res.x.a=mirvar_mem(_MIPP_ mem,0);
656 res.x.b=mirvar_mem(_MIPP_ mem,1);
657 res.x.c=mirvar_mem(_MIPP_ mem,2);
658 res.y.a=mirvar_mem(_MIPP_ mem,3);
659 res.y.b=mirvar_mem(_MIPP_ mem,4);
660 res.y.c=mirvar_mem(_MIPP_ mem,5);
661 w.x.a=mirvar_mem(_MIPP_ mem,6);
662 w.x.b=mirvar_mem(_MIPP_ mem,7);
663 w.x.c=mirvar_mem(_MIPP_ mem,8);
664 w.y.a=mirvar_mem(_MIPP_ mem,9);
665 w.y.b=mirvar_mem(_MIPP_ mem,10);
666 w.y.c=mirvar_mem(_MIPP_ mem,11);
667 res.unitary=FALSE;
668 w.unitary=FALSE;
669
670 epoint_norm(_MIPP_ P);
671 fast_tate_pairing(_MIPP_ P,Qx,Qy,q,cf,&w,&res);
672
673 zzn6_copy(&res,&w);
674 zzn6_powq(_MIPP_ &res);
675 zzn6_mul(_MIPP_ &res,&res,&res);
676
677 zzn6_powu(_MIPP_ &w,cf,&w);
678 zzn6_mul(_MIPP_ &res,&w,&res);
679
680 zzn3_copy(&(res.x),r);
681
682 #ifndef MR_STATIC
683 memkill(_MIPP_ mem,12);
684 #else
685 memset(mem,0,MR_BIG_RESERVE(12));
686 #endif
687 }
688
main()689 int main()
690 {
691 #ifdef MR_GENERIC_MT
692 miracl instance;
693 #endif
694 big p,A,B,Fr,q,cf,sru,t,T;
695 zzn3 res,Qx,Qy;
696 epoint *P;
697 int i,romptr;
698 #ifndef MR_STATIC
699 #ifdef MR_GENERIC_MT
700 miracl *mr_mip=mirsys(&instance,WORDS*NPW,16);
701 #else
702 miracl *mr_mip=mirsys(WORDS*NPW,16);
703 #endif
704 char *mem=memalloc(_MIPP_ 18);
705 char *mem1=ecp_memalloc(_MIPP_ 1);
706 #else
707 #ifdef MR_GENERIC_MT
708 miracl *mr_mip=mirsys(&instance,MR_STATIC*NPW,16);
709 #else
710 miracl *mr_mip=mirsys(MR_STATIC*NPW,16);
711 #endif
712 char mem[MR_BIG_RESERVE(18)]; /* reserve space on the stack for 18 bigs */
713 char mem1[MR_ECP_RESERVE(1)]; /* reserve space on stack for 1 curve points */
714 memset(mem,0,MR_BIG_RESERVE(18)); /* clear this memory */
715 memset(mem1,0,MR_ECP_RESERVE(1));
716 #endif
717 p=mirvar_mem(_MIPP_ mem,0);
718 A=mirvar_mem(_MIPP_ mem,1);
719 B=mirvar_mem(_MIPP_ mem,2);
720 T=mirvar_mem(_MIPP_ mem,3);
721 q=mirvar_mem(_MIPP_ mem,4);
722 Fr=mirvar_mem(_MIPP_ mem,5);
723 cf=mirvar_mem(_MIPP_ mem,6);
724 res.a=mirvar_mem(_MIPP_ mem,7);
725 res.b=mirvar_mem(_MIPP_ mem,8);
726 res.c=mirvar_mem(_MIPP_ mem,9);
727 sru=mirvar_mem(_MIPP_ mem,10);
728 t=mirvar_mem(_MIPP_ mem,11);
729 Qx.a=mirvar_mem(_MIPP_ mem,12);
730 Qx.b=mirvar_mem(_MIPP_ mem,13);
731 Qx.c=mirvar_mem(_MIPP_ mem,14);
732 Qy.a=mirvar_mem(_MIPP_ mem,15);
733 Qy.b=mirvar_mem(_MIPP_ mem,16);
734 Qy.c=mirvar_mem(_MIPP_ mem,17);
735
736 P=epoint_init_mem(_MIPP_ mem1,0);
737 convert(_MIPP_ -3,A);
738
739 romptr=0;
740 init_big_from_rom(p,WORDS,romp,ROMSZ,&romptr);
741 init_big_from_rom(B,WORDS,romp,ROMSZ,&romptr);
742 init_big_from_rom(q,WORDS,romp,ROMSZ,&romptr);
743 init_big_from_rom(cf,WORDS,romp,ROMSZ,&romptr);
744 init_big_from_rom(sru,WORDS,romp,ROMSZ,&romptr);
745
746
747 #ifndef MR_NO_STANDARD_IO
748 printf("ROM size= %ld\n",sizeof(romp)+sizeof(Prom));
749 printf("sizeof(miracl)= %ld\n",sizeof(miracl));
750 #endif
751
752 premult(_MIPP_ p,CF,t);
753 subtract(_MIPP_ cf,t,cf);
754 ecurve_init(_MIPP_ A,B,p,MR_BEST);
755 zzn3_set(_MIPP_ CNR,sru);
756
757 romptr=0;
758 init_point_from_rom(P,WORDS,Prom,PROMSZ,&romptr);
759 init_big_from_rom(Qx.a,WORDS,Prom,PROMSZ,&romptr);
760 init_big_from_rom(Qx.b,WORDS,Prom,PROMSZ,&romptr);
761 init_big_from_rom(Qx.c,WORDS,Prom,PROMSZ,&romptr);
762 init_big_from_rom(Qy.a,WORDS,Prom,PROMSZ,&romptr);
763 init_big_from_rom(Qy.b,WORDS,Prom,PROMSZ,&romptr);
764 init_big_from_rom(Qy.c,WORDS,Prom,PROMSZ,&romptr);
765
766 #ifdef MR_COUNT_OPS
767 fpa=fpc=fpx=0;
768 #endif
769
770 ecap(_MIPP_ P,&Qx,&Qy,q,cf,&res);
771
772 #ifdef MR_COUNT_OPS
773 printf("fpc= %d\n",fpc);
774 printf("fpa= %d\n",fpa);
775 printf("fpx= %d\n",fpx);
776 fpa=fpc=fpx=0;
777 #endif
778
779 bigbits(_MIPP_ 160,t);
780 zzn3_powl(_MIPP_ &res,t,&res);
781
782 #ifndef MR_NO_STANDARD_IO
783 zzn3_out(_MIPP_ "res= ",&res);
784 #endif
785
786 ecurve_mult(_MIPP_ t,P,P);
787 ecap(_MIPP_ P,&Qx,&Qy,q,cf,&res);
788
789 #ifndef MR_NO_STANDARD_IO
790 zzn3_out(_MIPP_ "res= ",&res);
791 #endif
792
793 #ifndef MR_STATIC
794 memkill(_MIPP_ mem,18);
795 ecp_memkill(_MIPP_ mem1,1);
796 #else
797 memset(mem,0,MR_BIG_RESERVE(18)); /* clear this stack memory */
798 memset(mem1,0,MR_ECP_RESERVE(1));
799 #endif
800 return 0;
801 }
802
803
804