PD Dr. Martin Kreuzer Regensburg, den 24.5.2000 Fakultät für Mathematik Universität Regensburg

Übungen zur Vorlesung “Kryptographie”

Blatt 3

(Abgabetermin: 8.6.2000)

Aufgabe 12. (Babylonischer Algorithmus zur Wurzelberechnung)

a) Sei r ∈ ℝ_{+} eine positive reelle Zahl. Wir definieren eine Folge (x_{i})_{i≥0} reeller Zahlen durch x_{0} = r und x_{i+1} = \frac{1}{2} (x_{i} + \frac{r}{x_{i}}) für i ≥ 0. Beweisen Sie, daß diese Folge gegen \sqrt{r} konvergiert.

b) Schreiben Sie eine CoCoA Funktion Sqrt(…), die eine positive rationale Zahl q ∈ ℚ_{+} und eine positive ganze Zahl n ∈ ℕ_{+} als Argumente hat und die \sqrt{q} auf n Nachkommastellen genau berechnet.

Aufgabe 13. (Das RSA Kryptosystem)

Für das RSA Kryptosystem verwenden wir das übliche Alphabet mit 26 Buchstaben. Die Zahl n = pq erfülle 26^{9} < n < 26^{10}.

a) Schreiben Sie CoCoA Funktionen PreProcess(…) und PostProcess(…), die einen Klartext in eine Folge von Restklassen in ℤ/nZ umwandeln bzw. eine solche Folge in einen Geheimtext aus den 26 Buchstaben.

Hinweise: Ist die letzte Klartexteinheit zu kurz, so soll sie mit Zufallszeichen aufgefüllt werden. Finden Sie “gute” Injektionen ℤ/26^{9}ℤ ⟶ ℤ/nℤ ⟶ ℤ/26^{10}ℤ.

b) Schreiben Sie zwei CoCoA Funktionen RSAEncrypt(…) und RSADecrypt(…), die die Unterprogramme aus a) verwenden und die Verschlüsselungsfunktion f : ℤ/nℤ ⟶ ℤ/nℤ (x ↦ x^{e}) bzw. g : ℤ/nℤ ⟶ ℤ/nℤ (x ↦ x^{d}) implementieren. Hinweis: Um große Potenzen x^{e} modulo n zu berechnen, stellt man e im Binärsystem dar und multipliziert die entsprechenden Potenzen x^{2^{i}}.

c) Verschlüsseln Sie die Nachricht “BITTE SOFORT DREI MILLIONEN EURO UEBERWEISEN” mit Hilfe des RSA Kryptosystems zum öffentlichen Schlüssel (n, e) = (98 022 850 618 897, 31).

Aufgabe 14. (Attacken auf das RSA Kryptosystem)

a) In einer Firma wird stets das RSA Kryptosystem mit e = 3, aber verschiedenen n = pq benutzt. Eines Tages versendet der Chef an drei Mitarbeiter die gleiche Nachricht. Erklären Sie, wie Sie die Nachricht entschlüsseln können. (Tip: Wenden Sie den Chinesischen Restsatz an.)

b) Durch einen Programmierfehler im Zufallsgenerator eines RSA Kryptosystems erhalten zwei Benutzer den gleichen RSA-Modul n = pq zugeteilt. Zeigen Sie, daß jeder die Nachrichten des anderen wie folgt mitlesen kann.

1) Sei e_{A} der öffentliche Schlüssel des anderen, und seien e_{B}, d_{B} der öffentliche und der geheime Schlüssel des Benutzers. Er berechnet h = (e_{B}d_{B} − 1)/ggT(e_{A}, e_{B}d_{B} − 1).

2) Mit Hilfe des erweiterten Euklidischen Algorithmus findet er Zahlen c, d ∈ ℤ mit c h + d e_{A} = 1. (Warum geht dies?)

3) Er potenziert de Geheimtexte das anderen mit d.

c) Bei einem RSA Kryptosystem mit n = pq wurden p und q sehr nahe beieinander gewählt. Zeigen Sie, daß man n wie folgt faktorisieren kann.

1) Prüfe für die ganzen Zahlen t ≥ \sqrt{n} der Reihe nach, ob t^{2} − n eine Quadratzahl ist.

2) Gilt t^{2} − n = s^{2}, so setze p = t + s und q = t − s.

d) Knacken Sie das Kryptosystem aus Aufgabe 13 c).

Aufgabe 15. (ElGamal Kryptographie mit Fermatschen Primzahlen) Sei p ≥ 17 eine Fermatsche Primzahl, d.h. eine Primzahl der Form p = 2^{2^{k}} + 1 mit k ≥ 2.

a)^{∗} Beweisen Sie, daß die Restklasse von 5 die multiplikative Gruppe (ℤ/pℤ)^{×} erzeugt. (Hinweis: Verwenden Sie (ohne Beweis), daß es keine Zahl a ∈ ℤ gibt mit a^{2} ≡ 5 (mod p).)

b) Zeigen Sie, daß man das ElGamal Kryptosystem in ℤ/pℤ wie folgt knacken kann. Gegeben sei a ∈ ℤ und ein g ∈ ℕ_{+}, so daß die Restklasse von g ein Erzeuger von (ℤ/pℤ)^{×} ist. Gesucht sei ein x ∈ {0, …, p − 1} mit g^{x} ≡ a (mod p).

1) Sei ℓ = 2^{k} und sei a_{0} die Restklasse von a in ℤ/pℤ.

2) Für j = 1, …, ℓ berechne b_{j} = a_{j−1}^{2^{ℓ−j}} ∈ {1, −1} und setze x_{j−1} = 0 falls b_{j} = 1 bzw. x_{j−1} = 1 falls b_{j} = −1. Ferner setze g_{j} = g_{j−1}^{2} und a_{j} = a_{j−1} · g_{j−1}^{x_{j−1}}.

3) Gib das Ergebnis x = p − 1 − (x_{0} + 2x_{1} + ⋯ + 2^{ℓ−1}x_{ℓ−1}) aus. Tip: Zeigen Sie g_{j} = g^{2^{j}} und a_{j} = g^{x_{0}+2x_{1}+···+2^{j−1}x_{j−1}} · a für j = 0, …, ℓ.

c) Bei einem ElGamal Kryptosystem mit p = 65537 und öffentlichem Schlüssel 5^{a} = 27849 erreicht uns die Nachricht

(5660, 28471), (17747, 6537), (26694, 32563), (32609, 35447)

Ein Block von drei Buchstaben ABC wurde dabei in die Zahl α·26^{2}+β·26+γ umgewandelt, wobei α, β, γ die Nummern der entsprechenden Buchstaben sind. Entschlüsseln Sie die Nachricht!