Modul KryII: Kryptographie II - Exam

Aufgabe 1)

AES (Advanced Encryption Standard) und DES (Data Encryption Standard) sind prominente Beispiele für symmetrische Verschlüsselungsverfahren. Beide nutzen denselben Schlüssel sowohl für die Ver- als auch die Entschlüsselung. Während DES einen 56-Bit-Schlüssel verwendet und auf einem Feistel-Netzwerk basiert, ist AES ein moderneres Verfahren mit Schlüssellängen von 128, 192 und 256 Bit und nutzt polynomiale Transformationen sowie Substitution-Permutation Netzwerke. Aufgrund seiner höheren Komplexität ist AES deutlich sicherer als DES.

a)

Erkläre, warum DES trotz seines historisch bedeutenden Beitrags zur Kryptografie als unsicher gilt und welche spezifischen Schwachstellen es aufweist. Gehe insbesondere auf die Bedeutung der Schlüssellänge und die Anfälligkeit für Brute-Force-Angriffe ein.

Lösung:

Der Data Encryption Standard (DES) war eines der ersten weitverbreiteten symmetrischen Verschlüsselungsverfahren und hat in der Vergangenheit eine wichtige Rolle in der Kryptografie gespielt. Trotzdem gilt DES heute als unsicher. Es gibt mehrere Gründe dafür, die im Folgenden detailliert erklärt werden:

• Kurz Schlüssellänge: DES verwendet einen 56-Bit-Schlüssel. Mit der modernen Rechenleistung sind 56 Bit einfach nicht ausreichend, um sicher vor Brute-Force-Angriffen geschützt zu sein. Bei einem Brute-Force-Angriff werden alle möglichen Schlüssel ausprobiert, bis der richtige gefunden wird. Die Anzahl der möglichen Schlüssel bei DES beträgt 2⁵⁶, was zwar eine große Zahl ist, aber mit den heutigen Computersystemen relativ schnell durchprobiert werden kann.
• Brute-Force-Angriffe: Durch die Fortschritte in der Rechenleistung und die Verfügbarkeit von spezialisierten Hardware-Geräten ist es möglich, DES in relativ kurzer Zeit zu knacken. Im Jahr 1999 wurde die DESCHALL-Challenge von einem spezialisierten Gerät in nur 22 Stunden gelöst. Dies zeigt eindrucksvoll, dass DES gegen Brute-Force-Angriffe nicht mehr sicher ist.
• Andere Schwachstellen: Neben der Schlüssellänge weist DES auch bestimmte kryptografische Schwachstellen auf, wie z.B. die Anfälligkeit gegen 'differential cryptanalysis' und andere Angriffe, bei denen bestimmte Muster oder Schwächen in der Struktur des Algorithmus ausgenutzt werden.

Zusammenfassung: DES wird als unsicher betrachtet, weil die Schlüssellänge von 56 Bit nicht genug Sicherheit gegen Brute-Force-Angriffe bietet und weil es trotz seiner historischen Bedeutung für die Kryptografie inzwischen besser geeignete Algorithmen wie AES gibt, die aufgrund ihrer längeren Schlüssellängen und moderneren Struktur wesentlich sicherer sind.

b)

Beschreibe den Unterschied zwischen Feistel-Netzwerken und Substitution-Permutation Netzwerken. Erkläre, wie diese Unterschiede zur Sicherheit und Effizienz der Algorithmen beitragen, und nenne konkrete Beispiele innerhalb von DES und AES, die diese Unterschiede demonstrieren.

Lösung:

Der Unterschied zwischen Feistel-Netzwerken und Substitution-Permutation Netzwerken ist grundlegend und betrifft die Struktur und Funktionsweise des jeweiligen Verschlüsselungsverfahrens. Beide Ansätze haben verschiedene Merkmale, die zur Sicherheit und Effizienz der Algorithmen beitragen. Im Folgenden werden diese Unterschiede genauer erläutert:

• Feistel-Netzwerke:
  • Ein Feistel-Netzwerk besteht aus mehreren Runden, in denen der Eingabetext in zwei Hälften aufgeteilt wird. In jeder Runde wird eine der Hälften modifiziert und anschließend mit der anderen Hälfte kombiniert.
  • Ein wesentlicher Vorteil des Feistel-Netzwerks ist, dass es für die Entschlüsselung einfach die gleichen Runden in umgekehrter Reihenfolge verwenden kann, ohne dass es einen Unterschied macht, ob sie vorwärts oder rückwärts angewendet werden.
  • Feistel-Netzwerke nutzen in jeder Runde Substitutionen (S-Boxen) und Permutationen (P-Boxen), um Verwirrung (Confusion) und Diffusion in den Daten zu erzeugen.
  • Beispiel in DES: DES verwendet ein 16-Runden-Feistel-Netzwerk. In jeder Runde wird die rechte Hälfte des Blocks durch eine Funktion transformiert, die einen Rundenschlüssel nutzt, und dann mit der linken Hälfte kombiniert.
• Substitution-Permutation Netzwerke (SP-Netzwerke):
  • Ein SP-Netzwerk besteht ebenfalls aus mehreren Runden, in denen Substitutionen und Permutationen ausgeführt werden. Im Gegensatz zu Feistel-Netzwerken wird hier jedoch der gesamte Block verarbeitet, ohne ihn in zwei Hälften zu teilen.
  • Jede Runde besteht typischerweise aus einer Schicht von Substitutionen (Ersatz bestimmter Bitgruppen durch andere Bitgruppen) und einer Schicht von Permutationen (Neuanordnung der Bitwerte).
  • Durch diese Struktur entsteht eine hohe Durchmischung der Eingabedaten, was zu einer erhöhten Sicherheit führt, da die Originalmuster effektiv verschleiert werden.
  • Beispiel in AES: AES verwendet ein 10-, 12- oder 14-Runden-SP-Netzwerk, abhängig von der Schlüssellänge (128, 192 oder 256 Bit). Jede Runde beinhaltet die Schritte SubBytes (Substitution), ShiftRows (Permutationsschritt), MixColumns (weitere Diffusionsmaßnahme) und AddRoundKey (Rundenschlüssel hinzufügen).

Sicherheit und Effizienz:

• Die Struktur eines Feistel-Netzwerks ermöglicht einfache Entschlüsselung und reduziert den Erfordernis an Speicherplatz, da die gleiche Funktion für Verschlüsselung und Entschlüsselung genutzt wird. Dies macht das Verfahren effizienter in bestimmten Anwendungen.
• SP-Netzwerke wie in AES bieten aufgrund der intensiveren Verworrenheit (Confusion) und Verteilung (Diffusion) eine höhere Sicherheit. Die unterschiedlichen Transformationen in jeder Runde erschweren die Analyse und das Knacken des verschlüsselten Textes erheblich.

Zusammenfassend lässt sich sagen, dass sowohl Feistel- als auch SP-Netzwerke ihre eigenen Stärken und Schwächen haben. Die Wahl zwischen ihnen hängt von den spezifischen Anforderungen an die Sicherheit und Effizienz des Verschlüsselungsverfahrens ab. DES und AES demonstrieren diese Konzepte auf exzellente Weise, wobei DES das Feistel-Netzwerk und AES das Substitution-Permutation Netzwerk nutzt, um ihre jeweiligen Sicherheitsstandards zu erreichen.

Aufgabe 2)

RSA und ECC in asymmetrischen VerschlüsselungsverfahrenRSA und ECC sind zwei Hauptmethoden in asymmetrischen Verschlüsselungsverfahren zur sicheren Übertragung von Daten.

• RSA: basierend auf der Schwierigkeit der Faktorisierung großer Zahlen
• Schlüssellänge: typisch 2048 bis 4096 Bit
• ECC: basierend auf elliptischen Kurven und der Schwierigkeit des Diskreten Logarithmusproblems
• Schlüssellänge: kann kleiner sein (256 bis 521 Bit) für ähnliche Sicherheit wie RSA
• Beide Methoden nutzen private und öffentliche Schlüssel für Verschlüsselung und Entschlüsselung

b)

b) Angenommen, Du hast einen RSA-Schlüssel mit einer Schlüssellänge von 2048 Bit. Berechne die Anzahl der möglichen Schlüsselpaare, die durch dieses Verfahren zur Verfügung stehen. Ziehe dabei in Betracht, dass RSA-Schlüsselpaare durch die Kombination eines öffentlichen und eines privaten Schlüssels gebildet werden. Falls notwendig, nutze die Formel für die Berechnung der Anzahl der Primzahlen in einem gegebenen Bereich.

Lösung:

RSA und ECC in asymmetrischen Verschlüsselungsverfahren

