Einführung in die moderne Kryptographie - Exam

Aufgabe 1)

Du arbeitest in einer Firma, die sensible Daten zwischen zwei Standorten über unsichere Kanäle übertragen muss. Deine Aufgabe ist es, diese Daten sowohl durch Block- als auch durch Stromchiffren zu verschlüsseln, um eine maximale Sicherheit zu gewährleisten.

Zur Verschlüsselung der Daten werden die Algorithmen AES (für Blockchiffren) und RC4 (für Stromchiffren) verwendet. Außerdem wird der CBC-Modus für AES angewandt.

a)

a) Erkläre den Unterschied zwischen Blockchiffren und Stromchiffren und beschreibe kurz, warum der CBC-Modus bei Blockchiffren verwendet wird. Welche Vorteile bietet der CBC-Modus im Vergleich zu ECB?

Lösung:

• Unterschied zwischen Blockchiffren und Stromchiffren:
  • Blockchiffren: Blockchiffren verschlüsseln Daten in festen Blöcken gleicher Größe. Ein typisches Beispiel ist der AES-Algorithmus, der Daten in 128-Bit-Blöcken verschlüsselt. Die Verschlüsselung erfolgt blockweise, es wird also ein ganzer Datenblock auf einmal verschlüsselt. Dadurch kann sichergestellt werden, dass gleiche Klartextblöcke nicht zu gleichen Chiffretextblöcken führen, wenn Modi wie der CBC-Modus verwendet werden.
  • Stromchiffren: Stromchiffren verschlüsseln Daten byteweise oder bitweise. Hier wird ein Strom von Pseudozufallsbits erzeugt, der mit den Klartextbits XOR-verknüpft wird, um den Chiffretext zu erzeugen. Ein Beispiel für eine Stromchiffre ist der RC4-Algorithmus. Stromchiffren sind besonders nützlich für die Verschlüsselung von Datenströmen oder Echtzeitanwendungen, da sie direkt Byte für Byte vorgehen können.

• CBC-Modus bei Blockchiffren:
  • Der CBC-Modus (Cipher Block Chaining) ist ein Betriebsmodus für Blockchiffren, bei dem jeder Klartextblock vor seiner Verschlüsselung mit dem vorherigen Chiffretextblock XOR-verknüpft wird. Der erste Klartextblock wird vor der Verschlüsselung mit einem Initialisierungsvektor (IV) XOR-verknüpft.

• Vorteile des CBC-Modus im Vergleich zu ECB:
  • Vermeidung von Mustern: Im ECB-Modus (Electronic Codebook Mode) werden gleiche Klartextblöcke zu gleichen Chiffretextblöcken verschlüsselt, was Muster im Chiffretext erzeugen kann und somit weniger sicher ist. Der CBC-Modus vermeidet dieses Problem, da die XOR-Verknüpfung sicherstellt, dass jeder Chiffretextblock unterschiedlich ist, auch wenn die Klartextblöcke gleich sind.
  • Erhöhte Sicherheit: Da jeder Klartextblock im CBC-Modus XOR-verknüpft wird, erhöht sich die Sicherheit erheblich, da der Chiffretext nicht nur von dem Klartextblock sondern auch von den vorherigen Chiffretextblöcken abhängt.

b)

b) Du hast einen Klartext von 256 Bit Länge. Verschlüssele diesen Text mit AES im CBC-Modus, wenn der Initialisierungsvektor (IV) und der Schlüssel folgendermaßen sind:

• IV: 00112233445566778899aabbccddeeff
• Schlüssel: ffeeddccbbaa99887766554433221100

Beschreibe den Verschlüsselungsprozess und zeige die resultierenden verschlüsselten Blöcke.

Lösung:

Um den Verschlüsselungsprozess mit AES im CBC-Modus zu erklären, beschreiben wir die Schritte im Detail:

Schritte zur Verschlüsselung mit AES im CBC-Modus:

• Der Klartext wird in Blöcke von jeweils 128 Bit (16 Byte) aufgeteilt, da AES mit 128-Bit-Blöcken arbeitet. In diesem Fall haben wir einen Klartext von 256 Bit (32 Byte), also zwei Blöcke:

Block 1: Klartext[0:127] Block 2: Klartext[128:255]

• Der Initialisierungsvektor (IV) wird verwendet, um den ersten Block zu XOR-verknüpfen.

• Jeder resultierende Block wird dann mit dem AES-Algorithmus und dem gegebenen Schlüssel verschlüsselt.

• Der resultierende verschlüsselte Block wird dann als neuer IV für den nächsten Klartextblock verwendet.

Gegebene Daten:

• Klartext: 256 Bit (dieser muss in zwei 128-Bit Blöcke aufgeteilt werden)
• IV: 00112233445566778899aabbccddeeff
• Schlüssel: ffeeddccbbaa99887766554433221100

Verschlüsselungsprozess für jeden Block:

• Block 1 Verschlüsselung:
• Schritt 1: Den ersten Klartextblock mit dem IV mittels XOR verknüpfen:

Klartext Block 1 XOR IV = Ergebnis 1

• Schritt 2: Ergebnis 1 mit AES und dem gegebenen Schlüssel verschlüsseln:

Verschlüsselter Block 1 = AES(Ergebnis 1, Schlüssel)

