From: "Trei, Peter" <ptrei@securitydynamics.com>
Date: Mon, 8 Dec 1997 22:27:25 +0800
To: "'cryptography@c2.net>
Subject: ECCp-79 challenge cracked
Message-ID: <6B5344C210C7D011835C0000F80127668B1587@exna01.securitydynamics.com>
MIME-Version: 1.0
Content-Type: text/plain



I'm enclosing two messages from sci.crypt:

Peter Trei

------------------------------------------------------------------------
First message

On sci.crypt Volker Mueller <vmueller@cdc.informatik.tu-darmstadt.de>
wrote:
>[...] Maybe the problem  is not so easy. The biggest  DL computation
for an
>elliptic curve was  a 19 digit  prime order computation (up to my
>knowledge).  The first Certicom "exercise"  has 79 bits or 24 decimal
>digits.
>
>Cheers,  Volker

You're right, the so-called "exercise"  was not so easy!

However a few Alphas and some optimised code got through it
eventually.  I just posted the following to Certicom...

-- Rob.

PS: Any volunteers willing to dedicate Alpha CPU time for cracking the
    next challenge?  With a bunch of machines it would be a piece of
cake!


------------------------------------------------------------------------
------
This message is copyright Robert J. Harley, 1997.
If you wish to quote more than one sentence, please quote the whole
thing.

To: certicom-ecc-challenge@certicom.com

                                        Robert J. Harley,
                                        Se`vres, France,
                                        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  `-'
------------------------------------------------------------------------
------

------------------------------------------------------------------------
----------------------------------------------
Second message:


From:         Dimitris Tsapakidis <dimitris@alien.bt.co.uk>
Date:         1997/12/08
Message-ID:   <348BDD10.B5B2E641@alien.bt.co.uk>
Newsgroups:   sci.crypt
[More Headers]


Hello Robert,

Congratulations on your effort. We would like to post some
information on our attempt at BT Labs. We found the private key
after you at 19:58 GMT on Sunday the 7th. We only completed 481
billion ECC operations at a peak rate of 84 billion per day using
170 to 210 machines.

A couple of months ago we contributed 180-250 machines to the
distributed.net/Bovine group attack on RC5-56, peaking at
60 million keys/sec.

  Dimitris