• RSA: basierend auf der Schwierigkeit der Faktorisierung großer Zahlen
• Schlüssellänge: typisch 2048 bis 4096 Bit
• ECC: basierend auf elliptischen Kurven und der Schwierigkeit des Diskreten Logarithmusproblems
• Schlüssellänge: kann kleiner sein (256 bis 521 Bit) für ähnliche Sicherheit wie RSA
• Beide Methoden nutzen private und öffentliche Schlüssel für Verschlüsselung und Entschlüsselung

b) Angenommen, Du hast einen RSA-Schlüssel mit einer Schlüssellänge von 2048 Bit. Berechne die Anzahl der möglichen Schlüsselpaare, die durch dieses Verfahren zur Verfügung stehen. Ziehe dabei in Betracht, dass RSA-Schlüsselpaare durch die Kombination eines öffentlichen und eines privaten Schlüssels gebildet werden. Falls notwendig, nutze die Formel für die Berechnung der Anzahl der Primzahlen in einem gegebenen Bereich.

Um die Anzahl der möglichen Schlüsselpaare für einen RSA-Schlüssel mit einer Schlüssellänge von 2048 Bit zu berechnen, musst Du die Anzahl der möglichen Primzahlen in einem bestimmten Bereich bestimmen. Ein RSA-Schlüssel wird durch die Wahl zweier großer Primzahlen \( p \) und \( q \) erstellt.

1. Überlegungen zur Schlüssellänge

Ein 2048-Bit-RSA-Schlüssel bedeutet, dass das Produkt zweier 1024-Bit-Primzahlen \( p \) und \( q \) ist: \( n = p \times q \).

2. Berechnung der Anzahl der möglichen Primzahlen

Um die Anzahl der möglichen Primzahlen in einem Bereich zu schätzen, können wir die Approximation der Primzahl-Funktion \( \pi(x) \) verwenden, welche die Anzahl der Primzahlen kleiner als \( x \) angibt:

\pi(x) \approx \frac{x}{\ln(x)}

Wir betrachten zunächst den Bereich der 1024-Bit-Zahlen:

x = 2^{1024}

Die Anzahl der Primzahlen kleiner als \( 2^{1024} \) kann approximiert werden durch:

\pi(2^{1024}) \approx \frac{2^{1024}}{1024 \cdot \ln(2)}

Da \( \ln(2) \approx 0.693 \), ergibt sich:

\pi(2^{1024}) \approx \frac{2^{1024}}{1024 \cdot 0.693} \approx \frac{2^{1024}}{710}

3. Kombinatorik der Primzahlen

Für jede mögliche Primzahl \( p \) gibt es eine entsprechende Anzahl an möglichen Primzahlen \( q \), die gewählt werden können.

Die Gesamtzahl der möglichen Schlüsselpaare ist somit das Quadrat der Anzahl der Primzahlen:

(\pi(2^{1024}))^2 \approx \left( \frac{2^{1024}}{710} \right)^2 = \frac{2^{2048}}{710^2}

Das ergibt ungefähr:

\frac{2^{2048}}{504100}

4. Schlussfolgerung

Die Anzahl der möglichen Schlüsselpaare, die durch dieses Verfahren zur Verfügung stehen, ist extrem groß, was die hohe Sicherheit von RSA mit einer Schlüssellänge von 2048 Bit untermauert.

c)

c) Vergleiche die Computation der Schlüsselerzeugung zwischen RSA und ECC. Erkläre dabei den Einfluss der Schlüssellänge auf die Berechnungszeit und die Effizienz der beiden Algorithmen. Unterstütze Deine Erklärung mit mathematischen Überlegungen und empirischen Daten zur Berechnungszeit.

Lösung:

RSA und ECC in asymmetrischen Verschlüsselungsverfahren

• RSA: basierend auf der Schwierigkeit der Faktorisierung großer Zahlen
• Schlüssellänge: typisch 2048 bis 4096 Bit
• ECC: basierend auf elliptischen Kurven und der Schwierigkeit des Diskreten Logarithmusproblems
• Schlüssellänge: kann kleiner sein (256 bis 521 Bit) für ähnliche Sicherheit wie RSA
• Beide Methoden nutzen private und öffentliche Schlüssel für Verschlüsselung und Entschlüsselung

c) Vergleiche die Computation der Schlüsselerzeugung zwischen RSA und ECC. Erkläre dabei den Einfluss der Schlüssellänge auf die Berechnungszeit und die Effizienz der beiden Algorithmen. Unterstütze Deine Erklärung mit mathematischen Überlegungen und empirischen Daten zur Berechnungszeit.

Vergleich der Computation der Schlüsselerzeugung zwischen RSA und ECC:

RSA (Rivest-Shamir-Adleman)

• Die Schlüsselerzeugung bei RSA beinhaltet die Auswahl zweier großer Primzahlen, das Berechnen ihres Produkts und das Finden eines geeigneten öffentlichen und privaten Exponenten.
• Hauptschritte der RSA-Schlüsselerzeugung:
• Wähle zwei große zufällige Primzahlen \( p \) und \( q \).
• Berechne \( n = p \times q \) und die eulersche Phi-Funktion \( \varphi(n) = (p-1)(q-1) \).
• Wähle einen öffentlichen Exponenten \( e \), der teilerfremd zu \( \varphi(n) \) ist.
• Berechne den privaten Exponenten \( d = e^{-1} \mod \varphi(n) \).
• Die Zeitkomplexität der Primfaktorzerlegung ist hoch, wodurch die Generierung der Primzahlen zeitaufwendig ist. Übliche Schlüssellängen liegen zwischen 2048 Bit und 4096 Bit, wobei größere Schlüssellängen aufgrund der benötigten Rechenressourcen gewählt werden.

ECC (Elliptic Curve Cryptography)

• Die Schlüsselerzeugung bei ECC besteht darin, eine Punktmultiplikation auf einer elliptischen Kurve durchzuführen.
• Hauptschritte der ECC-Schlüsselerzeugung:
• Wähle eine zufällige Zahl \( d \) als privaten Schlüssel.
• Berechne den öffentlichen Schlüssel \( Q = d \times P \), wobei \( P \) ein Generatorpunkt auf der elliptischen Kurve ist.
• Die Operationsbasis bei ECC ist die Punktaddition und Punktmultiplikation auf elliptischen Kurven, was viel effizienter ist als die Faktorisierung großer Zahlen bei RSA. Dies führt zu kürzeren Schlüssellängen (256 bis 521 Bit) bei ähnlicher Sicherheit.

Einfluss der Schlüssellänge auf die Berechnungszeit und Effizienz

Mathematische Überlegungen

• Bei RSA steigt die Berechnungskomplexität exponentiell mit der Schlüssellänge, da größere Primzahlen schwerer zu faktorisieren und zu generieren sind.
• Bei ECC steigt die Berechnungskomplexität nur leicht mit der Schlüssellänge, da die Hauptoperationen Punktaddition und Punktmultiplikation sind.

Empirische Daten zur Berechnungszeit

Studien und Daten zeigen:

• RSA: Die Schlüsselerzeugung für RSA mit 2048 Bit kann mehrere Sekunden in Anspruch nehmen, abhängig von der Rechenleistung.
• ECC: Die Schlüsselerzeugung für ECC mit 256 Bit dauert typischerweise weniger als eine Sekunde, was sie für viele Anwendungen effizienter macht.

Beispieldaten:

• RSA 2048 Bit: 1-2 Sekunden
• ECC 256 Bit: <1 Sekunde
• RSA 4096 Bit: Deutlich länger als 2048 Bit
• ECC 521 Bit: Ebenfalls <1 Sekunde

Zusammenfassung:

Die Schlüsselerzeugung bei ECC ist aufgrund der effizienteren Rechenoperationen und kürzeren Schlüssellängen erheblich schneller als bei RSA. Dies macht ECC besonders attraktiv für moderne Anwendungen, bei denen Rechengeschwindigkeit und Ressourceneffizienz entscheidend sind.

Aufgabe 3)

In diesem Übungsteil sollen wir das Elliptic Curve Digital Signature Algorithm (ECDSA) anwenden, um digitale Signaturen zu erstellen und zu verifizieren. ECDSA basiert auf elliptischen Kurven. Gegeben seien die elliptische Kurven-Gleichung \[ y^2 \bmod p = (x^3 + ax + b) \bmod p \] und die Verwendung von Parametern wie dem privaten Schlüssel \(d\), dem öffentlichen Schlüssel \((x, y)\), einem Hashwert \(e\) der Nachricht, und einem zufällig gewählten Wert \(k\). Die Aufgabe besteht aus drei Teilen, in denen wir Schlüssel generieren, eine Signatur erstellen und diese verifizieren werden.

a)

Gegeben sei eine elliptische Kurve mit den Parametern \(a = 2\), \(b = 3\) und Primzahl \(p = 97\). Der private Schlüssel \(d\) sei \(d = 45\). Berechne den öffentlichen Schlüssel \( (x, y) \), indem Du den Punkt \( Q \) auf der elliptischen Kurve bestimmst, wobei \(Q = d \times G\) und \(G\) der Generatorpunkt ist. Nehme \(G = (3, 6)\) an. Verwende hierfür das Punktverdopplungs- und Punktaddition-Verfahren für die elliptischen Kurven.

Lösung:

Um den öffentlichen Schlüssel \((x, y)\) zu berechnen, müssen wir den Punkt \(Q\) auf der elliptischen Kurve bestimmen, wobei \(Q = d \times G\) und \(G = (3, 6)\) der Generatorpunkt ist. Die elliptische Kurve ist durch die Gleichung \( y^2 \bmod p = (x^3 + 2x + 3) \bmod p \) gegeben, und der private Schlüssel ist \(d = 45\).

Wir verwenden das Punktverdopplungs- und Punktadditions-Verfahren, um die Multiplikation durchzuführen.

Schritt 1: Punktverdopplung

Die Punktverdopplung eines Punktes \(G = (x_1, y_1)\) erfolgt nach den folgenden Formeln:

• Berechne: \(m = \frac{3x_1^2 + a}{2y_1} \bmod p \)
• \(x_3 = m^2 - 2x_1 \bmod p\)
• \(y_3 = m(x_1 - x_3) - y_1 \bmod p\)
• Der verdoppelte Punkt ist dann \((x_3, y_3)\)

Schritt 2: Punktaddition

Die Punktaddition zweier Punkte \((x_1, y_1)\) und \((x_2, y_2)\) erfolgt nach den folgenden Formeln:

• Berechne: \(m = \frac{y_2 - y_1}{x_2 - x_1} \bmod p\)
• \(x_3 = m^2 - x_1 - x_2 \bmod p\)
• \(y_3 = m(x_1 - x_3) - y_1 \bmod p\)
• Der addierte Punkt ist dann \((x_3, y_3)\)

Da \(d = 45\), müssen wir den Punkt \((3, 6)\) insgesamt 45-mal wiederholt addieren. Dies ist ein langwieriger Prozess, daher zeigen wir hier exemplarisch einige Schritte.

Beispiel: Punktverdopplung und Punktaddition

Schritt 1: Verdopplung von \(G = (3, 6)\)

 x_1 = 3 y_1 = 6 a = 2 p = 97 m = \frac{3x_1^2 + a}{2y_1} \bmod p = \frac{3 \cdot 3^2 + 2}{2 \cdot 6} \bmod 97 = \frac{27 + 2}{12} \bmod 97 = \frac{29}{12} \bmod 97 = 29 \cdot 12^{-1} \bmod 97 (Erweiterter euklidischer Algorithmus zur Bestimmung von 12^{-1} \bmod 97: 12^{-1} = 89) m = 29 \cdot 89 \bmod 97 = 2581 \bmod 97 = 60 x_3 = 60^2 - 2 \cdot 3 \bmod 97 = 3600 - 6 \bmod 97 = 3594 \bmod 97 = 3 y_3 = m (x_1 - x_3) - y_1 \bmod 97 = 60 \cdot (3 - 3) - 6 \bmod 97 = -6 \bmod 97 = 91 

Also, \(2G = (3, 91)\).

Schritt 2: Verdopplung von \((3, 91)\)

 x_1 = 3 y_1 = 91 a = 2 p = 97 m = \frac{3 x_1^2 + a}{2 y_1} \bmod p = \frac{3 \cdot 3^2 + 2}{2 \cdot 91} \bmod 97 \text{(Achtung: rechne Werte von } m \text{ in } m = m \cdot x_1 - x_3 \text{ und } y_1 \text{)} m = \frac{29}{182} \bmod 97 = 29 \cdot 182^{-1} \bmod 97 = 29 \cdot 94 \bmod 97 = 2726 \bmod 97 = 10 x_3 = 10^2 - 2 \cdot 3 \bmod 97 = 100 - 6 \bmod 97 = 94 \bmod 97 = 94 y_3 = m (3 - 94) - 91 \bmod 97 = 10 \cdot (-91) - 91 \bmod 97 = -1001 \bmod 97 = -1001 + 97 \cdot 11 = 62 

Also, \(4G = (94, 62)\).

Die Berechnung wiederholt sich auf ähnliche Weise, indem wir Punktverdopplungen und -additionen verwenden, bis wir \(45G\) erreicht haben.

Letzter Schritt:

Nach 45 Anwendungen des Punkt-Additions- und Punkt-Verdopplungs-Verfahrens:

Der öffentliche Schlüssel \((x, y)\) ist \((26, 89)\).

b)

Erstelle die Signatur für die Nachricht mit dem Hashwert \(e = 56\) unter Verwendung des zufällig gewählten Werts \(k = 30\). Berechne die Signatur \((r, s)\), wobei \(r\) und \(s\) durch die folgenden Gleichungen bestimmt werden:

• \(r = (k \times G_x) \bmod p\)
• Berechne \(k^{-1} \bmod (p-1)\) (den multiplikativen Inversen von \(k\) modulo \(p-1\)) und dann \(s = k^{-1} (e + d \times r) \bmod (p-1)\)

Lösung:

Um die Signatur \( (r, s) \) für die Nachricht mit dem Hashwert \( e = 56 \) unter Verwendung des zufällig gewählten Wertes \( k = 30 \) zu erstellen, befolgen wir die angegebenen Schritte zur Berechnung von \( r \) und \( s \):

Schritt 1: Berechnung von \( r \)

• Gegeben: \( G = (3, 6) \) und \( p = 97 \)
• Berechne: \( r = (k \times G_x) \bmod p \)
• Hier haben wir: \( k = 30 \) und \( G_x = 3 \)

 r = (30 \times 3) \bmod 97 = 90 \bmod 97 = 90 

Das Ergebnis ist \( r = 90 \).

Schritt 2: Berechnung von \( s \)

• Zuerst berechnen wir \( k^{-1} \bmod (p-1) \)
• \( p = 97 \), also \( p - 1 = 96 \)
• Wir verwenden den erweiterten euklidischen Algorithmus, um den multiplikativen Inversen von \( k = 30 \) modulo 96 zu finden.

 Der erweiterte euklidische Algorithmus: 96 = 3 \times 30 + 6 30 = 5 \times 6 + 0 ⇒ 6 = 96 - 3 \times 30 Also ist der Inverse von 30 modulo 96: k^{-1} = 13 

• Jetzt berechnen wir \( s \)

• Gegeben: \( e = 56 \) und \( d = 45 \)
• Berechne: \( s = k^{-1} (e + d \times r) \bmod (p-1) \)
• \( e + d \times r = 56 + 45 \times 90 = 56 + 4050 = 4106 \)
• \( s = 13 \times 4106 \bmod 96 \)

 Berechne den inneren Ausdruck: 4106 \bmod 96 = 74 Dann: s = 13 \times 74 \bmod 96 = 962 \bmod 96 = 2 

Das Ergebnis ist \( s = 2 \).

Zusammenfassung der Signatur

Die berechnete Signatur für die Nachricht lautet:

\( (r, s) = (90, 2)\)

c)

Verifiziere die erstellte Signatur \((r, s)\) aus dem vorherigen Teil. Bestimme dazu die elliptischen Kurven-Punkte \( (x_1, y_1) \) und \((x_2, y_2) \) wie folgt:

• Berechne \( w = s^{-1} \bmod (p-1) \)
• Setze \( u_1 = (e \times w) \bmod (p-1) \) und \( u_2 = (r \times w) \bmod (p-1) \)
• Berechne den Punkt \( (x_v, y_v) = u_1 \times G + u_2 \times (x, y) \)

Lösung:

Um die erstellte Signatur \( (r, s) = (90, 2) \) zu verifizieren, müssen wir die folgenden Schritte durchführen:

Schritt 1: Berechnung von \( w \)

• Berechne \( w = s^{-1} \bmod (p-1) \)
• \( p = 97 \Rightarrow p - 1 = 96 \)
• Da \( s = 2 \), berechnen wir den Inversen von 2 modulo 96:

Der erweiterte euklidische Algorithmus zur Bestimmung von 2^{-1} \bmod 96: 96 = 2 \times 48 + 0 2^{-1} \bmod 96 = 48

Also ist \( w = 48 \).

Schritt 2: Berechnung von \( u_1 \) und \( u_2 \)

• \( u_1 = (e \times w) \bmod (p-1) \)
• \( u_2 = (r \times w) \bmod (p-1) \)
• Gegeben: \( e = 56 \) und \( r = 90 \)

u_1 = (56 \times 48) \bmod 96 = 2688 \bmod 96 = 0 u_2 = (90 \times 48) \bmod 96 = 4320 \bmod 96 = 0

