ECC2-109 (beendet)

Bei diesem Projekt soll der ECC2-109-Wettbewerb der Firma Certicom in Angriff genommen werden.

Es handelt sich bei dieser Verschlüsselung 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 y² = x³ + 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 v² - u³ - 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 (und die Verschlüsselung sehr schnell ist). Certicom hat nun P und Q veröffentlicht und die Aufgabe besteht darin, k zu ermitteln.

Allerdings ist k so groß (109 Bit Schlüssellänge), dass man auch mit vielen Computern nicht einfach alle Möglichkeiten ausprobieren kann (wie zum Beispiel beim Projekte RC5-64), sondern geschicktere Verfahren nutzen muss. Deshalb kommt hier der sogenannte verteilte Rho-Algorithmus von Pollard zur Anwendung. Dieser basiert auf den gleichen Überlegungen wie das Geburtstags-Paradoxon. Bei nur 23 zufällig ausgewählten Personen ist die Wahrscheinlichkeit, dass mindestens 2 von ihnen am gleichen Tag Geburtstag haben, bereits über 50 Prozent. Dies liegt daran, dass die Wahrscheinlichkeit (in etwa) mit dem Quadrat der Anzahl Personen (wegen der Paarbildung) ansteigt. Dieser Effekt funktioniert genauso mit den Punkten auf der elliptischen Kurve. D.h. schon durch die Berechnung von relativ wenigen (im Vergleich zum gesamten möglichen Parameterraum) Punkten auf der Kurve ist die Wahrscheinlichkeit sehr hoch, dass verschiedene Projektteilnehmer den gleichen Punkt auf der Kurve berechnen (und dafür verschiedene zufällige Parameter nutzen). Aus den beiden Parameternsätzen, die für die Berechnung dieser gleichen Punkte verwendet wurden, kann dann der Schlüssel berechnet werden.

Prinzipiell müssen also alle generierten Punkte miteinander verglichen werden, um eine mögliche Übereinstimmung zu finden. Dies würde es aber erfordern, alle berechneten Punkte an den zentralen Server zu schicken, was wegen der immer noch großen Menge von Punkten nicht möglich ist. Deshalb kommt folgendes Verfahren zum Einsatz: Von allen berechneten Punkten werden nur diejenigen an den zentralen Server zum Vergleich geschickt, die ein bestimmtes beliebig wählbares Kriterium erfüllen, sogenannte Distinguished Points. Es reicht aus, diese Punkte miteinander zu vergleichen. Dies liegt daran, dass zwei Teilnehmer, die einen gleichen (beliebigen) Punkt berechnet haben, sich bei der Berechnung automatisch in der gleichen Richtung auf der Kurve weiterbewegen und damit der nächste Distinguished Point bei beiden ebenfalls gleich ist.

Auf der Webseite von Certicom ist eine genaue Aufstellung aller Einzelheiten (Wettkampfregeln, Schlüsseldaten, etc.) zu den Wettbewerben zu finden. Dort findet sich unter anderem eine Schätzung von 21.000.000 CPU-Tagen auf einem Pentium 100 für die Lösung des Wettbewerbs. Certicom schätzt die benötigte Zeit damit ca. 2,3mal so hoch wie beim erfolgreich beendeten Projekt ECCp-109 ein.

Der Schlüssel wurde am 8.4.2004 vom Projekt gefunden.

Projektübersicht

ECC2-109
Name	ECC2-109
Kategorie	Kryptographie
Ziel	Knacken einer Verschlüsselung beim Certicom-Wettbewerb
Kommerziell	nein
Homepage	ecc2.com (hier Archivlink)

	Dieses Projekt wird in Arizona, USA durchgeführt.

Projektstatus

Projektstatus
Status	beendet
Beginn	07.11.2002
Ende	14.04.2004

Projektlinks

• Hintergrundinfos
• Download
• Statistiken
• Forum

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.
• Der Client benötigt unbedingt einen MMX-fähigen Prozessor.
• Der Client ist multiprozessorfähig und verteilt seine Threads automatisch auf die vorhandenen CPUs.

Veröffentlichte Versionen

• 30.11.1999: 0.99

Installationsanleitung

• Download des Clients
• Installation
• Ausführen des Clients
• Benutzeraccount einrichten & Teambeitritt
• Zusatztools
• Manuelles Hochladen von Ergebnissen

Tools

• ECC2-109 GUI: Mit diesem Programm kann man sowohl lokale Clients als auch Clients im Netzwerk beobachten und konfigurieren.

• ecc2109c: Bei diesem Programm handelt es sich um einen Konsolenclient für das Projekt, der gegenüber dem offiziellen Client viele zusätzliche Features besitzt und den normalen Client komplett ersetzen kann.

• ecc2GUI: Dieses Tool erlaubt es, den Client von einer graphischen Oberfläche aus zu starten und zu stoppen. Es kann Benchmarkwerte sowie detaillierte Computerinformationen anzeigen.

• FlyGUI: Das Aussehen dieser GUI lässt sich mit Skins an eigene Bedürfnisse anpassen.

Screenshots

• 

  Konsole

Meldungen

• 27.04.2004: Certicom Announces Elliptic Curve Cryptosystem (ECC) Challenge Winner