Kryptographie II - Exam

Aufgabe 1)

Symmetrische Verschlüsselungsverfahren: AES, RijndaelBlockchiffre, die für Verschlüsselung und Entschlüsselung denselben Schlüssel verwendet.

• AES (Advanced Encryption Standard)
• Basierend auf dem Rijndael-Algorithmus
• Blockgröße: 128 Bit
• Schlüsselgrößen: 128, 192 oder 256 Bit
• Operationen: SubBytes, ShiftRows, MixColumns, AddRoundKey
• Rundenanzahl hängt von der Schlüssellänge ab: 10 (128 Bit), 12 (192 Bit), 14 (256 Bit)

a)

Erkläre detailliert den Ablauf der Funktion SubBytes in AES und beschreibe, welche Rolle die S-Box spielt. Wie führt diese Funktion zur Verschleierung der Daten?

Lösung:

Die Funktion SubBytes ist eine der grundlegenden Operationen im AES (Advanced Encryption Standard) Verschlüsselungsalgorithmus. Sie hilft dabei, die Daten zu verschleiern und Kryptographie-Expertise zu erhöhen. Hier wird der Ablauf der SubBytes-Funktion und die Rolle der S-Box detailliert erklärt:

• Was ist SubBytes?Die SubBytes-Funktion ist eine nicht-lineare Byte-Ersatz-Transformation. Sie wird auf jedes Byte des 4x4 Zustandsarrays (State-Array) angewendet. Das State-Array repräsentiert den aktuellen Zustand des verschlüsselten Datenblocks.
• Rolle der S-BoxDie S-Box (Substitution Box) ist eine 16x16 Lookup-Tabelle, die eine Substitution von Bytes ermöglicht. Jedes Byte im State-Array wird durch die S-Box ersetzt. Die S-Box dient dazu, lineare und deterministische Muster in den Daten zu brechen, was eine kryptographisch starke Verschleierung (Confusion) bewirkt.
• Funktionsweise der SubBytes-Operation
  1. Jedes Byte im 4x4 State-Array wird ausgelesen.
  2. Das Byte wird als Index verwendet, um in die S-Box einzulesen. Der Index besteht aus den oberen vier Bits und den unteren vier Bits des Bytes. Diese Bits bestimmen die Zeilen- und Spaltenposition in der 16x16 S-Box.
  3. Das Byte an der entsprechenden Position in der S-Box ersetzt das Originalbyte im State-Array.
• BeispielAngenommen, das Byte in der ersten Position des State-Arrays ist 0x53. In hexadezimaler Darstellung bedeutet dies, dass das Byte den Zeilenindex 5 und den Spaltenindex 3 in der S-Box hat. Der Wert, der sich an Position (5, 3) in der S-Box befindet, ersetzt das ursprüngliche Byte 0x53 im State-Array.
• Verschleierung der DatenDurch die nicht-lineare Substitution der Bytes mittels der S-Box wird sichergestellt, dass Unterschiede in den Eingangsbytes zu erheblichen und nicht vorhersagbaren Veränderungen im Ergebnis führen. Dies erhöht die Verschlüsselungssicherheit, da einfache Muster in den Klartextdaten durch die SubBytes-Operation effektiv verschleiert werden.

Die SubBytes-Funktion ist also ein essenzieller Bestandteil von AES, um die Vertraulichkeit und Sicherheit der verschlüsselten Daten zu gewährleisten.

b)

Beschreibe die Funktion ShiftRows und ihre Bedeutung im Rijndael-Algorithmus. Wie trägt diese Operation zur Verteilung der Informationen über den gesamten Datenblock bei?

Lösung:

Die Funktion ShiftRows ist eine der grundlegenden Operationen im AES (Advanced Encryption Standard) Verschlüsselungsalgorithmus, der auf dem Rijndael-Algorithmus basiert. Diese Operation spielt eine wesentliche Rolle bei der Verteilung (Diffusion) der Daten innerhalb des State-Arrays. Im Folgenden wird der Ablauf der ShiftRows-Funktion und ihre Bedeutung detailliert beschrieben:

• Was ist ShiftRows?ShiftRows ist eine byteweise Schiebetransformation, die auf das 4x4 State-Array angewendet wird. Dabei wird jede Zeile des Arrays unterschiedlich verschoben, um die Positionen der Bytes zu verändern und damit die Diffusion zu fördern.
• Ablauf der ShiftRows-OperationDie ShiftRows-Transformation verschiebt die Bytes der einzelnen Zeilen des State-Arrays wie folgt:
  • Erste Zeile: Die erste Zeile des State-Arrays bleibt unverändert.
  • Zweite Zeile: Die Bytes der zweiten Zeile werden um eine Position nach links verschoben.
  • Dritte Zeile: Die Bytes der dritten Zeile werden um zwei Positionen nach links verschoben.
  • Vierte Zeile: Die Bytes der vierten Zeile werden um drei Positionen nach links verschoben.
• Beispiel der ShiftRows-OperationAngenommen, der anfängliche 4x4 State-Array sieht so aus:

