Ziel dieser Arbeit ist es, eine verständliche Einführung zum Original-Verfahren von McEliece aus 1978 sowie zur Niederreiter Variante des Verfahrens zu geben.
Hierfür wird die in den Systemen verwendete Code Klasse der Goppa Codes detailliert eingeführt. Es sollen Optimierungen und Schwächen des McEliece sowie des Niederreiter Systems aufgezeigt werden. Anschließend soll darauf aufbauend die aktuelle Classic McEliece Variante des Systems vorgestellt werden. Danach erfolgt eine Sicherheitsanalyse der Classic McEliece Variante, da diese höchste Relevanz und Aktualität bietet. Abschließend gibt diese Arbeit einen Vorschlag zu einer didaktischen Umsetzung bezüglich der Behandlung etwaiger Themen.
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen
2.1 Hamming-Distanz und -Gewicht
2.2 Fehlererkennende und -korrigierende Codes
2.3 Lineare Codes
3 Goppa Codes
3.1 Parameter eines Goppa Codes
3.2 Binäre Goppa Codes
3.3 Kontrollmatrix
3.4 Generatormatrix
3.5 Fehlerbehebung für irreduzible binäre Goppa Codes
3.6 Entschlüsselung
3.7 Beispiel eines irreduziblen binären Goppa Codes
3.7.1 Schlüsselerzeugung
3.7.2 Ver- und Entschlüsselung
4 Das McEliece Kryptosytem
4.1 Symmetrische und asymmetrische Verschlüsselungsverfahren
4.2 Schlüsselerzeugung
4.3 Ver- und Entschlüsselung im McEliece Kryptosystem
4.4 Beispiel zum McEliece Kryptoystem
4.4.1 Verschlüsselung und Schlüsselerzeugung
4.4.2 Entschlüsselung
4.5 Optimierung des Systems
5 Das Niederreiter Kryptosystem
5.1 Schlüsselerzeugung
5.2 Verschlüsselung
5.3 Entschlüsselung
5.4 Beispiel zum Niederreiter Kryptosystem
5.4.1 Verschlüsselung
5.4.2 Entschlüsselung
5.5 Optimierung des Systems
6 Schwächen des Systems
6.1 Message-Resend Condition Attack
6.2 Broadcast Attack
6.3 Sicherheitseigenschaften der Systeme
7 Aktuelle Variante des Systems
8 Sicherheit des Systems
8.1 Äquivalenz der Kryptosysteme
8.1.1 Transformation von McEliece zu Niederreiter
8.1.2 Tansformation von Niederreiter zu McEliece
8.2 Angriffe auf das System
8.2.1 Sicherheit der Nachricht
8.2.2 Sicherheit des Schlüssels
8.2.3 Side Channel Attacks
8.3 Wahl der Parameter
9 Didaktische Umsetzung
9.1 Bildungsziele
9.2 Umsetzung der Unterrichtsreihe
10 Ausblick
Zielsetzung & Themen
Die Arbeit verfolgt das Ziel, eine verständliche Einführung in das ursprüngliche McEliece-Verfahren von 1978 sowie dessen Niederreiter-Variante zu bieten. Im Fokus steht die detaillierte Analyse der verwendeten Goppa-Codes, eine Untersuchung der Schwächen und Optimierungsmöglichkeiten sowie eine sicherheitstheoretische Bewertung des aktuellen Classic-McEliece-Verfahrens, ergänzt durch einen didaktischen Vorschlag für deren Behandlung im Informatikunterricht.
- Grundlagen fehlerkorrigierender Codes (Hamming-Distanz, lineare Codes)
- Mathematische Fundierung und Funktionsweise von Goppa-Codes
- Implementierung der McEliece- und Niederreiter-Kryptosysteme
- Sicherheitsanalyse gegen moderne Angriffe (ISD, SSA, Side Channel)
- Didaktische Konzepte zur Vermittlung in der gymnasialen Oberstufe
Auszug aus dem Buch
3.5 Fehlerbehebung für irreduzible binäre Goppa Codes
Wie bereits in Theorem 3.2 gezeigt, gilt für einen binären irreduziblen Goppa Code, welcher durch ein Polynom vom Grad t generiert wurde, dass die minimale Hamming-Distanz 2t + 1 beträgt. Wir wissen, dass der Code also bis zu t Fehler korrigieren kann. Im Folgenden wird der 1975 von Patterson [Pat75] veröffentlichte Fehlerkorrektur-Algorithmus vorgestellt. Dieser ermöglicht es für einen irreduziblen binären Goppa Code Γ(L, g(x)) bis zu t auftretende Fehler effizient korrigieren zu können.
Sei c ∈ Γ(L, g(x)) ein Codewort und f ∈ K₂ⁿ mit wt(f) ≤ t der Fehlervektor, der bei der Übertragung von Codewort c auftritt. Nach der Übertragung von c erhalten wir ein fehlerhaftes Wort ĉ für das ĉ = c + f gilt. Um die auftretenden Fehler in den übertragenen Nachrichten effizient ermitteln zu können, lässt sich im Folgenden ein sogenanntes Fehlerlokalisierungspolynom definieren. Das Fehlerlokalisierungspolynom σ(x) ist von der Form σ(x) = Π_{i, f_i=0} (x − α_i) ∈ K_{2^m}[X].
Die Einträge f_i stehen für die Bits aus dem Fehlervektor an i-ter Stelle, die ungleich der Null sind. Das Produkt enthält also für jedes f_i = 1 den passenden Term (x − α_i). Dadurch lässt sich der Fehlervektor anhand des Fehlerlokalisierungspolynoms rekonstruieren. Dies funktioniert indem man alle α_i, aus dem Support L, in σ(x) einsetzt. Falls gilt σ(α_i)=0 ist klar, dass an einer Stelle des Produktes (α_i − α_i)=0 enthalten sein muss. Daraus lässt sich folgern, dass an i-ter Stelle des Fehlervektors eine 1 steht.
Im Folgenden wird gezeigt, wie sich ein solches Polynom σ(x) für binäre irreduzible Goppa Codes bestimmen lässt.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung motiviert die Relevanz der Post-Quanten-Kryptographie angesichts der Bedrohung durch Quantencomputer und führt das Classic McEliece Verfahren als vielversprechenden, sicherheitsgeprüften Kandidaten ein.
2 Grundlagen: Hier werden die mathematischen Basisbegriffe der Kryptographie sowie fehlerkorrigierender Codes, insbesondere Hamming-Distanz und lineare Codes, definiert.
3 Goppa Codes: Dieses Kapitel führt Goppa-Codes formal ein, erläutert ihre Parameter, Generierung und Matrixdarstellung und beschreibt den Patterson-Algorithmus zur Fehlerkorrektur.
4 Das McEliece Kryptosytem: Es erfolgt die Einführung in die Funktionsweise des asymmetrischen McEliece-Systems, inklusive detaillierter Schlüsselerzeugung, Ver- und Entschlüsselung sowie Optimierungsansätzen.
5 Das Niederreiter Kryptosystem: Dieses Kapitel stellt die Niederreiter-Variante vor, die durch die Verwendung von Syndromen anstelle von Codewörtern eine effizientere Implementierung ermöglicht.
6 Schwächen des Systems: Es werden Sicherheitslücken wie die Message-Resend Condition Attack und die Broadcast Attack thematisiert, die bei unsachgemäßer Verwendung auftreten können.
7 Aktuelle Variante des Systems: Hier wird das Classic McEliece KEM als zeitgemäße, gegen adaptive Angriffe resistente Variante vorgestellt.
8 Sicherheit des Systems: Es wird die theoretische Äquivalenz zwischen McEliece und Niederreiter dargelegt und eine Analyse gegen moderne Bedrohungen wie ISD- und Side-Channel-Angriffe durchgeführt.
9 Didaktische Umsetzung: Dieser Abschnitt erörtert die Einbindung des Themas in den Informatikunterricht der gymnasialen Oberstufe unter Berücksichtigung fächerübergreifender mathematischer Kompetenzen.
10 Ausblick: Das Kapitel schließt mit einer Bewertung des Classic McEliece Verfahrens als zukunftsträchtige Lösung und verweist auf den Bedarf an weiteren Optimierungen für ressourcenbeschränkte Systeme.
Schlüsselwörter
Kryptographie, Post-Quanten-Kryptographie, McEliece, Niederreiter, Goppa-Codes, Fehlerkorrektur, Patterson-Algorithmus, Classic McEliece, KEM, Sicherheit, Matrizen, Vektoren, Informatikunterricht, Didaktik, Quantencomputer
Häufig gestellte Fragen
Worum geht es in dieser Bachelorarbeit grundsätzlich?
Die Arbeit befasst sich mit der Analyse und didaktischen Einordnung von code-basierten Verschlüsselungsverfahren, insbesondere des klassischen McEliece-Kryptosystems und dessen Niederreiter-Variante, im Kontext der Post-Quanten-Kryptographie.
Welche zentralen Themenfelder behandelt die Arbeit?
Die zentralen Schwerpunkte liegen auf den mathematischen Grundlagen der Goppa-Codes, deren Anwendung in kryptografischen Systemen, der Sicherheitsanalyse gegen verschiedene Angriffsvektoren sowie der praktischen Umsetzung im schulischen Bildungskontext.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist es, eine verständliche Einführung in die Funktionsweise und Sicherheit der McEliece- und Niederreiter-Verfahren zu geben und zu zeigen, wie diese komplexe Thematik für den Informatikunterricht in der Oberstufe aufbereitet werden kann.
Welche wissenschaftlichen Methoden werden verwendet?
Es handelt sich um eine theoretische Arbeit, die auf der mathematischen Herleitung von Codierungseigenschaften, einer vergleichenden Analyse kryptografischer Protokolle und der Literaturrecherche aktueller Sicherheitsstandards basiert.
Welche Aspekte stehen im Hauptteil der Arbeit im Vordergrund?
Der Hauptteil konzentriert sich auf die formale Definition von Goppa-Codes, die detaillierte Beschreibung des Entschlüsselungsprozesses mittels Patterson-Algorithmus und die sicherheitstheoretische Diskussion der Robustheit gegenüber modernen Angriffen wie ISD oder Side-Channel-Attacken.
Durch welche Schlüsselbegriffe ist die Arbeit charakterisiert?
Die Arbeit ist geprägt durch Begriffe wie quantencomputerresistente Verfahren, Goppa-Codes, Syndrom-Decodierung, IND-CCA2-Sicherheit und didaktische Reduktion mathematischer Komplexität.
Was unterscheidet das Niederreiter-System vom ursprünglichen McEliece-System?
Während McEliece auf der Generatormatrix basiert und ein fehlerhaftes Codewort sendet, nutzt das Niederreiter-System die Kontrollmatrix und überträgt ein Syndrom, was oft zu einer effizienteren Implementierung führt.
Warum ist das Classic McEliece KEM als Sicherheitsstandard relevant?
Das Classic McEliece KEM gilt als hochgradig sicher gegen Post-Quanten-Angriffe und ist ein aktueller Finalist im NIST-Standardisierungsprozess für neue kryptografische Verfahren.
- Quote paper
- Jannik Büscher (Author), 2021, Goppa Codes und ihr Nutzen im McEliece Kryptosystem, Munich, GRIN Verlag, https://www.grin.com/document/1119022
