Elliptische-Kurven-Kryptografie

Elliptische Kurve über R

Unter Elliptic Curve Cryptosystems (ECC) versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern verwenden. Die Sicherheit dieser Verfahren basiert auf der Schwierigkeit der Berechnung des diskreten Logarithmus in der Gruppe der Punkte der elliptischen Kurve. Da dieses Berechnungsproblem deutlich schwerer ist als die Berechnung des diskreten Logarithmus in endlichen Körpern oder die Faktorisierung von ganzen Zahlen, kommen Elliptic Curve Cryptosystems – bei vergleichbarer Sicherheit – mit erheblich kürzeren Schlüsseln aus als die herkömmlichen asymmetrischen Kryptoverfahren, wie z. B. das RSA-Kryptosystem oder der Diffie-Hellman-Schlüsselaustausch. Nach heutigem Kenntnisstand wird z. B. mit einer Schlüssellänge von 160 Bit eine ähnliche Sicherheit erreicht wie bei RSA mit 1024 Bit. ECC eignet sich daher besonders dann, wenn die Speicher- oder Rechenkapazität begrenzt ist, z. B. in Smartcards.

Jedes Verfahren, das auf dem diskreten Logarithmus in endlichen Körpern basiert, wie z. B. der Digital Signature Algorithm, das Elgamal-Kryptosystem oder der Diffie-Hellman-Schlüsselaustausch, lassen sich in einfacher Weise auf elliptische Kurven übertragen und somit zu einem Elliptic Curve Cryptosystem umformen. Dabei werden die beim Originalverfahren eingesetzten Operationen (Multiplikation und Division) auf dem endlichen Körper durch entsprechende Operationen (Addition und Subtraktion) der Punkte auf der elliptischen Kurve ersetzt. Das n-fache Addieren eines Punktes P mit sich selbst wird mit nP bezeichnet und entspricht einer Exponentiation xⁿ im ursprünglichen Verfahren.

Funktionsprinzip

Bestimmung der Schlüssel

Beide Seiten A und B des zu sichernden Kommunikationskanals einigen sich öffentlich auf eine gültige elliptische Kurve und einen Punkt P auf dieser Kurve. Weiter beschafft A sich geheim eine Zufallszahl a_s, diese Zahl ist der private Schlüssel von A. Analog beschafft sich B seinen privaten Schlüssel b_s.

Nun berechnet A seinen öffentlichen Schlüssel a_p = a_sP. Analog bestimmt B seinen öffentlichen Schlüssel b_p = b_sP. Da die Punkte auf der elliptischen Kurve zusammen mit einem „unendlichen Punkt“ eine Gruppe bilden, liegen beide öffentliche Schlüssel auf der Kurve oder im unendlichen Punkt.

Ver- und Entschlüsseln

Es gilt nun a_sb_p = a_sb_sP = b_sa_sP = b_sa_p. Damit ist ein zufälliger Punkt der Kurve gegeben, der nur für A und B einfach zu berechnen ist. Er stellt daher ein öffentlich ausgetauschtes Geheimnis dar und kann als Schlüssel verwendet werden. Das Geheimnis ist zerstört, wenn aus den öffentlichen Punkten P und a_p beziehungsweise P und b_p die Zufallszahlen a_s oder b_s mit vertretbarem Aufwand berechnet werden können.

Siehe auch

• DNSCurve

Weblinks

• Allgemeine Beschreibung des Verfahrens (deutsch)
• Video einer Vorlesung über Elliptic-Curve-Cryptology (englisch)
• ECC-Arbeitsgruppe, Domainparameter
• Tutorial mit Java Applets - Krypto-Verfahren basierend auf elliptischen Kurven
• Umfassende Einführung in elliptische Kurven und ECC (englisch)