Post-Quanten-Kryptografie

Fehlererkennende und fehlerkorrigierende Codes

Ein Code ist in diesem Zusammenhang eine Menge von Wörtern über 𝔹 = {0, 1}, den Codewörtern. Wenn alle Codewörter eine feste Länge n ∈ ℕ haben, so spricht man von einem Blockcode C ⊆ 𝔹ⁿ oder auch einfach von einem n-Bit-Code. Die Codewörter eines Blockcodes lassen sich auch als Vektoren auf­fassen, also als Elemente des Vektorraums 𝔹ⁿ über dem Körper 𝔹 = ℤ₂. Die Vektoren werden im Folgenden ähnlich wie Wörter als Zeilen­vektoren geschrieben.

Ein Blockcode C der Länge n mit weniger als |𝔹ⁿ| = 2ⁿ Codewörtern bietet grund­sätzlich die Möglichkeit der Fehler­erkennung. Solche Fehler sind beispiels­weise Über­tragungsfehler beim Senden über einen störungsanfälligen Kanal.

Denn beim Senden werden aus­schließ­lich Codewörter gesendet – wird jedoch ein Nicht-Codewort empfangen, so ist ein Fehler aufgetreten und damit erkannt worden. Dies ist das Prinzip der Fehler­erkennung bei Codes. Ist ein Fehler erkannt worden, so kann man ihn möglicher­weise sogar korrigieren, indem man annimmt, dass das empfangene Wort aus dem "nächst­gelegenen" Codewort hervor­gegangen ist. Eine wichtige Voraus­setzung hierfür ist, dass das "nächst­gelegene" Codewort eindeutig ist.

Hamming-Abstand

Der Hamming-Abstand ist ein Maß dafür, wie nahe zwei Wörter beieinanderliegen. Er besagt, an wievielen Positionen sich die Bits dieser Wörter unter­scheiden. Um den Hamming-Abstand d(x, y) zweier Wörterx und y ∈ 𝔹ⁿ zu bestimmen, schreiben Sie die Wörter unter­einander und vergleichen sie Bit für Bit. Technisch führen Sie den Vergleich durch, indem Sie die Bits modulo 2 addieren – kommt 1 heraus, so sind die Bits unter­schiedlich, kommt 0 heraus, so sind sie gleich. Oder noch technischer: indem Sie die Wörter als Vektoren auf­fassen und diese addieren.

Die Anzahl der Einsen in einem Wort x ∈ 𝔹ⁿ wird als das Hamming-Gewicht w(x) des Wortes x bezeichnet. Damit gilt für den Hamming-Abstand

d(x, y)  =  w(x⊕y)

Der Hamming-Abstand d(C) eines Codes C ist das Minimum aller Hamming-Abstände zwischen je zwei ver­schiedenen Codewörtern.

Fehlermodell

Die Fehler, die im Folgenden betrachtet werden, entstehen aus­schließ­lich durch "Umkippen" von Bits, also dadurch, dass eine 0 in eine 1 verfälscht wird oder umgekehrt. Nicht betrachtet werden dagegen Fehler, die entstehen, wenn Bits verloren gehen oder sich zusätzlich einschleichen.

Technisch gesehen ist ein Fehler ein Wort e ∈ 𝔹ⁿ mit w(e) > 0. Indem Sie e zu einem Codewort x addieren, verfälschen Sie das Codewort. Der Fehler wird erkannt, wenn x ⊕ e ∉ C gilt, wenn also ein Nicht-Codewort herauskommt.

Ein Fehler e heißt Einfach­fehler, wenn w(e) = 1, und Doppelfehler, wenn w(e) = 2.

Ein Code C mit Hamming-Abstand d(C) > 1 erkennt alle Einfach­fehler. Ein Code C mit d(C) > 2 erkennt alle Doppelfehler usw.

Ein Code C mit d(C) > 2 korrigiert alle Einfach­fehler. Allgemein korrigiert ein Code C mit d(C) > 2·k alle k-fach-Fehler.

Lineare Codes

Ein n-Bit-Code ist ein linearer Code, wenn die Summe zweier Codewörter wieder ein Codewort ergibt. Ein linearer Code bildet einen Teilraum des Vektorraums 𝔹ⁿ.

Wir betrachten im Folgenden eine bestimmte Art von linearen Codes, die systematischen (n,k)-Codes. Dies sind n-Bit-Codes, bei denen die ersten k Bits der Codewörter die eigentliche Information enthalten. Die restlichen n-k Bits sind Prüfbits. Die Prüfbits stellen die nötige Redundanz zur Verfügung, die für die Fehler­erkennung erforderlich ist.

Ein (n,k)-Code enthält 2^k Codewörter, er hat als Teilraum von 𝔹ⁿ die Dimension k.

Die k Basis­vektoren eines (n,k)-Codes unter­einander geschrieben bilden eine Generator­matrix G des Codes. So ist beispiels­weise

G  =

1 0 0 1 0 1 0 1 0 0 1 1

eine Generator­matrix des Codes C4,3.

Die Generator­matrix ist nicht eindeutig, da es verschiedene Basis­vektoren gibt und deren Reihenfolge als Zeilen der Matrix nicht festgelegt ist. Durch äquivalente Umformungen kann die Generator­matrix in die systematische Form G = [I_k P] gebracht werden, wobei I_k die k×k-Einheits­matrix ist. P steht für die weiteren n-k Spalten der Matrix. Die Generator­matrix aus dem obigen Beispiel befindet sich bereits in dieser systematischen Form.

Die Generator­matrix G erzeugt den Code C, indem alle Produkte von Vektoren aus 𝔹^k und G gebildet werden:

C  =   { a·G  |  a ∈ 𝔹^k }

Kontroll­matrix

Aus einer systematischen Generator­matrix G = [I_k P] konstruieren Sie in folgender Weise eine Kontroll­matrix H:

H  =  [P^T I_n-k]

Sie trans­ponieren also den Teil P der systematischen Generator­matrix G und fügen eine (n-k)×(n-k)-Einheits­matrix an.

Fehler­erkennung mit der Kontroll­matrix

Das Produkt x·H^T des Vektors x mit der transponierten Kontroll­matrix wird als das Syndrom von x bezeichnet. Ist das Syndrom ungleich 0, so ist ein Fehler aufgetreten.

Bei fehler­korrigierenden Codes liefert das Syndrom die Information darüber, wie der Fehler zu korrigieren ist. Ein Beispiel hierfür ist der Hamming-Code.

Das Syndrom-Dekodierungs-Problem

Der Hamming-Code ist gerade so konstruiert, dass die Fehler­korrektur mithilfe des Syndroms einfach ist. Im Allgemeinen jedoch ist die Zuordnung zwischen Syndrom und Fehler schwierig. Dies ist das sogenannte Syndrom-Dekodierungs-Problem.

Syndrom-Dekodierungs-Problem

Gegeben:

Linearer (n,k)-Code C mit Hamming-Abstand h, zugehörige (n-k)×n-Kontroll­matrix H, Syndrom s der Länge n-k

Gesucht:

Fehlervektor e der Länge n mit Hamming-Gewicht t ≤ (h-1) div 2, derart dass  e·H^T  =  s  gilt.

Das Syndrom-Dekodierungs-Problem machen Sie in folgender Weise für die Kryptografie nutzbar. Grundlage ist ein linearer Code C, dessen Syndrom einfach zu dekodieren ist (wie z.B. der Hamming-Code). Nun machen Sie die Generator­matrix G dieses Codes unkenntlich, indem sie diese mit zwei zufällig erzeugten Matrizen S und P multiplizieren:

G'  =  S · G · P

Als Empfänger verwenden Sie G' als öffentlichen Schlüssel. Die Matrizen S, G und P bilden Ihren zugehörigen privaten Schlüssel. Ein Syndrom s' von G' ist für einen Angreifer schwer zu dekodieren. Sie hingegen als legitimer Empfänger trans­formieren s' mithilfe von S und P und können es anschließend einfach dekodieren.

Dies ist die Idee des Verschlüsselungs­verfahrens von McEliece, es stammt bereits aus dem Jahr 1978. Damals gab es noch keine Quanten­computer, sondern gerade einmal den 16-Bit-Prozessor Intel 8086 – sicher ein Grund dafür, dass dieses Verfahren seither nicht die Popularität etwa von RSA erfahren hat, denn es ist aufwendiger und schwieriger zu parametrisieren.

McEliece-Verschlüsselung

Gegeben ist die Generator­matrix G eines linearen (n,k)-Codes mit Hamming-Abstand h und eine zugehörige Syndrom-Dekodierungs-Funktion.

Schlüssel erzeugen

Ausgabe:

Öffentlicher Schlüssel G' und privater Schlüssel (S, G, P)

Methode:

1. Erzeuge eine zufällige, invertierbare k×k-Matrix S
2. Erzeuge eine zufällige n×n-Permutationsmatrix P
3. Berechne   G'  =  S · G · P
4. Gib G' als öffentlichen Schlüssel und (S, G, P) als privaten Schlüssel zurück

Verschlüsseln

Eingabe:

Öffentlicher Schlüssel G' und Klartext m ∈ 𝔹ⁿ

Ausgabe:

Geheimtext c

Methode:

1. Erzeuge einen zufälligen n-Bit-Vektor e mit Hamming-Gewicht w(e) = (h-1) div 2
2. Berechne   c  =  m · G'  + e
3. Gib den Geheimtext c zurück

Entschlüsseln

Eingabe:

Privater Schlüssel (S, G, P) und Geheimtext c

Ausgabe:

Klartext m ∈ 𝔹ⁿ

Methode:

1. Berechne   u  =  c · P^-1
2. Berechne das Syndrom   s'  =  u · H^T
3. Dekodiere aus s' den zugehörigen Fehlervektor e'
4. Berechne v'  =  u + e' und berücksichtige nur die Informationsbits, also die ersten k Bits von v' und erhalte so v
5. Berechne m  =  v · S^-1

Beispiel mit kleinen Zahlen

Gegeben ist ein linearer (7,4)-Code C mit 4×7-Generator­matrix

G  =

1 0 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1

und die zugehörige 3×7-Kontroll­matrix

H  =

0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1

Der Code hat den Hamming-Abstand d(C) = 3.

Schlüssel erzeugen

In Schritt 1 erzeugen Sie eine zufällige, invertier­bare 4×4-Matrix

S  =

1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0

In Schritt 2 erzeugen Sie eine zufällige 7×7-Permutationsmatrix

P  =

1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0

In Schritt 3 berechnen Sie G'  =  S · G · P

G'  =

1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1

Sie geben nun den öffentlichen Schlüssel G' und den privaten Schlüssel (S, G, P) zurück.

Verschlüsseln

Als Eingabe verwenden Sie den öffentlichen Schlüssel G' des Empfängers sowie einen Klartext der Länge 4, also z.B. m  =  [1 0 1 1].

In Schritt 1 erzeugen Sie einen zufälligen n-Bit-Vektor e mit Hamming-Gewicht w(e)  =  (h-1) div 2  =  1:

e  =  [0 0 1 0 0 0 0]

In Schritt 2 berechnen Sie   c  =  m · G' + e   =  

[ 1 0 1 1 ]

·

1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1

+

[ 0 0 1 0 0 0 0 ]

=

[ 0 1 0 0 1 1 0 ]

Zum Schluss geben Sie den Geheimtext c  =  [0 1 0 0 1 1 0] zurück.

Entschlüsseln

Als Eingabe verwenden Sie Ihren privaten Schlüssel (S, G, P) sowie den Geheimtext c.

In Schritt 1 berechnen Sie   u  =  c · P^-1  =  

[ 0 1 0 0 1 1 0 ]

·

1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0

=

[ 0 0 0 1 1 0 1 ]

Für eine Permutationsmatrix P gilt   P^-1  =  P^T.

In Schritt 2 berechnen Sie   s'  =  u · H^T   =  

[ 0 0 0 1 1 0 1 ]

·

0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1

=

[ 0 1 0 ]

In Schritt 3 dekodieren Sie das Syndrom s', d.h. Sie suchen den zugehörigen Fehlervektor e'. Dieser ist

e'  =  [0 0 0 0 0 1 0]   (denn e' · H^T  =  s')

In Schritt 4 korrigieren Sie das Zwischen­ergebnis u, indem Sie den Fehlervektor e' addieren:

v'   =   u + e'   =   [0 0 0 1 1 0 1] + [0 0 0 0 0 1 0]   =   [0 0 0 1 1 1 1]

Von v' berück­sichtigen Sie nur die Informationsbits, also die ersten 4 Bits, und erhalten

v   =   [0 0 0 1]

In Schritt 5 schließlich machen Sie S rückgängig durch   m  =  v · S^-1  =  

[ 0 0 0 1 ]

·

1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1

=

[ 1 0 1 1 ]

Wie gewünscht haben Sie den ursprüng­lichen Klartext m zurückerhalten.

Literatur

Die hier gewählte Darstellung folgt dem Buch

[PPG 24]   C. Paar, J. Pelzl, T. Güneysu: Understanding Crytography. 2. Auflage, Springer (2024)