\begin{bmatrix} a0 & a1 & a2 & a3 \ b0 & b1 & b2 & b3 \ c0 & c1 & c2 & c3 \ d0 & d1 & d2 & d3 \end{bmatrix}

• Nach Anwendung der ShiftRows-Operation wird der State-Array zu:

\begin{bmatrix} a0 & a1 & a2 & a3 \ b1 & b2 & b3 & b0 \ c2 & c3 & c0 & c1 \ d3 & d0 & d1 & d2 \end{bmatrix}

• Verteilung der Informationen (Diffusion)Die ShiftRows-Operation trägt entscheidend zur Verteilung der Informationen über den gesamten Block bei. Durch die unterschiedlich verschobenen Bytes in den Zeilen wird der ursprüngliche Zusammenhang der Datenelemente aufgebrochen, was entscheidend zur kryptographischen Stärke des Algorithmus beiträgt.Dadurch, dass die Positionen der Bytes verändert werden, werden die Daten so verteilt, dass gleiche Muster in verschiedenen Teilen des State-Arrays auftauchen und dadurch schwerer zu erkennen und zu analysieren sind.
• Zusammenarbeit mit anderen TransformationenDie effektive Vermischung der Daten wird in den weiteren Schritten durch die MixColumns-Operation verstärkt. Hier werden die Zellen einer jeden Spalte mittels linearer Transformationen gemischt, wodurch die Verschiebungen von ShiftRows die resultierenden Daten zusätzlich diffundieren. Damit kooperieren ShiftRows und MixColumns eng, um eine starke und sichere Diffusion der Daten im gesamten 128-Bit-Block zu gewährleisten.

Zusammengefasst ist die ShiftRows-Funktion ein integraler Bestandteil des Rijndael-Algorithmus. Sie sorgt durch das Verschieben der Positionen der Bytes innerhalb des State-Arrays für die notwendige Diffusion und trägt somit entscheidend zur kryptographischen Sicherheit des gesamten Verschlüsselungsprozesses bei.

c)

Berechne die Anzahl der AddRoundKey-Operationen während der Verschlüsselung eines 256-Bit Schlüssels mit AES. Zeige den Berechnungsweg vollständig auf.

Lösung:

Die AddRoundKey-Operation im AES-Algorithmus ist eine der wichtigsten Transformationen, bei der jeder Byte des State-Arrays mit einem Byte des Rundenschlüssels per XOR verknüpft wird. Um die Anzahl der AddRoundKey-Operationen während der Verschlüsselung eines 256-Bit Schlüssels zu berechnen, erläutern wir Schritt für Schritt den gesamten Prozess:

• Anzahl der Runden in AES bei 256-Bit-SchlüsselnBei einem 256-Bit Schlüssel besteht der AES-Algorithmus aus 14 Runden, da die Rundenanzahl von der Schlüssellänge abhängt (10 Runden für 128-Bit, 12 Runden für 192-Bit, und 14 Runden für 256-Bit).
• Anzahl der AddRoundKey-OperationenDie AddRoundKey-Operation wird zu Beginn jeder Runde sowie nach der letzten Runde angewendet. Das bedeutet, dass die AddRoundKey-Operation wie folgt platziert wird:
  • 1 Initiale AddRoundKey-Operation vor der ersten Runde
  • 13 AddRoundKey-Operationen nach jeder der ersten 13 Runden
  • 1 AddRoundKey-Operation nach der letzten (14.) Runde
• Daraus ergibt sich die Gesamtanzahl der AddRoundKey-Operationen:

Berechnungsweg:

• Initiale AddRoundKey-Operation: 1
• AddRoundKey-Operationen in den ersten 13 Runden: 13
• Abschließende AddRoundKey-Operation nach der 14. Runde: 1

Zusammengefasst ergibt sich die Gesamtanzahl der AddRoundKey-Operationen zu:

1 (Initial) + 13 (nach den ersten 13 Runden) + 1 (Abschließend) = 15

Die Anzahl der AddRoundKey-Operationen während der Verschlüsselung mit AES unter Verwendung eines 256-Bit Schlüssels beträgt also 15.

d)

Analysiere die Sicherheit von AES mit einer Schlüssellänge von 128 Bit gegen brute-force Angriffe. Berechne die benötigte Zeit für einen brute-force Angriff, wenn 10^12 Schlüssel pro Sekunde getestet werden können.

Lösung:

Die Sicherheit des AES-Verschlüsselungsalgorithmus mit einer Schlüssellänge von 128 Bit basiert auf der großen Anzahl möglicher Schlüssel, die durch die Länge des Schlüssels vorgegeben wird. Um die Sicherheit gegen brute-force Angriffe zu analysieren und die benötigte Zeit für einen solchen Angriff zu berechnen, befolgen wir die folgenden Schritte:

• Anzahl der möglichen SchlüsselBei einer Schlüssellänge von 128 Bit gibt es insgesamt \(2^{128}\) mögliche Schlüssel. Diese Anzahl ist enorm groß und ergibt sich wie folgt:

\[2^{128} \approx 3.4 \times 10^{38}\]

• Berechnung der Anzahl der möglichen SchlüsselDie genaue Anzahl der möglichen Schlüssel beträgt:

\[2^{128} = 340,282,366,920,938,463,463,374,607,431,768,211,456\]

• Rate der SchlüsseltestsAngenommen, ein Angreifer kann \(10^{12}\) (eine Billion) Schlüssel pro Sekunde testen.

• Berechnung der benötigten Zeit für den brute-force AngriffDie Zeit, die benötigt wird, um alle möglichen Schlüssel zu testen, wird durch die folgende Gleichung berechnet:

\[\text{Zeit} = \frac{\text{Anzahl der möglichen Schlüssel}}{\text{Schlüsseltests pro Sekunde}}\]

Einsetzen der Werte:

\[\text{Zeit} = \frac{2^{128}}{10^{12}} = \frac{340,282,366,920,938,463,463,374,607,431,768,211,456}{10^{12}}\]

\[\text{Zeit} = 340,282,366,920,938,463,463,374,607,431,768 \text{ Sekunden}\]

• Um diese Zahl besser verständlich zu machen, konvertieren wir die Sekunden in Jahre:

\[\text{Zeit in Jahren} = \frac{340,282,366,920,938,463,463,374,607,431,768}{60 \times 60 \times 24 \times 365.25}\]

\[\text{Zeit in Jahren} \approx 10^{26} \text{ Jahre}\]

• Ergebnis und InterpretationDie benötigte Zeit, um einen 128-Bit AES Schlüssel durch brute-force vollständig zu durchprobieren, beträgt etwa \(10^{26}\) Jahre, selbst bei einer extrem hohen Rate von \(10^{12}\) Schlüsseltests pro Sekunde. Dies ist weit länger als das Alter des Universums, welches etwa 13.8 Milliarden Jahre beträgt.
• Dies zeigt, dass AES mit einer Schlüssellänge von 128 Bit äußerst sicher gegenüber brute-force Angriffen ist. Die Größe des Schlüssels macht es praktisch unmöglich, durch reine brute-force Methode einen gültigen Schlüssel zu finden.

Aufgabe 2)

Kontext: In dieser Aufgabe wirst Du Asymmetrische Verschlüsselungsverfahren analysieren, mit einem Fokus auf RSA und ElGamal. Diese Verfahren werden sowohl zur Verschlüsselung als auch für digitale Signaturen verwendet.

• RSA:
  • Schlüsselerzeugung: Wähle zwei große Primzahlen p, q. Berechne n = p * q. Wähle e, sodass ggT(e, (p-1)(q-1)) = 1. Berechne d, sodass e * d ≡ 1 (mod (p-1)(q-1)).
  • Verschlüsselung: C = M^e mod n
  • Entschlüsselung: M = C^d mod n
• ElGamal:
  • Schlüsselerzeugung: Wähle eine große Primzahl p und eine Primitivwurzel g mod p. Wähle zufälligen privaten Schlüssel x und berechne den öffentlichen Schlüssel y = g^x mod p.
  • Verschlüsselung: Wähle zufälligen k. Berechne c1 = g^k mod p und c2 = M * y^k mod p. Das Chiffretextpaar ist (c1, c2).
  • Entschlüsselung: Berechne M = c2 / c1^x mod p

a)

A) Gegeben sei das RSA-Verschlüsselungsverfahren. Angenommen, zwei Primzahlen p = 61 und q = 53 wurden gewählt.

• Berechne n und Φ(n).
• Wähle e = 17. Berechne den privaten Schlüssel d.
• Verschlüssele die Nachricht M = 65.
• Entschlüssele den erhaltenen Chiffretext.

Lösung:

Teilaufgabe A)Gegeben sei das RSA-Verschlüsselungsverfahren. Angenommen, zwei Primzahlen p = 61 und q = 53 wurden gewählt.1. Berechne n und Φ(n):

• = p * q
• Φ(n) = (p-1)(q-1)

anzeigen uns die Schritte zur Berechnung:

• = 61 * 53 = 3233
• Φ(n) = (61-1)*(53-1) = 60*52 = 3120

2. Wähle e = 17. Berechne den privaten Schlüssel d.: Der private Schlüssel d muss die Bedingung erfullen: e * d ≡ 1 (mod Φ(n)). Das bedeutet, dass d der multiplikative Inverse von e modulo Φ(n) ist. Um d zu finden, verwenden wir den erweiterten euklidischen Algorithmus:

• 17d ≡ 1 (mod 3120)
• Der erweiterte Algorithmus ergibt: d = 2753

förmiger verständlicher Schrittverrechnung:

• 3120 = 183 * 17 + 9
• 17 = 1 * 9 + 8
• 9 = 1 * 8 + 1
• 8 = 8 * 1 + 0
• Der Algorithmus wird rückwärts gemacht.

Endgültiges Ergebnis:

• d = 2753

3. Verschlüssele die Nachricht M = 65:Die Verschlüsselung des Nachrichtentexts M -> C.