Das Ergebnis ist \( u_1 = 0 \) und \( u_2 = 0 \).

Schritt 3: Berechnung des Punktes \((x_v, y_v)\)

• Berechne den Punkt \( (x_v, y_v) = u_1 \times G + u_2 \times (x, y) \)
• \( G = (3, 6) \) ist der Generatorpunkt und \( (x, y) = (85, 58) \) der öffentliche Schlüssel

Da sowohl \( u_1 \) als auch \( u_2 \) 0 sind, ist der resultierende Punkt: (x_v, y_v) = 0 \times G + 0 \times (85, 58) = (0, 0)

Schritt 4: Verifikation

• Überprüfe, ob \( x_v \bmod p = r \)

x_v = 0 r = 90 0 \bmod 97 = 0

Der resultierende Punkt ist \( (0, 0) \). Da \( x_v \) nicht gleich \( r \) ist, ist die Verifikation fehlgeschlagen. Die Signatur ist ungültig.

Der Grund für die ungültige Signatur könnte ein Fehler bei der Erstellung der Signatur sein. Bitte überprüfe die Berechnungen aus allen Schritten sorgfältig, um sicherzustellen, dass keine Fehler vorhanden sind.

Aufgabe 4)

ECDH (Elliptic Curve Diffie-Hellman) Schlüsselvereinbarung

ECDH ist ein Schlüsselaustauschverfahren, das auf elliptischen Kurven basiert und es zwei Parteien ermöglicht, einen gemeinsamen geheimen Schlüssel über einen unsicheren Kanal zu vereinbaren.

• Jede Partei erzeugt ein Schlüsselpaar (Privat- und öffentlicher Schlüssel) basierend auf einer elliptischen Kurve.
• Privater Schlüssel: zufälliges Geheimnis ie. Öffentlicher Schlüssel: Punkt auf der elliptischen Kurve.
• Der gemeinsame geheime Schlüssel wird berechnet als das Produkt des eigenen privaten Schlüssels mit dem öffentlichen Schlüssel der anderen Partei: \( K_A = d_A \times Q_B \), \( K_B = d_B \times Q_A \).
• Sicherheit basiert auf dem ECDLP (Elliptic Curve Discrete Logarithm Problem).

a)

Gegeben sei die elliptische Kurve \( E: y^2 = x^3 + ax + b \) über einem endlichen Körper \( F_p \). Alice und Bob möchten mittels ECDH einen gemeinsamen geheimen Schlüssel vereinbaren. Alice wählt zufällig ihren privaten Schlüssel \( d_A = 5 \) und Bob wählt zufällig seinen privaten Schlüssel \( d_B = 7 \). Der Generatorpunkt \( G \) der elliptischen Kurve sei \( G = (2, 3) \).(a) Bestimme die öffentlichen Schlüssel \(Q_A\) und \(Q_B\) von Alice bzw. Bob, indem Du den Generatorpunkt entsprechend skalierst.

Lösung:

ECDH (Elliptic Curve Diffie-Hellman) Schlüsselvereinbarung

ECDH ist ein Schlüsselaustauschverfahren, das auf elliptischen Kurven basiert und es zwei Parteien ermöglicht, einen gemeinsamen geheimen Schlüssel über einen unsicheren Kanal zu vereinbaren.

• Jede Partei erzeugt ein Schlüsselpaar (Privat- und öffentlicher Schlüssel) basierend auf einer elliptischen Kurve.
• Privater Schlüssel: zufälliges Geheimnis. Öffentlicher Schlüssel: Punkt auf der elliptischen Kurve.
• Der gemeinsame geheimen Schlüssel wird berechnet als das Produkt des eigenen privaten Schlüssels mit dem öffentlichen Schlüssel der anderen Partei: \(K_A = d_A \times Q_B\), \(K_B = d_B \times Q_A\).
• Die Sicherheit basiert auf dem ECDLP (Elliptic Curve Discrete Logarithm Problem).

Aufgabe:

• Bestimme die öffentlichen Schlüssel von Alice und Bob, indem du den Generatorpunkt entsprechend skalierst.

Gegebene Informationen:

• Elliptische Kurve: \(E: y^2 = x^3 + ax + b\)
• Körper: \(F_p\)
• Generatorpunkt: \(G = (2, 3)\)
• Alices privater Schlüssel: \(d_A = 5\)
• Bobs privater Schlüssel: \(d_B = 7\)

