1 /*
2 Scott's AKE Client/Server testbed
3
4 See http://eprint.iacr.org/2002/164
5
6 Compile as
7 cl /O2 /GX /DZZNS=16 ake4mnta.cpp zzn4.cpp zzn2.cpp ecn2.cpp big.cpp zzn.cpp
8 ecn.cpp miracl.lib
9 Fastest using COMBA build for 160-bit mod-mul
10
11 The file k4mnt.ecs is required
12 Security is G155/F640 (155-bit group, 640-bit field)
13
14 Speeded up using ideas from
15 "Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields"
16 by Sanjit Chatterjee1, Palash Sarkar1 and Rana Barua1
17
18 Modified to prevent sub-group confinement attack
19
20 */
21
22 #include <iostream>
23 #include <fstream>
24 #include <string.h>
25 #include "ecn.h"
26 #include <ctime>
27 #include "ecn2.h"
28 #include "zzn4.h"
29
30 using namespace std;
31
32 Miracl precision(10,0);
33
34 // Using SHA-1 as basic hash algorithm
35
36 #define HASH_LEN 20
37 #define COF 34
38
39 #ifdef MR_COUNT_OPS
40 extern "C"
41 {
42 int fpc,fpa,fpx;
43 }
44 #endif
45
46 //
47 // Define one or the other of these
48 //
49 // Which is faster depends on the I/M ratio - See imratio.c
50 // Roughly if I/M ratio > 16 use PROJECTIVE, otherwise use AFFINE
51 //
52
53 #ifdef MR_AFFINE_ONLY
54 #define AFFINE
55 #else
56 #define PROJECTIVE
57 #endif
58
59 //
60 // Tate Pairing Code
61 //
62 // Extract ECn point in internal ZZn format
63 //
64
extract(ECn & A,ZZn & x,ZZn & y)65 void extract(ECn& A,ZZn& x,ZZn& y)
66 {
67 x=(A.get_point())->X;
68 y=(A.get_point())->Y;
69 }
70
line(ECn2 & A,ECn2 & C,ECn2 & B,BOOL Doubling,ZZn2 & lam,ZZn2 & extra1,ZZn2 & extra2,ZZn & Qx,ZZn & Qy)71 ZZn4 line(ECn2& A,ECn2& C,ECn2& B,BOOL Doubling,ZZn2& lam,ZZn2& extra1,ZZn2& extra2,ZZn& Qx,ZZn& Qy)
72 {
73 ZZn4 w;
74 ZZn2 z3;
75
76 #ifdef AFFINE
77
78 ZZn2 x,y;
79 A.get(x,y);
80 w.set(ZZn2(0,Qy),lam*(tx(x)+Qx)-tx(y));
81
82 #endif
83
84 #ifdef PROJECTIVE
85
86 C.getZ(z3);
87
88 if (!Doubling)
89 {
90 ZZn2 x2,y2;
91 B.get(x2,y2);
92 w.set(tx(z3*Qy),lam*(tx(x2)+Qx)-z3*tx(y2));
93 }
94 else
95 {
96 ZZn2 x,y,z;
97 A.get(x,y,z);
98 w.set(tx(z3*extra2*Qy),lam*(extra2*Qx+tx(x))-tx(extra1));
99 }
100 /*
101 A.get(x,y,z);
102 x=tx(x); y=tx(y);
103 t=z; x*=z; z*=z; z*=t;
104 w.set(z3*z*ZZn2(0,Qy),lam*(x+z*Qx)-y*z3);
105 */
106 #endif
107
108 return w;
109 }
110
g(ECn2 & A,ECn2 & B,ZZn & Qx,ZZn & Qy)111 ZZn4 g(ECn2& A,ECn2& B,ZZn& Qx,ZZn& Qy)
112 {
113 BOOL Doubling;
114 ZZn2 lam,extra1,extra2;
115 ECn2 P=A;
116
117 ZZn2 x,y,z;
118
119 // Evaluate line from A
120
121 Doubling=A.add(B,lam,extra1,extra2);
122 if (A.iszero()) return (ZZn4)1;
123
124 return line(P,A,B,Doubling,lam,extra1,extra2,Qx,Qy);
125 }
126
127 //
128 // Ate Pairing - note denominator elimination has been applied
129 //
130 // P is a point of order q. Q(x,y) is a point of order m.q.
131 // Note that P is a point on the curve over Fp, Q(x,y) a point on the
132 // extension field Fp^2
133 //
134
ate(ECn2 & P,ECn Q,Big & t1,ZZn2 & Fr,Big cof,ZZn2 & r)135 BOOL ate(ECn2& P,ECn Q,Big& t1,ZZn2 &Fr,Big cof,ZZn2& r)
136 {
137 int i,j,n,nb;
138 ECn2 A;
139 ZZn4 w,res;
140 ZZn Qx,Qy;
141
142 #ifdef MR_COUNT_OPS
143 fpc=fpa=fpx=0;
144 #endif
145
146 P.norm();
147 normalise(Q);
148 extract(Q,Qx,Qy);
149
150 Qx+=Qx; // because x^4+2 is irreducible..
151 Qy+=Qy;
152
153 res=1;
154
155 /* Miller loop - Left to right method */
156 A=P;
157 nb=bits(t1);
158 for (i=nb-2;i>=0;i--)
159 {
160 res*=res;
161 res*=g(A,A,Qx,Qy);
162 if (bit(t1,i))
163 res*=g(A,P,Qx,Qy);
164 }
165
166 #ifdef MR_COUNT_OPS
167 printf("After Miller fpc= %d fpa= %d fpx= %d\n",fpc,fpa,fpx);
168 fpa=fpc=fpx=0;
169 #endif
170
171 w=res;
172 w.powq(Fr); w.powq(Fr); // ^(p^2-1)
173 res=w/res;
174
175 res.mark_as_unitary();
176
177 res*=res; w=res; res*=res; res*=res; res*=res; res*=res; res*=w; // res=powu(res,34);
178
179
180 w=res;
181 res.powq(Fr);
182 res*=powu(w,cof);
183
184 #ifdef MR_COUNT_OPS
185 printf("After Final exp. fpc= %d fpa= %d fpx= %d\n",fpc,fpa,fpx);
186 fpa=fpc=fpx=0;
187 #endif
188
189 r=real(res);
190
191 if (r.isunity()) return FALSE;
192 return TRUE;
193 }
194
195 //
196 // Hash functions
197 //
198
H1(char * string)199 Big H1(char *string)
200 { // Hash a zero-terminated string to a number < modulus
201 Big h,p;
202 char s[HASH_LEN];
203 int i,j;
204 sha sh;
205
206 shs_init(&sh);
207
208 for (i=0;;i++)
209 {
210 if (string[i]==0) break;
211 shs_process(&sh,string[i]);
212 }
213 shs_hash(&sh,s);
214 p=get_modulus();
215 h=1; j=0; i=1;
216 forever
217 {
218 h*=256;
219 if (j==HASH_LEN) {h+=i++; j=0;}
220 else h+=s[j++];
221 if (h>=p) break;
222 }
223 h%=p;
224 return h;
225 }
226
H2(ZZn2 x)227 Big H2(ZZn2 x)
228 { // Hash an Fp2 to a big number
229 sha sh;
230 Big a,u,v;
231 char s[HASH_LEN];
232 int m;
233
234 shs_init(&sh);
235 x.get(u,v);
236
237 a=u;
238 while (a>0)
239 {
240 m=a%256;
241 shs_process(&sh,m);
242 a/=256;
243 }
244 a=v;
245 while (a>0)
246 {
247 m=a%256;
248 shs_process(&sh,m);
249 a/=256;
250 }
251 shs_hash(&sh,s);
252 a=from_binary(HASH_LEN,s);
253 return a;
254 }
255
256 // Hash and map a Server Identity to a curve point E(Fp2)
257
hash2(char * ID)258 ECn2 hash2(char *ID)
259 {
260 ECn2 T;
261 ZZn2 x;
262 Big x0,y0=0;
263
264 x0=H1(ID);
265 do
266 {
267 x.set(x0,y0);
268 x0+=1;
269 }
270 while (!is_on_curve(x));
271 T.set(x);
272
273 // cout << "T= " << T << endl;
274
275 return T;
276 }
277
278 // Hash and map a Client Identity to a curve point E(Fp)
279
hash_and_map(char * ID,Big cof)280 ECn hash_and_map(char *ID,Big cof)
281 {
282 ECn Q;
283 Big x0=H1(ID);
284
285 while (!is_on_curve(x0)) x0+=1;
286 Q.set(x0); // Make sure its on E(F_p)
287
288 Q*=cof;
289 return Q;
290 }
291
292 //
293 // fast multiplication by p-1+t
294 // We know F^2-tF+p = 0
295 // So p.S=t.F(S)-F^2(S), where F is Frobenius Endomorphism
296 // So (p-1+t).S = t(F(S)+S)-F^2(S)-S
297 // This is just multiplication by t, which is half size of (p-1+t)
298 //
299
cofactor(ECn2 & S,ZZn2 & Fr,Big & t)300 void cofactor(ECn2& S,ZZn2& Fr,Big& t)
301 {
302 ECn2 T,K;
303 ZZn2 x,y,tx,tty;
304
305 K=S;
306 S.get(x,y);
307 x=txd(x);
308 y=txd(txd(y)); // untwist
309
310 x.conj();
311 y.conj(); y*=Fr; // ^p
312
313 tx=txx(x); tty=txx(txx(y));
314 S.set(tx,tty); // twist again
315
316 x.conj();
317 y.conj(); y*=Fr; // ^(p^2)
318
319 tx=txx(x); tty=txx(txx(y));
320 T.set(tx,tty); // twist
321
322 S+=K;
323 S*=t;
324 S-=T;
325 S-=K;
326 }
327
main()328 int main()
329 {
330 ifstream common("k4mnt.ecs"); // elliptic curve parameters
331 miracl* mip=&precision;
332 ECn Alice,Bob,sA,sB;
333 ECn2 Server,sS,tP;
334 ZZn2 res,sp,ap,bp,Fr,x,y;
335 ZZn4 X,Y,X2,Y2;
336 Big a,b,s,ss,p,q,r,B,delta,fr,t,t1;
337
338 int bits,A;
339 time_t seed;
340
341 cout << "Started" << endl;
342 common >> bits;
343 mip->IOBASE=16;
344 common >> p;
345 common >> A;
346 common >> B;
347 common >> q >> delta;
348 common >> fr;
349
350 cout << "Initialised... " << p%24 << endl;
351
352 t=p+1-COF*q;
353 t1=p-COF*q;
354
355 //cout << "p= " << p << endl;
356 //cout << "p%8= " << p%8 << endl;
357 cout << "t= " << t << endl;
358 //cout << "delta= " << delta << endl;
359
360 time(&seed);
361 irand((long)seed);
362
363 #ifdef AFFINE
364 ecurve(A,B,p,MR_AFFINE);
365 #endif
366 #ifdef PROJECTIVE
367 ecurve(A,B,p,MR_PROJECTIVE);
368 #endif
369
370 // Fr=get_frobenius_constant();
371
372 Fr=(ZZn2)fr;
373 mip->IOBASE=16;
374 mip->TWIST=MR_QUADRATIC; // map Server to point on twisted curve E(Fp2)
375
376 // hash Identities to curve point
377
378 ss=rand(q); // TA's super-secret
379
380 cout << "Mapping Server ID to point" << endl;
381 Server=hash2((char *)"Server");
382 cofactor(Server,Fr,t); // multiply by cofactor (p-1+t)
383 Server*=COF;
384
385 cout << "Mapping Alice & Bob ID's to points" << endl;
386 Alice=hash_and_map((char *)"Alice",COF);
387
388 Bob= hash_and_map((char *)"Robert",COF);
389 cout << "Alice, Bob and the Server visit Trusted Authority" << endl;
390
391 sS=ss*Server;
392 sA=ss*Alice;
393 sB=ss*Bob;
394
395 cout << "Alice and Server Key Exchange" << endl;
396
397 a=rand(q); // Alice's random number
398 s=rand(q); // Server's random number
399
400 if (!ate(Server,sA,t1,Fr,delta,res)) cout << "Trouble" << endl;
401
402 if (powl(res,q)!=(ZZn2)1)
403 {
404 cout << "Wrong group order - aborting" << endl;
405 exit(0);
406 }
407
408 ap=powl(res,a);
409
410 if (!ate(sS,Alice,t1,Fr,delta,res)) cout << "Trouble" << endl;
411 if (powl(res,q)!=(ZZn2)1)
412 {
413 cout << "Wrong group order - aborting" << endl;
414 exit(0);
415 }
416 sp=powl(res,s);
417
418 cout << "Alice Key= " << H2(powl(sp,a)) << endl;
419 cout << "Server Key= " << H2(powl(ap,s)) << endl;
420
421 cout << "Bob and Server Key Exchange" << endl;
422
423 b=rand(q); // Bob's random number
424 s=rand(q); // Server's random number
425
426 if (!ate(Server,sB,t1,Fr,delta,res)) cout << "Trouble" << endl;
427 if (powl(res,q)!=(ZZn2)1)
428 {
429 cout << "Wrong group order - aborting" << endl;
430 exit(0);
431 }
432 bp=powl(res,b);
433
434 if (!ate(sS,Bob,t1,Fr,delta,res)) cout << "Trouble" << endl;
435 if (powl(res,q)!=(ZZn2)1)
436 {
437 cout << "Wrong group order - aborting" << endl;
438 exit(0);
439 }
440 sp=powl(res,s);
441
442 cout << "Bob's Key= " << H2(powl(sp,b)) << endl;
443 cout << "Server Key= " << H2(powl(bp,s)) << endl;
444
445 return 0;
446 }
447