• C = M^e mod n

beipflichtige Rechnung:

• C = 65^17 mod 3233
• C = 2790

4. Entschlüssele den erhaltenen Chiffretext:Die Entschlüsselung von Chiffretext C -> M:

• M = C^d mod n

regelmäßige Berechnung:

• M = 2790^2753 mod 3233
• M = 65

b)

B) Angenommen, Du verwendest das ElGamal-Verschlüsselungsverfahren mit den folgenden Parametern:

• Wähle die Primzahl p = 467 und die Primitivwurzel g = 2.
• Wähle einen privaten Schlüssel x = 123 und berechne den öffentlichen Schlüssel y.
• Verschlüssele die Nachricht M = 321 mit einem zufälligen k = 100.
• Entschlüssele das Chiffretextpaar (c1, c2).

Lösung:

Teilaufgabe B)Angenommen, Du verwendest das ElGamal-Verschlüsselungsverfahren mit den folgenden Parametern:1. Wähle die Primzahl p = 467 und die Primitivwurzel g = 2.2. Wähle einen privaten Schlüssel x = 123 und berechne den öffentlichen Schlüssel y:Der öffentliche Schlüssel y wird wie folgt berechnet:

• y = g^x mod p

Schritte zur Berechnung:

• y = 2^123 mod 467 = 144

3. Verschlüssele die Nachricht M = 321 mit einem zufälligen k = 100:Die Verschlüsselung folgt diesen Schritten:

• Berechne c1 = g^k mod p
• Berechne c2 = M * y^k mod p

Schritte zur Berechnung:

• c1 = 2^100 mod 467 = 72
• c2 = 321 * 144^100 mod 467 = 271

Das Chiffretextpaar ist (c1, c2) = (72, 271)4. Entschlüssele das Chiffretextpaar (c1, c2):Die Entschlüsselung folgt diesen Schritten:

• Berechne c1^x mod p
• Berechne den Inversen davon mod p
• M = c2 * (c1^x)^(-1) mod p

Schritte zur Berechnung:

• Berechne c1^x mod p:(c1^x) = 72^123 mod 467 = 64
• Berechne den Inversen davon mod p:der multiplikative Inverse von 64 mod 467 ist 256
• Berechne M = c2 * (c1^x)^(-1) mod p:M = 271 * 256 mod 467 = 321

Wir haben erfolgreich die Nachricht M entschlüsselt: M = 321

c)

C) Vergleiche die Sicherheitsmerkmale von RSA und ElGamal.

• Diskutiere die Sicherheit der Schlüssellängen beider Verfahren.
• Betrachte die Sicherheit gegen bekannte Angriffe wie zum Beispiel den Faktorisierungsangriff bei RSA und den diskreten Logarithmusangriff bei ElGamal.

Lösung:

Teilaufgabe C)Vergleich der Sicherheitsmerkmale von RSA und ElGamal:

• Sicherheit der Schlüssellängen:
  • RSA: Die Sicherheit von RSA basiert auf der Schwierigkeit, große Zahlen zu faktorisieren. Um ein vergleichbares Sicherheitsniveau wie bei symmetrischen Schlüsseln zu erreichen, sind bei RSA längere Schlüssellängen erforderlich. Zum Beispiel wird eine Schlüssellänge von 2048 Bit für ein hohes Maß an Sicherheit empfohlen.
  • ElGamal: Die Sicherheit von ElGamal basiert auf der Schwierigkeit, diskrete Logarithmen zu berechnen. Wie bei RSA sind ebenfalls längere Schlüssellängen erforderlich, um ein hohes Maß an Sicherheit zu gewährleisten. Auch für ElGamal sind Schlüssellängen von mindestens 2048 Bit empfehlenswert.
• Sicherheit gegen bekannte Angriffe:
  • RSA-Faktorisierungsangriff: Ein bekannter Angriff auf RSA ist der Faktorisierungsangriff, bei dem der Angreifer versucht, den Modulus n in seine Primfaktoren p und q zu zerlegen. Da die Faktorisierung großer Zahlen sehr rechenintensiv und zeitaufwändig ist, gilt RSA als sicher, solange die verwendeten Primzahlen ausreichend groß und zufällig gewählt sind. Fortschritte in der Faktorisierungstechnik und der Quantencomputing-Forschung könnten jedoch in Zukunft die Sicherheit von RSA beeinträchtigen.
  • ElGamal-diskreter Logarithmusangriff: Ein bekannter Angriff auf ElGamal ist der diskrete Logarithmusangriff, bei dem der Angreifer versucht, das diskrete Logarithmusproblem zu lösen, um den privaten Schlüssel x zu ermitteln. Auch dieser Angriff ist derzeit sehr rechenintensiv und gilt als sicher, solange die verwendeten Zahlen groß und zufällig gewählt sind. Quantencomputer könnten potenziell auch diese Art von Verschlüsselung bedrohen, da sie in der Lage wären, das diskrete Logarithmusproblem effizienter zu lösen.

