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=16 ake2cpt2.cpp ecn2.cpp zzn2.cpp big.cpp zzn.cpp ecn.cpp miracl.lib
9 using COMBA build
10
11 Cocks-Pinch curve - Type 2 Tate pairing
12
13 Requires file k2.ecs which contains details of non-supersingular
14 elliptic curve, with order divisible by q=2^159+2^17+1, and security
15 multiplier k=2. The prime p is 512 bits
16
17 CHANGES: This version uses a Type 2 pairing
18 Use Lucas functions to evaluate powers.
19 Output of tate pairing is now a ZZn (half-size)
20
21 Modified to prevent sub-group confinement attack
22
23 For a Type 2 curve ecap(P,Q) = e(Trace(P),Q)
24
25 ecap(P,Q) = ecap(Q,P)
26
27 */
28
29 #include <iostream>
30 #include <fstream>
31 #include "ecn.h"
32 #include <ctime>
33 #include "zzn2.h"
34 #include "ecn2.h"
35
36 using namespace std;
37
38 Miracl precision(32,0);
39
40 // Using SHA-512 as basic hash algorithm
41
42 #define HASH_LEN 64
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 ZZn2 line(ECn& A,ECn& C,ZZn& slope,ZZn2& Qx,ZZn2& Qy)
89 {
90 ZZn2 w=Qy,n=Qx;
91 ZZn x,y,z,t;
92
93 #ifdef AFFINE
94 extract(A,x,y);
95 n-=x; n*=slope;
96 w-=y; w-=n;
97
98 #endif
99 #ifdef PROJECTIVE
100 extract(A,x,y,z);
101 x*=z; t=z; z*=z; z*=t;
102 n*=z;
103 n-=x;
104 w*=z;; w-=y;
105 extract(C,x,y,z); // only need z - its the denominator of the slope
106 w*=z;
107 n*=slope;
108 w-=n;
109
110 #endif
111 return w;
112 }
113
114 /*
115
116 ZZn2 vertical(ECn& A,ZZn2& Qx)
117 {
118 ZZn2 n=Qx;
119 ZZn x,y,z;
120 #ifdef AFFINE
121 extract(A,x,y);
122 n-=x;
123 #endif
124 #ifdef PROJECTIVE
125 extract(A,x,y,z);
126 z*=z;
127 n*=z; n-=x;
128 #endif
129 return n;
130 }
131
132 */
133
134 //
135 // Add A=A+B (or A=A+A)
136 // Bump up num
137 //
138
g(ECn & A,ECn & B,ZZn2 & Qx,ZZn2 & Qy)139 ZZn2 g(ECn& A,ECn& B,ZZn2& Qx,ZZn2& Qy)
140 {
141 int type;
142 ZZn lam;
143 ECn P=A;
144 big ptr;
145
146 // Evaluate line from A - lam is line slope
147 type=A.add(B,&ptr);
148 if (!type) return (ZZn2)1;
149 lam=ptr; // in projective case slope = lam/A.z
150
151 return line(P,A,lam,Qx,Qy) /* *conj(vertical(A,Qx)) */ ;
152 }
153
Trace2(ECn2 P)154 ECn2 Trace2(ECn2 P)
155 {
156 ECn R;
157 ECn2 Q;
158 ZZn2 x,y;
159 Big X,Y;
160 P.get(x,y);
161 x=conj(x); y=conj(y);
162 Q.set(x,y);
163 P+=Q;
164 P.norm();
165 return P;
166 }
167
168 //
169 // Tate Pairing - note denominator elimination has been applied
170 //
171 // P is a point of order q. Q(x,y) is a point of order q.
172 // Note that P is a point on the curve over Fp, Q(x,y) a general point on the
173 // curve E(Fp^2)
174 //
175
tate(ECn & P,ECn2 & Q,Big & q,ZZn & r)176 BOOL tate(ECn& P,ECn2& Q,Big& q,ZZn& r)
177 {
178 int i,nb,qnr;
179 ZZn2 res;
180 ZZn2 Qx,Qy;
181 Big p,x,y;
182 ECn A;
183 ECn2 NQ,TQ;
184
185 p=get_modulus();
186
187 // Note that q is fixed - q.P=2^17*(2^142.P + P) + P
188
189 // Now set Q = kQ-Tr(Q) so we can use denominator elimination
190 normalise(P);
191 Q.norm();
192 NQ=Q;
193
194 NQ=2*NQ;
195 TQ=Trace2(Q);
196 NQ-=TQ;
197 NQ.get(Qx,Qy);
198
199 A=P; // remember A
200 nb=bits(q);
201 res=1;
202
203 for (i=nb-2;i>=0;i--)
204 {
205 res*=res; // 2 modmul
206 res*=g(A,A,Qx,Qy);
207
208 if (bit(q,i))
209 res*=g(A,P,Qx,Qy); // executed just once
210 }
211
212 if (!A.iszero() || res.iszero()) return FALSE;
213 res=conj(res)/res; // raise to power of (p-1)
214
215 r=powl(real(res),(p+1)/q); // raise to power of (p+1)/q
216
217 if (r==1) return FALSE;
218 return TRUE;
219 }
220
221 //
222 // Hash functions
223 //
224
H1(char * string)225 Big H1(char *string)
226 { // Hash a zero-terminated string to a number < modulus
227 Big h,p;
228 char s[HASH_LEN];
229 int i,j;
230 sha512 sh;
231
232 shs512_init(&sh);
233
234 for (i=0;;i++)
235 {
236 if (string[i]==0) break;
237 shs512_process(&sh,string[i]);
238 }
239 shs512_hash(&sh,s);
240 p=get_modulus();
241 h=1; j=0; i=1;
242 forever
243 {
244 h*=256;
245 if (j==HASH_LEN) {h+=i++; j=0;}
246 else h+=s[j++];
247 if (h>=p) break;
248 }
249 h%=p;
250 return h;
251 }
252
H2(ZZn x)253 Big H2(ZZn x)
254 { // Hash an Fp to a big number
255 sha sh;
256 Big a,h,p;
257 char s[20];
258 int m;
259
260 shs_init(&sh);
261 a=(Big)x;
262 while (a>0)
263 {
264 m=a%256;
265 shs_process(&sh,m);
266 a/=256;
267 }
268 shs_hash(&sh,s);
269 h=from_binary(20,s);
270 return h;
271 }
272
273 // hash to a *general* point of order q on E(F_p^2)
274
hash2(char * ID)275 ECn2 hash2(char *ID)
276 {
277 ECn2 T;
278 ZZn2 x;
279 Big x0,y0=1; // Note y0 !=0
280
281 x0=H1(ID);
282 do
283 {
284 x.set(x0,y0);
285 x0+=1;
286 }
287 while (!is_on_curve(x));
288 T.set(x);
289
290 return T;
291 }
292
293 // Trace function
294
Trace(ECn2 P)295 ECn Trace(ECn2 P)
296 {
297 ECn R;
298 ECn2 Q;
299 ZZn2 x,y;
300 Big X,Y;
301 P.get(x,y);
302 x=conj(x); y=conj(y);
303 Q.set(x,y);
304 P+=Q;
305
306 P.get(x,y);
307 X=real(x);
308 Y=real(y);
309 R.set(X,Y);
310 return R;
311 }
312
313 /* Note that if #E(Fp) = p+1-t
314 then #E(Fp2) = (p+1-t)(p+1+t) (a multiple of #E(Fp))
315 (Weil's Theorem)
316 */
317
main()318 int main()
319 {
320 ifstream common("k2.ecs"); // elliptic curve parameters
321 miracl* mip=&precision;
322 ECn2 Alice,Bob,sA,sB,Ps,Pt;
323 ECn2 Server,sS;
324 ECn T;
325 ZZn res,sp,ap,bp;
326 Big r,a,b,s,ss,p,q,n,x,y,B,cof,cf1,cf2,t;
327 int nbits,A,qnr;
328 time_t seed;
329
330 common >> nbits;
331 mip->IOBASE=16;
332 common >> p;
333 common >> A;
334 common >> B;
335 common >> cof;
336 common >> q;
337
338 time(&seed);
339 // seed=1;
340 irand((long)seed);
341
342 //
343 // initialise twisted curve...
344 // Server ID is hashed to points on this
345 //
346
347 modulo(p);
348
349 mip->IOBASE=16;
350 t=p+1-cof*q;
351
352 cf1=(p+1-t)/q;
353 cf2=(p+1+t)/q;
354
355 // initialise curve...
356
357 #ifdef AFFINE
358 ecurve(A,B,p,MR_AFFINE);
359 #endif
360 #ifdef PROJECTIVE
361 ecurve(A,B,p,MR_PROJECTIVE);
362 #endif
363
364 // hash Identity to curve point
365
366 ss=rand(q); // TA's super-secret
367
368 cout << "Mapping Server ID to point on curve" << endl;
369 Server=hash2((char *)"Server");
370
371
372 cout << "Server visits trusted authority" << endl;
373 sS=ss*Server;
374 sS*=cf1; sS*=cf2;
375
376 cout << "Mapping Alice & Bob ID's to points on curve" << endl;
377
378 Alice=hash2((char *)"Alice");
379 Bob=hash2((char *)"Bob");
380
381 // Alice, Bob are points of order q
382
383 cout << "Alice and Bob visit Trusted Authority" << endl;
384
385 sA=ss*Alice;
386 sA*=cf1; sA*=cf2;
387 sB=ss*Bob;
388 sB*=cf1; sB*=cf2;
389
390 cout << "Alice and Server Key exchange" << endl;
391
392 a=rand(q); // Alice's random number
393 s=rand(q); // Server's random number
394
395 T=Trace(sA); T*=cf1;
396 if (!tate(T,Server,q,res)) cout << "Trouble" << endl;
397
398 if (powl(res,q)!=(ZZn)1)
399 {
400 cout << "Wrong group order - aborting" << endl;
401 exit(0);
402 }
403 ap=powl(res,a);
404
405 T=Trace(Alice); T*=cf1;
406 if (!tate(T,sS,q,res)) cout << "Trouble" << endl;
407
408 if (powl(res,q)!=(ZZn)1)
409 {
410 cout << "Wrong group order - aborting" << endl;
411 exit(0);
412 }
413
414 sp=powl(res,s);
415
416 cout << "Alice Key= " << H2(powl(sp,a)) << endl;
417 cout << "Server Key= " << H2(powl(ap,s)) << endl;
418
419 cout << "Bob and Server Key exchange" << endl;
420
421 b=rand(q); // Bob's random number
422 s=rand(q); // Server's random number
423
424 T=Trace(sB); T*=cf1;
425 if (!tate(T,Server,q,res)) cout << "Trouble" << endl;
426 if (powl(res,q)!=(ZZn)1)
427 {
428 cout << "Wrong group order - aborting" << endl;
429 exit(0);
430 }
431 bp=powl(res,b);
432
433 T=Trace(Bob); T*=cf1;
434 if (!tate(T,sS,q,res)) cout << "Trouble" << endl;
435 sp=powl(res,s);
436
437 cout << "Bob Key= " << H2(powl(sp,b)) << endl;
438 cout << "Server Key= " << H2(powl(bp,s)) << endl;
439
440 cout << "Alice and Bob's attempted Key exchange" << endl;
441
442 T=Trace(sB); T*=cf1;
443 if (!tate(T,Alice,q,res)) cout << "Trouble" << endl;
444 if (powl(res,q)!=(ZZn)1)
445 {
446 cout << "Wrong group order - aborting" << endl;
447 exit(0);
448 }
449 bp=powl(res,b);
450
451 T=Trace(Bob); T*=cf1;
452 if (!tate(T,sA,q,res)) cout << "Trouble" << endl;
453 ap=powl(res,a);
454
455 cout << "Alice Key= " << H2(powl(bp,a)) << endl;
456 cout << "Bob Key= " << H2(powl(ap,b)) << endl;
457
458 return 0;
459 }
460