Lernkontrollfragen

Public-Key-Algorithmen WS2015/2016
Lernkontrollfragen
Michael Braun
• Was bedeuten die kryptographischen Schutzziele
Vertraulichkeit, Integrität, Nachrichtenauthentizität,
Teilnehmerauthentizität, Verbindlichkeit?
• Durch welche Verfahren lassen sich die einzelnen Schutzziele
erreichen?
• Was ist die grundlegende Idee hinter einem symmetrischen
und einem asymmetrischen Ansatz?
1 / 17
• Wie ist die grundlegende Funktionsweise einer symmetrischen
Verschlüsselung und eines Message-Authentication-Codes?
• Wie ist die grundlegende Funktionsweise einer asymmetrischen
Verschlüsselung und einer digitalen Signatur?
• Wie ist die grundlegende Funktionsweise eines
Challenge-Response-Verfahrens? Welche Varianten gibt es
sowohl für einen symmetrischen als auch für einen
asymmetrischen Ansatz?
2 / 17
• Wie ist die Funktionsweise der drei wesentlichen
asymmetrischen Ansätze: RSA, Diskreter Logarithmus (DL),
Elliptische Kurven (ECC)? Worauf beruht die Sicherheit der
drei Verfahren?
• Wie ist die Funktionsweise der RSA-Verschlüsselung (und
natürlich auch Entschlüsselung!) und der RSA-Signatur? Wie
werden die Schlüssel erzeugt?
• Wie sind die Systemparameter und die Schlüssel bei dem
herkömmlichen DL-Verfahren aufgebaut? Wie werden
DL-Schlüssel erzeugt?
• Wie sind die Systemparameter und die Schlüssel bei dem
ECC-Verfahren aufgebaut? Wie werden ECC-Schlüssel
erzeugt?
3 / 17
• Wie funktioniert das Diffie-Hellman-Protokoll in GF (p)? Was
kann damit erreicht werden? Worauf basiert die Sicherheit des
Protokolls?
• Wie funktioniert eine ElGamal-Verschlüsselung in GF (p)?
• Wie funktioniert eine Challenge-Response-Authentifizierung in
GF (p)?
4 / 17
• Wie sind endliche Körper definiert?
• Wie sind die beiden Typen von Körpern – Primkörper und
binärer Erweiterungskörper – aufgebaut? Wie lassen sich die
Körperelemente in beiden Fällen darstellen?
• Was ist ein unzerlegbares (=irreduzibles) Polynom und wozu
wird es benötigt bei der Konstruktion binärer
Erweiterungskörper?
• Wie lassen sich die Elemente eines binären
Erweiterungskörpers als Vektoren darstellen? Welche
algebraische Operation entspricht dann ein Links- bzw.
Rechtsshift bei den Vektoren?
• Wie werden die Elemente eines binären Erweiterungskörpers
effizient auf einer W -Bit-Plattform repräsentiert?
5 / 17
• Wie funktionieren die grundlegenden Rechenoperationen wie
Addition, Multiplikation, additive und multiplikative Inversion
in Primkörpern und binären Erweiterungskörpern?
• Wie funktionieren Subtraktion und additive Inversion in
binären Erweiterungskörpern? Wie kann man sich dieses
Verhalten erklären?
6 / 17
• Welche Algorithmen gibt es zur Multiplikation in binären
Erweiterungskörpern?
• Wie funktioniert der Shift-and-Add-Algorithmus zur
Multiplikation in binären Erweiterungskörpern und welche
Komplexität besitzt der Algorithmus? (Algorithmus soll
theoretisch beschrieben und praktisch angewendet werden
können)
• Wie funktionieren die folgenden Algorithmen zur
Multiplikation von binären Polynomen (ohne Reduktion!):
R2L, L2R, L2R-Window (Algorithmen, Ansätze und Ideen
müssen verstanden werden; Beschreibung der vollständigen
Algorithmen wird in der Klausur nicht verlangt)
• Wie funktioniert der Karatsuba-Algorithmus und was ist die
Komplexität des Algorithmus?
7 / 17
• Wie multipliziert man ein binäres Polynom effizient mit sich
selbst (=Quadrierung)?
• Wie wird grundlegend reduziert im binären
Erweiterungskörper?
• Wie funktioniert eine effiziente Reduktion?
• Wie funktioniert die spezielle Reduktion bei einem
vorgegebenen unzerlegbaren Polynom? (Idee hinter
Algorithmus muss verstanden werden; der in der Vorlesung
angegebene Algorithmus für 163 muss nicht wiedergegeben
werden in der Klausur)
8 / 17
• Wie funktioniert die Division mit Rest bei ganzen Zahlen?
• Was ist der größte gemeinsame Teiler von zwei ganzen
Zahlen?
• Welche grundlegende Eigenschaften erfüllt der größte
gemeinsame Teiler?
• Wie funktioniert der euklidische Algorithmus zur Berechnung
eines größten gemeinsamen Teilers? (rekursive und iterative
Versionen sollen theoretisch beschrieben und praktisch
angewendet werden können)
9 / 17
• Was besagt der Satz von Bezout?
• Wie funktioniert der erweiterte euklidische Algorithmus?
(Algorithmus soll verstanden werden und praktisch
angewendet werden können; es wird keine theoretische
Beschreibung des gesamten Algorithmus verlangt in der
Klausur)
• Was ist die grundlegende Idee hinter dem binären euklidischen
Algorithmus? (Algorithmus soll verstanden werden; es wird
keine theoretische Beschreibung des gesamten Algorithmus
verlangt in der Klausur)
10 / 17
• Wie lassen sich die Fragen der letzten beiden Folien für
Polynome über Primkörpern beantworten?
11 / 17
• Wie sind elliptische Kurven definiert über den reellen Zahlen?
Wie sind elliptische Kurven über einem endlichen Körper
(Primkörper bzw. binären Erweiterungskörper) definiert?
• Wie sieht eine elliptische Kurve im Reellen aus?
• Wie kann man eine elliptische Kurve über einem kleinen
Primkörper zeichnen?
• Wie kann man auf einer elliptische Kurve rechnen?
(Anschauliche Interpretation im Reellen und Übertragung auf
endliche Körper; die Formeln für Addition und Verdoppelung
müssen nicht auswendig gelernt werden; falls die Formeln
benötigt werden, sind sie angegeben)
12 / 17
• Was sind die Eigenschaften der Rechenregel? (additive
Gruppe)
• Wie sind negative Punkte definiert für elliptische Kurven über
den reellen Zahlen, über Primkörpern bzw. binären
Erweiterungskörpern?
• Was ist der unendliche ferne Punkt? Wie sind die
Rechenregeln für den unendlich fernen Punkt?
13 / 17
• Wie ist die Skalarmultiplikation auf elliptischen Kurven
definiert?
• Wie funktionieren Double-and-Add, Add-and-Double und die
Montgomery-Leiter zur Berechnung der Skalarmultiplikation?
(Alle drei Versionen der Algorithmen sollen verstanden und
theoretisch beschrieben werden können; Montgomery muss
nur auf High-Level-Ebene beschrieben werden können; die
Herleitung der Formeln für die projektiven Koordinaten ohne
y-Koordinate muss verstanden werden, wird aber nicht in der
Klausur verlangt)
• Was sind projektive Koordinaten und welche Vorteile ergeben
sich durch die Verwendung dieser Koordinaten?
14 / 17
• Was sind die Systemparameter einer elliptischen Kurve? Was
sind die einzelnen Bestandteile (Endliche Körper,
Kurvenparameter, Basispunkt, Ordnung des Basispunktes,
Cofaktor)
• Wie ist das Diskrete-Logarithmus-Problem (DLP) auf
elliptische Kurven?
• Wie funktioniert der Baby-Step-Giant-Step-Angriff zur
Berechnung des DLPs und welche Komplexität besitzt dieser
Angriff?
• Wie werden privater und öffentlicher Schlüssel eines
ECC-Systems erzeugt?
15 / 17
• Wie funktioniert das Diffie-Hellman-Protokoll für elliptische
Kurven? Was kann damit erreicht werden? Worauf basiert die
Sicherheit des Protokolls?
• Wie funktioniert eine ElGamal-Verschlüsselung auf Basis
elliptischer Kurven?
• Wie funktioniert eine Challenge-Response-Authentifizierung
auf Basis elliptischer Kurven?
• Wie funktioniert der DSA (Signaturstandard)? (Algorithmus
muss verstanden werden, aber nicht vollständig beschrieben
werden können in der Klausur)
16 / 17
• Es sind keine Hilfsmittel zugelassen!
• Es wird 5-6 Aufgaben aus allen wichtigen Themenfeldern der
Vorlesung geben (Arithmetik Zahlen/Polynome/Körper,
Arithmetik Kurven, Protokolle etc.)
17 / 17

Download Report