Lösung_10 - 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
10. Lösungsblatt — 17.12.2015
Ankündigung
-
P1 ElGamal - Schlüsselerzeugung
In der Vorlesung wurde ein Algorithmus zur Erzeugung sicherer Parameter für den Diffie-Hellman-Schlüsselaustausch
vorgestellt. Verwenden Sie diesen, um einen ElGamal Schlüssel mit einer 6-Bit Primzahl p und einer Basis g , deren
Ordnung (in Z∗p ) eine 3-Bit Primzahl ist, zu erzeugen.
Lösung. Wir wählen erst eine zufällige 3-Bit Primzahl und erhalten q = 5. Nun wählen wir zufällig eine natürliche
(6 − 3)-Bit Zahl und erhalten m = 6. Wir berechnen p = qm + 1 = 31. Da p prim ist fahren wir fort. Wir wählen zufällig
eine Zahl aus {2, 3, . . . , 29} und erhalten x = 14. Nun berechnen wir g = x m mod 31 = 8. Damit ist g ein Erzeuger einer
Untergruppe der Ordnung q von Z∗31 . Wir wählen jetzt noch einen Exponenten, erhalten a = 7, und berechnen A = g a
mod 31 = 2. Der öffentliche Schlüssel ist somit (p, g, A) = (31, 8, 2) und der private Schlüssel a = 7.
P2 ElGamal - Chosen Plaintext
In der Vorlesung wurde gezeigt, dass das ElGamal-Verfahren nicht Chosen-Plaintext sicher ist. Veranschaulichen Sie dies,
indem Sie einen Chosen-Plaintext-Angriff durchführen, wobei der öffentliche Schlüssel (p, g, A) = (601, 7, 598) gegeben
ist. Sie können dafür die Tatsache, dass 102 ein quadratischer Nicht-Rest modulo 601 ist, verwenden.
Hinweis: Wenn Sie das Jacobi-Symbol nicht von Hand berechnen können, können Sie WolframAlpha nutzen. Um ( na )
zu berechnen, wird der Befehl jacobiSymbol (a, n) genutzt. Sollten Sie weder Smartphone noch Laptop bei sich haben,
helfen Ihnen die Tutoren gerne weiter.
Lösung. Wir wählen als Nachrichten einen quadratischen Nicht-Rest modulo 601, zum Beispiel m0 = 102 und einen
quadratischen Rest modulo 601, zum Beispiel m1 = 67. Das Verschlüsselungsorakel wählt jetzt zufällig eine dieser Nachrichten und verschlüsselt diese. Wir bekommen von dem
Orakel die Verschlüsselung (B, c) = (279, 568).
m
598
Da 601
= 1 ist, setzen wir l = 1. Es gilt nun l ∗ 568
=
−1
= 6010 . Somit wurde die Nachricht m0 verschlüsselt.
601
P3 ElGamal - Chosen Ciphertext
In der Vorlesung wurde gezeigt, dass das ElGamal-Verfahren nicht sicher gegen Chosen-Ciphertext-Angriffe ist. Veranschaulichen Sie dies, indem Sie einen Chosen-Ciphertext-Angriff durchführen, wobei der öffentliche Schlüssel (p, g, A) =
(601, 7, 362) und der Chiffretext (B, c) = (54, 101) gegeben sind. Um die Ausgabe des Entschlüsselungsorakels zu berechnen, können Sie den privaten Schlüssel a = 51 verwenden. Verallgemeinern Sie den Angriff und zeigen Sie, dass
homomorphe Verschlüsselungsverfahren (d.h. Verfahren mit Enc(a · b) = Enc(a) · Enc(b)) nicht Chosen-Ciphertext sicher
sind.
Lösung. Wir wählen als neue Nachricht m1 = 234 und verschlüsseln diese. Dazu wählen wir r = 5 und berechnen
(B1 , c1 ) = (g r , Ar m1 ) = (580, 530). Nun lassen wir vom Orakel (BB1 , cc1 ) entschlüsseln und erhalten m0 = 37. Die
ursprüngliche Nachricht ist nun m = m0 m−1
mod 601 = 37 · 244 mod 601 = 13.
1
Die Methode lässt sich wie folgt verallgemeinern. Sei c der zu entschlüsselnde Chiffretext. Wir wählen eine neue Nachricht
m1 und berechnen c1 = Enc(m1 ). Anschließend lassen wir c0 = cc1 vom Orakel entschlüsseln und erhalten m0 mit
−1
−1
−1
Enc(m0 ) = c0 . Die gesuchte Nachricht ist nun m = m0 m−1
1 , da Enc(m) = Enc(m0 m1 ) = Enc(m0 )Enc(m1 ) = c0 c1 = c .
1
H1 ElGamal - Schlüsselerzeugung
Nennen Sie die Aspekte, die bei der Schlüsselerzeugung für das ElGamal-Verfahren zu beachten sind und erklären Sie,
warum diese wichtig sind.
Lösung. Die Primzahl p und der Erzeuger g müssen so gewählt werden wie für den Diffie-Hellman-Schlüsselaustausch.
Insbesondere muss p also so gewählt werden, dass das diskrete Logarithmusproblem modulo p schwer ist. Eine Tabelle mit Mindestgrößen für p, um verschiedene Sicherheitsniveaus zu garantieren, findet sich im Buch „Einführung in
die Kryptographie“. Außderdem muss p so gewählt werden, dass das diskrete Logarithmusproblem kein leichter Spezialfall ist, der von bekannten Algorithmen (z.B. Pohling-Hellman oder dem Zahlkörpersieb) gelöst werden kann. Um
beispielsweise Pohling-Hellman-Angriffe auszuschließen, darf p-1 nicht nur kleine Primfaktoren besitzen.
Nun zur Wahl des Erzeugers g . Es kann gezeigt werden, dass wenn g eine Primitivwurzel modulo p ist, das DecisionalDiffie-Hellman-Problem (DDH) lösbar ist. Stattdessen wird g als Element der Ordnung q gewählt, wobei q eine große
Primzahl ist. Nach aktueller Auffassung ist dann das DDH-Problem schwer zu lösen. Eine Tabelle mit Mindestgrößen für
q, um verschiedene Sicherheitsniveaus zu garantieren, findet sich ebenfalls im Buch „Einführung in die Kryptographie“.
H2 Ordnungen von Gruppenelementen
Sei G = Z∗101 und der Erzeuger g = 2 von G gegeben. Bestimmen Sie die Ordnungen der Gruppenelemente x 1 = 2, x 2 =
4, x 3 = 8, x 4 = g 15 , x 5 = g 50 , x 6 = g 70 , x 7 = g 81 , x 8 = g 100 .
Lösung. Es gilt or d(g k ) =
or d(g)
g g T (or d(g),k) .
Da g = 2 die Gruppe G erzeugt, gilt or d(g) = 100. Somit erhalten wir
or d(2) = 100, or d(4) = 50, or d(8) = 100, or d(g 15 ) = 20, or d(g 50 ) = 2, or d(g 70 ) = 10, or d(g 81 ) = 100
und
or d(g 100 ) = 1.
2

Download Report