Elliptische-Kurven-Kryptographie


Seminararbeit, 2016

26 Seiten, Note: 1,3


Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Mathematische Grundlagen
2.1 Modulare Arithmetik
2.2 Logikgesetze
2.3 Multiplikatives Inverse
2.4 Gruppen
2.5 Körper
2.6 Primitive Einheitswurzel
2.7 Diskretes Logarithmusproblem

3 Public Key Verfahren
3.1 Diffie-Hellman Schlüsselaustausch
3.2 Digital Signature Algorithm (DSA)
3.3 elGamal Verschlüsselung

4 Elliptische Kurven
4.1 Definition
4.2 Geometrische Betrachtung
4.3 Algebraische Betrachtung
4.4 Unterschiede zur Algebra mit Zahlen

5 Elliptische Kurven Kryptographie (ECC)
5.1 Elliptische Kurven Diffie-Hellman Schlüsselaustausch (ECDH)
5.2 Digitale Signatur mit elliptischen Kurven (ECDSA)

6 Fazit

Abbildungsverzeichnis

1 Diffie-Hellman Darstellung

2 Signatur- und Verifikationsprozess

3 Elliptische Kurve

4 Punktaddition auf elliptischer Kurve

5 Punktverdopplung auf elliptischer Kurve

6 Assoziativität bei elliptischer Kurve

7 Reihenfolge beim Potenzieren

8 Reihenfolge beim Potenzieren bei modularer Arithmetik

9 Elliptische Kurve in einem Galois Feld

10 Elliptische Kurven Diffie-Hellman Schlüsselaustausch (ECDH) Darstellung

11 Digitale Signatur mit elliptischen Kurven (ECDSA) Darstellung

12 RSA vs ECC

Abkürzungen

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Elliptische Kurven in der Kryptographie sind ein Beispiel für die hohe Nütz- lichkeit der reinen Mathematik. Elliptische Kurven werden seit langem stu- diert. Seit 30 Jahren finden die elliptischen Kurven Anwendung in kryp- tographischen Systemen. Die Verfahren sind so lange sicher, wie diskrete Logarithmen in der Gruppe der Punkte der elliptischen Kurve nicht effizient berechnet werden können. Alle Verfahren, die auf dem diskreten Logarithmus in endlichen Körpern basieren, können auf elliptische Kurven übertragen wer- den. Dazu zählen unter anderem der Diffie-Hellman-Schlüsselaustausch, der Digital Signature Algorithm oder das Elgamal-Verschlüsselungsverfahren.

Unternehmen wie die NSA entwickeln, standardisieren und nutzen diese Verschlüsselungen für Daten. Die meisten Menschen sind bereits in irgend- einer Form mit dieser Art von Kryptographie in Verbindung gekommen.

Allerdings werden es die wenigstens bemerkt haben. Einige weitere bekannte Anwendungsgebiete im Jahr 2016 sind:

- Signatur von Playstation 3 Spielen
- Zugriffsschutz der Chips bei europäischen Reisepässen
- Zugriff auf den Chip des deutschen Personalausweises
- Schlüsselaustausch bei WhatsApp (Curve25519)

Ziel dieser Seminararbeit ist es, die Grundlagen der Ellitptischen Kurven Kryptographie zu erläutern und auf grundlegende mathematische und kryp- tographische Verfahren einzugehen. Zu Beginn werden die mathematischen Grundlagen für den Leser geschaffen. Mit den erarbeiteten mathematischen Grundlagen lassen sich die kryptographischen Verfahren beschreiben. Ellipti- sche Kurven werden nur auf elementarem Niveau behandelt und es werden nur die benötigten Einzelheiten zum Rechnen auf den Kurven beschrieben. Im Anschluss werden die auf dem diskreten Logarithmus in endlichen Kör- pern basierenden Verfahren näher für elliptische Kurven erläutert. Am Ende wird die Arbeit mit einem Fazit abgerundet, da es sehr viele verschiedene Meinungen zu diesem Thema gibt.

2 Mathematische Grundlagen

Um die Kryptographie mit Elliptischen Kurven besser verständlich zu ma- chen, werden zuerst die mathematischen Grundlagen erarbeitet. Es wird weitgehend auf Beweise verzichtet und auf weiterführende Literatur verwie- sen.

2.1 Modulare Arithmetik

In diesem Abschnitt werden wir uns näher mit dem Rechnen mit Resten, auch modularer Arithmetik gennant, beschäftigen. Wir haben es dabei nur mit ganzen Zahlen (Z) zu tun. Modulare Arithmetik ist für viele Anwendungs- bereiche in der Informatik wichtig, besonders im Bereich der Kryptographie.

