ECCp-109 (beendet)

Aus Rechenkraft
(Weitergeleitet von ECCp-109)
Zur Navigation springen Zur Suche springen
Logo

Bei diesem Projekt geht es darum, einen Verschlüsselungswettbewerb der Firma Certicom zu lösen. Es handelt sich dabei um ein ECDLP (Elliptic Curve Discrete Logarithm Problem). Rudimentär kann man die zugrundeliegende Idee dieser Verschlüsselung so beschreiben:

Gegeben sei eine Kurve C der Form y2 = x3 + a · x + b für Konstanten a und b. Außerdem sei eine bestimmte große Primzahl p gegeben. Ein Punkt auf der Kurve ist ein Paar von Koordinaten (u,v), welches die Gleichung modulo p erfüllt. Oder anders gesagt: p teilt v2 - u3 - a · u - b.

Interessant ist nun, dass man einen dritten Punkt auf der Kurve berechnen kann, wenn man zwei Punkte auf der Kurve kennt (diese können auch identisch sein). Und hier kommt der Wettbewerb zum Tragen. Certicom hat einen Punkt P auf der Kurve festgelegt und durch extrem oft wiederholtes Ausführen (insgesamt k-mal) dieser Operation einen anderen Punkt Q berechnet. Dabei gibt es eine Möglichkeit, das Ergebnis mit nur log(k) Operationen zu berechnen, so dass man auch eine sehr große Anzahl von Wiederholungen k berechnen kann. Certicom hat nun P und Q veröffentlicht und die Aufgabe besteht darin, k zu ermitteln. Allerdings ist k so groß, dass man nicht einfach alle Möglichkeiten ausprobieren kann, sondern cleverere Methoden nutzen muss.

Der Schlüssel wurde am 15.10.2002 gefunden, es wurden 3,6*1016 (36 Billiarden) elliptische Kurven betrachtet.

Die Projekte ECC2-109 und ECC2K-108 versuchen sich an ähnlichen Problemen.


Projektübersicht

InfoIcon.png ECCp-109
Name ECCp-109
Kategorie Kryptographie
Ziel Knacken einer Verschlüsselung beim Certicom-Wettbewerb
Kommerziell   nein
Homepage www.nd.edu/~cmonico/eccp109


 
United States01.gif    Dieses Projekt wird in Indiana, USA durchgeführt.

Projektstatus

InfoIcon.png Projektstatus
Status   beendet
Beginn 14.04.2001
Ende 15.10.2002

Projektlinks

Clientprogramm

Betriebssysteme

Icon windows 16.png   Windows Checkbox 1.gif  
Icon linux 16.png   Linux Checkbox 1.gif  
Icon dos 16.png   DOS Checkbox 0.gif  


Icon freebsd 16.png   BSD Checkbox 0.gif  
Icon solaris 16.png   Solaris Checkbox 0.gif  
Icon java 16.png   Java (betriebssystemunabhängig)  Checkbox 0.gif  

Client-Eigenschaften

Funktioniert auch über Proxy Checkbox 1.gif
Normal ausführbares Programm Checkbox 1.gif
Als Bildschirmschoner benutzbar Checkbox 1.gif
Kommandozeilenversion verfügbar Checkbox 1.gif
Personal Proxy für Work units erhältlich   Checkbox 0.gif
Work units auch per Mail austauschbar Checkbox 0.gif
Quellcode verfügbar Checkbox 1.gif
Auch offline nutzbar Checkbox 1.gif
Checkpoints Checkbox 1.gif

Besonderheiten

Das Programm benutzt einen nichtdeterministischen Algorithmus, d.h. es rät einfach mögliche Punkte und prüft, ob diese auf der Kurve liegen. Deshalb genügt dafür auch eine seltene Online-Verbindung. Das Programm sammelt die gefundenen Punkte und schickt diese auf Anforderung des Nutzers an den Server.

Für Besitzer eines Athlon gibt es einen speziell optimierten Client auf der Webseite eines der teilnehmenden Teams. Damit lassen sich nochmal einige Prozent an Leistung herausquetschen.

Wer aufgrund einer Firewall oder eines Proxy keine Punkte einsenden kann, der kann dies auch mit Hilfe eines Webformulars tun.

Screenshots


Meldungen