Zusammenfassend lässt sich sagen, dass sowohl RSA als auch ElGamal bei ausreichender Schlüssellänge und sorgfältiger Wahl der Parameter als sicher gelten. Beide Verfahren sind jedoch anfällig für Fortschritte in der Quantencomputing-Forschung, sodass in Zukunft möglicherweise neue kryptografische Verfahren erforderlich sein könnten, um ein angemessenes Sicherheitsniveau zu gewährleisten.

d)

D) Implementiere das RSA-Verschlüsselungsverfahren in Python.

• Schlüsselerzeugung
• Verschlüsselung
• Entschlüsselung

Verwende die Bibliothek sympy für die Berechnung der Primzahlen und modularen Inversen. Der Python-Code sollte wie folgt aussehen:

import sympy

Lösung:

Teilaufgabe D)Implementiere das RSA-Verschlüsselungsverfahren in Python. Verwende die Bibliothek sympy für die Berechnung der Primzahlen und modularen Inversen. Der Python-Code sollte wie folgt aussehen:

import sympy# Schlüsselerzeugungp = sympy.prime(100)  # Zum Beispiel die 100. Primzahlq = sympy.prime(101) # Zum Beispiel die 101. Primzahln = p * qphi_n = (p - 1) * (q - 1)e = 17 # Wähle ein e, sodass gcd(e, phi_n) = 1# Berechne d, den modularen Inversen von e mod phi_nd = sympy.mod_inverse(e, phi_n)print(f'p = {p}')print(f'q = {q}')print(f'n = {n}')print(f'phi_n = {phi_n}')print(f'e = {e}')print(f'd = {d}')# Nachricht zum VerschlüsselnM = 65# VerschlüsselungC = pow(M, e, n)print(f'Verschlüsselte Nachricht: {C}')# EntschlüsselungM_dec = pow(C, d, n)print(f'Entschlüsselte Nachricht: {M_dec}')

• Schlüsselerzeugung: Das Python-Skript erzeugt zwei große Primzahlen p und q, berechnet n und phi_n, wählt e und berechnet den privaten Schlüssel d.
• Verschlüsselung: Die Nachricht M wird mit e und n verschlüsselt, um den Chiffretext C zu erhalten.
• Entschlüsselung: Der Chiffretext C wird mit d und n entschlüsselt, um die ursprüngliche Nachricht M_dec wiederherzustellen.

Aufgabe 3)

Elliptische Kurven Kryptographie (ECC) wird häufig für Public Key Kryptographie verwendet, einschließlich der Schlüsselgenerierung, Verschlüsselung und digitalen Signaturen. Die zugrunde liegende Mathematik dieser Techniken basiert auf elliptischen Kurven über endlichen Körpern und folgt der allgemeinen Gleichung \[ y^2 = x^3 + ax + b \]. Dabei werden Schlüsselpaare in der Form von \(P, kP\) genutzt. Ein wesentlicher Vorteil von ECC ist, dass im Vergleich zu RSA kürzere Schlüsselgrößen für die gleiche Sicherheit ausreichen. Zu den wichtigen Operationen gehören die Punktaddition und die Skalarmultiplikation. Bekannte Algorithmen, die auf ECC basieren, sind ECDH und ECDSA und sie finden Anwendung in SSL/TLS und Kryptowährungen.

a)

Sei die elliptische Kurve durch die Gleichung \[ y^2 = x^3 - 3x + b \] über dem endlichen Körper \(\text{GF}(97)\) gegeben. Bestimme den Wert von \(b\), sodass \(P = (3, 6)\) auf der Kurve liegt.

Lösung:

Um den Wert von b zu bestimmen, sodass der Punkt P = (3, 6) auf der elliptischen Kurve \[ y^2 = x^3 - 3x + b \] über dem endlichen Körper \( \text{GF}(97) \) liegt, musst Du den Punkt in die Gleichung einsetzen und b berechnen.

Folgende Schritte sind nötig:

• Setze die Koordinaten des Punktes P in die Kurvengleichung ein:

Schritt 1: Setze x = 3 und y = 6 in die Gleichung ein:

\[ 6^2 = 3^3 - 3 \cdot 3 + b \]

Schritt 2: Berechne die Werte:

\[ 36 = 27 - 9 + b \]

Schritt 3: Vereinfache die Gleichung:

\[ 36 = 18 + b \]

Schritt 4: Löse nach b auf:

\[ b = 36 - 18 \] \[ b = 18 \]

Also muss b = 18 sein, damit der Punkt P = (3, 6) auf der elliptischen Kurve y^2 = x^3 - 3x + b über GF(97) liegt.

b)

Implementiere in Python eine Methode zur Punktaddition für elliptische Kurven über endlichen Körpern. Die Methode soll zwei Punkte \(P_1\text{ und }P_2\) als Input erhalten und den resultierenden Punkt \(P_3\) zurückgeben. Berücksichtige dabei Sonderfälle, z.B. wenn \(P_1 = P_2\) oder \(P_1\) der Punkt im Unendlichen ist.

Lösung:

