ECC2-109 (beendet)

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

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 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 (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

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


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


Projektstatus

InfoIcon.png Projektstatus
Status   beendet
Beginn 07.11.2002
Ende 14.04.2004

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 1.gif  
Icon java 16.png   Java (betriebssystemunabhängig)  Checkbox 0.gif  

Client-Eigenschaften

Funktioniert auch über Proxy Checkbox 0.gif
Normal ausführbares Programm Checkbox 1.gif
Als Bildschirmschoner benutzbar Checkbox 0.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 1.gif
Quellcode verfügbar Checkbox 0.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.
  • 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

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


Meldungen