Certicom ECC Challenge Cracked

Certicom ECC Challenge Cracked
from TBTF for 1997-12-08

Certicom is a maker of eliptical-curve encryption software. ECC algorithms 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 mathematics and cryptosystems research community.

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 challenge.

On 1/26 Robery Harley <Robert.Harley at inria dot fr> announced that he and Wayne Baisley had cracked one of two first-level warmup exercises, a 79-bit problem designated ECCp-79. Here is harley's letter.

To: certicom-ecc-challenge@certicom.com
6th of December, 1997.
Dear Anonymous,
Certicom's professed aim in setting its ECC challenge is to encourage research into secure cryptosystems based on elliptic curve discrete logarithms. Yet Certicom is a member of the Key Recovery Alliance, a lobby group whose purpose is to promote the use of back-doors allowing supposedly secure communications to be intercepted. How are these contradictory positions reconciled?
The solution to your ECCp-79 problem is the residue class of 92221507219705345685350 modulo 466597814831947642887217. It was found by Wayne Baisley and myself using several Digital Alpha workstations running Linux and Digital Unix at the Institut National de Recherche en Informatique et Automatique (INRIA), at Fermi National Accelerator Laboratory and at the California Institute of Technology C.S. Department.
The method used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a random function (the same on all machines) until a collision was detected at 17:58 today at INRIA, Rocquencourt, France by a 500MHz Linux machine. This machine did 25 billion elliptic curve operations per day. The peak rate of all machines was approximately 6 six times as much. A total of about 1400 billion iterations were performed.
If this is the first correct submission, please send the prize (a copy of "Handbook of Applied Cryptography" and Maple software) to the following address:
  Robert Harley,
  c/o Sylvie Loubressac,
  Projet CRISTAL,
  INRIA,
  Domaine de Voluceau - Rocquencourt,
  78153 Le Chesnay,
  France.

Thank you,
  Rob.
     .-.                     Robert.Harley@inria.fr                    .-.
    /   \           .-.                                 .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'                     `-'         \   /
             `-'  Linux + 500MHz Alpha + 256MB SDRAM = heaven  `-'

[ TBTF for 1997-12-08 ]


TBTF HOME	CURRENT ISSUE	TBTF LOG	TABLE OF CONTENTS	TBTF THREADS	SEARCH TBTF

Certicom ECC Challenge Cracked from TBTF for 1997-12-08

Certicom ECC Challenge Cracked
from TBTF for 1997-12-08