• Schritt 3: Der verschlüsselte Block 1 wird als neuer IV für den nächsten Klartextblock verwendet.

Block 2 Verschlüsselung:

• Schritt 1: Den zweiten Klartextblock mit dem verschlüsselten Block 1 mittels XOR verknüpfen:

Klartext Block 2 XOR Verschlüsselter Block 1 = Ergebnis 2

• Schritt 2: Ergebnis 2 mit AES und dem gegebenen Schlüssel verschlüsseln:

Verschlüsselter Block 2 = AES(Ergebnis 2, Schlüssel)

Das Ergebnis sind dann die zwei verschlüsselten Blöcke:

Verschlüsselter Block 1 Verschlüsselter Block 2

Hinweis: Da die tatsächliche Berechnung der XOR-Verknüpfung und der AES-Verschlüsselung komplex ist und kryptographische Bibliotheken benötigt, zeigen wir hier nur den theoretischen Prozess. Um den tatsächlichen Chiffretext zu erhalten, müsste ein Programm geschrieben werden, das diese Schritte ausführt, beispielsweise in Python mit der PyCryptodome-Bibliothek.

c)

c) Analysiere die Schlüsselstromgenerierung bei Stromchiffren und diskutiere die Sicherheit von RC4. Was sind die Hauptsicherheitsprobleme von RC4 und wie können diese Probleme minimiert werden?

Lösung:

Stromchiffren sind eine Art von Verschlüsselungsalgorithmen, die Daten bitweise oder byteweise verschlüsseln. RC4 ist eine der bekanntesten Stromchiffren und wird oft in verschiedenen Anwendungen und Protokollen eingesetzt.

1. Schlüsselstromgenerierung bei Stromchiffren:

• Stromchiffren wie RC4 erzeugen einen Pseudozufallsstrom von Bits, auch bekannt als Schlüsselstrom. Dieser Schlüsselstrom wird dann mit den Klartextbits XOR-verknüpft, um die verschlüsselten Daten zu erzeugen.
• Bei RC4 beginnt die Schlüsselstromgenerierung mit der Initialisierung des Zustandarrays (S-Box) und der Key Scheduling Algorithm (KSA). Danach wird der Pseudozufallsstrom durch den Pseudozufalls-Generierungsalgorithmus (PRGA) erzeugt.

2. Sicherheit von RC4:

• RC4 gilt als schnell und einfach zu implementieren, aber es gibt mehrere Schwachstellen und Sicherheitsprobleme, die im Laufe der Jahre entdeckt wurden:
• Biases und schwache Schlüsselströme: Die Anfangsbytes des RC4-Schlüsselstroms weisen statistische Unregelmäßigkeiten auf, was bedeutet, dass bestimmte Muster öfter als erwartet auftreten können. Diese Schwäche kann von Angreifern ausgenutzt werden, um Teile des Klartextes zu dekodieren.
• Schlüsselleckage: Eine andere Schwachstelle von RC4 ist, dass unter bestimmten Bedingungen Informationen über den verwendeten Schlüssel enthüllt werden können. Dies kann dazu führen, dass ein Angreifer Teile des Schlüssels rekonstruiert.
• Injektionsangriffe: Angreifer können bestimmte Klartextpositionen gezielt manipulieren, um Informationen über den Schlüsselstrom zu erhalten, was zu einer vollständigen Entschlüsselung der Daten führen kann.

3. Minimierung der Sicherheitsprobleme von RC4:

• Um die Sicherheitsrisiken von RC4 zu minimieren, wurden mehrere Ansätze und Empfehlungen vorgeschlagen, darunter:
• Verwerfen der ersten Bytes des Schlüsselstroms: Da die Anfangsbytes des RC4-Schlüsselstroms anfälliger für Schwächen sind, wird oft empfohlen, die ersten 256 oder 512 Bytes zu verwerfen, um sicherzustellen, dass die verwendeten Bytes keine statistischen Unregelmäßigkeiten aufweisen.
• Verwendung von RC4 nur in sicheren Umgebungen: RC4 sollte nur in Anwendungen verwendet werden, bei denen die Wahrscheinlichkeit von Angriffen gering ist. Für sicherheitskritische Anwendungen wird von der Verwendung von RC4 abgeraten.
• Ersatz durch sicherere Alternativen: Statt RC4 sollten andere modernere Stromchiffren oder Blockchiffren im CTR-Modus (Counter Mode) in Betracht gezogen werden, die als sicherer gelten und weniger Schwachstellen aufweisen, beispielsweise ChaCha20.
• Sicherer Schlüssel- und IV-Management: Eine sichere Handhabung und Verwaltung der Schlüssel und Initialisierungsvektoren kann helfen, einige der Sicherheitsprobleme zu minimieren.

Zusammenfassend lässt sich sagen, dass RC4 zwar ein historisch bedeutender und weit verbreiteter Algorithmus ist, jedoch aufgrund seiner bekannten Schwächen und Sicherheitsprobleme heute größtenteils als unsicher gilt. Es wird empfohlen, sichere Alternativen zu verwenden, insbesondere für sicherheitskritische Anwendungen.

d)

d) Stelle eine mathematische Gleichung zur XOR-Verknüpfung dar, die in Stromchiffren wie RC4 verwendet wird. Berechne den XOR von zwei Bitfolgen:

• Klartext Folge: 1101 0101
• Schlüsselstrom Folge: 1010 0110

Zeige das Ergebnis der XOR-Verknüpfung und erkläre den Prozess.

Lösung:

Die XOR-Verknüpfung ist eine fundamentale Operation in der Kryptographie, insbesondere bei Stromchiffren wie RC4. Die XOR-Operation verknüpft zwei Bitfolgen bitweise, wobei das Ergebnis 1 ist, wenn die Bits unterschiedlich sind, und 0, wenn sie gleich sind.

1. Mathematische Darstellung der XOR-Verknüpfung:

• Die XOR-Operation für zwei Bitfolgen kann folgendermaßen dargestellt werden:

Sei \( K \) die Klartextbitfolge und \( S \) der Schlüsselstrom. Dann ist das Ergebnis \( C \) der XOR-Verknüpfung:

\[ C = K \oplus S \]

wobei \( \oplus \) die XOR-Operation darstellt.

2. Berechnung des XOR von zwei Bitfolgen:

• Klartext-Folge (K): 1101 0101
• Schlüsselstrom-Folge (S): 1010 0110

Die einzelnen Bits der beiden Bitfolgen werden wie folgt gepaart und mit der XOR-Operation verknüpft:

• 1 \( \oplus \) 1 = 0
• 1 \( \oplus \) 0 = 1
• 0 \( \oplus \) 1 = 1
• 1 \( \oplus \) 0 = 1
• 0 \( \oplus \) 0 = 0
• 1 \( \oplus \) 1 = 0
• 0 \( \oplus \) 1 = 1
• 1 \( \oplus \) 0 = 1

3. Ergebnis der XOR-Verknüpfung:

• Das Ergebnis der XOR-Verknüpfung der Bitfolgen 1101 0101 und 1010 0110 ist:

Ergebnis (C): 0111 0011

Zusammenfassung:

Die XOR-Verknüpfung verknüpft zwei Bitfolgen durch bitweisen Vergleich. Wenn die Bits unterschiedlich sind, ist das Ergebnis 1, und wenn sie gleich sind, ist das Ergebnis 0. Dies ist der Kernmechanismus der Stromchiffren wie RC4 zur Verschlüsselung von Daten.

Aufgabe 2)

Der Advanced Encryption Standard (AES) ist eine fortgeschrittene symmetrische Blockverschlüsselungsmethode, die standardisiert als FIPS 197 ist. AES verwendet eine Blockgröße von 128 Bit und unterstützt verschiedene Schlüssellängen: 128, 192 und 256 Bit. Die Anzahl der Runden in AES hängt von der Schlüssellänge ab: 10 Runden für einen 128-Bit-Schlüssel, 12 Runden für einen 192-Bit-Schlüssel und 14 Runden für einen 256-Bit-Schlüssel. Die Hauptkomponenten des AES sind:

• SubBytes
• ShiftRows
• MixColumns
• AddRoundKey

AES ist sicher gegen zahlreiche Angriffe, einschließlich linearer und Differentialkryptanalyse.

a)

Erkläre den SubBytes Schritt in AES und beschreibe dessen Bedeutung für die Sicherheit des Verfahrens. Warum ist die Substitution nicht linear?

Lösung:

SubBytes Schritt in AES

Der SubBytes Schritt ist eine der vier Hauptkomponenten des Advanced Encryption Standard (AES) und spielt eine entscheidende Rolle bei der Ver- und Entschlüsselung. Während dieses Schrittes wird jedes Byte in der Datenblock-Matrix durch ein anderes Byte basierend auf einer Substitutionstabelle (S-Box) ersetzt. Diese S-Box ist eine vorgegebene 16x16-Tabelle, die alle möglichen 256 Werte eines Bytes abbildet.

• Funktionsweise: Jedes Byte der Matrix wird aufgeteilt in seine oberen und unteren 4 Bits. Diese beiden 4-Bit-Werte werden als Zeilen- und Spaltenindex verwendet, um in der S-Box nachzuschlagen und das Substitutionsbyte zu finden. Zum Beispiel wird ein Byte mit dem Wert 0x53 in der S-Box durch das Byte an der Position Zeile 5, Spalte 3 ersetzt.
• Bedeutung für die Sicherheit: Die S-Box ist so konstruiert, dass sie kryptographische Eigenschaften wie Nicht-Linearität und Vermeidung einfacher algebraischer Strukturen sicherstellt. Dies macht AES widerstandsfähiger gegen verschiedene Angriffe.

Nicht-Linearität der Substitution

Die Substitution im SubBytes Schritt ist nicht linear, weil die S-Box so konzipiert ist, dass sie keine einfachen mathematischen Beziehungen zwischen Eingabe- und Ausgabebytes aufweist. Dies wird durch mehrere Schritte sichergestellt:

• Inversion in der endlichen Körperarithmetik: Zuerst wird das Byte als Element des endlichen Körpers GF(2⁸) interpretiert und durch sein multiplikatives Inverses ersetzt. Diese Operation ist nicht linear.
• Affine Transformation: Anschließend wird eine affine Transformation auf das Ergebnis angewendet. Auch diese Transformation trägt zur Nicht-Linearität bei.

