1 /*
2
3 Scott's AKE Client/Server testbed
4
5 See http://eprint.iacr.org/2002/164
6
7 Compile as
8 cl /O2 /GX /DZZNS=5 ake6mntt.cpp zzn6.cpp ecn3.cpp zzn3.cpp big.cpp zzn.cpp ecn.cpp miracl.lib
9 using COMBA build
10
11 MNT Curve - Tate pairing
12
13 The required file mnt.ecs is created from a curve generated by the mnt
14 utility, and created by the cm utility. For convenience the value of
15 (p^2-p+1)/q and the 6th root of unity (cnr^(p-1)/6) have been manually
16 calculated and appended to this file (replacing the x,y values in the
17 original .ecs file)
18
19 NOTE: Irreducible polynomial MUST be of the form x^6+CNR. This excludes many of the curves
20 found using the mnt utility!
21
22 Use the irred utility
23
24 Modified to prevent sub-group confinement attack
25
26 NOTE: Key exchange bandwidth could be reduced further using ideas from
27 "Doing more with Fewer Bits", Brouwer, Pellikaan & Verheul, Asiacrypt
28 '99
29
30 Speeded up using ideas from
31 "Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields"
32 by Sanjit Chatterjee1, Palash Sarkar1 and Rana Barua1
33
34 */
35
36 #include <iostream>
37 #include <fstream>
38 #include <string.h>
39 #include "ecn.h"
40 #include <ctime>
41 #include "ecn3.h"
42 #include "zzn6.h"
43
44 // fix a couple of things for this particular curve
45 // cofactor - number of points on curve=CF.q
46 // Cubic non-residue mod p
47
48 #define CF 2
49 #define CNR 2 // irreducible is x^6-2
50
51 using namespace std;
52
53 Miracl precision(5,0);
54
55 #ifdef MR_COUNT_OPS
56 extern "C"
57 {
58 int fpc,fpa,fpx,fpm2,fpi2;
59 }
60 #endif
61
62 // Using SHA-1 as basic hash algorithm
63
64 #define HASH_LEN 20
65
66 //
67 // Define one or the other of these
68 //
69 // Which is faster depends on the I/M ratio - See imratio.c
70 // Roughly if I/M ratio > 16 use PROJECTIVE, otherwise use AFFINE
71 //
72
73 #ifdef MR_AFFINE_ONLY
74 #define AFFINE
75 #else
76 #define PROJECTIVE
77 #endif
78
79 //
80 // Tate Pairing Code
81 //
82 // Extract ECn point in internal ZZn format
83 //
84
extract(ECn & A,ZZn & x,ZZn & y)85 void extract(ECn& A,ZZn& x,ZZn& y)
86 {
87 x=(A.get_point())->X;
88 y=(A.get_point())->Y;
89 }
90
91 #ifdef PROJECTIVE
extract(ECn & A,ZZn & x,ZZn & y,ZZn & z)92 void extract(ECn& A,ZZn& x,ZZn& y,ZZn& z)
93 {
94 big t;
95 x=(A.get_point())->X;
96 y=(A.get_point())->Y;
97 t=(A.get_point())->Z;
98 if (A.get_status()!=MR_EPOINT_GENERAL) z=1;
99 else z=t;
100 }
101 #endif
102
103 //
104 // Line from A to destination C. Let A=(x,y)
105 // Line Y-slope.X-c=0, through A, so intercept c=y-slope.x
106 // Line Y-slope.X-y+slope.x = (Y-y)-slope.(X-x) = 0
107 // Now evaluate at Q -> return (Qy-y)-slope.(Qx-x)
108 //
109
line(ECn & A,ECn & C,ECn & B,int type,ZZn & slope,ZZn & ex1,ZZn & ex2,ZZn3 & Qx,ZZn3 & Qy)110 ZZn6 line(ECn& A,ECn& C,ECn& B,int type,ZZn& slope,ZZn& ex1,ZZn& ex2,ZZn3& Qx,ZZn3& Qy)
111 {
112 ZZn6 w;
113 #ifdef AFFINE
114 ZZn3 nn=Qx;
115 ZZn x,y;
116 extract(A,x,y);
117 nn-=x;
118 nn*=slope;
119 nn+=y;
120 w.set(-nn,Qy);
121 #endif
122 #ifdef PROJECTIVE
123 if (type==MR_ADD)
124 {
125 ZZn x2,y2,x3,z3;
126 extract(B,x2,y2);
127 extract(C,x3,x3,z3);
128 w.set(slope*(Qx-x2)+z3*y2,-z3*Qy);
129 }
130 if (type==MR_DOUBLE)
131 {
132 ZZn x,y,x3,z3;
133 extract(A,x,y);
134 extract(C,x3,x3,z3);
135 w.set((slope*ex2)*Qx-slope*x+ex1,-(z3*ex2)*Qy);
136 }
137 /* extract(A,x,y,z);
138 x*=z; t=z; z*=z; z*=t;
139 x*=slope; t=slope*z;
140 nn*=t; nn-=x; t=z;
141 extract(C,x,x,z);
142 nn+=(z*y); t*=z;
143 w.set(nn,-Qy*t);
144 */
145 #endif
146 return w;
147 }
148
149 //
150 // Add A=A+B (or A=A+A)
151 // Return line function value
152 //
153
g(ECn & A,ECn & B,ZZn3 & Qx,ZZn3 & Qy)154 ZZn6 g(ECn& A,ECn& B,ZZn3& Qx,ZZn3& Qy)
155 {
156 ZZn lam,extra1,extra2;
157 int type;
158 ZZn6 u;
159 big ptr,ex1,ex2;
160 ECn P=A;
161
162 // Evaluate line from A
163 type=A.add(B,&ptr,&ex1,&ex2);
164 if (!type) return (ZZn6)1;
165 lam=ptr;
166 extra1=ex1;
167 extra2=ex2;
168 return line(P,A,B,type,lam,extra1,extra2,Qx,Qy);
169 }
170
171 //
172 // Tate Pairing - note denominator elimination has been applied
173 //
174 // P is a point of order q. Q(x,y) is a point of order m.q.
175 // Note that P is a point on the curve over Fp, Q(x,y) a point on the
176 // twisted curve over the extension field Fp^3
177 //
178
fast_tate_pairing(ECn & P,ZZn3 & Qx,ZZn3 & Qy,Big & q,Big & cf,ZZn6 & res)179 BOOL fast_tate_pairing(ECn& P,ZZn3& Qx,ZZn3& Qy,Big& q,Big &cf,ZZn6& res)
180 {
181 int i,j,n,nb,nbw,nzs;
182 ECn A,P2,t[8];
183 ZZn6 w,hc,z2n,zn[8];
184
185 res=zn[0]=1;
186
187 t[0]=P2=A=P;
188 z2n=g(P2,P2,Qx,Qy);
189
190 normalise(P2);
191 //
192 // Build windowing table
193 //
194
195 for (i=1;i<8;i++)
196 {
197 hc=g(A,P2,Qx,Qy);
198 t[i]=A;
199 zn[i]=z2n*zn[i-1]*hc;
200 }
201
202 multi_norm(8,t); // make t points Affine
203
204 A=P; // reset A
205 nb=bits(q);
206
207 for (i=nb-2;i>=0;i-=(nbw+nzs))
208 {
209 n=window(q,i,&nbw,&nzs,4); // standard MIRACL windowing
210
211 for (j=0;j<nbw;j++)
212 {
213 res*=res;
214 res*=g(A,A,Qx,Qy);
215 }
216
217 if (n>0)
218 {
219 res*=zn[n/2];
220 res*=g(A,t[n/2],Qx,Qy);
221 }
222
223 for (j=0;j<nzs;j++)
224 {
225 res*=res;
226 res*=g(A,A,Qx,Qy);
227 }
228
229 if (res.iszero()) return FALSE;
230 }
231 #ifdef MR_COUNT_OPS
232 printf("After Miller fpc= %d fpa= %d fpx= %d\n",fpc,fpa,fpx);
233 #endif
234 // if (!A.iszero() || res.iszero()) return FALSE;
235
236 w=res;
237 w.powq();
238 res*=w; // ^(p+1)
239
240 w=res;
241 w.powq(); w.powq(); w.powq();
242 res=w/res; // ^(p^3-1)
243
244 // res=pow(res,cf); // ^(p*p-p+1)/q
245
246 // exploit the clever "trick" for a half-length exponentiation!
247 // cout << "Final Exponentiation" << endl;
248 res.mark_as_unitary();
249
250 w=res;
251 res.powq(); res*=res; // res*=res; // res=pow(res,CF);
252
253 if (cf<0) res/=powu(w,-cf);
254 else res*=powu(w,cf);
255 //cout << "res= " << res << endl;
256 //exit(0);
257
258
259 /*
260 cout << "res*res= " << res*res << endl;
261
262 res.make_unitary();
263
264 cout << "res*res= " << res*res << endl;
265
266 ZZn3 r0,r1;
267
268 r0=real(res);
269 r1=imaginary(res);
270
271 cout << "real= " << 2*tx(r1*r1)+(ZZn3)1 << endl;
272 cout << "Imaginary= " << (r0+r1)*(r0+r1)-tx(r1*r1)-(ZZn3)1-r1*r1 << endl;
273
274
275 exit(0);
276
277
278 w=res;
279
280 r=2*real(res);
281
282 ZZn3 rp,ra;
283
284 res.powq();
285 rp=2*real(res);
286
287 res/=w;
288 ra=2*real(res);
289
290 Big a=rand(q);
291
292 cout << "powl(r,a)= " << powl(r,a) << endl;
293
294 Big a0,a1;
295 a0=a%T; a1=a/T;
296
297 cout << "pow(r,a)= " << powl(rp,a1,r,a0,ra) << endl;
298
299 exit(0);
300 */
301
302 if (res==(ZZn6)1) return FALSE;
303 return TRUE;
304 }
305
306 //
307 // ecap(.) function
308 //
309
ecap(ECn & P,ECn3 & Q,Big & order,Big & cf,ZZn6 & res)310 BOOL ecap(ECn& P,ECn3& Q,Big& order,Big& cf,ZZn6& res)
311 {
312 BOOL Ok;
313 ECn PP=P;
314 ZZn3 Qx,Qy;
315 int qnr=get_mip()->cnr;
316
317 normalise(PP);
318 Q.get(Qx,Qy);
319
320 // untwist
321 Qx=Qx/qnr;
322 Qy=tx(Qy);
323 Qy=Qy/(qnr*qnr);
324
325 #ifdef MR_COUNT_OPS
326 fpc=fpa=fpx=0;
327 #endif
328
329 Ok=fast_tate_pairing(PP,Qx,Qy,order,cf,res);
330
331 #ifdef MR_COUNT_OPS
332 printf("After tate fpc= %d fpa= %d fpx= %d\n",fpc,fpa,fpx);
333 fpa=fpc=fpx=0;
334 #endif
335
336 if (Ok) return TRUE;
337 return FALSE;
338 }
339
340 //
341 // Hash functions
342 //
343
H1(char * string)344 Big H1(char *string)
345 { // Hash a zero-terminated string to a number < modulus
346 Big h,p;
347 char s[HASH_LEN];
348 int i,j;
349 sha sh;
350
351 shs_init(&sh);
352
353 for (i=0;;i++)
354 {
355 if (string[i]==0) break;
356 shs_process(&sh,string[i]);
357 }
358 shs_hash(&sh,s);
359 p=get_modulus();
360 h=1; j=0; i=1;
361 forever
362 {
363 h*=256;
364 if (j==HASH_LEN) {h+=i++; j=0;}
365 else h+=s[j++];
366 if (h>=p) break;
367 }
368 h%=p;
369 return h;
370 }
371
H2(ZZn3 x)372 Big H2(ZZn3 x)
373 { // Hash an Fp3 to a big number
374 sha sh;
375 ZZn u,v,w;
376 Big a,h,p,xx[3];
377 char s[HASH_LEN];
378 int i,j,m;
379
380 shs_init(&sh);
381 x.get(u,v,w);
382 xx[0]=u; xx[1]=v; xx[2]=w;
383 for (i=0;i<3;i++)
384 {
385 a=xx[i];
386 while (a>0)
387 {
388 m=a%256;
389 shs_process(&sh,m);
390 a/=256;
391 }
392 }
393 shs_hash(&sh,s);
394 h=from_binary(HASH_LEN,s);
395 return h;
396 }
397
398 // Hash and map a Server Identity to a curve point E_(Fp3)
399
hash_and_map3(char * ID)400 ECn3 hash_and_map3(char *ID)
401 {
402 int i;
403 ECn3 S;
404 ZZn3 X;
405
406 Big x0=H1(ID);
407 forever
408 {
409 x0+=1;
410 X.set2((ZZn)x0);
411 if (!S.set(X)) continue;
412
413 break;
414 }
415
416 // cout << "S= " << S << endl;
417 return S;
418 }
419
420 // Hash and map a Client Identity to a curve point E_(Fp) of order q
421
hash_and_map(char * ID)422 ECn hash_and_map(char *ID)
423 {
424 ECn Q;
425 Big x0=H1(ID);
426
427 while (!Q.set(x0,x0)) x0+=1;
428 Q*=CF;
429 return Q;
430 }
431
432 // Use Galbraith & Scott Homomorphism idea
433
mypow(ZZn6 & res,Big & e,Big & T)434 ZZn3 mypow(ZZn6& res,Big &e,Big &T)
435 {
436 ZZn6 w=res;
437 ZZn3 ra,rp,r=real(res);
438 Big e0,e1;
439 e0=e%T; e1=e/T;
440 w.powq(); rp=real(w); w/=res; ra=real(w);
441 // Use GLV method, and double exponentiation a la Lucas (see ZZn3.cpp)
442 return powl(rp,e1,r,e0,ra);
443 }
444
main()445 int main()
446 {
447 ifstream common("mnt.ecs"); // MNT elliptic curve parameters
448 miracl* mip=&precision;
449 ECn Alice,Bob,sA,sB;
450 ECn3 B6,Server,sS;
451 ZZn3 sp,ap,bp;
452 ZZn6 res;
453 Big a,b,s,ss,p,q,x,y,B,cf,cfp,t,sru,T;
454 int i,bits,A;
455 time_t seed;
456
457 common >> bits;
458 mip->IOBASE=16;
459 common >> p;
460 common >> A;
461 common >> B >> q >> cf >> sru;
462
463 T=p-q*CF;
464
465 time(&seed);
466 irand((long)seed);
467
468 #ifdef AFFINE
469 ecurve(A,B,p,MR_AFFINE);
470 #endif
471 #ifdef PROJECTIVE
472 ecurve(A,B,p,MR_PROJECTIVE);
473 #endif
474
475 set_zzn3(CNR,sru);
476 cfp=cf-CF*p; // ~ (t-1)
477
478 mip->IOBASE=16;
479 mip->TWIST=MR_QUADRATIC; // map Server to point on twisted curve E(Fp3)
480
481 ss=rand(q); // TA's super-secret
482
483 cout << "Mapping Server ID to point" << endl;
484 Server=hash_and_map3((char *)"Server");
485 sS=ss*Server;
486
487 cout << "Mapping Alice & Bob ID's to points" << endl;
488 Alice=hash_and_map((char *)"Alice");
489 Bob= hash_and_map((char *)"Robert");
490
491 cout << "Alice, Bob and the Server visit Trusted Authority" << endl;
492
493
494 sA=ss*Alice;
495 sB=ss*Bob;
496
497 cout << "Alice and Server Key Exchange" << endl;
498
499 a=rand(q); // Alice's random number
500 s=rand(q); // Server's random number
501
502 if (!ecap(sA,Server,q,cfp,res)) cout << "Trouble" << endl;
503
504 if (powl(real(res),q)!=(ZZn3)1)
505 {
506 cout << "Wrong group order - aborting" << endl;
507 exit(0);
508 }
509 // ap=powl(real(res),a);
510 ap=mypow(res,a,T);
511
512 //for (i=0;i<10000;i++)
513 if (!ecap(Alice,sS,q,cfp,res)) cout << "Trouble" << endl;
514 if (powl(real(res),q)!=(ZZn3)1)
515 {
516 cout << "Wrong group order - aborting" << endl;
517 exit(0);
518 }
519 // sp=powl(real(res),s);
520 sp=mypow(res,s,T);
521
522 cout << "Alice Key= " << H2(powl(sp,a)) << endl;
523 cout << "Server Key= " << H2(powl(ap,s)) << endl;
524
525 cout << "Bob and Server Key Exchange" << endl;
526
527 b=rand(q); // Bob's random number
528 s=rand(q); // Server's random number
529
530 if (!ecap(sB,Server,q,cfp,res)) cout << "Trouble" << endl;
531 if (powl(real(res),q)!=(ZZn3)1)
532 {
533 cout << "Wrong group order - aborting" << endl;
534 exit(0);
535 }
536 bp=powl(real(res),b);
537
538 if (!ecap(Bob,sS,q,cfp,res)) cout << "Trouble" << endl;
539 if (powl(real(res),q)!=(ZZn3)1)
540 {
541 cout << "Wrong group order - aborting" << endl;
542 exit(0);
543 }
544 sp=powl(real(res),s);
545
546 cout << "Bob's Key= " << H2(powl(sp,b)) << endl;
547 cout << "Server Key= " << H2(powl(bp,s)) << endl;
548
549 return 0;
550 }
551
552