Forwarded message:
From owner-austin-cpunks@ssz.com Tue Dec 9 10:26:41 1997 Message-Id: <9712091607.AA17974@sso-austin.sps.mot.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: combee@sso-austin.sps.mot.com (Ben Combee) To: austin-cpunks@ssz.com Subject: Elliptic Curve Tidbit Date: Tue, 9 Dec 97 10:06:53 CST Sender: owner-austin-cpunks@ssz.com Precedence: bulk Reply-To: austin-cpunks@ssz.com
(From today's TBTF) ..First level of Certicom Challenge falls The first shot is fired in an elliptic-curve challenge Certicom is a maker of elliptic-curve encryption software. ECC al- gorithms are drawing considerable interest and study because they hold out the possibility of offering security comparable to the RSA algorithms using smaller keys, therefore requiring less computation. This possibility is not yet considered verified by most of the math- ematics and cryptosystems research community. The assumption that ECC encryption can use smaller keys is the as- sumption that no subexponential-time solution exists for the mathe- matical problem (the elliptic curve discrete logarithm problem) on which ECC is based. The only solution to ECDLP known to exist takes fully exponential time. In contrast, both of the other well-studied mathematical problems that underly modern cryptosystems -- the in- teger factorization problem (e.g., RSA) and the discrete logarithm problem (e.g., Diffie-Hellman) -- have solutions that require only subexponential time. In order to gain exposure and to jumpstart the expert scrutiny that ECC will need if it is to be widely trusted, Certicom is sponsoring a crypto crack contest (they call it a challenge) [17]. The challenge comes in three parts: a series of "warmup exercises" followed by Level 1 and Level 2 problems [18]. A total of $625,000 in prize money is offered. Yesterday Robery Harley <Robert.Harley@inria.fr> announced [19] that he and Wayne Baisley had cracked one of two first-level warmup exer- cises, a 79-bit problem [20] designated ECCp-79. At this writing he has had no reply and the Certicom status page [21] has not been up- dated, so it is possible (but unlikely) that Harley's claim will prove not to be the first. If it is, he will receive as a prize a copy of the Handbook of Applied Cryptography (though somehow I suspect he's already read it) and a Maple V encryption package from Certicom. Certicom estimates the difficulty of the warmup exercises thus:
Using a network of 3000 computers, it is expected that the 79-bit exercise could be solved in a matter of hours, the 89-bit in a matter of days, and the 97-bit in a matter of weeks.
Harley and Baisley applied 6 computers to ECCp-79 and solved it in a bit under 10 days, which would have amounted to less than half an hour had they had 3000 machines to throw at the problem. Harley takes the opportunity presented by his winning claim [19] to tweak Certicom for their membership in the Key Recovery Alliance [22]. If the company replies to him substantively on this point, I'll post their response on the TBTF archive. [17] http://www.certicom.com/chal/index.htm [18] http://www.certicom.com/chal/ch4.htm [19] http://www.tbtf.com/resource/certicom1.html [20] http://www.certicom.com/chal/curves.htm [21] http://www.certicom.com/chal/ch_52.htm [22] http://www.kra.org/roster.html -- Ben Combee, Software Guru (ARMy Core of Engineers) Motorola > MIMS > MSPG > CTSD > Austin Design Center E-mail: ra3781@email.mot.com Phone: (512) 895-7141