Um die Punktaddition für elliptische Kurven über endlichen Körpern in Python zu implementieren, müssen wir die notwendigen mathematischen Operationen berücksichtigen, einschließlich der Sonderfälle, wenn die Punkte gleich sind oder einer der Punkte der Punkt im Unendlichen ist. Hier ist eine Python-Implementierung:

def point_addition(P1, P2, a, p):    # Punkt(zero) im Unendlichen    O = (None, None)    # Wenn P1 der Punkt im Unendlichen ist, gib P2 zurück    if P1 == O:        return P2    # Wenn P2 der Punkt im Unendlichen ist, gib P1 zurück    if P2 == O:        return P1    x1, y1 = P1    x2, y2 = P2    # Wenn x1 == x2 und y1 != y2, dann ist das Ergebnis der Punkt im Unendlichen    if x1 == x2 and y1 != y2:        return O    # Berechne den Anstieg (slope)    if P1 != P2:        m = (y2 - y1) * pow(x2 - x1, -1, p) % p    else:        m = (3 * x1**2 + a) * pow(2 * y1, -1, p) % p    # Berechne x3 und y3    x3 = (m**2 - x1 - x2) % p    y3 = (m * (x1 - x3) - y1) % p    return (x3, y3)# Beispiel für die NutzungP1 = (3, 6)P2 = (3, 6)a = -3p = 97result = point_addition(P1, P2, a, p)print('Das Ergebnis der Punktaddition ist:', result)

• Die Funktion point_addition nimmt die Punkte P1 und P2, den Parameter a und die Primzahl p (definierend den endlichen Körper GF(p)) als Eingabe.

• Die Funktion gibt den resultierenden Punkt P3 als Ausgabe zurück, welcher das Ergebnis der Addition von P1 und P2 auf der elliptischen Kurve ist.

• Die Funktion behandelt auch die Sonderfälle, wenn einer der Punkte der Punkt im Unendlichen ist oder wenn P1 und P2 gleich sind.

c)

Berechne die Skalarmultiplikation \(5P\) für die elliptische Kurve aus der ersten Teilaufgabe und den Punkt \(P = (3, 6)\). Verwende dafür das Doppeln und Addieren Verfahren.

Lösung:

Um die Skalarmultiplikation 5P für die elliptische Kurve \[ y^2 = x^3 - 3x + b \] über dem endlichen Körper \( \text{GF}(97) \) und den Punkt P = (3, 6) zu berechnen, verwenden wir das Doppeln-und-Addieren-Verfahren. Dafür ist es notwendig, die Punktaddition und Punktverdopplung zu implementieren. Dies kann in Python durch die folgenden Schritte realisiert werden:

def point_addition(P1, P2, a, p):    # Punkt(zero) im Unendlichen    O = (None, None)    # Wenn P1 der Punkt im Unendlichen ist, gib P2 zurück    if P1 == O:        return P2    # Wenn P2 der Punkt im Unendlichen ist, gib P1 zurück    if P2 == O:        return P1    x1, y1 = P1    x2, y2 = P2    # Wenn x1 == x2 und y1 != y2, dann ist das Ergebnis der Punkt im Unendlichen    if x1 == x2 and y1 != y2:        return O    # Berechne den Anstieg (slope)    if P1 != P2:        m = (y2 - y1) * pow(x2 - x1, -1, p) % p    else:        m = (3 * x1**2 + a) * pow(2 * y1, -1, p) % p    # Berechne x3 und y3    x3 = (m**2 - x1 - x2) % p    y3 = (m * (x1 - x3) - y1) % p    return (x3, y3)# Punktverdopplung ist nur eine spezielle Art von Punktadditiondef point_doubling(P, a, p):    return point_addition(P, P, a, p)def scalar_multiplication(k, P, a, p):    # Punkt(zero) im Unendlichen    Q = (None, None)    N = P    while k:        if k & 1:  # Wenn das niedrigste Bit von k 1 ist            Q = point_addition(Q, N, a, p)        N = point_doubling(N, a, p)  # Verdopple den Punkt N        k >>= 1  # Verschiebe k um ein Bit nach rechts    return Q# Beispiel für die VerwendungP = (3, 6)a = -3p = 97b = 18k = 5result = scalar_multiplication(k, P, a, p)print('Das Ergebnis von', k, 'P ist:', result)

• Die Funktion scalar_multiplication führt die Skalarmultiplikation mithilfe des Doppeln-und-Addieren-Verfahrens aus. Sie nimmt eine ganze Zahl k, einen Punkt P, den Parameter a und die Primzahl p (definierend den endlichen Körper GF(p)).

• Die Punkte Q und N werden zur Berechnung verwendet. N wird in jedem Schritt verdoppelt, während Q die Summen berechnet.

• Das Ergebnis 5P wird durch die Funktion am Ende ausgegeben.

Nach der Ausführung des Codes sollte das Ergebnis der Skalarmultiplikation 5P für P = (3, 6) auf der elliptischen Kurve y^2 = x^3 - 3x + 18 über GF(97) berechnet und angezeigt werden.

d)

