6.2 Time estimates for the open problems This subsection provides very rough estimates for the running times to solve the open challenge problems. These estimates are for software implementations; we do not assume that any special hardware for parallelized Pollard rho attacks is used. We consider a k-bit challenge with parameter n. Recall from Section 2.2 that the distributed version of Pollard's rho algorithm using M processors takes approximately /M iterations. Here, each iteration consists of an elliptic curve addition or double together with some rho-method specific operations such as evaluations of hash functions and/or a membership tests.Also recall from Section 2.2 that for binary anomalous curves (Koblitz curves) over F2m the number of iterations can be reduced up to a factor of , and for all other curves up to a factor of . Thus, if a computer can perform l iterations per second, then the number of computer days required for each processor until a discrete logarithm is found is expected to be roughly 1 _______ x _______ 10-5 x _______ machine days l x 60 x 60 x 24 2M lM in the case of binary anomalous curves over F2m, and 1 _______ x _______ 10-5 x _______ machine days l x 60 x 60 x 24 2M lM for all other curves. To illustrate this, consider solving an instance of the ECDLP over F289 with n 289 on a widely available computer, say a Pentium 100. We estimate that a Pentium 100 can perform 16000 iterations per second on a curve over F289. Thus, to find a single logarithm would require the expected running time of 10-5 x _______ x 1 _______ 15550 _______ machine days 16000 M M So, for example, a single Pentium 100 running 24 hours a day would require 15550 days. A network of 3000 such machines would require about 5 days in this instance. When estimating for the open challenge problems, we take into account that the iterations scale quadratically on the number of machine words required by the field. We assume that we work with a 32-bit machine. Then, for example, a 109-bit field requires 4 machine words while a 89-bit field requires only 3 machine words.This means that each iteration in a 109-bit field should cost (4/3)2 as much. Hence, a Pentium 100 can perform about l = (3/4)2 x 16000 = 9000 iterations per second for a curve over F2109. For a curve over a 89-bit prime field, we estimate that a Pentium 100 can perform about l = 48000 iterations per second. For a Koblitz curve over F289, we estimate that a Pentium 100 can perform about l = 24000 iterations per second. Here we assume that iterations are done on orbits of points rather than on points. This slightly increases the time needed for one iteration while it considerably reduces the expected number of iterations. In the tables below, for each open challenge problem we give the expected number of iterations, the estimated number of iterations per second on a Pentium 100, and then the estimated number of machine days on a Pentium 100 according to the displayed formulas above. To relate these run time estimates and the actual run times measured for the solved challenges, we note that a 500 MHz Alpha workstation can perform about 15 times as many iterations per second as a Pentium 100. Using the estimates below, it is expected that the open 97-bit exercise could be solved in a matter of weeks using a network of 3000 computers. The 109-bit Level I challenges are feasible using a very large network of computers. The 131-bit Level I challenges are expected to be infeasible against realistic software and hardware attacks, unless of course a new algorithm for the ECDLP is discovered. The Level II challenges are infeasible given today's computer technology and knowledge. The elliptic curves for these challenges meet the stringent security requirements imposed by forthcoming ANSI banking standards [X963]. An implementation report of the Pollard rho algorithm for solving the ECDLP can be found in [HMV]. An implementation report of the solution of some of the exercises can be found in [Escott]. 6.2.1 Elliptic curves over F2m 6.2.1 Excercises   Estimated number of Challenge elliptic curve operations iterations per second* machine days* ECC2-97 3.5 x 1014 16000 2.5 x 105 6.2.1 Level I challenges   Estimated number of Challenge elliptic curve operations iterations per second* machine days* ECC2-109 2.3 x 1016 9000 5.4 x 107 ECC2K-108 1.5 x 1015 13500 1.3 x 106 ECC2-131 4.6 x 1019 5760 3.1 x 1010 ECC2K-130 2.9 x 1018 8640 3.8 x 109 6.2.1 Level II challenges   Estimated number of Challenge elliptic curve operations iterations per second* machine days* ECC2-163 3 x 1024 4000 2.9 x 1015 ECC2K-163 2.4 x 1023 6000 4.6 x 1014 ECC2-191 5 x 1028 4000 1.4 x 1020 ECC2-238 5.9 x 1035 2250 3.0 x 1027 ECC2K-238 3.8 x 1034 3375 1.3 x 1026 ECC2-353 1.2 x 1053 1000 1.4 x 1045 ECC2K-358 3.6 x 1052 1500 2.8 x 1044 6.2.2 Elliptic curves over FP 6.2.2 Level I challenges   Estimated number of Challenge elliptic curve operations iterations per second* machine days* ECCp-109 2.3 x 1016 27000 9.7 x 106 ECCp-131 4.6 x 1019 17280 3.1 x 1010 6.2.2 Level II challenges   Estimated number of Challenge elliptic curve operations iterations per second* machine days* ECCp-163 3 x 1024 12000 2.9 x 1015 ECCp-191 5 x 1028 12000 4.8 x 1019 ECCp-239 8.3 x 1035 7750 1.2 x 1027 ECCp-359 9.6 x 1053 3000 3.7 x 1045 * on a Pentium 100

Copyright © Certicom Corp., 1997-2000. All rights reserved. Information subject to change. http://www.certicom.com