Immer, wenn man es mit einem endlichen auf Zahlen abgebildeten Alphabet zu tun hat, stößt man unumgänglich auf Reste.

Wenn a ∈ Z und m ∈ N, so kann man a in der Form a = q - m + r schreiben, wobei q und r aus Z eindeutig bestimmt sind durch die Festlegung 0 < r < m. Diese Zahl r heißt Rest der Division und man verwendet auch die Schreibweise r = a mod m. Beispiel: 19 mod 5 = 4 »19 modulo 5 ist 4« Haben zwei ganze Zahlen a und b bei Division durch m ∈ N denselben Rest, so sagt man, a und b sind kongruent modulo m. Die Zahl m heißt Modul. Zwei Zahlen a und b sind genau dann kongruent modulo m, wenn sie sich um ein Vielfaches von m unterscheiden. Beispiel: 19 = 24 (mod 5) »19 modulo 5 und 24 modulo 5 haben beide den Rest 4«[Tes08]

2.2 Logikgesetze

Das Kommutativgesetz beim Rechnen besagt nichts anderes, als dass zum Beispiel 2 - 3 dasselbe ist wie 3 - 2 oder 2 + 3 dasselbe ist wie 3 + 2. [Mei11]

a+b=b+a

a-b=b-a

Die Assoziativgesetze sagen aus, dass man in einem längeren Ausdruck, der nur eine Verknüpfungsart enthält, keine Klammern setzten muss, weil es auf die Reihenfolge nicht ankommt. 1 - (2 - 3) ist dasselbe wie (1 - 2) - 3, daher kann man die Klammern hier direkt weglassen und 1 - 2 - 3 schreiben. Wenn ein Ausdruck sowohl - als auch + enthält, dann müssen Klammern gesetzt werden, um die Reihenfolge der Auswertung klarzustellen. [Mei11]

a+(b+c)=(a+b)+c

(a - b) - c = a - (b - c)

Die Distributivgesetze sind mathematische Regeln, die angeben, wie sich zwei zweistellige Verknüpfungen bei der Auflösung von Klammern zueinan- der verhalten. [Mei11]

a+(b-c)=(a+b)-(a+c) a-(b+c)=(a-b)+(a-c)

2.3 Multiplikatives Inverse

Wenn es zu e ∈ Z m eine Zahl d ∈ Z m gibt mit e - d = 1 (mod m) so nennt man d das multiplikative Inverse zu e mod m. [Tes08]

2.4 Gruppen

Sei G eine Menge mit einer Verknüpfung, die je zwei Elementen a, b ∈ G ein Element a ◦ b ∈ G zuordnet.(G; ◦) wird eine Gruppe genannt, wenn folgendes gilt:

1. Es gilt (a ◦ b) ◦ c = a ◦ (b ◦ c) für alle a; b; c ∈ G (Assoziativgesetz).
2. Es gibt ein neutrales Element n ∈ G, das n ◦ a = a ◦ n = a für alle a ∈ G erfüllt.
3. Zu jedem a ∈ G gibt es ein inverses Element i(a) ∈ G, das a ◦ i(a) = i(a) ◦ a = n erfüllt.

Gilt außerdem:

4. a ◦ b = b ◦ a für alle a; b ∈ G (Kommutativgesetz),

so spricht man von einer kommutativen oder abelschen Gruppe. Die Anzahl der Elemente in G wird als Ordnung der Gruppe bezeichnet. Ist die Anzahl endlich, so spricht man von einer endlichen Gruppe, ansonsten von einer unendlichen Gruppe. [Tes08]

Eine Teilmenge H von G heißt Untergruppe von G, falls H eine Gruppe bezüglich der auf H eingeschränkten Gruppenoperation von G ist. Ist G endlich, so ist die Ordnung jeder Untergruppe ein Teiler der Ordnung von G.

Die ist der Satz von Lagrange. [Wer02]

2.5 Körper

Ein Körper ist in der Mathematik ein Zahlenbereich, in dem die vier Grundrechenarten +, −, -, / mit Rechenregeln wie dem Kommutativ-, dem Assoziativund dem Distributivgesetz durchgeführt werden können.

Ein endlicher Körper mit pk Elementen wird auch Galois-Körper genannt und symbolisch GF(pk) geschrieben. Somit gibt es Körper mit 2, [Abbildung in dieser Leseprobe nicht enthalten] Elementen.

