From: Jim Choate <ravage@ssz.com>
Date: Wed, 10 Dec 1997 05:49:49 +0800
To: cypherpunks@ssz.com (Cypherpunks Distributed Remailer)
Subject: Elliptic Curve Tidbit (fwd)
Message-ID: <199712092201.QAA06107@einstein.ssz.com>
MIME-Version: 1.0
Content-Type: text



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