1 //==============================================================================================
2 //
3 // This file is part of LiDIA --- a library for computational number theory
4 //
5 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
6 //
7 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
8 //
9 //----------------------------------------------------------------------------------------------
10 //
11 // $Id$
12 //
13 // Author : Volker Mueller (VM), Markus Maurer (MM), Andrea Rau (AR)
14 // Changes : See CVS log
15 //
16 //==============================================================================================
17
18
19
20 #ifdef HAVE_CONFIG_H
21 # include "config.h"
22 #endif
23 #include "LiDIA/rational_factorization.h"
24 #include "LiDIA/eco_prime.h"
25 #include "LiDIA/trace_list.h"
26 #include "LiDIA/EC_domain_parameters_P1363.h"
27 #include "LiDIA/timer.h"
28
29 #include <cstdlib> // declares exit()
30
31
32 #ifdef LIDIA_NAMESPACE
33 namespace LiDIA {
34 #endif
35
36
37
38 int EC_domain_parameters_P1363::GFP = 1;
39 int EC_domain_parameters_P1363::GF2N = 1;
40
41
42 lidia_size_t EC_domain_parameters_P1363::defaultBitsize_ = 160;
43 lidia_size_t EC_domain_parameters_P1363::defaultPercentage_ = 10;
44
45
46
47 //
48 // Constructor / destructor
49 //
50
EC_domain_parameters_P1363()51 EC_domain_parameters_P1363::EC_domain_parameters_P1363()
52 {
53 initialized = false;
54 }
55
56
57
~EC_domain_parameters_P1363()58 EC_domain_parameters_P1363::~EC_domain_parameters_P1363()
59 {
60 }
61
62
63
64 //
65 // assignments and access
66 //
67
default_bitsize()68 lidia_size_t EC_domain_parameters_P1363::default_bitsize()
69 {
70 return EC_domain_parameters_P1363::defaultBitsize_;
71 }
72
73
74
default_percentage()75 lidia_size_t EC_domain_parameters_P1363::default_percentage()
76 {
77 return EC_domain_parameters_P1363::defaultPercentage_;
78 }
79
80
81
assign(const EC_domain_parameters_P1363 & I)82 void EC_domain_parameters_P1363::assign(const EC_domain_parameters_P1363 & I)
83 {
84
85 if (this != &I) {
86 initialized = I.initialized;
87
88 if (initialized) {
89 a = I.a;
90 b = I.b;
91 q = I.q;
92 r = I.r;
93 k = I.k;
94 G = I.G;
95 }
96 }
97 }
98
99
100
101 EC_domain_parameters_P1363 &
operator =(const EC_domain_parameters_P1363 & I)102 EC_domain_parameters_P1363::operator = (const EC_domain_parameters_P1363 & I)
103 {
104 this->assign(I);
105 return *this;
106 }
107
108
109
110 const bigint & EC_domain_parameters_P1363
get_q() const111 ::get_q () const
112 {
113 if (!initialized)
114 lidia_error_handler("EC_domain_parameters_P1363", "get_q::not initialized");
115
116 return q;
117 }
118
119
120
121 const gf_element & EC_domain_parameters_P1363
get_a() const122 ::get_a () const
123 {
124 if (!initialized)
125 lidia_error_handler("EC_domain_parameters_P1363", "get_a::not initialized");
126
127 return a;
128 }
129
130
131
132 const gf_element & EC_domain_parameters_P1363
get_b() const133 ::get_b () const
134 {
135 if (!initialized)
136 lidia_error_handler("EC_domain_parameters_P1363", "get_b::not initialized");
137
138 return b;
139 }
140
141
142
143 const bigint & EC_domain_parameters_P1363
get_k() const144 ::get_k () const
145 {
146 if (!initialized)
147 lidia_error_handler("EC_domain_parameters_P1363", "get_k::not initialized");
148
149 return k;
150 }
151
152
153
154 const bigint & EC_domain_parameters_P1363
get_r() const155 ::get_r () const
156 {
157 if (!initialized)
158 lidia_error_handler("EC_domain_parameters_P1363", "get_r::not initialized");
159
160 return r;
161 }
162
163
164
165 const point< gf_element > & EC_domain_parameters_P1363
get_G() const166 ::get_G () const
167 {
168 if (!initialized)
169 lidia_error_handler("EC_domain_parameters_P1363", "get_G::not initialized");
170
171 return G;
172 }
173
174
175
176 void EC_domain_parameters_P1363
get_twist_coeff(gf_element & new_a,gf_element & new_b)177 ::get_twist_coeff(gf_element & new_a, gf_element & new_b)
178 {
179 gf_element d(a);
180 do {
181 d.randomize();
182 } while (jacobi(d.polynomial_rep().const_term(), d.characteristic()) != -1);
183
184 new_a = a*d*d;
185 new_b = b*d*d*d;
186 }
187
188
189
190 //
191 // Curve generation
192 //
193
194 void EC_domain_parameters_P1363
generate_parameters(int field,int info)195 ::generate_parameters(int field, int info)
196 {
197 this->generate_parameters(field, this->default_bitsize(),
198 this->default_percentage(), info);
199 }
200
201
202
203 void EC_domain_parameters_P1363
generate_parameters(int field,int bitsize_factor,int info)204 ::generate_parameters(int field, int bitsize_factor, int info)
205 {
206 this->generate_parameters(field, bitsize_factor,
207 this->default_percentage(), info);
208 }
209
210
211
212 //--------------------------------------------------------------------
213 //
214
215
generate_parameters(int field,int bitsize_factor,int percentage,int info)216 void EC_domain_parameters_P1363::generate_parameters(int field,
217 int bitsize_factor,
218 int percentage,
219 int info)
220 {
221 bigint p, co_factor, found_co_factor, found_co_factor_tw, order;
222 int tries = 1;
223 rational_factorization rf_order;
224
225 // here we need something like
226 // if(field != GFP)
227 // lidia_error_handler("not yet implemented");
228
229 // Initialize timer
230 //
231 timer t; t.set_print_mode (HMS_MODE);
232 timer t2; t2.set_print_mode(HMS_MODE);
233
234 // Initialize counters
235 //
236 int both_abort = 0;
237 int no_abort = 0;
238
239 // computation control
240 //
241 bool good_curve_Etw;
242 bool good_curve_E;
243 bool stop_computation;
244
245 shift_left(p, bigint(1), bitsize_factor - 1);
246
247 // determine cofactor = 2^{n}, n = "percentage" percent of bitsize_factor.
248 //
249 if (percentage >= 100)
250 co_factor = p;
251 else {
252 co_factor.assign_one();
253 if (percentage != 0 && (static_cast<int>((static_cast<double>(bitsize_factor) / 100.0)
254 * static_cast<double>(percentage)) - 1 > 0))
255 shift_left(co_factor, co_factor,
256 static_cast<int>((static_cast<double>(bitsize_factor)/100.0) *
257 static_cast<double>(percentage)) - 1);
258
259 if (co_factor > p)
260 co_factor = p;
261 }
262
263 // determine characteristic p of prime field
264 //
265 multiply(p, p, co_factor);
266 p = next_prime(p-1);
267
268 // The field
269 //
270 galois_field theField(p);
271 bigmod::set_modulus(p);
272
273 // Twist coordinates
274 //
275 gf_element a4tw(theField), a6tw(theField);
276
277
278 // initialize computation
279 //
280 elliptic_curve< gf_element > e;
281 trace_list tl;
282 trace_mod tm;
283 udigit ll;
284 long qq;
285 eco_prime ep;
286 bigint g;
287
288 if (info >= MUCH_INFO) {
289 ep.set_info_mode(1);
290 trace_list::set_info_mode(1);
291 }
292 else {
293 ep.set_info_mode(0);
294 trace_list::set_info_mode(0);
295 }
296 rf_order.verbose(0);
297 t.start_timer();
298
299
300 //
301 // Choose curves until strong one is found.
302 // Use early abort strategy on curve and its twist.
303 //
304
305 std::cout << "\nCharacteristic : q = " << p;
306 std::cout << " (" << p.bit_length() << " bits)" << std::endl;
307 std::cout << "Upper bound for the cofactor is " << co_factor;
308 std::cout << " (" << co_factor.bit_length() << " bits)" << std::endl;
309 std::cout << std::endl;
310
311 do {
312 // Choose next curve
313 //
314 a.assign_zero(theField);
315 b.assign_zero(theField);
316 a.randomize();
317 b.randomize();
318
319 if (info >= LITTLE_INFO) {
320 std::cout << "\n###############################################################";
321 std::cout << "\nChoosing random E : \n\na = " << a << "\nb = " << b << std::endl;
322 }
323
324 // initialize for new curve
325 //
326 tries ++;
327 found_co_factor = 1;
328 found_co_factor_tw = 1;
329
330 good_curve_E = true;
331 good_curve_Etw = true;
332 stop_computation = false;
333
334 e.set_coefficients(a, b);
335 ep.set_curve(a, b);
336 t2.start_timer();
337
338 // Test supersingularity
339 //
340 if (info >= MUCH_INFO)
341 std::cout << "\nTesting E for supersingularity ... " << std::flush;
342
343 if (ep.is_supersingular(order)) {
344 if (info >= MUCH_INFO)
345 std::cout << "YES" << std::endl;
346 continue;
347 }
348 else
349 if (info >= MUCH_INFO)
350 std::cout << "NO" << std::endl;
351
352 // Test for isogeny to curve with j-invariant 0 or 1728
353 //
354
355 if (info >= MUCH_INFO)
356 std::cout << "Testing whether E is Fq-isogenous to curve with "
357 "j-invariant 0 or 1728 ... " << std::flush;
358
359 if (ep.check_j_0_1728 (order)) {
360 if (info >= MUCH_INFO)
361 std::cout << "YES" << std::endl;
362 continue;
363 }
364 else
365 if (info >= MUCH_INFO)
366 std::cout << "NO" << std::endl;
367
368
369 // Determine coefficients of twist.
370 //
371 get_twist_coeff(a4tw, a6tw);
372
373 // Test twist for supersingularity
374 //
375 if (info >= MUCH_INFO)
376 std::cout << "Testing twist(E) for supersingularity ... " << std::flush;
377
378 if (ep.is_supersingular(order)) {
379 if (info >= MUCH_INFO)
380 std::cout << "YES" << std::endl;
381 continue;
382 }
383 else
384 if (info >= MUCH_INFO)
385 std::cout << "NO" << std::endl;
386
387
388 // Test twist for isogeny to curve with j-invariant 0 or 1728
389 //
390 if (info >= MUCH_INFO)
391 std::cout << "Testing whether twist(E) is Fq-isogenous to curve "
392 "with j-invariant 0 or 1728 ... " << std::flush;
393
394 if (ep.check_j_0_1728 (order)) {
395 if (info >= MUCH_INFO)
396 std::cout << "YES" << std::endl;
397 continue;
398 }
399 else
400 if (info >= MUCH_INFO)
401 std::cout << "NO" << std::endl;
402
403
404 // Compute trace modulo 2
405 //
406 tl.clear();
407 tl.set_curve(e);
408
409 // trace mod 2
410 //
411 if (info >= MUCH_INFO) {
412 std::cout << std::endl;
413 std::cout << "-------------------------------------------------------" << std::endl;
414 std::cout << "Working on prime l = 2" << std::endl;
415 }
416
417 ep.compute_mod_2_power();
418 tm.set_vector(ep.get_prime(), ep.get_relation());
419 tl.append(tm);
420
421 qq = remainder(p, ep.get_prime());
422 g = gcd(p + 1 - (ep.get_relation())[0], ep.get_prime());
423 if (! g.is_one())
424 multiply(found_co_factor, found_co_factor, g);
425 g = gcd(p + 1 + (ep.get_relation())[0], ep.get_prime());
426 if (! g.is_one())
427 multiply(found_co_factor_tw, found_co_factor_tw, g);
428
429
430 // for each prime ll compute trace mod ll
431 // and check for divisor of group order
432 //
433 ll = 3;
434
435 do {
436 if (found_co_factor > co_factor && found_co_factor_tw > co_factor) {
437 t2.stop_timer();
438 if (info >= LITTLE_INFO) {
439 if (info >= MUCH_INFO)
440 std::cout << "\n";
441 std::cout << "\nTest No. " << tries-1;
442 std::cout <<" (early abort for E and twist(E)) took time " << t2 << std::endl;
443 }
444 both_abort ++;
445 good_curve_E = good_curve_Etw = false;
446 stop_computation = true;
447 }
448 else {
449 if (info >= MUCH_INFO) {
450 std::cout << std::endl;
451 std::cout << "-------------------------------------------------------" << std::endl;
452 std::cout << "Working on prime l = " << ll <<std::endl;
453 }
454
455 if (ep.set_prime(ll)) {
456 ep.compute_splitting_type();
457
458 if (ep.is_elkies()) {
459 ep.compute_trace_elkies();
460
461 qq = remainder(p, ep.get_prime());
462 g = gcd(p + 1 - static_cast<long>(ep.get_relation()[0]), ep.get_prime());
463 if (! g.is_one())
464 multiply(found_co_factor, found_co_factor, g);
465 g = gcd(p + 1 + static_cast<long>(ep.get_relation()[0]), ep.get_prime());
466 if (! g.is_one())
467 multiply(found_co_factor_tw, found_co_factor_tw, g);
468 }
469 else
470 ep.compute_trace_atkin();
471
472 tm.set_vector(ep.get_prime(), ep.get_relation());
473 stop_computation = tl.append(tm);
474 }
475 else
476 if (ll >= 1020)
477 lidia_error_handler("EC_domain_parameters_P1363", "Not "
478 "enough modular equations");
479 else
480 lidia_warning_handler("EC_domain_parameters_P1363",
481 "Modular equation could not be"
482 " found, ignored ...");
483
484 ll = next_prime(ll+1);
485 }
486 } while (!stop_computation);
487
488 // Early abort
489 //
490 if (!good_curve_E && !good_curve_Etw)
491 continue;
492
493
494 // Determine group order of E
495 //
496
497 if (info >= MUCH_INFO)
498 std::cout << "\n";
499 order = tl.bg_search_for_order();
500 no_abort ++;
501 t2.stop_timer();
502 if (info >= LITTLE_INFO) {
503 std::cout << "\nTest No. " << tries-1 << " took time " << t2 <<"\n"<< std::endl;
504 }
505
506 // Test for strong curve E
507 //
508 if (found_co_factor <= co_factor) {
509 t2.start_timer();
510 rf_order.assign(order);
511 good_curve_E = this->is_strong_curve(rf_order, order, co_factor,
512 p, info);
513 t2.stop_timer();
514 if (info >= LITTLE_INFO) {
515 std::cout << "\nTest for strong curve took time "
516 << t2 << std::endl;
517 }
518 }
519 else
520 good_curve_E = false;
521
522
523 // Test for strong twist Etw
524 //
525 if (!good_curve_E) {
526 if (found_co_factor_tw <= co_factor) {
527 t2.start_timer();
528 order = p + 1 + (p+1-order);
529 rf_order.assign(order);
530
531 good_curve_Etw = this->is_strong_curve(rf_order, order,
532 co_factor, p, info);
533 t2.stop_timer();
534 if (info >= LITTLE_INFO) {
535 std::cout << "\nTest for strong twist "
536 << "took time "
537 << t2 << std::endl;
538 }
539
540 if (good_curve_Etw) {
541 a = a4tw;
542 b = a6tw;
543 }
544 }
545 else
546 good_curve_Etw = false;
547 }
548 } while (!good_curve_E && !good_curve_Etw);
549 t.stop_timer();
550
551
552 // Verification of the group order
553 //
554 e.set_coefficients(a, b);
555
556 if (e.probabilistic_test_of_group_order(order)) {
557 if (info >= LITTLE_INFO) {
558 std::cout << "\n\nFOUND GOOD CURVE : ";
559 std::cout << "\nCharacteristic : " << p << " (" << p.bit_length();
560 std::cout << " bits)" << std::flush;
561 std::cout << "\nCoefficient a : "; std::cout << a;
562 std::cout << "\nCoefficient b : "; std::cout << b;
563 std::cout << "\n\nGroup order is " << order << std::endl;
564 std::cout << " = " << rf_order << std::endl;
565 }
566 // Initialize P1363 parameters
567 //
568 q = p;
569 r = rf_order.base(rf_order.no_of_comp()-1);
570 k = order / r;
571
572 // search point G of order r
573 //
574
575 point< gf_element > P;
576 do {
577 P = e.random_point();
578 multiply(G, k, P);
579 } while (G.is_zero());
580
581 if (info >= LITTLE_INFO) {
582 std::cout << "\nPrime Factor r of group order is : " << r << std::endl;
583 std::cout << "Point G of order r : " << G << std::endl;
584 std::cout << "Cofactor k is : " << k << std::endl;
585 std::cout << "\n\nComplete Test took " << tries-1 << " tries and "
586 "time " << t << "\n";
587 std::cout << "\nearly abort for both curves was used in ";
588 std::cout << both_abort << " tests ";
589 std::cout << "\nfull group order comp. was used in "<< no_abort << " tests \n\n";
590 }
591
592 initialized = true;
593 }
594 else {
595 std::cout << "\n\nERROR: Probabilistic correctness test rejects candidate!!\n";
596 std::exit(1);
597 }
598 }
599
600
601
is_strong_curve(rational_factorization & rf_order,const bigint & order,const bigint & co_factor,const bigint & p,int info) const602 bool EC_domain_parameters_P1363::is_strong_curve(rational_factorization &
603 rf_order,
604 const bigint & order,
605 const bigint & co_factor,
606 const bigint & p,
607 int info) const
608 {
609 bool good_curve = true;
610
611
612 if (info >= MUCH_INFO)
613 std::cout << "Checking whether small cofactor is too large ... " << std::flush;
614
615 if (!rf_order.is_prime_factorization()) {
616 rf_order.trialdiv();
617 rf_order.ecm();
618 }
619
620 if (!rf_order.is_prime_factorization()) {
621 good_curve = false;
622 if (info >= MUCH_INFO)
623 std::cout << " --> can not factor order." << std::endl;
624 }
625 else
626 if (order/rf_order.base(rf_order.no_of_comp()-1) <= co_factor) {
627 if (info >= MUCH_INFO)
628 std::cout << "NO" << std::endl;
629 good_curve = true;
630 }
631 else {
632 if (info >= MUCH_INFO) {
633 std::cout << "YES (";
634 std::cout << order/rf_order.base(rf_order.no_of_comp()-1) << ")" << std::endl;
635 }
636 good_curve = false;
637 }
638
639 if (good_curve) {
640 if (info >= MUCH_INFO)
641 std::cout << "\nTesting for anomalous curve ... " << std::flush;
642
643 if (order == p) {
644 if (info >= MUCH_INFO)
645 std::cout << "YES" << std::endl;
646 good_curve = false;
647 }
648 else
649 if (info >= MUCH_INFO)
650 std::cout << "NO" << std::endl;
651 }
652
653 // Test that order does not divide (p^B)-1 for B small
654 // (Reduction to finite fields attack).
655 //
656
657 if (good_curve) {
658 int i;
659 int log2 = p.bit_length() - 1;
660 int stop = static_cast<int>(std::floor(2000.0 / log2));
661
662 if (info >= MUCH_INFO) {
663 std::cout << "Test whether order divides q^k-1 for some 1 <= k <= ";
664 std::cout << stop << " ... " << std::flush;
665 }
666
667 multi_bigmod p_mod(p, order);
668 multi_bigmod ppower_mod(1, order);
669
670 for (i = 1; i <= stop; i++) {
671 multiply(ppower_mod, ppower_mod, p_mod);
672 if (ppower_mod.is_one()) {
673 if (info >= MUCH_INFO)
674 std::cout << "YES (k = " << i << ")" << std::endl;
675 good_curve = false;
676 i = stop+1;
677 }
678 }
679
680 if (good_curve && info >= MUCH_INFO)
681 std::cout << "NO" << std::endl;
682 }
683
684 return good_curve;
685 }
686
687
688
689 #ifdef LIDIA_NAMESPACE
690 } // end of namespace LiDIA
691 #endif
692