2.6 Primitive Einheitswurzel

In der Algebra werden Zahlen, deren n-te Potenz die Zahl 1 ergeben, n -te Einheitswurzeln genannt. x ist genau dann eine primitive Einheitswurzel, wenn gilt: [Tes08]

Abbildung in dieser Leseprobe nicht enthalten

2.7 Diskretes Logarithmusproblem

In der Gruppen- und Zahlentheorie ist der diskrete Logarithmus das Analo- gon zum gewöhnlichen Logarithmus aus der Analysis. In diesem Zusammen- hang kann diskret wie ganzzahlig verstanden werden.

Sei (G, +) eine additiv geschriebene Gruppe, H eine von einem Element erzeugte Untergruppe von G, d.h. H = 〈h〉. Für ein beliebiges Element a ∈ G besteht das diskrete Logarithmus Problem darin, zu entscheiden, ob a ∈ H, und falls ja, ein m ∈ Z zu berechnen, sodass [Abbildung in dieser Leseprobe nicht enthalten]

Dieses m wird als logh a, der Logarithmus von a, bezeichnet. Wie beim Faktorisieren stellt sich bei der Berechnung von diskreten Loga- rithmen heraus, dass im Allgemeinen keine effizienten, d.h in Polynomialzeit durchführbaren Algorithmen, bekannt sind. Während für die Faktorisierung einer beliebigen Zahl grundsätzlich subexponentielle Algorithmen zur Verfü- gung stehen, sind subexponentielle Algorithmen zur Berechnung diskreter Logarithmen nicht bekannt. [Vig]

3 Public Key Verfahren

Viele kryptographische Verfahren basieren auf den bisher beschriebenen ma- thematischen Grundlagen. Um die Verfahren in der elliptischen Kurven Kryp- tographie verstehen zu können, müssen noch die zugrundeliegenden Public Key Verfahren beschrieben werden. Man spricht auch von sogenannten asym- metrischen Verfahren. Bei diesen Algorithmen wird der eigentliche Schlüssel eines Benutzers in zwei Teile gespaltet. Aus dem Schlüssel wird ein Schlüssel- paar. Der öffentliche Schlüssel darf oder sollte sogar allgemein bekannt sein, lediglich der geheime Schlüssel ist nur dem rechtmäßigen Besitzer bekannt. [Kri16]

3.1 Diffie-Hellman Schlüsselaustausch

Diffie und Hellman stellten 1976 das nach ihnen benannte Verfahren zur siche- ren Schlüsselvereinbarung vor. Das Verfahren lässt die Kommunikationspart- ner einen gemeinsamen und einen geheimen Sitzungsschlüssel berechnen. Die Kommunikationspartner werden durch das Verfahren nicht authentifiziert. Obwohl das Verfahren private und öffentliche Schlüsselpaare verwendet, ist es nicht zum Ver- und Entschlüsseln von Daten geeignet. Es ist also kein asym- metrisches Kryptosystem. Die Funktionalität des Diffie-Hellman-Verfahrens besteht somit allein darin, einen gemeinsamen Schlüssel dezentral zu verein- baren. Das Verfahren beruht auf dem diskreten Logarithmusproblem.

Informationen, die allen Kommunikationsteilnehmern bekannt sein müssen und die nicht gegenüber Dritten geheim zu halten sind, bilden die gemeinsa- me Basis des Verfahrens. Das Verfahren lässt sich wie folgt beschreiben:

1. Es ist eine große Primzahl q zu wählen, die das Galois-Feld GF(q) be- stimmt.
2. Es ist eine primitive Einheitswurzel a (2 ≤ a ≤ q − 2) vonGF(q) zu bestimmen, so dass jedes Element des Feldes erzeugbar ist.
3. Die Primzahl q und der Wert a sind nun öffentliche Diffie-Hellman Parameter.
4. Jeder Teilnehmer i wählt eine Zufallszahl 1 ≤ Xi ≤ q − 1.

Xi ist der geheime Schlüssel von Teilnehmer i. Xi entspricht dem privaten Schlüssel eines asymmetrischen Kryptosystems.

5. Teilnehmer i berechnet den öffentlichen Schlüssel [Abbildung in dieser Leseprobe nicht enthalten] mod q. Die öffentlichen Schlüssel werden von den Teilnehmern gespeichert und bei Bedarf an andere Kommunikationspartner übermittelt.