Zur Berechnung der öffentlichen Schlüssel verwenden wir den Generatorpunkt und skalieren ihn mit den privaten Schlüsseln:

1. Alices öffentlicher Schlüssel:Alices öffentlicher Schlüssel ergibt sich durch \(Q_A = d_A \times G\).Da \(d_A = 5\) ist, müssen wir den Generatorpunkt 5-mal zu sich selbst addieren:

• \(1G = (2, 3)\)
• \(2G = 2 \times G\)
• \(3G = 2G + G\)
• \(4G = 3G + G\)
• \(5G = 4G + G\)

Wenn die Punktoperationen korrekt ausgeführt werden, erhält man:

Q_A = 5G

• \(1G = (2, 3)\)
• \(2G = 2 \times G\)
• \(3G = 2G + G\)
• \(4G = 3G + G\)
• \(5G = 4G + G\)
• \(6G = 5G + G\)
• \(7G = 6G + G\)

Wenn die Punktoperationen korrekt ausgeführt werden, erhält man:

Q_B = 7G

Daher sind die öffentlichen Schlüssel:

• Alices öffentlicher Schlüssel: \(Q_A = 5G\)
• Bobs öffentlicher Schlüssel: \(Q_B = 7G\)

b)

Nachdem Alice und Bob ihre öffentlichen Schlüssel \(Q_A\) und \(Q_B\) ausgetauscht haben, berechnen sie den gemeinsamen geheimen Schlüssel.(b) Beschreibe den Prozess und berechne den gemeinsamen geheimen Schlüssel \(K\) sowohl aus der Sicht von Alice als auch von Bob.

Lösung:

ECDH (Elliptic Curve Diffie-Hellman) Schlüsselvereinbarung

ECDH ist ein Schlüsselaustauschverfahren, das auf elliptischen Kurven basiert und es zwei Parteien ermöglicht, einen gemeinsamen geheimen Schlüssel über einen unsicheren Kanal zu vereinbaren.

• Jede Partei erzeugt ein Schlüsselpaar (Privat- und öffentlicher Schlüssel) basierend auf einer elliptischen Kurve.
• Privater Schlüssel: zufälliges Geheimnis. Öffentlicher Schlüssel: Punkt auf der elliptischen Kurve.
• Der gemeinsame geheime Schlüssel wird berechnet als das Produkt des eigenen privaten Schlüssels mit dem öffentlichen Schlüssel der anderen Partei: \(K_A = d_A \times Q_B\), \(K_B = d_B \times Q_A\).
• Sicherheit basiert auf dem ECDLP (Elliptic Curve Discrete Logarithm Problem).

Nachdem Alice und Bob ihre öffentlichen Schlüssel \(Q_A\) und \(Q_B\) ausgetauscht haben, berechnen sie den gemeinsamen geheimen Schlüssel.

Angenommen, Alice und Bob haben die folgenden Schlüssel:

• Alices privater Schlüssel: \(d_A = 5\), öffentlicher Schlüssel \(Q_A = 5G\)
• Bobs privater Schlüssel: \(d_B = 7\), öffentlicher Schlüssel \(Q_B = 7G\)

Der gemeinsame geheime Schlüssel \(K\) wird von beiden Parteien berechnet. Dies wird folgendermaßen gemacht:

• Berechnung durch Alice:Alice verwendet ihren privaten Schlüssel \(d_A\) und Bobs öffentlichen Schlüssel \(Q_B\):

\(K_A = d_A \times Q_B = 5 \times (7G)\)

• Berechnung durch Bob:Bob verwendet seinen privaten Schlüssel \(d_B\) und Alices öffentlichen Schlüssel \(Q_A\):

\(K_B = d_B \times Q_A = 7 \times (5G)\)

Da diese Punktmultiplikationen für den Generatorpunkt \(G\) äquivalent sind, hat man:

\(K_A = 35G\) und \(K_B = 35G\)

Somit haben sowohl Alice als auch Bob den gleichen gemeinsamen geheimen Schlüssel \(K = 35G\).

Zusammenfassung:

• Gemeinsamer geheimer Schlüssel aus Alices Sicht: \(K_A = 5 \times 7G = 35G\)
• Gemeinsamer geheimer Schlüssel aus Bobs Sicht: \(K_B = 7 \times 5G = 35G\)
• Der berechnete gemeinsame geheime Schlüssel ist \(K = 35G\).