Das ist (für Mathematiker) eigentlich eine sehr banale Idee. Dass sie trotzdem sichere Verschlüsselungsverfahren liefert, liegt daran, dass es Gruppen G gibt, die viel komplizierter sind als die ganzen Zahlen, und für die das Problem des diskreten Logarithmus schwer zu lösen ist.
Problem des diskreten Logarithmus: In einer abelschen Gruppe G seien ein Element g und eine Potenz ga gegeben. Berechne die ganze Zahl a.
Der Diffie-Hellman-Schlüsselaustausch lässt sich knacken, wenn in einer Gruppe G der diskrete Logarithmus leicht zu berechnen ist, wie etwa in den ganzen Zahlen. Schwer zu berechnen ist der diskrete Logarithmus zum Beispiel in
Um das Prinzip an einem sehr einfachen Beispiel zu veranschaulichen, nehmen wir mal die Kurve
Der Buchstabe A entspreche dem Punkt (0,5), der Buchstabe B dem Punkt (0,18), der Buchstabe H dem Punkt (4,20), der Buchstabe Z dem Punkt (20,9), das Leerzeichen dem Punkt (20,14) und der Punkt dem Punkt im Unendlichen. Wenn wir dann etwa als Verschlüsselungsfunktion
In der Praxis werden natürlich nicht Buchstaben, sondern Blöcke von Bits verschlüsselt, außerdem braucht man elliptische Kurven mit wesentlich mehr Punkten. Bei nur 28 Punkten wäre die Entschlüsselung notfalls auch durch brachiales Probieren machbar, mit Computer-Hilfe eine Sache von Sekunden-Bruchteilen.
Real verwendet man elliptische Kurven mit mindestens 2256 Punkten. Nach der von Hasse bewiesenen Riemann-Vermutung für Funktionenkörper elliptischer Kurven ist die Anzahl der Punkte einer elliptischen Kurve näherungsweise p+1 – genauer
Entschlüsselung
In der Kryptographie gelten Verschlüsselungsverfahren als unsicher, wenn es Entschlüsselungs-Algorithmen in subexponentieller Zeit gibt.
Es gibt eine Reihe von Algorithmen zum Knacken elliptischer Kurven, die exponentielle Zeit benötigen. Bekannte Beispiele sind der Babystep-Giantstep-Algorithmus, der Pohlig-Hellman-Algorithmus, der Pollard ρ-Algorithmus und der Pollard λ-Algorithmus. Wegen ihres hohen Zeit- und Speicher-Aufwandes sind sie nicht praktikabel und stellen also keine Gefahr dar.
Darüber hinaus gibt es Algorithmen, die für sehr spezielle elliptische Kurven tatsächlich Entschlüsselung in subexponentieller Zeit erreichen. Diese speziellen elliptischen Kurven dürfen dann natürlich in der Verschlüsselung nicht verwendet werden.
Konkret dürfen sogenannte “supersinguläre” und “anomale” Kurven nicht verwendet werden.
Eine “supersinguläre” Kurve ist eine Kurve, für die die Anzahl der Punkte genau p+1 ist, also Gleichheit im Satz von Hasse gilt. (Jedenfalls, wenn man modulo einer Primzahl
Eine “anomale” elliptische Kurve ist eine Kurve, für die die Anzahl der Punkte genau p ist. Für anomale Kurven gibt es den SSSA-Algorithmus, der in subexponentieller Zeit entschlüsselt.
In der Praxis verwendet man ohnehin nur eine relativ kleine Auswahl von elliptischen Kurven. Die NSA zum Beispiel hat eine überschaubare Liste von zu verwendenden elliptischen Kurven.
In choosing an elliptic curve as the foundation of a public key system there are a variety of different choices. The National Institute of Standards and Technology (NIST) has standardized on a list of 15 elliptic curves of varying sizes. Ten of these curves are for what are known as binary fields and 5 are for prime fields. Those curves listed provide cryptography equivalent to symmetric encryption algorithms (e.g. AES, DES or SKIPJACK) with keys of length 80, 112, 128, 192, and 256 bits and beyond.
Kommentare (12)