6. Möchte Teilnehmer i mit dem Teilnehmer j kommunizieren, so berech- net jeder der Teilnehmer einen Sitzungsschlüssel Ki,j bzw. Kj,i, wobei durch die Berechnungsvorschrift sichergestellt ist, dass gilt: Ki,j = Kj,i = [Abbildung in dieser Leseprobe nicht enthalten] mod q.

Zur Berechnung von Ki,j benötigt i den öffentlichen Schlüssel Yi von j. Damit berechnet er:

Abbildung in dieser Leseprobe nicht enthalten

Der Teilnehmer j berechnet den Schlüssel Kj,i analog mit dem öffentlichen Schlüssel Yi von i:

Abbildung in dieser Leseprobe nicht enthalten

Nach dem sechsten Schritt haben beide Kommunikationspartner unabhängig voneinander einen gemeinsamen, geheimen Schlüssel berechnet, den sie für ihre vertrauliche Kommunikation verwenden können. [Eck13] Abbildung 1 zeigt das beschriebene Verfahren zusammengefasst grafisch aufbereitet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Diffie-Hellman Darstellung

3.2 Digital Signature Algorithm (DSA)

Der Digital Signature Algorithm ist ein Standard der US-Regierung für Di- gitale Signaturen und basiert auf dem Problem des diskreten Logarithmus. DSA Signaturen sind bei einem Sicherheitsniveau von 1024 Bit lediglich 320 Bit lang. DSA ist somit für ressourcenbeschränkte Anwendungsgebiete, wie beispielsweise Smartcards oder RFID Chips, gut geeignet. Der DSA basiert auf der Nutzung von zwei Gruppen, die auf Primzahlen p und q basieren.

Im Folgenden wird beschrieben, wie die erforderlichen Signier- und Verifi- kationsschlüssel bei DSA erzeugt und wie diese zur Erstellung und Validie- rung von digitalen Signaturen eingesetzt werden. Das Verfahren arbeitet hier mit Schlüssellängen zwischen 512 und 1024 Bit.

Schlüsselgenerierung

1. Generiere eine Primzahl p der Länge L Bits, wobei 512 ≤ L ≤ 1024 und L ein Vielfaches von 64 ist.

2. Berechne einen Primfaktor q von p − 1 mit [Abbildung in dieser Leseprobe nicht enthalten], d.h. q ist 160 Bit lang.

3. Bestimme einen Wert g, mit [Abbildung in dieser Leseprobe nicht enthalten] mod p, wobei gilt 0 < j < p − 1 und [Abbildung in dieser Leseprobe nicht enthalten] mod p > 1

4. Wähle einen Wert x, mit 0 < x < q. x ist der geheime Signierschlüssel.

5. Berechne y, mit y = gx mod p.

y ist der zu x gehörende öffentliche Schlüssel, also der Verifikationsschlüssel.

6. Wähle eine sichere Hashfunktion H.

Die Werte p, q und g sind öffentlich bekannt und können von einer Gruppe von Benutzern gemeinsam verwendet werden. Durch die Nutzung von zwei Gruppen, basierend einerseits auf einer großen Primzahl p und andererseits auf einer deutlich kleineren Primzahl q ist es möglich, den hohen Berech- nungsaufwand, der für Operationen in der großen Gruppe erforderlich ist, auf wenige Operationen zu reduzieren.

Signatur-Erstellung

Wir nehmen an, dass die Kommunikationspartnerin Alice das Dokument M signieren möchte und xA ihr privater und yA ihr öffentlicher Schlüssel ist.

[...]

Ende der Leseprobe aus 26 Seiten

Details

Titel
Elliptische-Kurven-Kryptographie
Hochschule
Technische Hochschule Rosenheim  (Informatik)
Veranstaltung
Seminar theoretische Informatik
Note
1,3
Autor
Jahr
2016
Seiten
26
Katalognummer
V337700
ISBN (eBook)
9783668270374
ISBN (Buch)
9783668270381
Dateigröße
2067 KB
Sprache
Deutsch
Schlagworte
Kryptographie, Theoretische Informatik, NSA, ECC, Elliptische Kurven, Verschlüsselung, Diffie-Hellman, DSA, Signaturen, elGamal, Elliptic Curve, Cryptography, ECDH, ECDSA, Diskretes Logarithmusproblem
Arbeit zitieren
Tobias Jonas (Autor), 2016, Elliptische-Kurven-Kryptographie, München, GRIN Verlag, https://www.grin.com/document/337700

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Elliptische-Kurven-Kryptographie



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden