Ferienübung - CDC - Technische Universität Darmstadt

Technische Universität Darmstadt
Fachgebiet Theoretische Informatik
Prof. Johannes Buchmann
Thomas Wunderer
Einführung in die
Kryptographie
WS 2016/ 2017
Ferienübung
Diese Ferienübung ist personalisiert. Das heißt, Sie erstellen sich aus ihrer Matrikelnummer k ihre individuellen
Aufgaben. Bei jeder Aufgabe müssen Sie ein “Lösungswort” (kein echtes Wort) erstellen und dieses in die folgende
Tabelle eintragen. Die letzte Spalte lassen Sie frei, diese wird bei der Korrektur ausgefüllt.
Personalien (ausfüllen)
Lösungen (ausfüllen)
richtig/falsch
`1 :
`2 :
Name:
`3 :
Matrikelnummer k:
`4 :
`5 :
Bonus ja/nein:
Die Bearbeitung der Aufgaben ist freiwillig.
Sie erhalten einen Bonus für die Klausur, wenn Sie mindestens 3 der 5 Aufgaben richtig gelöst haben. Der Bonus
entspricht einer Notenstufe und wird nur angerechnet, falls die Klausur auch ohne Bonus bestanden ist. Der Bonus
kann also nicht beim Bestehen der Klausur helfen.
Eine Aufgabe gilt als richtig gelöst, wenn das Lösungswort richtig ist und der vollständige Rechenweg ersichtlich ist.
Wird in der Aufgabe ein spezieller Rechenweg gefordert (beispielsweise schnelle Exponentiation oder Low-Exponent
Angriff), muss dieser auch verwendet werden. Folgefehler werden nicht berüchsichtigt (das Lösungswort muss richtig
sein, damit eine Aufgabe als richtig gilt) und es werden keine Teilpunkte auf Aufgaben vergeben. Überprüfen Sie
daher sorgfältig Ihr Ergebnis.
Geben Sie Ihren handgeschriebenen vollständigen Rechenweg sowie dieses Deckblatt ausgefüllt und zusammengeheftet
in einer Übung oder Sprechstunde bis spätestens zum 13.01.2017 (einschließlich) ab. Sollten Sie bis dahin nicht
in Darmstadt sein, melden Sie sich bitte bei [email protected]. Alle Übungen, die bis
Freitag, den 13.01.2017, nicht abgegeben werden, werden nicht bewertet. Sie bekommen die Ferienübungen nicht
korrigiert zurück und es wird keine eigene Einsicht für die Ferienübung geben. Sie können die Ferienübung bei der
Klausureinsicht mit einsehen.
F1 Erweiterter Euklidischer Algorithmus
Sei k Ihre Matrikelnummer.
1. Berechnen Sie mit Hilfe des Euklidischen Algorithmus
ggT(k, 24), ggT(k, 31), ggT(k, 37), ggT(k, 43), ggT(k, 55).
2. Invertieren Sie die gegebenen Zahlen im jeweiligen Ring mit Hilfe des erweiterten Euklidischen Algorithmus
oder argumentieren Sie, warum kein Inverses existiert:
k mod 24 ∈ Z/24Z, k mod 31 ∈ Z/31Z, k mod 37 ∈ Z/37Z, k mod 43 ∈ Z/43Z, k mod 55 ∈ Z/55Z.
3. Ihr Lösungswort ist
¨
`1 = (x 24 , x 31 , x 37 , x 43 , x 55 ),
wobei x i =
(k mod i)−1 ∈ Z/iZ
falls k mod i invertierbar in Z/iZ ist
ggT(k, i)
sonst
.
F2 Affin lineare Blockchiffre
Sei k Ihre Matrikelnummer. Wir betrachten eine affin lineare Blockchiffre E : (Z13 )3 → (Z13 )3 , x → (Ax + b) mod 13
mit Klar- und Schlüsseltextraum (Z13 )3 .
Sie kennen die folgenden Klar- und Schlüsseltextpaare einer affin linearen Blockchiffre:
Klartext
m0 = (2, 5, 1)>
m1 = (1, 8, 7)>
m2 = (11, 6, 3)>
m3 = (4, 9, 10)>
→
→
→
→
→
Schlüsseltext
c0 = E(m0 ) = ((10 + 6k) mod 13, (7 + k) mod 13, 11 mod 13)>
c1 = E(m1 ) = ((1 + 2k) mod 13, (3 + 7k) mod 13, 3 mod 13)>
c2 = E(m2 ) = ((12 + 9k) mod 13, (10 + 3k) mod 13, 4 mod 13)>
c3 = E(m3 ) = ((6k) mod 13, (10k) mod 13, 12 mod 13)>
3
Bestimmen Sie die Verschlüsselungsfunktion (also die Matrix A ∈ Z3×3
13 und den Vektor b ∈ Z13 ).
Das Lösungswort ist `2 = (A, b).
F3 RSA
Sei n = 55 = pq mit p = 5 und q = 11.
1. Berechnen Sie Ihren öffentlichen RSA-Schlüssel wie folgt aus Ihrer Matrikelnummer k. Setzen Sie e = k mod
ϕ(n). Ist e = 0, so wählen Sie stattdessen e = 7. Ist e = 1, so wählen Sie stattdessen e = 11. Testen Sie,
ob e ein zulässiger Verschlüsselungsexponent zu n ist. Falls nicht, so wählen Sie e als den nächst größeren
Verschlüsselungsexponenten, der von n zugelassen wird. Ihr öffentlicher Schlüssel ist nun (n, e).
2. Berechnen Sie Ihren zugehörigen privaten Schlüssel d .
3. Wählen Sie als Nachricht m1 = k mod n. Ist m1 = 0, so wählen Sie stattdessen m1 = 7. Ist m1 = 1, so wählen
Sie stattdessen m1 = 11. Berechnen Sie c1 als Verschlüsselung von m1 mit Ihrem öffentlichen Schlüssel unter
Verwendung schneller Exponentiation.
4. Wählen Sie als Chiffretext c2 = k mod n. Ist c2 = 0, so wählen Sie stattdessen c2 = 7. Ist c2 = 1, so wählen
Sie stattdessen c2 = 11. Berechnen Sie m2 als Entschlüsselung von c2 mit Ihrem privaten Schlüssel unter
Verwendung des chinesischen Restsatzes.
5. Das Lösungswort `3 ist
`3 = (e, d, m1 , c1 , m2 , c2 ).
2
F4 Low-Exponent Angriff auf Rabin
Sei k Ihre Matrikelnummer, k0 die letzte Ziffer von k und k00 die vorletzte Ziffer von k (Beispiel: ist k = 123456 so ist
k0 = 6 und k00 = 5).
Seien n1 = 161 und n2 = 781 zwei öffentliche Rabin-Schlüssel und c1 = (k0 (9k0 + 6k00 + 19) + k00 (k00 + 60) + 95) mod 161
und c2 = (9(k0 )2 + 6k0 k00 + 180k0 + (k00 )2 + 60k00 + 119) mod 781 zugehörige Verschlüsselungen der selben Nachricht m.
Verwenden Sie den Low-Exponent Angriff um die Nachricht m zu bestimmen. Ihr Lösungswort `4 ist
`4 = (c1 , c2 , m).
F5 Diffie-Hellman
Sei k Ihre Matrikelnummer, k0 die letzte Ziffer von k und k00 die vorletzte Ziffer von k (Beispiel: ist k = 123456 so ist
k0 = 6 und k00 = 5).
Alice und Bob benutzen das Diffie-Hellman-Schlüsselaustausch-Verfahren mit der Gruppe G = (Z/17Z)∗ und dem
Basiselement (Erzeuger) g = 3 ∈ G . Sie belauschen, dass Alice den Wert A = k0 + 5 an Bob schickt und Bob mit
B = k00 + 6 antwortet.
1. Wie lautet Alices geheimer Exponent a?
2. Was ist Bobs geheimer Exponent b?
3. Wie lautet der gemeinsame Schlüssel K , auf den sich die beiden geeinigt haben?
Ihr Lösungswort `5 ist
`5 = (A, a, B, b, K).
3

Download Report