Erkläre den Unterschied zwischen den Algorithmen ECDH und ECDSA. Beschreibe, in welchem Kontext sie jeweils benutzt werden und wie sie zur Sicherheit von SSL/TLS-Protokollen beitragen.

Lösung:

Elliptic Curve Diffie-Hellman (ECDH) und Elliptic Curve Digital Signature Algorithm (ECDSA) sind zwei verschiedene Algorithmen, die auf elliptischen Kurven basieren und in der Kryptographie verwendet werden. Hier sind die Unterschiede und Anwendungen der beiden Algorithmen:

• ECDH (Elliptic Curve Diffie-Hellman):

Beschreibung: ECDH ist ein Schlüsselaustauschprotokoll, das es zwei Parteien ermöglicht, eine gemeinsame geheime Information zu berechnen, ohne dass die Information über einen unsicheren Kanal übertragen wird. Dieser geheime Schlüssel kann dann für symmetrische Verschlüsselung verwendet werden.

Kontext: ECDH wird hauptsächlich für sichere Kommunikationskanäle verwendet. Es ermöglicht zwei Parteien, die sich nicht persönlich kennen, einen geheimen Schlüssel zu erstellen, den sie zur Verschlüsselung ihrer Kommunikation verwenden können.

Sicherheit in SSL/TLS: In SSL/TLS-Protokollen trägt ECDH zur sicheren Sitzungsschlüsselgenerierung bei. Es ermöglicht dem Client und dem Server, einen gemeinsamen Sitzungsschlüssel zu berechnen, der dann für die symmetrische Verschlüsselung des Datentransfers während der Sitzung verwendet wird.

• ECDSA (Elliptic Curve Digital Signature Algorithm):

Beschreibung: ECDSA ist ein Algorithmus zur Erstellung und Verifikation digitaler Signaturen. Es ermöglicht es einer Partei, eine Nachricht digital zu signieren, sodass andere Parteien die Authentizität und Integrität der Nachricht überprüfen können.

Kontext: ECDSA wird zur Erstellung digitaler Signaturen verwendet, um die Authentizität und Integrität von Dokumenten oder Nachrichten zu gewährleisten. Es wird häufig in Anwendungen wie Software-Updates, elektronische Verträge und digitalen Zertifikaten verwendet.

Sicherheit in SSL/TLS: In SSL/TLS-Protokollen trägt ECDSA zur Authentifizierung von Servern und Clients bei. Es wird verwendet, um digitale Zertifikate zu signieren, die die Identitäten der Kommunikationsparteien verifizieren. Dies verhindert Man-in-the-Middle-Angriffe, indem es sicherstellt, dass die Parteien, die kommunizieren, tatsächlich die sind, die sie vorgeben zu sein.

• Zusammenfassung: Während ECDH verwendet wird, um einen geheimen Schlüssel für die symmetrische Verschlüsselung sicher zu berechnen, wird ECDSA verwendet, um digitale Signaturen zu erstellen und zu verifizieren, um die Authentizität und Integrität von Nachrichten sicherzustellen. Beide Algorithmen sind wesentliche Komponenten zur Sicherstellung der Sicherheit und Vertrauenswürdigkeit von SSL/TLS-Protokollen.

Aufgabe 4)

Gegeben sei das Diffie-Hellman Schlüsselaustauschverfahren, welches zum sicheren Austausch kryptografischer Schlüssel über einen unsicheren Kanal genutzt wird. Zwei Teilnehmer, Alice und Bob, möchten mittels Diffie-Hellman einen gemeinsamen geheimen Schlüssel K erzeugen. Alice und Bob wählen gemeinsam eine große Primzahl p und einen Primzahlgenerator g, wobei 1 < g < p gilt. Alice wählt ihren geheimen Wert a und Bob wählt seinen geheimen Wert b. Anschließend sendet Alice den Wert g^a mod p an Bob und Bob sendet den Wert g^b mod p an Alice. Beide Teilnehmer können nun das gemeinsame Geheimnis, den Schlüssel K, berechnen.

a)

Angenommen, Alice und Bob wählen die Primzahl p = 23 und den Primzahlgenerator g = 5. Alice wählt ihren geheimen Wert a = 6 und Bob wählt seinen geheimen Wert b = 15. Berechne die öffentlichen Werte, die zwischen Alice und Bob ausgetauscht werden.

Lösung:

Berechnung der öffentlichen Werte im Diffie-Hellman Schlüsselaustauschverfahren:

Um die öffentlichen Werte, die zwischen Alice und Bob ausgetauscht werden, zu berechnen, folgen wir diesen Schritten:

• Alice und Bob wählen gemeinsam eine Primzahl p = 23 und einen Primzahlgenerator g = 5.
• Alice wählt ihren geheimen Wert a = 6 und Bob wählt seinen geheimen Wert b = 15.

Die öffentlichen Werte werden folgendermaßen berechnet:

• Alice berechnet A = g^a mod p:

Wir berechnen:

• A = 5^6 mod 23

Zuerst berechnen wir 5^6:

• 5^6 = 15625

Nun berechnen wir den Modulo-Operator:

