ECCp-109 (beendet)
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.
Inhalt
Projektübersicht
 ECCp-109
| |
|---|---|
| Name | ECCp-109 |
| Kategorie | Kryptographie |
| Ziel | Knacken einer Verschlüsselung beim Certicom-Wettbewerb |
| Kommerziell | nein |
| Homepage | www.nd.edu/~cmonico/eccp109 |
| Dieses Projekt wird in Indiana, USA durchgeführt. |
Projektstatus
Projektlinks
Clientprogramm
Betriebssysteme
| Windows | ||
| Linux | ||
| DOS |
| |
| BSD | ||
| Solaris | ||
| Java (betriebssystemunabhängig) |
Client-Eigenschaften
| Funktioniert auch über Proxy | 
|
| Normal ausführbares Programm |
|
| Als Bildschirmschoner benutzbar |
|
| Kommandozeilenversion verfügbar |
|
| Personal Proxy für Work units erhältlich | 
|
| Work units auch per Mail austauschbar |
|
| Quellcode verfügbar |
|
| Auch offline nutzbar |
|
| Checkpoints |
|
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
Installation
Programm läuft
Ergebnisse verschickt
| Projekte die sich an den Certicom Challenges beteiligen |
|---|
| ECC2K-108 (2000, 108-bit) • ECCp-109 (2001-2, 109-bit) • ECC2-109 (2002-4, 109-bit) • SHETI (2009, 131-bit) |
