Thema der Woche

29. April 2004

109-Bit-ECC-Challenge gelöst

Ein Mathematikerteam um Chris Monico, einem Assistenzprofessor an der Texas Tech University, hat den Certicom-Wettbewerb um das Brechen eines 109 Bit langen Krypto-Schlüssels auf Basis elliptischer Kurven gelöst. Für den Certicom-ECC-2-109-Challenge (Elliptic Curve Cryptography, ECC) waren 2 600 Computer sowie ein Zeitaufwand von 17 Monaten nötig. Das ausschreibende Unternehmen vergleicht die eingesetzte Brutto-CPU-Zeit mit der eines Athlon XP 3200+, der ungefähr 1 200 Jahre lang ununterbrochen arbeiten würde. Monico stand bereits dem Team vor, das im November 2002 den ECC-p-109-Challenge gewann, der sich zwar auf dieselbe Schlüssellänge bezog, jedoch über einem Primzahlfeld gelöst wurde; ECC-2 bezog sich hingegen auf ein so genanntes F₂m-Feld.

Certicom hat den [externer Link] ECC-Challenge im November 1997 eröffnet, um in der Industrie sowohl das Verständnis als auch die Anerkennung der Schwierigkeit des Diskreten-Logarithmus-Problems (DLP) elliptischer Kurven zu steigern sowie um weitere Forschungsanstrengungen in der Sicherheitsanalyse von Elliptic-Curve-Kryptosystemen anzuregen. Der in der jetzigen Aufgabe geknackte Schlüssel mit 109 Bit liegt weit unter der empfohlenen Stärke kommerzieller ECC-Systeme von 163 Bit oder mehr. Laut Certicom wäre es annähernd einhundert Millionen Mal schwieriger ECC 163 zu knacken.

Chris Monico vermutet denn auch, dass das jetzige Ergebnis der letzte ECC-Challenge ist, der in den nächsten Jahren gelöst werden kann: "Die einzige Möglichkeit, zu den Challenges auf 130-Bit-Pegel zu gelangen, besteht in einer Kombination von Moore's Gesetz (dem Warten darauf, dass die Computer schneller werden) und dem Zusammenfassen von noch mehr Computern. Ich persönlich glaube, dass es unwahrscheinlich ist, dass dieser Fall schon bald eintritt." Jeder Teil des 109-Bit-Wettbewerbs war mit 10 000 US-$ Preisgeld ausgeschrieben; den Gewinnern der nächsten Stufe mit 130-Bit-Schlüsseln winken bereits je 20 000 US-$.