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=8 ake4sbt.cpp zzn4.cpp zzn2.cpp ecn2.cpp big.cpp zzn.cpp
9 ecn.cpp miracl.lib
10 Fastest using COMBA build for 256-bit mod-mul
11
12 Scott-Barreto Curve - Tate pairing
13
14 The file kw4.ecs is required
15 Security is G160/F1024 (160-bit group, 1024-bit field)
16
17 Modified to prevent sub-group confinement attack
18
19 NOTE: assumes p = 3 mod 8, p is 256-bits
20
21 **** NEW **** Based on the observation by R. Granger and D. Page and N.P. Smart in "High Security
22 Pairing-Based Cryptography Revisited" that multi-exponentiation can be used for the final exponentiation
23 of the Tate pairing, we suggest the Power Pairing, which calculates E(P,Q,e) = e(P,Q)^e, where the
24 exponentiation by e is basically for free, as it can be folded into the multi-exponentiation.
25
26 */
27
28 #include <iostream>
29 #include <fstream>
30 #include <string.h>
31 #include "ecn.h"
32 #include <ctime>
33 #include "ecn2.h"
34 #include "zzn4.h"
35
36 using namespace std;
37
38 Miracl precision(12,0);
39
40 // Using SHA-1 as basic hash algorithm
41
42 #define HASH_LEN 20
43
44 //
45 // Define one or the other of these
46 //
47 // Which is faster depends on the I/M ratio - See imratio.c
48 // Roughly if I/M ratio > 16 use PROJECTIVE, otherwise use AFFINE
49 //
50
51 #ifdef MR_AFFINE_ONLY
52 #define AFFINE
53 #else
54 #define PROJECTIVE
55 #endif
56
57 //
58 // Tate Pairing Code
59 //
60 // Extract ECn point in internal ZZn format
61 //
62
extract(ECn & A,ZZn & x,ZZn & y)63 void extract(ECn& A,ZZn& x,ZZn& y)
64 {
65 x=(A.get_point())->X;
66 y=(A.get_point())->Y;
67 }
68
69 #ifdef PROJECTIVE
extract(ECn & A,ZZn & x,ZZn & y,ZZn & z)70 void extract(ECn& A,ZZn& x,ZZn& y,ZZn& z)
71 {
72 big t;
73 x=(A.get_point())->X;
74 y=(A.get_point())->Y;
75 t=(A.get_point())->Z;
76 if (A.get_status()!=MR_EPOINT_GENERAL) z=1;
77 else z=t;
78 }
79 #endif
80
81 //
82 // Line from A to destination C. Let A=(x,y)
83 // Line Y-slope.X-c=0, through A, so intercept c=y-slope.x
84 // Line Y-slope.X-y+slope.x = (Y-y)-slope.(X-x) = 0
85 // Now evaluate at Q -> return (Qy-y)-slope.(Qx-x)
86 //
87
line(ECn & A,ECn & C,ZZn & slope,ZZn2 & Qx,ZZn2 & Qy)88 ZZn4 line(ECn& A,ECn& C,ZZn& slope,ZZn2& Qx,ZZn2& Qy)
89 {
90 ZZn4 w;
91 ZZn2 m=Qx;
92 ZZn x,y,z,t;
93 #ifdef AFFINE
94 extract(A,x,y);
95 m-=x; m*=slope;
96 w.set((ZZn2)-y,Qy); w-=m;
97 #endif
98 #ifdef PROJECTIVE
99 extract(A,x,y,z);
100 x*=z; t=z; z*=z; z*=t;
101 x*=slope; t=slope*z;
102 m*=t; m-=x; t=z;
103 extract(C,x,x,z);
104 m+=(z*y); t*=z;
105
106 w.set(m,-Qy*t);
107
108 #endif
109 return w;
110 }
111
112 //
113 // Add A=A+B (or A=A+A)
114 // Bump up num
115 //
116
g(ECn & A,ECn & B,ZZn2 & Qx,ZZn2 & Qy)117 ZZn4 g(ECn& A,ECn& B,ZZn2& Qx,ZZn2& Qy)
118 {
119 int type;
120 ZZn lam;
121 big ptr;
122 ECn P=A;
123
124 // Evaluate line from A
125 type=A.add(B,&ptr);
126 if (!type) return (ZZn4)1;
127 lam=ptr;
128 return line(P,A,lam,Qx,Qy);
129 }
130
131 //
132 // Tate Pairing - note denominator elimination has been applied
133 //
134 // P is a point of order q. Q(x,y) is a point of order m.q.
135 // Note that P is a point on the curve over Fp, Q(x,y) a point on the
136 // extension field Fp^2
137 //
138 // New! Power Pairing calculates E(P,Q,e) = e(P,Q)^e at no extra cost!
139 //
140
power_tate(ECn & P,ECn2 Q,Big & q,Big * cf,ZZn2 & Fr,Big & e,ZZn2 & r)141 BOOL power_tate(ECn& P,ECn2 Q,Big& q,Big *cf,ZZn2 &Fr,Big &e,ZZn2& r)
142 {
143 int i,nb;
144 ECn A;
145 ZZn4 w,res,a[2];
146 ZZn2 Qx,Qy;
147 Big carry,ex[2],p=get_modulus();
148 // ZZn4 Y,X;
149
150 Q.get(Qx,Qy);
151 // Qx=-tx(Qx)/2; // convert from twist to (x,0),(0,y)
152 // Qy/=2;
153
154 Qx=txd(Qx);
155 Qy=txd(txd(Qy));
156
157 // cout << "Qx= " << Qx << endl;
158 // cout << "Qy= " << Qy << endl;
159
160 // X.set(Qx,(ZZn2)0);
161 // Y.set((ZZn2)0,Qy);
162
163 // cout << "Y^2= " << Y*Y << endl;
164 // cout << "X^3+AX+B= " << X*X*X+getA()*X+getB() << endl;
165
166 res=1;
167
168 /* Left to right method */
169 A=P;
170 nb=bits(q);
171 for (i=nb-2;i>=0;i--)
172 {
173 res*=res;
174 res*=g(A,A,Qx,Qy);
175 if (bit(q,i))
176 res*=g(A,P,Qx,Qy);
177 }
178
179 if (!A.iszero() || res.iszero()) return FALSE;
180 w=res;
181 w.powq(Fr); w.powq(Fr); // ^(p^2-1)
182 res=w/res;
183
184 res.mark_as_unitary();
185
186 if (e.isone())
187 {
188 ex[0]=cf[0];
189 ex[1]=cf[1];
190 }
191 else
192 { // cf *= e
193 carry=mad(cf[1],e,(Big)0,p,ex[1]);
194 mad(cf[0],e,carry,p,ex[0]);
195 }
196
197 a[0]=a[1]=res;
198 a[0].powq(Fr);
199 res=pow(2,a,ex);
200
201 r=real(res); // compression
202
203 if (r.isunity()) return FALSE;
204 return TRUE;
205 }
206
207 //
208 // Hash functions
209 //
210
H1(char * string)211 Big H1(char *string)
212 { // Hash a zero-terminated string to a number < modulus
213 Big h,p;
214 char s[HASH_LEN];
215 int i,j;
216 sha sh;
217
218 shs_init(&sh);
219
220 for (i=0;;i++)
221 {
222 if (string[i]==0) break;
223 shs_process(&sh,string[i]);
224 }
225 shs_hash(&sh,s);
226 p=get_modulus();
227 h=1; j=0; i=1;
228 forever
229 {
230 h*=256;
231 if (j==HASH_LEN) {h+=i++; j=0;}
232 else h+=s[j++];
233 if (h>=p) break;
234 }
235 h%=p;
236 return h;
237 }
238
H2(ZZn2 x)239 Big H2(ZZn2 x)
240 { // Hash an Fp2 to a big number
241 sha sh;
242 Big a,u,v;
243 char s[HASH_LEN];
244 int m;
245
246 shs_init(&sh);
247 x.get(u,v);
248
249 a=u;
250 while (a>0)
251 {
252 m=a%256;
253 shs_process(&sh,m);
254 a/=256;
255 }
256 a=v;
257 while (a>0)
258 {
259 m=a%256;
260 shs_process(&sh,m);
261 a/=256;
262 }
263 shs_hash(&sh,s);
264 a=from_binary(HASH_LEN,s);
265 return a;
266 }
267
268 // Hash and map a Server Identity to a curve point E(Fp2)
269
hash2(char * ID)270 ECn2 hash2(char *ID)
271 {
272 ECn2 T;
273 ZZn2 x;
274 Big x0,y0=0;
275
276 x0=H1(ID);
277 do
278 {
279 x.set(x0,y0);
280 x0+=1;
281 }
282 while (!is_on_curve(x));
283 T.set(x);
284
285 // cout << "T= " << T << endl;
286
287 return T;
288 }
289
290 // Hash and map a Client Identity to a curve point E(Fp)
291
hash_and_map(char * ID,Big cof)292 ECn hash_and_map(char *ID,Big cof)
293 {
294 ECn Q;
295 Big x0=H1(ID);
296
297 while (!is_on_curve(x0)) x0+=1;
298 Q.set(x0); // Make sure its on E(F_p)
299
300 Q*=cof;
301 return Q;
302 }
303
get_frobenius_constant()304 ZZn2 get_frobenius_constant()
305 {
306 ZZn2 Fr;
307 Big p=get_modulus();
308 switch (get_mip()->pmod8)
309 {
310 case 5:
311 Fr.set((Big)0,(Big)1); // = (sqrt(-2)^(p-1)/2
312 break;
313 case 3: // = (1+sqrt(-1))^(p-1)/2
314 case 7: // = (1+sqrt(-2))^(p-1)/2
315 Fr.set((Big)1,(Big)1);
316 default: break;
317 }
318 return pow(Fr,(p-1)/2);
319 }
320
321 #define COF 58
322
main()323 int main()
324 {
325 ifstream common("kw4.ecs"); // elliptic curve parameters
326 miracl* mip=&precision;
327 ECn Alice,Bob,sA,sB;
328 ECn2 Server,sS;
329 ZZn2 res,sp,ap,bp,wa,wb,w1,w2;
330 ZZn ww;
331 ZZn4 w;
332 ZZn2 Fr;
333 Big a,b,s,ss,p,q,r,B,cof,t,qcof;
334 Big cf[2];
335 // this is read-only
336 // and never copied.
337 int i,bitz,A;
338 time_t seed;
339
340 cout << "Started" << endl;
341 common >> bitz;
342 mip->IOBASE=16;
343 common >> p;
344 common >> A;
345 common >> B;
346 common >> cof; // #E/q
347 common >> q; // low hamming weight q
348 common >> cf[0]; // [(p^2+1)/q]/p
349 common >> cf[1]; // [(p^2+1)/q]%p
350
351 cout << "Initialised... " << p%8 << endl;
352 cout << "cf= " << cf[0]*p+cf[1] << endl;
353
354 //
355 // Note: COF*q has a low hamming weight for this particular curve - so use this instead..
356 //
357
358 qcof=q*COF;
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 // cout << "qnr= " << get_mip()->qnr << endl;
373
374 mip->IOBASE=16;
375 mip->TWIST=MR_QUADRATIC; // map Server to point on twisted curve E(Fp2)
376
377 // hash Identities to curve point
378
379 ss=rand(q); // TA's super-secret
380
381 cout << "Mapping Server ID to point" << endl;
382 Server=hash2((char *)"Server");
383
384 cout << "Mapping Alice & Bob ID's to points" << endl;
385 Alice=hash_and_map((char *)"Alice",cof);
386
387 Bob= hash_and_map((char *)"Robert",cof);
388 cout << "Alice, Bob and the Server visit Trusted Authority" << endl;
389
390 sS=ss*Server;
391 sA=ss*Alice;
392 sB=ss*Bob;
393
394 cout << "Alice and Server Key Exchange" << endl;
395
396 a=rand(q); // Alice's random number
397 s=rand(q); // Server's random number
398
399 if (!power_tate(sA,Server,qcof,cf,Fr,a,res)) cout << "Trouble" << endl;
400
401 if (powl(res,q)!=(ZZn2)1)
402 {
403 cout << "res= " << res << endl;
404 cout << "Wrong group order - aborting" << endl;
405 exit(0);
406 }
407 // ap=powl(res,a);
408 ap=res;
409
410 if (!power_tate(Alice,sS,qcof,cf,Fr,s,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 sp=res;
418
419 cout << "Alice Key= " << H2(powl(sp,a)) << endl;
420 cout << "Server Key= " << H2(powl(ap,s)) << endl;
421
422 cout << "Bob and Server Key Exchange" << endl;
423
424 b=rand(q); // Bob's random number
425 s=rand(q); // Server's random number
426
427 if (!power_tate(sB,Server,qcof,cf,Fr,b,res)) cout << "Trouble" << endl;
428 if (powl(res,q)!=(ZZn2)1)
429 {
430 cout << "Wrong group order - aborting" << endl;
431 exit(0);
432 }
433 // bp=powl(res,b);
434 bp=res;
435
436 if (!power_tate(Bob,sS,qcof,cf,Fr,s,res)) cout << "Trouble" << endl;
437 if (powl(res,q)!=(ZZn2)1)
438 {
439 cout << "Wrong group order - aborting" << endl;
440 exit(0);
441 }
442 // sp=powl(res,s);
443 sp=res;
444
445 cout << "Bob's Key= " << H2(powl(sp,b)) << endl;
446 cout << "Server Key= " << H2(powl(bp,s)) << endl;
447
448 return 0;
449 }
450
451