1 /*
2 *
3 * cp_pair.cpp
4 *
5 * Cocks-Pinch curve, Tate pairing embedding degree 2, ideal for security level AES-80
6 *
7 * Provides high level interface to pairing functions
8 *
9 * GT=pairing(G2,G1)
10 *
11 * This is calculated on a Pairing Friendly Curve (PFC), which must first be defined.
12 *
13 * G1 is a point over the base field, G2 is a point on the quadratic twist
14 * GT is a finite field point over the 2nd extension, where 2 is the embedding degree.
15 *
16 */
17
18 #define MR_PAIRING_CP
19 #include "pairing_3.h"
20
21 // Cocks-Pinch curve parameters, A,B and n, where p=3 mod 4
22 // AES_SECURITY=80 bit curve
23 // Curve E:y^2=x^3-3x+B, #E=COF*order, modulus p
24
25 static char MODtext[]="8D5006492B424C09D2FEBE717EE382A57EBE3A352FC383E1AC79F21DDB43706CFB192333A7E9CF644636332E83D90A1E56EFBAE8715AA07883483F8267E80ED3";
26 static char Btext[]="609993837367998001C95B87A6BA872135E26906DB4C192D6E038486177A3EDF6C50B9BB20DF881F2BD05842F598F3E037B362DBF89F0A62E5871D41D951BF8E";
27 static char COFtext[]="11AA00C9256849813A5FD7CE2FDC7054AFD7809E7F7FD948C4B9C1C1E76FFEFF4ECAB83C950112DECB41D6EDA";
28
read_only_error(void)29 void read_only_error(void)
30 {
31 cout << "Attempt to write to read-only object" << endl;
32 exit(0);
33 }
34
35 // Using SHA256 as basic hash algorithm
36 //
37 // Hash function
38 //
39
40 #define HASH_LEN 32
41
H1(char * string)42 Big H1(char *string)
43 { // Hash a zero-terminated string to a number < modulus
44 Big h,p;
45 char s[HASH_LEN];
46 int i,j;
47 sha256 sh;
48
49 shs256_init(&sh);
50
51 for (i=0;;i++)
52 {
53 if (string[i]==0) break;
54 shs256_process(&sh,string[i]);
55 }
56 shs256_hash(&sh,s);
57 p=get_modulus();
58 h=1; j=0; i=1;
59 forever
60 {
61 h*=256;
62 if (j==HASH_LEN) {h+=i++; j=0;}
63 else h+=s[j++];
64 if (h>=p) break;
65 }
66 h%=p;
67 return h;
68 }
69
start_hash(void)70 void PFC::start_hash(void)
71 {
72 shs256_init(&SH);
73 }
74
finish_hash_to_group(void)75 Big PFC::finish_hash_to_group(void)
76 {
77 Big hash;
78 char s[HASH_LEN];
79 shs256_hash(&SH,s);
80 hash=from_binary(HASH_LEN,s);
81 return hash%(*ord);
82 }
83
add_to_hash(const GT & x)84 void PFC::add_to_hash(const GT& x)
85 { // compress it and add
86 ZZn2 u=x.g;
87 Big a;
88 int m;
89
90 u.get(a);
91
92 while (a>0)
93 {
94 m=a%256;
95 shs256_process(&SH,m);
96 a/=256;
97 }
98 }
99
add_to_hash(const G1 & x)100 void PFC::add_to_hash(const G1& x)
101 {
102 Big a,X,Y;
103 int i,m;
104 x.g.get(X,Y);
105 a=X;
106 while (a>0)
107 {
108 m=a%256;
109 shs256_process(&SH,m);
110 a/=256;
111 }
112 a=Y;
113 while (a>0)
114 {
115 m=a%256;
116 shs256_process(&SH,m);
117 a/=256;
118 }
119 }
120
add_to_hash(const G2 & x)121 void PFC::add_to_hash(const G2& x)
122 {
123 Big a,X,Y;
124 int i,m;
125 x.g.get(X,Y);
126 a=X;
127 while (a>0)
128 {
129 m=a%256;
130 shs256_process(&SH,m);
131 a/=256;
132 }
133 a=Y;
134 while (a>0)
135 {
136 m=a%256;
137 shs256_process(&SH,m);
138 a/=256;
139 }
140 }
141
add_to_hash(const Big & x)142 void PFC::add_to_hash(const Big& x)
143 {
144 int m;
145 Big a=x;
146 while (a>0)
147 {
148 m=a%256;
149 shs256_process(&SH,m);
150 a/=256;
151 }
152 }
153
H2(ZZn2 y)154 Big H2(ZZn2 y)
155 { // Hash and compress an Fp2 to a big number
156 sha256 sh;
157 Big a,h;
158 char s[HASH_LEN];
159 int m;
160
161 shs256_init(&sh);
162 y.get(a);
163
164 while (a>0)
165 {
166 m=a%256;
167 shs256_process(&sh,m);
168 a/=256;
169 }
170 shs256_hash(&sh,s);
171 h=from_binary(HASH_LEN,s);
172 return h;
173 }
174
175 #ifndef MR_AFFINE_ONLY
176
force(ZZn & x,ZZn & y,ZZn & z,ECn & A)177 void force(ZZn& x,ZZn& y,ZZn& z,ECn& A)
178 { // A=(x,y,z)
179 copy(getbig(x),A.get_point()->X);
180 copy(getbig(y),A.get_point()->Y);
181 copy(getbig(z),A.get_point()->Z);
182 A.get_point()->marker=MR_EPOINT_GENERAL;
183 }
184
extract(ECn & A,ZZn & x,ZZn & y,ZZn & z)185 void extract(ECn &A, ZZn& x,ZZn& y,ZZn& z)
186 { // (x,y,z) <- A
187 big t;
188 x=(A.get_point())->X;
189 y=(A.get_point())->Y;
190 t=(A.get_point())->Z;
191 if (A.get_status()!=MR_EPOINT_GENERAL) z=1;
192 else z=t;
193 }
194
195 #endif
196
force(ZZn & x,ZZn & y,ECn & A)197 void force(ZZn& x,ZZn& y,ECn& A)
198 { // A=(x,y)
199 copy(getbig(x),A.get_point()->X);
200 copy(getbig(y),A.get_point()->Y);
201 A.get_point()->marker=MR_EPOINT_NORMALIZED;
202 }
203
extract(ECn & A,ZZn & x,ZZn & y)204 void extract(ECn& A,ZZn& x,ZZn& y)
205 { // (x,y) <- A
206 x=(A.get_point())->X;
207 y=(A.get_point())->Y;
208 }
209
extractZ(ECn & A,ZZn & z)210 void extractZ(ECn& A,ZZn& z)
211 {
212 big t;
213 t=(A.get_point())->Z;
214 if (A.get_status()!=MR_EPOINT_GENERAL) z=1;
215 else z=t;
216 }
217
218 //
219 // Line from A to destination C. Let A=(x,y)
220 // Line Y-slope.X-c=0, through A, so intercept c=y-slope.x
221 // Line Y-slope.X-y+slope.x = (Y-y)-slope.(X-x) = 0
222 // Now evaluate at Q -> return (Qy-y)-slope.(Qx-x)
223 //
224
line(ECn & A,ECn & C,ECn & B,int type,ZZn & slope,ZZn & ex1,ZZn & ex2,ZZn & Px,ZZn & Py)225 ZZn2 line(ECn& A,ECn& C,ECn& B,int type,ZZn& slope,ZZn& ex1,ZZn& ex2,ZZn& Px,ZZn& Py)
226 {
227 ZZn2 w;
228 ZZn x,y,z3;
229
230 extractZ(C,z3);
231 if (type==MR_ADD)
232 {
233 extract(B,x,y);
234 w.set(slope*(x+Px)-z3*y,z3*Py);
235 }
236 if (type==MR_DOUBLE)
237 {
238 extract(A,x,y);
239 w.set(-(slope*ex2)*Px-slope*x+ex1,-(z3*ex2)*Py);
240 }
241
242 /*
243 extract(A,x,y,z);
244 x*=z; t=z; z*=z; z*=t; // 9 ZZn muls
245 n*=z; n+=x; n*=slope;
246 d*=z; w.set(-y,d);
247 extractZ(C,z3);
248
249 w*=z3; w+=n;
250 */
251
252 // w.set(Px*z*z*z*slope+slope*x*z-y*z3,Py*z*z*z*z3);
253 return w;
254 }
255
256 //
257 // Add A=A+B (or A=A+A)
258 // Return line function value
259 //
260
g(ECn & A,ECn & B,ZZn & Px,ZZn & Py)261 ZZn2 g(ECn& A,ECn& B,ZZn& Px,ZZn& Py)
262 {
263 int type;
264 ZZn lam,extra1,extra2;
265 ZZn2 u;
266 ECn P=A;
267 big ptr,ex1,ex2;
268
269 type=A.add(B,&ptr,&ex1,&ex2);
270 if (!type) return (ZZn2)1;
271 lam=ptr;
272 extra1=ex1;
273 extra2=ex2;
274
275 return line(P,A,B,type,lam,extra1,extra2,Px,Py);
276 }
277
278 // if multiples of G2 can be precalculated, its a lot faster!
279
gp(ZZn * ptable,int & j,ZZn & Px,ZZn & Py)280 ZZn2 gp(ZZn* ptable,int &j,ZZn& Px,ZZn& Py)
281 {
282 ZZn2 w;
283 w.set(ptable[j]*Px+ptable[j+1],Py);
284 j+=2;
285 return w;
286 }
287
288 //
289 // Spill precomputation on pairing to byte array
290 //
291
spill(G2 & w,char * & bytes)292 int PFC::spill(G2& w,char *& bytes)
293 {
294 int i,j,n=2*(bits(*ord-1)-2+ham(*ord));
295 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
296 int len=n*bytes_per_big;
297 Big x;
298 if (w.ptable==NULL) return 0;
299
300 bytes=new char[len];
301 for (i=j=0;i<n;i++)
302 {
303 x=w.ptable[i];
304 to_binary(x,bytes_per_big,&bytes[j],TRUE);
305 j+=bytes_per_big;
306 }
307
308 delete [] w.ptable;
309 w.ptable=NULL;
310 return len;
311 }
312
313 //
314 // Restore precomputation on pairing to byte array
315 //
316
restore(char * bytes,G2 & w)317 void PFC::restore(char * bytes,G2& w)
318 {
319 int i,j,n=2*(bits(*ord-1)-2+ham(*ord));
320 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
321 int len=n*bytes_per_big;
322 Big x;
323
324 if (w.ptable!=NULL) return;
325
326 w.ptable=new ZZn[n];
327 for (i=j=0;i<n;i++)
328 {
329 x=from_binary(bytes_per_big,&bytes[j]);
330 w.ptable[i]=x;
331 j+=bytes_per_big;
332 }
333 for (i=0;i<len;i++) bytes[i]=0;
334 delete [] bytes;
335 }
336
337
338 // precompute G2 table for pairing
339
precomp_for_pairing(G2 & w)340 int PFC::precomp_for_pairing(G2& w)
341 {
342 int i,j,nb,len;
343 ECn A,Q,B;
344 ZZn lam,x,y;
345 big ptr;
346 Big iters=*ord-1;
347
348 A=w.g;
349 normalise(A);
350 B=A;
351 nb=bits(iters);
352 j=0;
353 len=2*(nb-2+ham(*ord));
354 w.ptable=new ZZn[len];
355 get_mip()->coord=MR_AFFINE;
356 for (i=nb-2;i>=0;i--)
357 {
358 Q=A;
359 // Evaluate line from A to A+B
360 A.add(A,&ptr);
361 lam=ptr;
362 extract(Q,x,y);
363 w.ptable[j++]=lam; w.ptable[j++]=lam*x-y;
364
365 if (bit(iters,i)==1)
366 {
367 Q=A;
368 A.add(B,&ptr);
369 lam=ptr;
370 extract(Q,x,y);
371 w.ptable[j++]=lam; w.ptable[j++]=lam*x-y;
372 }
373 }
374 get_mip()->coord=MR_PROJECTIVE;
375 return len;
376 }
377
multi_miller(int n,G2 ** QQ,G1 ** PP)378 GT PFC::multi_miller(int n,G2** QQ,G1** PP)
379 {
380 GT z;
381 ZZn *Px,*Py;
382 int i,j,*k,nb;
383 ECn *Q,*A;
384 ECn P;
385 ZZn2 res;
386 Big iters=*ord-1;
387
388 Px=new ZZn[n];
389 Py=new ZZn[n];
390 Q=new ECn[n];
391 A=new ECn[n];
392 k=new int[n];
393
394 nb=bits(iters);
395 res=1;
396
397 for (j=0;j<n;j++)
398 {
399 k[j]=0;
400 P=PP[j]->g; normalise(P); Q[j]=QQ[j]->g; normalise(Q[j]);
401 extract(P,Px[j],Py[j]);
402 }
403
404 for (j=0;j<n;j++) A[j]=Q[j];
405
406 for (i=nb-2;i>=0;i--)
407 {
408 res*=res;
409 for (j=0;j<n;j++)
410 {
411 if (QQ[j]->ptable==NULL)
412 res*=g(A[j],A[j],Px[j],Py[j]);
413 else
414 res*=gp(QQ[j]->ptable,k[j],Px[j],Py[j]);
415 }
416 if (bit(iters,i)==1)
417 for (j=0;j<n;j++)
418 {
419 if (QQ[j]->ptable==NULL)
420 res*=g(A[j],Q[j],Px[j],Py[j]);
421 else
422 res*=gp(QQ[j]->ptable,k[j],Px[j],Py[j]);
423 }
424 if (res.iszero()) return 0;
425 }
426
427 delete [] k;
428 delete [] A;
429 delete [] Q;
430 delete [] Py;
431 delete [] Px;
432
433 z.g=res;
434 return z;
435 }
436
437 //
438 // Tate Pairing G1 x G1 -> GT
439 //
440 // P and Q are points of order q in G1.
441 //
442
miller_loop(const G2 & QQ,const G1 & PP)443 GT PFC::miller_loop(const G2& QQ,const G1& PP)
444 {
445 GT z;
446 int i,j,n,nb,nbw,nzs;
447 ECn A,Q;
448 ECn P;
449 ZZn Px,Py;
450 BOOL precomp;
451 ZZn2 res;
452 Big iters=*ord-1; // can omit last addition
453
454 P=PP.g; Q=QQ.g;
455 precomp=FALSE;
456 if (QQ.ptable!=NULL) precomp=TRUE;
457
458 normalise(P);
459 normalise(Q);
460 extract(P,Px,Py);
461 //Px=-Px;
462
463 res=1;
464 A=Q; // reset A
465 nb=bits(iters);
466
467 j=0;
468
469 for (i=nb-2;i>=0;i--)
470 {
471 res*=res;
472 if (precomp) res*=gp(QQ.ptable,j,Px,Py);
473 else res*=g(A,A,Px,Py);
474
475 if (bit(iters,i)==1)
476 {
477 if (precomp) res*=gp(QQ.ptable,j,Px,Py);
478 else res*=g(A,Q,Px,Py);
479 }
480 }
481
482 z.g=res;
483 return z;
484 }
485
final_exp(const GT & z)486 GT PFC::final_exp(const GT& z)
487 {
488 GT y;
489 ZZn2 res;
490
491 res=z.g;
492 res=conj(res)/res;
493 res=pow(res,(*mod+1)/(*ord)); // raise to power of (p^2-1)/q
494
495 y.g=res;
496
497 return y;
498 }
499
PFC(int s,csprng * rng)500 PFC::PFC(int s, csprng *rng)
501 {
502 int mod_bits,words;
503
504 if (s!=80)
505 {
506 cout << "No suitable curve available" << endl;
507 exit(0);
508 }
509
510 mod_bits=512;
511
512 if (mod_bits%MIRACL==0)
513 words=(mod_bits/MIRACL);
514 else
515 words=(mod_bits/MIRACL)+1;
516
517 #ifdef MR_SIMPLE_BASE
518 miracl *mip=mirsys((MIRACL/4)*words,16);
519 #else
520 miracl *mip=mirsys(words,0);
521 mip->IOBASE=16;
522 #endif
523
524 B=new Big;
525 mod=new Big;
526 ord=new Big;
527 cof=new Big;
528 npoints=new Big;
529 trace=new Big;
530
531 *B=Btext;
532
533 *cof=COFtext;
534 *ord=pow((Big)2,159)+pow((Big)2,17)+1;
535 *npoints=*cof*(*ord);
536
537 S=s;
538 *mod=MODtext;
539 *trace=*mod+1-*npoints;
540
541 ecurve(-3,*B,*mod,MR_PROJECTIVE);
542
543 RNG=rng;
544 }
545
~PFC()546 PFC::~PFC()
547 {
548 delete B;
549 delete mod;
550 delete ord;
551 delete cof;
552 delete npoints;
553 delete trace;
554 mirexit();
555 }
556
mult(const G1 & w,const Big & k)557 G1 PFC::mult(const G1& w,const Big& k)
558 {
559 G1 z;
560 if (w.mtable!=NULL)
561 { // we have precomputed values
562
563 Big e=k;
564 if (k<0) e=-e;
565
566 int i,j,t=w.mtbits; // MR_ROUNDUP(2*S,WINDOW_SIZE);
567 j=recode(e,t,WINDOW_SIZE,t-1);
568 z.g=w.mtable[j];
569 for (i=t-2;i>=0;i--)
570 {
571 j=recode(e,t,WINDOW_SIZE,i);
572 z.g+=z.g;
573 if (j>0) z.g+=w.mtable[j];
574 }
575 if (k<0) z.g=-z.g;
576 }
577 else
578 {
579 z.g=w.g;
580 z.g*=k;
581 }
582 return z;
583 }
584
mult(const G2 & w,const Big & k)585 G2 PFC::mult(const G2& w,const Big& k)
586 {
587 G2 z;
588 if (w.mtable!=NULL)
589 { // we have precomputed values
590
591 Big e=k;
592 if (k<0) e=-e;
593
594 int i,j,t=w.mtbits; // MR_ROUNDUP(2*S,WINDOW_SIZE);
595 j=recode(e,t,WINDOW_SIZE,t-1);
596 z.g=w.mtable[j];
597 for (i=t-2;i>=0;i--)
598 {
599 j=recode(e,t,WINDOW_SIZE,i);
600 z.g+=z.g;
601 if (j>0) z.g+=w.mtable[j];
602 }
603 if (k<0) z.g=-z.g;
604 }
605 else
606 {
607 z.g=w.g;
608 z.g*=k;
609 }
610 return z;
611 }
612
power(const GT & w,const Big & k)613 GT PFC::power(const GT& w,const Big& k)
614 {
615 GT z;
616 Big e=k;
617 if (k<0) e=-e;
618 if (w.etable!=NULL)
619 { // precomputation is available
620 int i,j,t=w.etbits; //MR_ROUNDUP(2*S,WINDOW_SIZE);
621 j=recode(e,t,WINDOW_SIZE,t-1);
622 z.g=w.etable[j];
623 for (i=t-2;i>=0;i--)
624 {
625 j=recode(e,t,WINDOW_SIZE,i);
626 z.g*=z.g;
627 if (j>0) z.g*=w.etable[j];
628 }
629 }
630 else
631 {
632 z.g=powu(w.g,e);
633 }
634 if (k<0) z.g=conj(z.g);
635 return z;
636 }
637
638 // random group member
639
random(Big & w)640 void PFC::random(Big& w)
641 {
642 if (RNG==NULL) w=rand(*ord);
643 else w=strong_rand(RNG,*ord);
644 }
645
646 // random AES key
647
rankey(Big & k)648 void PFC::rankey(Big& k)
649 {
650 if (RNG==NULL) k=rand(S,2);
651 else k=strong_rand(RNG,S,2);
652 }
653
654 // Can be done deterministicly
655
hash_and_map(G1 & w,char * ID)656 void PFC::hash_and_map(G1& w,char *ID)
657 {
658 Big x0=H1(ID);
659 while (!w.g.set(x0,x0)) x0+=1;
660 w.g*=*cof;
661 }
662
hash_and_map(G2 & w,char * ID)663 void PFC::hash_and_map(G2& w,char *ID)
664 {
665 Big x0=H1(ID);
666 *B=-(*B);
667 ecurve((Big)-3,*B,*mod,MR_PROJECTIVE); // move to twist
668 while (!w.g.set(x0,x0)) x0+=1;
669 w.g*=(*mod+1+*trace)/(*ord);
670 *B=-(*B);
671 ecurve((Big)-3,*B,*mod,MR_PROJECTIVE); // move back
672 }
673
random(G1 & w)674 void PFC::random(G1& w)
675 {
676 Big x0;
677 if (RNG==NULL) x0=rand(*mod);
678 else x0=strong_rand(RNG,*mod);
679 while (!w.g.set(x0,x0)) x0+=1;
680 w.g*=*cof;
681 }
682
random(G2 & w)683 void PFC::random(G2& w)
684 {
685 Big x0;
686 if (RNG==NULL) x0=rand(*mod);
687 else x0=strong_rand(RNG,*mod);
688
689 *B=-(*B);
690 ecurve((Big)-3,*B,*mod,MR_PROJECTIVE); // move to twist
691 while (!w.g.set(x0,x0)) x0+=1;
692 w.g*=(*mod+1+*trace)/(*ord);
693 *B=-(*B);
694 ecurve((Big)-3,*B,*mod,MR_PROJECTIVE); // move back
695 }
696
hash_to_aes_key(const GT & w)697 Big PFC::hash_to_aes_key(const GT& w)
698 {
699 Big m=pow((Big)2,S);
700 return H2(w.g)%m;
701 }
702
hash_to_group(char * ID)703 Big PFC::hash_to_group(char *ID)
704 {
705 Big m=H1(ID);
706 return m%(*ord);
707 }
708
operator *(const GT & x,const GT & y)709 GT operator*(const GT& x,const GT& y)
710 {
711 GT z=x;
712 z.g*=y.g;
713 return z;
714 }
715
operator /(const GT & x,const GT & y)716 GT operator/(const GT& x,const GT& y)
717 {
718 GT z=x;
719 z.g*=conj(y.g); // elements in GT are unitary
720 return z;
721 }
722
723 //
724 // spill precomputation on GT to byte array
725 //
726
spill(char * & bytes)727 int GT::spill(char *& bytes)
728 {
729 int i,j,n=(1<<WINDOW_SIZE);
730 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
731 int len=n*2*bytes_per_big;
732 Big x,y;
733
734 if (etable==NULL) return 0;
735
736 bytes=new char[len];
737 for (i=j=0;i<n;i++)
738 {
739 etable[i].get(x,y);
740 to_binary(x,bytes_per_big,&bytes[j],TRUE);
741 j+=bytes_per_big;
742 to_binary(y,bytes_per_big,&bytes[j],TRUE);
743 j+=bytes_per_big;
744 }
745 delete [] etable;
746 etable=NULL;
747 return len;
748 }
749
750 //
751 // restore precomputation for GT from byte array
752 //
753
restore(char * bytes)754 void GT::restore(char *bytes)
755 {
756 int i,j,n=(1<<WINDOW_SIZE);
757 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
758 int len=n*2*bytes_per_big;
759 Big x,y;
760 if (etable!=NULL) return;
761
762 etable=new ZZn2[1<<WINDOW_SIZE];
763 for (i=j=0;i<n;i++)
764 {
765 x=from_binary(bytes_per_big,&bytes[j]);
766 j+=bytes_per_big;
767 y=from_binary(bytes_per_big,&bytes[j]);
768 j+=bytes_per_big;
769 etable[i].set(x,y);
770 }
771 delete [] bytes;
772 }
773
operator +(const G1 & x,const G1 & y)774 G1 operator+(const G1& x,const G1& y)
775 {
776 G1 z=x;
777 z.g+=y.g;
778 return z;
779 }
780
operator -(const G1 & x)781 G1 operator-(const G1& x)
782 {
783 G1 z=x;
784 z.g=-z.g;
785 return z;
786 }
787
788 //
789 // spill precomputation on G1 to byte array
790 //
791
spill(char * & bytes)792 int G1::spill(char *& bytes)
793 {
794 int i,j,n=(1<<WINDOW_SIZE);
795 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
796 int len=n*2*bytes_per_big;
797 Big x,y;
798
799 if (mtable==NULL) return 0;
800
801 bytes=new char[len];
802 for (i=j=0;i<n;i++)
803 {
804 mtable[i].get(x,y);
805 to_binary(x,bytes_per_big,&bytes[j],TRUE);
806 j+=bytes_per_big;
807 to_binary(y,bytes_per_big,&bytes[j],TRUE);
808 j+=bytes_per_big;
809 }
810 delete [] mtable;
811 mtable=NULL;
812 return len;
813 }
814
815 //
816 // restore precomputation for G1 from byte array
817 //
818
restore(char * bytes)819 void G1::restore(char *bytes)
820 {
821 int i,j,n=(1<<WINDOW_SIZE);
822 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
823 int len=n*2*bytes_per_big;
824 Big x,y;
825 if (mtable!=NULL) return;
826
827 mtable=new ECn[1<<WINDOW_SIZE];
828 for (i=j=0;i<n;i++)
829 {
830 x=from_binary(bytes_per_big,&bytes[j]);
831 j+=bytes_per_big;
832 y=from_binary(bytes_per_big,&bytes[j]);
833 j+=bytes_per_big;
834 mtable[i].set(x,y);
835 }
836 delete [] bytes;
837 }
838
839
operator +(const G2 & x,const G2 & y)840 G2 operator+(const G2& x,const G2& y)
841 {
842 G2 z=x;
843 z.g+=y.g;
844 return z;
845 }
846
operator -(const G2 & x)847 G2 operator-(const G2& x)
848 {
849 G2 z=x;
850 z.g=-z.g;
851 return z;
852 }
853
854 //
855 // spill precomputation on G2 to byte array
856 //
857
spill(char * & bytes)858 int G2::spill(char *& bytes)
859 {
860 int i,j,n=(1<<WINDOW_SIZE);
861 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
862 int len=n*2*bytes_per_big;
863 Big x,y;
864
865 if (mtable==NULL) return 0;
866
867 bytes=new char[len];
868
869 for (i=j=0;i<n;i++)
870 {
871 mtable[i].get(x,y);
872 to_binary(x,bytes_per_big,&bytes[j],TRUE);
873 x=from_binary(bytes_per_big,&bytes[j]);
874
875 j+=bytes_per_big;
876 to_binary(y,bytes_per_big,&bytes[j],TRUE);
877 j+=bytes_per_big;
878 }
879 delete [] mtable;
880 mtable=NULL;
881 return len;
882 }
883
884 //
885 // restore precomputation for G2 from byte array
886 //
887
restore(char * bytes)888 void G2::restore(char *bytes)
889 {
890 int i,j,n=(1<<WINDOW_SIZE);
891 int bytes_per_big=(MIRACL/8)*(get_mip()->nib-1);
892 int len=n*2*bytes_per_big;
893 Big x,y,B;
894 if (mtable!=NULL) return;
895
896 mtable=new ECn[1<<WINDOW_SIZE];
897 B=getB();
898 B=-B;
899 ecurve((Big)-3,B,get_modulus(),MR_PROJECTIVE); // move to twist
900 for (i=j=0;i<n;i++)
901 {
902 x=from_binary(bytes_per_big,&bytes[j]);
903 j+=bytes_per_big;
904 y=from_binary(bytes_per_big,&bytes[j]);
905 j+=bytes_per_big;
906
907 mtable[i].set(x,y);
908
909 }
910 B=-B;
911 ecurve((Big)-3,B,get_modulus(),MR_PROJECTIVE); // move back
912 delete [] bytes;
913 }
914
member(const GT & z)915 BOOL PFC::member(const GT& z)
916 {
917 ZZn2 r=z.g;
918
919 if (pow(r,*ord)!=(ZZn2)1) return FALSE;
920
921 return TRUE;
922 }
923
pairing(const G2 & x,const G1 & y)924 GT PFC::pairing(const G2& x,const G1& y)
925 {
926 GT z;
927 z=miller_loop(x,y);
928 z=final_exp(z);
929 return z;
930 }
931
multi_pairing(int n,G2 ** y,G1 ** x)932 GT PFC::multi_pairing(int n,G2 **y,G1 **x)
933 {
934 GT z;
935 z=multi_miller(n,y,x);
936 z=final_exp(z);
937 return z;
938
939 }
940
precomp_for_mult(G1 & w,BOOL small)941 int PFC::precomp_for_mult(G1& w,BOOL small)
942 {
943 ECn v=w.g;
944 int i,j,k,bp,is,t;
945 if (small) t=MR_ROUNDUP(2*S,WINDOW_SIZE);
946 else t=MR_ROUNDUP(bits(*ord),WINDOW_SIZE);
947 w.mtable=new ECn[1<<WINDOW_SIZE];
948 w.mtable[1]=v;
949 w.mtbits=t;
950 for (j=0;j<t;j++)
951 v+=v;
952 k=1;
953 for (i=2;i<(1<<WINDOW_SIZE);i++)
954 {
955 if (i==(1<<k))
956 {
957 k++;
958 normalise(v);
959 w.mtable[i]=v;
960 for (j=0;j<t;j++)
961 v+=v;
962 continue;
963 }
964 bp=1;
965 for (j=0;j<k;j++)
966 {
967 if (i&bp)
968 {
969 is=1<<j;
970 w.mtable[i]+=w.mtable[is];
971 }
972 bp<<=1;
973 }
974 normalise(w.mtable[i]);
975 }
976 return (1<<WINDOW_SIZE);
977 }
978
precomp_for_mult(G2 & w,BOOL small)979 int PFC::precomp_for_mult(G2& w,BOOL small)
980 {
981 ECn v;
982 int i,j,k,bp,is,t;
983 if (small) t=MR_ROUNDUP(2*S,WINDOW_SIZE);
984 else t=MR_ROUNDUP(bits(*ord),WINDOW_SIZE);
985 normalise(w.g);
986 v=w.g;
987 w.mtable=new ECn[1<<WINDOW_SIZE];
988 w.mtable[1]=v;
989 w.mtbits=t;
990 for (j=0;j<t;j++)
991 v+=v;
992 k=1;
993 for (i=2;i<(1<<WINDOW_SIZE);i++)
994 {
995 if (i==(1<<k))
996 {
997 k++;
998 normalise(v);
999 w.mtable[i]=v;
1000 for (j=0;j<t;j++)
1001 v+=v;
1002 continue;
1003 }
1004 bp=1;
1005 for (j=0;j<k;j++)
1006 {
1007 if (i&bp)
1008 {
1009 is=1<<j;
1010 w.mtable[i]+=w.mtable[is];
1011 }
1012 bp<<=1;
1013 }
1014 normalise(w.mtable[i]);
1015 }
1016 return (1<<WINDOW_SIZE);
1017 }
1018
precomp_for_power(GT & w,BOOL small)1019 int PFC::precomp_for_power(GT& w,BOOL small)
1020 {
1021 ZZn2 v=w.g;
1022 int i,j,k,bp,is,t;
1023 if (small) t=MR_ROUNDUP(2*S,WINDOW_SIZE);
1024 else t=MR_ROUNDUP(bits(*ord),WINDOW_SIZE);
1025 w.etable=new ZZn2[1<<WINDOW_SIZE];
1026 w.etable[0]=1;
1027 w.etable[1]=v;
1028 w.etbits=t;
1029 for (j=0;j<t;j++)
1030 v*=v;
1031 k=1;
1032
1033 for (i=2;i<(1<<WINDOW_SIZE);i++)
1034 {
1035 if (i==(1<<k))
1036 {
1037 k++;
1038 w.etable[i]=v;
1039 for (j=0;j<t;j++)
1040 v*=v;
1041 continue;
1042 }
1043 bp=1;
1044 w.etable[i]=1;
1045 for (j=0;j<k;j++)
1046 {
1047 if (i&bp)
1048 {
1049 is=1<<j;
1050 w.etable[i]*=w.etable[is];
1051 }
1052 bp<<=1;
1053 }
1054 }
1055 return (1<<WINDOW_SIZE);
1056 }
1057