Lösung_07 - CDC - Technische Universität Darmstadt

TECHNISCHE UNIVERSITÄT DARMSTADT
FACHGEBIET THEORETISCHE INFORMATIK
PROF. JOHANNES BUCHMANN
DR. JULIANE KRÄMER
Einführung in die
Kryptographie
WS 2015/ 2016
7. Lösungsblatt — 26.11.2015
Ankündigung
-
P1 RSA
Es sei n = pq ein RSA-Modul, wobei p und q verschiedene Primzahlen sind. Im RSA-Verfahren müssen nicht nur der geheime Schlüssel d , sondern auch p, q und ϕ(n) geheimgehalten werden, da aus jedem dieser vier Parameter die anderen
drei berechnet werden können.
1. Zeigen Sie, dass man den Entschlüsselungsexponenten d finden kann, wenn man den öffentlichen RSA-Schlüssel
(n, e) kennt und n faktorisieren kann.
2. Zeigen Sie, wie man n mit Kenntnis von ϕ(n) faktorisieren kann.
3. Es gilt auch, dass man n mit Kenntnis des Entschlüsselungsexponenten d faktorisieren kann. Für kleine e ist dies
einfach zu zeigen, da in diesem Fall ed − 1 ein kleines Vielfaches von ϕ(n) ist. Durch Ausprobieren kann dann also
ϕ(n) herausbekommen werden (womit nach 2. auch n faktorisiert werden kann). Rechnen Sie dies an folgendem
Beispiel nach: n = 187, e = 3, d = 107.
Lösung.
1. Kann man den RSA-Modul n = pq faktorisieren, wobei p und q verschieden Primzahlen sind, so kann man ϕ(n) =
(p − 1)(q − 1) berechnen und damit den Entschlüsselungsexponenten d mit ed = 1 mod ϕ(n) finden.
2. Es gilt ϕ(n) = (p − 1)(q − 1). Wir substituieren nun p = n/q und erhalten ϕ(n) = (n/q − 1)(q − 1) = n − n/q − q + 1,
also die quadratische Gleichung q2 − (n + 1 − ϕ(n)) · q + n = 0. Lösen dieser Gleichung liefert nun q und damit
auch p.
3. Es ist ed − 1 = 320 = 26 · 5, d.h. ϕ(n) ∈ {2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 160, 320}. Da jedoch d < ϕ(n) gilt,
bleiben nur zwei Kandidaten für ϕ(n): 160 und 320. Da ϕ(n) ≤ n ist, können wir 320 ausschließen. Aus 2. wissen
wir: ϕ(n) − n = −p − q + 1 Für 160 ergibt sich nun: 160 − 187 = −27 = −p − q + 1 ⇐⇒ 28 = p + q. Für (p, q)
ergeben sich zwei Kandidaten: (5, 23), (11, 17). Nachrechnen ergibt (p, q) = (11, 17), da ϕ(n) = 160.
P2 RSA
(a) Wählen Sie eine zufällige zweistellige Primzahl p, indem Sie zunächst eine zufällige zweistellige Zahl wählen und
anschließend die nächstgrößere Primzahl finden. Wählen Sie genauso eine Primzahl q. Es soll gelten, dass der
RSA-Modul den Verschlüsselungsexponenten 3 zulässt - sollte dies für Ihre Zahlen nicht zutreffen, wählen Sie bitte
neue.
Lösung. Sei 70 zufällig gewählt. Dann ist p = 71. Sei weiterhin 91 zufällig gewählt. Die nächste Primzahl ist 97.
Für q = 97 ist e = 3 nicht zulässig. Wir wählen zufällig 10 und erhalten q = 11. Somit ist n = p · q = 781 und e = 3
ein zulässiger Verschlüsselungsexponent, denn es gilt ϕ(n) = (p − 1)(q − 1) = 70 · 10 = 700 und ggT(700, 3) = 1.
(b) Bestimmen Sie den Entschlüsselungsexponenten d zum Verschlüsselungsexponenten e = 3 und zum RSA-Modul
aus (a).
Lösung. Wir wenden den erweiterten euklidischen Algorithmus an, um den privaten Schlüssel zu bestimmen. Die
Ausgabe des Algorithmus ist: 700(1) + 3(−233) = 1
Somit ist d = −233 mod 700=467.
1
(c) Verschlüsseln Sie mit den Parametern aus (b) den Klartext m = 13.
Lösung.Es gilt: c = me mod n und daher c = (13)3 mod 781 = 635.
(d) Entschlüsseln Sie den Chiffretext aus (c) mit dem chinesischen Restsatz.
Lösung. Es gilt:
m p = (c d mod p−1 mod p) mod p und mq = (c d mod q−1 mod q) mod q ⇒
m p = (635)467 mod 71 = (67)47 mod 71 = 13
mq = (635)467 mod 11 = (8)7 mod 11 = 2
Somit ist m ≡ 13 mod 71 und m ≡ 2 mod 11
M1 = np = q = 11, M2 = qn = p = 71
Der erweiterte euklidische Algorithmus von p und q ergibt 71(−2) + 11(13) = 1. Daher ist M1−1 = 13 mod 71 = 13
und M2−1 = −2 mod 11 = 9 und m = 13 · 11 · 13 + 2 · 71 · 9 mod 781 = 13.
P3 Low-Exponent-Angriff
Besorgen Sie sich von den anderen Studierenden in der Übung zwei weitere RSA-Moduli und Chiffretexte, die in P2 (c)
berechnet wurden. Wenden Sie den Low-Exponent-Angriff an, um den Chiffretext zu entschlüsseln.
Lösung. Angenommen, es liegen folgende Informationen vor:
Öffentlicher Schlüssel
Chiffretext
(n1 , e) = (781, 3)
(n2 , e) = (85, 3)
(n3 , e) = (69, 3)
635
72
58
Man beachte, dass n1 , n2 und n3 paarweise teilerfremd sein müssen. Es gilt:
m3 ≡ 635 mod 781
m3 ≡ 72 mod 85
m3 ≡ 58 mod 69
n = n1 · n2 · n3 = 781 · 85 · 69 = 4580565
M1 = nn1 = 5865, M2 = nn2 = 53889, M3 = nn3 = 66385.
Die Ausgabe vom erweiterten euklidischen Algorithmus für jeweils Mi und ni (i = 1, 2, 3) ist:
5865(−104) + 781(781) = 1 ⇒ M1−1 = −104 mod 781 = 677
53889(−1) + 85(634) = 1 ⇒ M2−1 = −1 mod 85 = 84
66385(10) + 69(−9621) = 1 ⇒ M3−1 = 10 mod 69 = 10
Daher ist
m3 = 5865 · 677 · 635 + 53889 · 84 · 72 + 66385 · 10 · 58 mod n
= 2023425 + 700557 + 1858780 mod 4580565
= 2197
Somit ist m =
p
3
2197 = 13
H1 Symmetrische und asymmetrische Kryptographie
Alice will an k ihrer Kollegen dieselbe sehr große Datei verschlüsselt senden. Sie kennt bereits die öffentlichen Schlüssel
ihrer Kollegen. Zusätzlich steht ihr und ihren Kollegen ein symmetrisches Verschlüsselungsverfahren (z.B. AES) zur Verfügung. Erklären Sie, wie Alice effizient vorgehen kann, d.h. wie sie möglichst wenige Daten verschlüsseln muss.
Lösung. Alice wählt einen AES-Schlüssel k. Mit diesem verschlüsselt sie die Datei. Dies muss sie nur ein mal machen.
Außerdem verschlüsselt sie mit jedem der öffentlichen Schlüssel ihrer Kollegen den AES-Schlüssel k. Nun sendet sie
die AES-verschlüsselte Datei und die mit den öffentlichen Schlüsseln erstellten Verschlüsselungen von k den jeweiligen
Kollegen zu.
Da die öffentlichen Schlüssel wesentlich kleiner sind als die zu verschlüsselnde Datei, ist dieses Vorgehen effizienter, als
die Datei k mal mit den verschiedenen öffentlichen Schlüsseln zu verschlüsseln.
2

Download Report