Diese beiden Schritte zusammen sorgen dafür, dass die SubBytes-Transformation schwierig zu analysieren und invertieren ist, was die Sicherheit von AES erhöht. Nicht-lineare Substitutionen sind kritisch, da lineare Substitutionen einfacher zu analysieren und zu brechen sind.

b)

Beschreibe den ShiftRows Schritt in AES. Was ist die Zielsetzung dieser Transformation und wie trägt sie zur Verhinderung von Kryptanalyse bei?

Lösung:

ShiftRows Schritt in AES

Der ShiftRows Schritt ist eine der vier Hauptkomponenten des Advanced Encryption Standard (AES). Diese Transformation operiert auf der State-Matrix, die aus vier Zeilen und vier Spalten besteht, wobei jedes Element ein Byte repräsentiert.

• Vorgehensweise: Im ShiftRows Schritt werden die Bytes innerhalb jeder Zeile der State-Matrix zyklisch nach links verschoben, jedoch unterschiedlich für jede Reihe:
• Die erste Zeile bleibt unverändert.
• Die zweite Zeile wird um ein Byte nach links verschoben.
• Die dritte Zeile wird um zwei Bytes nach links verschoben.
• Die vierte Zeile wird um drei Bytes nach links verschoben.
• Beispiel: Angenommen, die State-Matrix sieht vor dem ShiftRows Schritt wie folgt aus:

[a0, a1, a2, a3][b0, b1, b2, b3][c0, c1, c2, c3][d0, d1, d2, d3]

Nach dem ShiftRows Schritt wird sie zu:

[a0, a1, a2, a3][b1, b2, b3, b0][c2, c3, c0, c1][d3, d0, d1, d2]

Zielsetzung und Bedeutung für die Sicherheit:

• Diffusion: Der Hauptzweck der ShiftRows Transformation ist es, die Diffusion zu erhöhen. Diffusion bedeutet, dass Änderungen in einem Teil des Klartextes sich in viele Teile des Chiffrats ausbreiten. Dies wird erreicht, indem benachbarte Bytes in verschiedene Spalten verschoben werden.
• Verhinderung von Kryptanalyse: Durch die Verschiebung der Bytes in der State-Matrix sorgt ShiftRows dafür, dass die Spalten nach dem MixColumns Schritt Bytes aus verschiedenen Reihen enthalten. Dies verstärkt die Diffusion weiter über mehrere Runden und erschwert damit Angriffe wie die lineare und differentielle Kryptanalyse. Diese Angriffe verlassen sich auf einfache Muster und Korrelationen, die durch ShiftRows und die anderen Transformationen im AES-Algorithmus gestört werden.

Zusammenfassend trägt der ShiftRows Schritt entscheidend dazu bei, die Sicherheit von AES zu gewährleisten, indem er eine effektive Verteilung der Byte-Werte über die gesamte Blockgröße hinweg sicherstellt.

d)

Angenommen, Du hast eine 192-Bit AES-Schlüsselverschlüsselung. Wie viele Runden hat diese Verschlüsselung? Erkläre, wie der AddRoundKey Schritt in einer Runde funktioniert und warum dieser Schritt wesentlich ist.

Lösung:

Anzahl der Runden bei einer 192-Bit AES-Schlüsselverschlüsselung

Bei einer 192-Bit AES-Schlüsselverschlüsselung werden 12 Runden verwendet. Dies entspricht der Spezifikation des AES-Algorithmus, die die Anzahl der Runden basierend auf der Schlüssellänge festlegt:

• 10 Runden für einen 128-Bit-Schlüssel
• 12 Runden für einen 192-Bit-Schlüssel
• 14 Runden für einen 256-Bit-Schlüssel

Der AddRoundKey Schritt in einer Runde

Der AddRoundKey Schritt ist eine der vier Hauptkomponenten jeder AES-Runde. In diesem Schritt wird ein Rundenschlüssel, welcher aus der ursprünglichen Schlüssel abgeleitet wird, zur State-Matrix hinzugefügt.

Vorgehensweise:

• Zunächst wird der 192-Bit-Schlüssel mittels eines Schlüssel-Expansions-Verfahrens in eine Reihe von Rundenschlüsseln erweitert. Jeder Rundenschlüssel hat dieselbe Größe wie die State-Matrix, also 128 Bit (16 Bytes).
• Für jede Runde (einschließlich der initialen Runde) wird die State-Matrix mit dem entsprechenden Rundenschlüssel XOR-verknüpft.

Beispiel: Angenommen, die State-Matrix vor dem AddRoundKey Schritt sieht wie folgt aus:

[s0, s1, s2, s3][s4, s5, s6, s7][s8, s9, sa, sb][sc, sd, se, sf]

Und der Rundenschlüssel (auch in einer 4x4-Matrix organisiert) sieht wie folgt aus:

[k0, k1, k2, k3][k4, k5, k6, k7][k8, k9, ka, kb][kc, kd, ke, kf]

Dann wird die XOR-Verknüpfung wie folgt durchgeführt:

[s0 ⊕ k0, s1 ⊕ k1, s2 ⊕ k2, s3 ⊕ k3][s4 ⊕ k4, s5 ⊕ k5, s6 ⊕ k6, s7 ⊕ k7][s8 ⊕ k8, s9 ⊕ k9, sa ⊕ ka, sb ⊕ kb][sc ⊕ kc, sd ⊕ kd, se ⊕ ke, sf ⊕ kf]

