ECC2-79 cracké:Alpha Linux l'a fait.

  
>From Robert.Harley@inria.fr Fri Dec 19 15:45:18 1997 
Date: Tue, 16 Dec 1997 14:18:54 +0100 (MET) 
From: Robert Harley  
Reply-To: axp-list@redhat.com 
To: axp-list@redhat.com 
Subject: ECC2-79 cracked: Alpha Linux did it. 
Resent-Date: 16 Dec 1997 13:19:42 -0000 
Resent-From: axp-list@redhat.com 
Resent-cc: recipient list not shown: ; 
 
Jus' sent this out. 
 
------------------------------------------------------------------------------ 
Ce message est la propriété de Robert J. Harley, 1997. 
Si vous désirez en citer plus d'une phrase, citez-le en entier. 
 
To: certicom-ecc-challenge@certicom.com 
 
                                        Robert J. Harley, 
                                        Sèvres, France, 
                                        le 16 décembre 1997. 
 
Cher M. Gallant, 
 
Il y'a deux types de communications. D'un côté, les communications
sécurisées, intelligibles seulement par leur destinataire, et de l'autre
côté tout le reste. Entre les deux, comme Louis Freeh pourrait le dire,
il y'a une "ligne brillante". De quel côté de la ligne se trouve
Certicom?

La solution de votre problème ECC2-79 est la classe résiduelle de 
276856274258963891889538 modulo 302231454903954479142443. Le travail
a été mené par un groupe de fanatiques d'Alpha Linux, et l'équipe de
British Telecom Labs s'est jointe à nous également. Nous avons utilisé
environ 30 Alphas tournant sous Linux, allant des UDBs jusqu'aux stations
de travail 600 MHz. La nouvelle machine 21264 de Jay Estabrook joua un
rôle également! Il y'avait aussi 4 Alphas tournant sous Digital Unix. 
 
Les Participants étaient: 
 
    Andries Brouwer     Andries.Brouwer@cwi.nl 
    Christopher Brown   cbrown@alaska.net 
    Zach Brown          zab@zabbo.net 
    Jay Estabrook       Jay.Estabrook@digital.com 
    Rick Gorton         gorton@amt.tay1.dec.com 
    Oleg Gusev          oleg@usm.uni-muenchen.de 
    Robert Harley       Robert.Harley@inria.fr 
    Richard Holmes      holmes@lanl.gov 
    Andy Isaacson       adi@acm.org 
    Greg Lindahl        lindahl@cs.virginia.edu 
    Jon Nathan          jon@blading.com 
    Dennis Opacki       dopacki@mac-guru.com 
    Vance Petree        vwp@vancpower.com 
    Tim Rowley          tor@cs.brown.edu 
    Michael Sandfort    sandfort@post.cis.smu.edu 
    Jason Shiffer       jshiffer@home.com 
    Aaron Spink         spink@pa.dec.com 
    B.T. Labs Team      jcs@zoo.bt.co.uk 
    Bart-Jan Vrielink   bartjan@mail.de-boulevard.nl 
    Marinos Yannikos    nino@complang.tuwien.ac.at 
    Xiaoguang Zhang     xgz@mn.ms.ornl.gov 
 
    et quelques autres anonymes.   
 
La méthode utilisée était un algorithme "birthday paradox" (paradoxe
d'anniversaire) qui itérait à partir d'un point initial aléatoire (un
par machine) avec une fonction pseudo-aléatoire (la même sur toutes les 
machines) jusqu'à ce qu'une collision soit détectée à 12h47 aujourd'hui.
Un total de 1737410165382 itérations ont été effectuées, trouvant 1617
points "remarquables" et une collision. Notre code source peut être
chargé de:
 
  http://pauillac.inria.fr/~harley/ecdl/ 
 
 
Nous voudrions remercier Michael Wiener pour nous avoir envoyé son
papier, co-écrit avec Paul van Oorschot, dans lequel ils suggéraient
d'utiliser des points remarquables pour des calculs discrets
logarithmiques. Nous avons utilisé cette idée pour simplifier notre
programme client.
 
Merci également à John Sager qui isola une ligne de code fausse dans
une version du programme. Nous fûmes alors capable de vérifier 
rapidement que cela n'avait causé aucun dommage.

Si ceci est la solution correcte, alors, hé bien je ne sais pas trop
ce que nous devrions faire du prix! Peut-être faire une loterie parmi
les participants?
 
Merci, 
  Rob. 
     .-.                     Robert.Harley@inria.fr                    .-. 
    /   \           .-.                                 .-.           /   \ 
   /     \         /   \       .-.     _     .-.       /   \         /     \ 
  /       \       /     \     /   \   / \   /   \     /     \       /       \ 
 /         \     /       \   /     `-'   `-'     \   /       \     /         \ 
            \   /         `-'                     `-'         \   / 
             `-' Linux + 500MHz Alpha + 256MB SDRAM = paradis  `-' 
------------------------------------------------------------------------------. 
 
Je supppose que ça veut dire qu'Alpha Linux est pas mal cool. 
 
Qui se dévoue pour ECCp-89?   =:-)