Elliptische Kurven in der Kryptographie

Mit Kryptographie bezeichnet man das Studium mathematischer Techniken, welche die Sicherheit von Informationen betreffen. In der Vergangenheit lag die Bedeutung der Kryptographie vor allem auf dem militärischen und diplomatischen Sektor. Dabei wurden sogenannte symmetrische kryptographische Verfahren verwendet, um geheime Nachrichten zu verschlüsseln. Bevor die verschlüsselten Botschaften übermittelt werden können, einigen sich Sender und Empfänger hier auf einen gemeinsamen geheimen Schlüssel (bei einem persönlichen Treffen, durch einen Kurier…). Natürlich besteht dabei das Risiko, daß der Schlüssel belauscht oder gestohlen wird. Mit Hilfe dieses Schlüssels kodiert der Sender die geheimen Botschaften und verschickt sie dann durch einen eventuell nicht abhörsicheren Kanal (Brief, Radio…) an den Empfänger. Dieser benutzt den Schlüssel, um aus dem erhaltenen Kryptogramm wieder die ursprüngliche Botschaft zu machen.

Ziel dieses Kapitels ist es, elliptische Kurven zu definieren und die dadurch gegebene Gruppenstruktur zu untersuchen. Dies ist der Inhalt des dritten Abschnittes. Davor müssen wir zunächst einmal allgemeine Kurven studieren. Im ersten Abschnitt beginnen wir mit der Definition einer affinen Kurve als Nullstellenmenge eines Polynoms in zwei Variablen. Um ein Gruppengesetz auf einer elliptischen Kurve zu definieren, ist allerdings noch ein zusätzlicher Punkt „im Unendlichen“ vonnöten. Daher definieren wir im zweiten Abschnitt den projektiven Raum sowie projektive Kuren.

Im ersten Abschnitt dieses Kapitels stellen wir die Frobeniusabbildung für elliptische Kurven über endlichen Körpern vor. Im zweiten und dritten Abschnitt gehen wir kurz auf verschiedene Verfahren ein, um die Gruppenordnung von E(F _q ) zu bestimmen. Der vierte Abschnitt behandelt die sogenannten supersingulären elliptischen Kurven. Dies ist für kryptographische Zwecke relevant, da Kurven mit bestimmter Gruppenordnung und supersinguläre Kurven keine kryptographische Sicherheit bieten, wie wir in Kapitel 4 sehen werden.

Wir haben nun eine ganze Reihe von endlichen abelschen Gruppen kennengelernt, nämlich die Gruppen G = E(F _q ) für eine elliptische Kurve E über dem endlichen Körper F _q . Für jede solche Gruppe G = E(F _q ) und jeden Punkt P ∈ E(F _q ) können wir also die in Kapitel 1 vorgestellten Verfahren der Public-Key-Kryptographie (Diffie-Hellman Schlüsselaustausch, ElGamal-Verschlüsselung und ElGamal-Signaturen) betrachten. Wir haben gesehen, daß diese Verfahren nur dann brauchbar sein können, wenn das diskrete Logarithmus-Problem in E(F _q ) „schwer“ zu lösen ist (auch wenn nicht bewiesen ist, daß dies schon ausreicht, um die kryptographische Sicherheit zu gewährleisten). In diesem Kapitel wollen wir die bekannten Angriffe auf das DL-Problem vorstellen und so herausfinden, wie man E(F _q ) und P wählen muß, damit das DL-Problem möglichst schwierig ist. Dabei konzentrieren wir uns auf die momentan tatsächlich durchführbaren Methoden und lassen die Angriffe durch (bisher) hypothetische Quantencomputer, mit denen alle gebräuchlichen Public-Key-Verfahren geknackt werden könnten, außer acht.

Die in Kapitel 4 vorgestellten Angriffe auf das DL-Problem auf einer elliptischen Kurve haben Konsequenzen für die Auswahl kryptogra-phisch sicherer Kurven. Diese wollen wir im ersten Abschnitt besprechen. Danach werden kurz einige Angriffe auf das RSA-Verfahren und auf das DL-Problem in der multiplikativen Gruppe F _q ^× beschrieben, die effizienter sind als die allgemeinen Methoden aus Kapitel 4. Im letzten Abschnitt gehen wir noch einmal ausführlicher auf digitale Unterschriften ein.