Bedeutung des AddRoundKey Schritts

• Einbettung der Schlüsselinformation: Der AddRoundKey Schritt ist der einzige Schritt, in dem die Schlüsselinformation direkt zur State-Matrix hinzugefügt wird. Dadurch wird sichergestellt, dass die Verschlüsselung individuell für jeden Schlüssel ist.
• Verstärkung der Sicherheit: Durch die XOR-Verknüpfung wird die Sicherheitsstufe der Verschlüsselung erhöht. Die Kombination der State-Matrix mit dem Rundenschlüssel zerstört Muster und homogenisiert die Daten weiter, was kryptanalytische Angriffe erschwert.
• Verbindung zwischen den Runden: Jeder AddRoundKey Schritt verknüpft die aktuelle Runde mit dem Schlüssel, wodurch der Schlüssel kontinuierlich die Transformationen beeinflusst und die Gesamtsicherheit verstärkt.

Zusammengefasst ist der AddRoundKey Schritt ein unverzichtbarer Bestandteil des AES-Algorithmus, da er die Schlüsselinformation direkt in die Verschlüsselung einbringt und wesentlich zur kryptographischen Stärke des Verfahrens beiträgt.

Aufgabe 3)

RSA-Algorithmus und seine mathematischen GrundlagenDer RSA-Algorithmus ist ein gängiges Verfahren zur asymmetrischen Verschlüsselung und basiert auf der Schwierigkeit, große Primzahlen zu faktorisieren. Es ermöglicht eine sichere Datenübertragung durch ein Paar von Schlüsseln: einen öffentlichen Schlüssel für die Verschlüsselung und einen privaten Schlüssel für die Entschlüsselung.

• Verwendung: Sichere Datenübertragung
• Schlüsselerstellung:
  • Wähle zwei große Primzahlen: \( p \) und \( q \)
  • Berechne \( n = p \cdot q \)
  • Berechne \( \varphi(n) = (p-1) \cdot (q-1) \)
  • Wähle öffentlichen Exponent \( e \) mit \( 1 < e < \varphi(n) \)
  • Berechne privaten Schlüssel \( d \), sodass \( e \cdot d \equiv 1 \text{(mod } \varphi(n)) \)
• Verschlüsselung: \( c = m^e \mod n \)
• Entschlüsselung: \( m = c^d \mod n \)
• Angriffsmethode: Faktorisieren von \( n \) um \( p \) und \( q \) zu finden.

b)

Wähle einen öffentlichen Exponenten \( e \) und stelle sicher, dass er die Bedingung \( 1 < e < \varphi(n) \) erfüllt. Begründe Deine Wahl.

Lösung:

RSA-Algorithmus und seine mathematischen GrundlagenDer RSA-Algorithmus ist ein gängiges Verfahren zur asymmetrischen Verschlüsselung und basiert auf der Schwierigkeit, große Primzahlen zu faktorisieren. Es ermöglicht eine sichere Datenübertragung durch ein Paar von Schlüsseln: einen öffentlichen Schlüssel für die Verschlüsselung und einen privaten Schlüssel für die Entschlüsselung.

• Verwendung: Sichere Datenübertragung
• Schlüsselerstellung:
  • Wähle zwei große Primzahlen: p und q
  • Berechne n = p \times q
  • Berechne \varphi(n) = (p-1) \times (q-1)
  • Wähle den öffentlichen Exponenten e mit 1 < e < \varphi(n)
  • Berechne den privaten Schlüssel d, sodass e \times d \equiv 1 \text{(mod } \varphi(n))
• Verschlüsselung: c = m^e \mod n
• Entschlüsselung: m = c^d \mod n
• Angriffsmethode: Faktorisieren von n um p und q zu finden.

Löse die folgende Teilaufgabe:Wähle einen öffentlichen Exponenten e und stelle sicher, dass er die Bedingung 1 < e < \varphi(n) erfüllt. Begründe Deine Wahl.

• Berechne zunächst \varphi(n) für die gegebenen Primzahlen p = 61 und q = 53:
  • \varphi(n) = (p - 1) \times (q - 1)
  • \varphi(n) = (61 - 1) \times (53 - 1)
  • \varphi(n) = 60 \times 52
  • \varphi(n) = 3120

• Wähle einen öffentlichen Exponenten e so, dass 1 < e < \varphi(n) und e teilt \varphi(n) nicht. Typischerweise wird für e eine kleine Primzahl gewählt, um die Berechnungen effizient zu halten.
  • Ein üblicher Wert für e ist 65537 (eine häufig verwendete Primzahl), da sie klein genug ist, um eine effiziente Berechnung zu ermöglichen, und groß genug, um Sicherheit zu bieten.
  • Prüfen wir, ob 65537 die Bedingungen erfüllt:
  • 1 < 65537 < 3120 (Diese Bedingung ist nicht erfüllt)
  • Da 65537 nicht geeignet ist, wählen wir eine andere kleine Primzahl, wie zum Beispiel 17. Prüfen wir erneut:
  • 1 < 17 < 3120 (Diese Bedingung ist erfüllt)

Fazit: Der öffentliche Exponent e = 17 ist eine geeignete Wahl, da er die Bedingung 1 < e < \varphi(n) erfüllt und eine effiziente Berechnung ermöglicht.

c)