• 15625 mod 23 = 8

Somit ist der von Alice gesendete Wert A = 8.

• Bob berechnet B = g^b mod p:

Wir berechnen:

• B = 5^15 mod 23

Zuerst berechnen wir 5^15:

• 5^15 = 30517578125

Nun berechnen wir den Modulo-Operator:

• 30517578125 mod 23 = 19

Somit ist der von Bob gesendete Wert B = 19.

Die öffentlichen Werte, die zwischen Alice und Bob ausgetauscht werden, sind:

• Alice sendet: A = 8
• Bob sendet: B = 19

b)

Berechne den gemeinsamen geheimen Schlüssel K, den sowohl Alice als auch Bob unter Verwendung ihrer erhaltenen öffentlichen Werte generieren.

Lösung:

Berechnung des gemeinsamen geheimen Schlüssels K im Diffie-Hellman Schlüsselaustauschverfahren:

Um den gemeinsamen geheimen Schlüssel K zu berechnen, folgen wir diesen Schritten:

Wir kennen bereits die öffentlichen Werte, die zwischen Alice und Bob ausgetauscht wurden:

• Alice sendet: A = 8
• Bob sendet: B = 19

Nun berechnen sowohl Alice als auch Bob den geheimen Schlüssel K:

Schritte:

• Alice berechnet K = B^a mod p
• Bob berechnet K = A^b mod p

Berechnung durch Alice:

• K = 19^6 mod 23

Zuerst berechnen wir 19^6:

• 19^6 = 470427017

Nun berechnen wir den Modulo-Operator:

• 470427017 mod 23 = 2

Somit ist der von Alice berechnete geheime Schlüssel K = 2.

Berechnung durch Bob:

• K = 8^15 mod 23

Zuerst berechnen wir 8^15:

• 8^15 = 35184372088832

Nun berechnen wir den Modulo-Operator:

• 35184372088832 mod 23 = 2

Somit ist der von Bob berechnete geheime Schlüssel K = 2.

Der gemeinsame geheime Schlüssel K, den sowohl Alice als auch Bob berechnet haben, beträgt 2.

c)

Erläutere die mathematische Sicherheit des Diffie-Hellman Schlüsselaustauschverfahrens. Welche Probleme könnten auftreten, wenn zu kleine Werte für p oder g gewählt werden?

Lösung:

Mathematische Sicherheit des Diffie-Hellman Schlüsselaustauschverfahrens:

Das Diffie-Hellman Schlüsselaustauschverfahren basiert auf der Schwierigkeit, diskrete Logarithmen in endlichen Körpern (typischerweise den Restklassenringen) zu berechnen. Das bedeutet, dass es extrem schwierig und zeitaufwendig ist, den geheimen Schlüssel zu berechnen, selbst wenn die öffentlichen Werte bekannt sind.

Grundlagen der Sicherheit:

• Die Schwierigkeit der Berechnung des diskreten Logarithmus: Der diskrete Logarithmus-Problem (DLP) ist als hartes mathematisches Problem bekannt. Angenommen, ein Angreifer kennt g und g^a mod p, dann ist es fast unmöglich für den Angreifer, a in vertretbarer Zeit zu berechnen. Dieses Problem wird als berechnungsproblem harte Funktion betrachtet.
• Diffie-Hellman Annahme: Diese Annahme besagt, dass es in angemessener Zeit unmöglich ist, den gemeinsamen geheimen Schlüssel K zu berechnen, selbst wenn die Werte g^a mod p und g^b mod p bekannt sind.

Probleme bei zu kleinen Werten für p oder g:

Wenn p oder g zu klein gewählt werden, könnten mehrere Probleme auftreten:

• Brute-Force-Angriffe: Bei kleinen Werten für p und g kann ein Angreifer mittels Brute-Force-Methoden alle möglichen Werte durchprobieren, um den geheimen Schlüssel zu finden. Beispielsweise sind bei einem kleinen p die Anzahl möglicher Werte für a und b begrenzt und überschaubar, was Brute-Force-Angriffe erleichtert.
• Schlüsseleigenschaften: Kleine Werte von g können weniger Sicherheit bieten, insbesondere wenn g zu Primzahl ist oder wenn g eine schlechte Wahl ist. Es ist sehr wichtig, dass g eine Primzahl ist und richtig ausgewählt wird.
• Mathematik in kleinen Gruppen: Wenn p klein ist, operieren wir in einer kleinen Gruppe, wodurch spezielle mathematische Angriffe wie das Pohlig-Hellman-Verfahren möglich werden. Diese Angriffe zielen darauf ab, den diskreten Logarithmus effizient zu berechnen, indem sie die Faktorisierung der Gruppengröße verwenden.

Insgesamt ist es wichtig, ausreichend große Werte für p und g zu wählen, um maximale Sicherheit im Diffie-Hellman Schlüsselaustauschverfahren zu gewährleisten. Typischerweise werden Werte von mindestens 2048 Bit für p empfohlen, um ein hohes Maß an Sicherheit zu gewährleisten.