Weitere asymmetrische Krypto-Verfahren - Kryptografie - page 222

Beachten Sie, dass im Gleichungssystem immer nur zwei x i -Variablen miteinan-
der multipliziert werden (es kommt also kein Ausdruck wie x 1 · x 2 · x 3 vor). Des-
halb gilt das Gleichungssystem als quadratisch. Diese Eigenschaft hat den Vorteil,
dass sich die jeweiligen Formeln schnell berechnen lassen. Quadratische Glei-
chungssysteme spielen im Übrigen auch bei der quadratischen Kryptoanalyse eine
Rolle, die Sie aus Abschnitt 7.3.4 kennen.
Nun benötigen wir noch ein weiteres Werkzeug: die affine Abbildung . Ist x
eine Variable mit Werten aus GF(2 n ), M eine n × n -Matrix und C eine Konstante
aus GF(2 n ), dann ist eine affine Abbildung A wie folgt definiert:
A ( x )= Mx + C
Mit anderen Worten: Eine affine Abbildung multipliziert eine Matrix mit einem
Vektor und zählt einen weiteren Vektor dazu. Wichtig für uns ist folgende Tatsa-
che, die für jede affine Abbildung A ( x ) gültig ist: Ist f ( x ) ein Polynom, dann sind
sowohl A ( f ( x )) als auch f ( A ( x )) ebenfalls Polynome. Außerdem gilt: Ist f ( x ) als
quadratisches Gleichungssystem darstellbar, dann geht diese Eigenschaft durch
eine affine Abbildung nicht verloren.
Das Verfahren
Um ein HFE-Schlüsselpaar zu generieren, benötigt Alice zunächst ein Polynom f
über GF(2 n ). f muss als quadratisches Gleichungssystem darstellbar sein. Außer-
dem braucht Alice zwei affine Abbildungen S und T , die ebenfalls auf GF(2 n )
arbeiten. Die Matrizen und Konstanten dieser affinen Abbildungen sind zufällig
gewählt. Der öffentliche Schlüssel des HFE-Verfahrens ist das Polynom
g ( x )= T ( f ( S ( x ))) als quadratisches Gleichungssystem dargestellt. Der private
Schlüssel besteht aus f sowie den beiden affinen Abbildungen S und T . Man kann
zeigen, dass es zu einem g ( x ) jeweils nur einen passenden Wert von S , T und f gibt
(wäre es anders, dann gäbe es mehrere private Schlüssel zu einem öffentlichen).
Dass Mallory den privaten HFE-Schlüssel nicht aus dem öffentlichen berech-
nen kann, liegt daran, dass das Umwandeln von f mithilfe von S und T in das
besagte Gleichungssystem, das mit g äquivalent ist, eine Einwegfunktion ist. Wie
bei anderen asymmetrischen Verfahren ist dies allerdings nicht bewiesen, sondern
nur eine Vermutung.
Das Verschlüsseln geschieht wie folgt: Bob nimmt einen n -Bit-Wert als Klar-
text w und berechnet daraus den Schlüsseltext c mit der einfachen Formel c =
g ( w ). Dieser Vorgang ist im Vergleich zu anderen asymmetrischen Verfahren aus-
gesprochen performant zu realisieren - es kommen ja nur Quadrierungen und
Additionen zum Einsatz - und erreicht nahezu die Geschwindigkeit symmetri-
scher Verfahren.
Zur Entschlüsselung berechnet Alice w = S -1 ( f -1 ( T -1 ))). Dieser Vorgang dauert
länger als das Verschlüsseln und benötigt zudem etwas Vorarbeit: Alice muss aus
f die Invertierung f -1 berechnen, was auf einem PC einige Sekunden dauern kann.