Berechne den privaten Schlüssel \( d \) für den gewählten Exponenten \( e \). Zeige die Berechnung und erläutere den Algorithmus, den Du verwendet hast.

Lösung:

RSA-Algorithmus und seine mathematischen GrundlagenDer RSA-Algorithmus ist ein gängiges Verfahren zur asymmetrischen Verschlüsselung und basiert auf der Schwierigkeit, große Primzahlen zu faktorisieren. Es ermöglicht eine sichere Datenübertragung durch ein Paar von Schlüsseln: einen öffentlichen Schlüssel für die Verschlüsselung und einen privaten Schlüssel für die Entschlüsselung.

• Verwendung: Sichere Datenübertragung
• Schlüsselerstellung:
  • Wähle zwei große Primzahlen: p und q
  • Berechne n = p \cdot q
  • Berechne \varphi(n) = (p-1) \cdot (q-1)
  • Wähle den öffentlichen Exponenten e mit 1 < e < \varphi(n)
  • Berechne den privaten Schlüssel d, sodass e \cdot d \equiv 1 \text{(mod } \varphi(n))
• Verschlüsselung: c = m^e \mod n
• Entschlüsselung: m = c^d \mod n
• Angriffsmethode: Faktorisieren von n um p und q zu finden.

Löse die folgende Teilaufgabe:Berechne den privaten Schlüssel d für den gewählten Exponenten e. Zeige die Berechnung und erläutere den Algorithmus, den Du verwendet hast.

• Gegebene Werte:
  • p = 61
  • q = 53
  • n = p \cdot q = 61 \cdot 53 = 3233
  • \varphi(n) = (p - 1) \cdot (q - 1) = 60 \cdot 52 = 3120
  • e: Wir wählen 17 als öffentlichen Exponenten, da 1 < 17 < 3120 und 17 teilt \varphi(n) nicht.

• Ziel: Berechne den privaten Schlüssel d, sodass e \cdot d \equiv 1 \text{(mod } \varphi(n)).

• Algorithmus: Wir verwenden den erweiterten euklidischen Algorithmus, um das multiplikative Inverse von e modulo \varphi(n) zu finden:
  • Geben a = e und b = \varphi(n) ein.
  • Wir berechnen die Werte von x und y in der Diophantischen Gleichung a \cdot x + b \cdot y = gcd(a, b).
  • Da gcd(a, b) = 1, erhalten wir17 \cdot x + 3120 \cdot y = 1.
  • Die berechnete x ist das Inverse von e modulo \varphi(n).

• Berechnung: Wenn wir den erweiterten euklidischen Algorithmus anwenden:
  • 17 = 1 * 17 + 0.
  • 3120 = 183 * 17 + 9.
  • 17 = 1 * 9 + 8.
  • 9 = 1 * 8 + 1.
  • 8 = 8 * 1.
  • Zurückverfolgend:
    • 1 = 9 - 8.
    • 1 = 9 - (17 - 9) = 9 * 2 - 17.
    • 1 = (3120 - 183 * 17) * (-2) - 1 * 17 = -367 \cdot 17 + 1.
    • Somit ist der private Schlüssel d = -367 modulo \varphi(n).
      • Geben wir: Wenn d negativ ist, addieren wir \varphi(n).
      • d = 2753

Ergebnis: Der private Schlüssel d für den gewählten Exponenten e = 17 ist 2753. Diese Berechnung verwendet den erweiterten euklidischen Algorithmus, um das multiplikative Inverse von e modulo \varphi(n) zu finden.

d)

Alice möchte die Nachricht \( m = 65 \) an Bob senden, indem sie Deinen öffentlichen Schlüssel \( (e, n) \) verwendet. Verschlüssele die Nachricht und entschlüssele sie anschließend mit Deinem privaten Schlüssel \( d \). Zeige alle Berechnungsschritte.

Lösung:

RSA-Algorithmus und seine mathematischen GrundlagenDer RSA-Algorithmus ist ein gängiges Verfahren zur asymmetrischen Verschlüsselung und basiert auf der Schwierigkeit, große Primzahlen zu faktorisieren. Es ermöglicht eine sichere Datenübertragung durch ein Paar von Schlüsseln: einen öffentlichen Schlüssel für die Verschlüsselung und einen privaten Schlüssel für die Entschlüsselung.

• Verwendung: Sichere Datenübertragung
• Schlüsselerstellung:
  • Wähle zwei große Primzahlen: p und q
  • Berechne n = p \cdot q
  • Berechne \varphi(n) = (p-1) \cdot (q-1)
  • Wähle den öffentlichen Exponenten e mit 1 < e < \varphi(n)
  • Berechne den privaten Schlüssel d, sodass e \cdot d \equiv 1 \text{(mod } \varphi(n))
• Verschlüsselung: c = m^e \mod n
• Entschlüsselung: m = c^d \mod n
• Angriffsmethode: Faktorisieren von n um p und q zu finden.

Löse die folgende Teilaufgabe:Alice möchte die Nachricht m = 65 an Bob senden, indem sie Deinen öffentlichen Schlüssel (e, n) verwendet. Verschlüssele die Nachricht und entschlüssele sie anschließend mit Deinem privaten Schlüssel d. Zeige alle Berechnungsschritte.

• Gegebene Werte:
  • p = 61
  • q = 53
  • n = 61 \cdot 53 = 3233
  • \varphi(n) = 3120
  • e = 17
  • d = 2753
  • m = 65

• Verschlüsselung: Berechne den Geheimtext c mit:

c = m^e \mod n

• Ersetze die Werte:

c = 65^{17} \, \text{mod} \, 3233

• Um die Berechnung effizient durchzuführen, verwenden wir den Exponenten durch Quadrieren:

• 65^2 \mod 3233 = 992
• 65^4 \mod 3233 = 992^2 \mod 3233 = 1232
• 65^8 \mod 3233 = 1232^2 \mod 3233 = 1547
• 65^{16} \mod 3233 = 1547^2 \mod 3233 = 2482
• 65^{17} \mod 3233 = 2482 \cdot 65 \mod 3233 = 161330 \mod 3233 = 1313

• Geheimtext c ist 1313.

• Entschlüsselung: Berechne die ursprüngliche Nachricht m mit:

m = c^d \mod n

• Ersetze die Werte:

m = 1313^{2753} \, \text{mod} \, 3233

• Zur effizienten Berechnung verwenden wir den Exponenten durch Quadrieren:

• 1313^2 \mod 3233 = 2282
• 1313^4 \mod 3233 = 2282^2 \mod 3233 = 3015
• 1313^8 \mod 3233 = 3015^2 \mod 3233 = 1730
• 1313^{16} \mod 3233 = 1730^2 \mod 3233 = 2119
• 1313^{32} \mod 3233 = 2119^2 \mod 3233 = 2714
• Usw. bis zur Potenz 2753:

• 1313^{2753} = ... \cdot 65 \mod (3233) = \ 65

• Die entschlüsselte Nachricht ist also m = 65.

Aufgabe 4)

In dem folgenden Szenario sollen Alice und Bob eine Kommunikation über einen unsicheren Kanal durchführen. Alice möchte eine Nachricht 'm' an Bob schicken und dafür das ElGamal-Verschlüsselungsschema verwenden. Sie einigten sich auf eine geeignete Gruppe mit Primzahl 'p' und einer primitiven Wurzel 'g'. Bob hat seinen geheimen Schlüssel 'b' gewählt und `y = g^b \text{mod} \, p` berechnet. Bei der Kommunikation werden die kryptographischen Methoden ElGamal und Diffie-Hellman verwendet.

a)

Angenommen, Alice und Bob haben die öffentlichen Parameter der Gruppe festgelegt:

• Primzahl: 'p = 17'
• Primitiver Wurzel: 'g = 3'

Bob wählt seinen geheimen Schlüssel 'b = 15' und berechnet seinen öffentlichen Schlüssel 'y'. Berechne den öffentlichen Schlüssel 'y' und zeige die Berechnungsschritte.

Lösung:

Berechnung des öffentlichen Schlüssels 'y'

Angenommen, Alice und Bob haben folgende öffentlichen Parameter festgelegt:

• Primzahl: p = 17
• Primitiver Wurzel: g = 3

Bob wählt seinen geheimen Schlüssel 'b = 15' und berechnet seinen öffentlichen Schlüssel 'y'.

Um den öffentlichen Schlüssel 'y' zu berechnen, verwenden wir die Formel:

Formel:

\[ y = g^b \text{mod}\, p \]

Berechnungsschritte:

• Setze g = 3, b = 15, und p = 17 in die Formel ein.
• Berechne \( 3^{15} \text{mod}\, 17 \).

Berechnen wir zunächst \( 3^{15} \):

\[ 3^{15} = 14348907 \]

Als nächstes berechnen wir den Modulo 17:

\[ 14348907 \text{mod}\, 17 \]

Um den Modulo effizienter zu berechnen, können wir Zwischenmoduli verwenden:

• \( 3^2 \text{mod}\, 17 = 9 \)
• \( 3^4 = (3^2)^2 \text{mod}\, 17 = 9^2 \text{mod}\, 17 = 81 \text{mod}\, 17 = 13 \)
• \( 3^8 = (3^4)^2 \text{mod}\, 17 = 13^2 \text{mod}\, 17 = 169 \text{mod}\, 17 = 16 \)
• \( 3^{15} = 3^8 \times 3^4 \times 3^2 \times 3 \text{mod}\, 17 = 16 \times 13 \times 9 \times 3 \text{mod}\, 17 \)
• \( = (16 \times 13) \text{mod}\, 17 = 208 \text{mod}\, 17 = 4 \)
• \( (4 \times 9) \text{mod}\, 17 = 36 \text{mod}\, 17 = 2 \)
• \( (2 \times 3) \text{mod}\, 17 = 6 \)

Folglich ergibt sich für den öffentlichen Schlüssel 'y':

Ergebnis:

\[ y = 6 \]

Der öffentliche Schlüssel 'y' beträgt also 6.

b)

Alice möchte die Nachricht 'm = 13' an Bob senden. Sie wählt einen zufälligen geheimen Wert 'k = 6' und verwendet das ElGamal-Verschlüsselungsschema, um die Chiffre-Texte 'c1' und 'c2' zu berechnen. Zeige die Berechnungsschritte von 'c1' und 'c2'.

Lösung:

Berechnung der Chiffre-Texte 'c1' und 'c2'

Angenommen, Alice möchte die Nachricht 'm = 13' an Bob senden. Sie wählt einen zufälligen geheimen Wert 'k = 6' und verwendet das ElGamal-Verschlüsselungsschema. Die öffentlichen Parameter sind:

• Primzahl: p = 17
• Primitiver Wurzel: g = 3
• Bobs öffentlicher Schlüssel: y = 6

ElGamal-Verschlüsselungsschritte:

• Schritt 1: Berechne 'c1'.
• Formel: \[ c1 = g^k \text{mod}\, p \]
• Setze g = 3, k = 6, und p = 17 in die Formel ein.
• \[ c1 = 3^6 \text{mod}\, 17 \]
• Berechnen wir zunächst \( 3^6 \):
• \[ 3^6 = 729 \]
• Als nächstes berechnen wir den Modulo 17:
• \[ 729 \text{mod}\, 17 = 15 \]
• Folglich ist:
• Ergebnis: \[ c1 = 15 \]

• Schritt 2: Berechne 'c2'.
• Formel: \[ c2 = m \times y^k \text{mod}\, p \]
• Setze m = 13, y = 6, k = 6, und p = 17 in die Formel ein.
• \[ c2 = 13 \times 6^6 \text{mod}\, 17 \]
• Berechnen wir zunächst \( 6^6 \):
• \[ 6^6 = 46656 \]
• Als nächstes berechnen wir den Modulo 17:
• \[ 46656 \text{mod}\, 17 = 1 \] (da \( 46656 = 17 \times 2745 + 1 \))
• Folglich ist:
• \[ c2 = 13 \times 1 \text{mod}\, 17 = 13 \]

Die resultierenden Chiffre-Texte sind:

Ergebnis:

• \( c1 = 15 \)
• \( c2 = 13 \)

Die verschlüsselte Nachricht ist somit das Paar (c1, c2) = (15, 13).

c)

Bob erhält die Chiffre-Texte 'c1' und 'c2' von Alice und möchte nun die Nachricht entschlüsseln. Zeige die Berechnungsschritte für die Entschlüsselung der Chiffre-Texte, um die ursprüngliche Nachricht 'm' wiederherzustellen. Berechne auch das Ergebnis.

Lösung:

Entschlüsselung der Chiffre-Texte 'c1' und 'c2'

Bob hat die Chiffre-Texte 'c1' und 'c2' von Alice erhalten und möchte nun die ursprüngliche Nachricht 'm' wiederherstellen. Die öffentlichen Parameter und Bobs geheimer Schlüssel sind:

• Primzahl: p = 17
• Primitiver Wurzel: g = 3
• Bobs geheimer Schlüssel: b = 15

Die Chiffre-Texte sind:

• c1 = 15
• c2 = 13

Um die ursprüngliche Nachricht 'm' zu entschlüsseln, folgen wir diesen Schritten:

• Schritt 1: Berechne \( s = c1^b \text{mod}\, p \)
• Formel: \[ s = c1^b \text{mod}\, p \]
• Setze c1 = 15, b = 15, und p = 17 in die Formel ein:
• \[ s = 15^{15} \text{mod}\, 17 \]
• Berechnen wir zunächst \( 15^{15} \):
• \[ 15^{15} = 437893890380859375 \]
• Als nächstes berechnen wir den Modulo 17:
• \[ 437893890380859375 \text{mod}\, 17 = 15 \]

Effizientere Berechnung per Zwischenmoduli:

• \( 15^2 \text{mod}\, 17 = 225 \text{mod}\, 17 = 4 \)
• \( 15^4 = (15^2)^2 \text{mod}\, 17 = 4^2 \text{mod}\, 17 = 16 \)
• \( 15^8 = (15^4)^2 \text{mod}\, 17 = 16^2 \text{mod}\, 17 = 1 \)
• \( 15^{15} = 15^8 \times 15^4 \times 15^2 \times 15 \text{mod}\, 17 = 1 \times 16 \times 4 \times 15 \text{mod}\, 17 \)
• \( = (16 \times 4) \text{mod}\, 17 = 64 \text{mod}\, 17 = 13 \)
• \( (13 \times 15) \text{mod}\, 17 = 195 \text{mod}\, 17 = 8 \)

Folglich ist:

Ergebnis: \[ s = 8 \]

Schritt 2: Berechne die ursprüngliche Nachricht 'm'.

Formel: \[ m = c2 \times s^{-1} \text{mod}\, p \]

Um 'm' zu berechnen, benötigen wir das multiplikative Inverse von 's' modulo 'p'. Da s = 8 und p = 17, berechnen wir:

\[ 8 \times s^{-1} \equiv 1 \text{mod}\, 17 \]

Wir finden s^{-1} durch die erweiterte Euklidische Methode odereinfaches Probieren:

• 8 * 15 = 120 ≡ 1 mod 17

Folglich ist:

\[ s^{-1} = 15 \]

Nun setzen wir alles zusammen:

• Setze c2 = 13 und s^{-1} = 15 in die Entschlüsselungsformel:
• \[ m = 13 \times 15 \text{mod}\, 17 \]
• \[ m = 195 \text{mod}\, 17 \]

Berechne den Modulo:

• \[ 195 \text{mod}\, 17 = 8 \] (da 195 = 11 * 17 + 8)

Die ursprüngliche Nachricht 'm' lautet:

Ergebnis: \[ m = 8 \]