Weitere asymmetrische Krypto-Verfahren - Kryptografie - page 218

Mathematische Grundlagen

Die Funktionsweise von NTRU lässt sich mithilfe mathematischer Strukturen
erklären, die man als Gitter bezeichnet. Die meisten Beschreibungen des Verfah-
rens beginnen daher mit einer Einführung in die Gittertheorie. Ich folge dagegen
an dieser Stelle der originalen Beschreibung von NTRU aus der Arbeit von Hoff-
stein, Pipher und Silverman, die ohne die Betrachtung von Gittern auskommt.
In NTRU spielen Polynome der Form f ( x )= a n-1 x n-1 + a n-2 x n-2 +...+ a 1 x + a 0 eine
Rolle. Die Koeffizienten a i sind natürliche Zahlen, mit denen modulogerechnet
wird. Werden zwei Polynome miteinander multipliziert und entsteht dabei ein
Polynom vom Grad n oder größer, dann erfolgt eine Reduzierung (»Abschnei-
den«) in Form einer Teilung durch das Polynom x n -1. Dieses Vorgehen, das dem
Verfahren seinen Namen gab, lässt sich vereinfacht so ausdrücken: Durch eine
Multiplikation entsteht immer ein Polynom vom Grad n -1 oder niedriger. Außer-
dem benötigen wir für die Nutzung von NTRU noch eine kleine natürliche Zahl
p und eine deutlich größere natürliche Zahl q . Typische Werte sind n =503, p =3
und q =256.
Neben der Multiplikation zweier Polynome gibt es auch eine Teilung (Poly-
nomdivision). Diese funktioniert jedoch nur, wenn zum Polynom f , das als Teiler
dient, ein inverses Polynom f -1 existiert, für das gilt: f

· f -1 = 1. Diese Bedingung ist
zwar nicht immer erfüllt, doch es gibt für unsere Zwecke ausreichend viele inver-
tierbare Polynome, die zudem leicht zu ermitteln sind.

Funktionsweise von NTRU

Der öffentliche NTRU-Schlüssel wird wie folgt berechnet: Alice wählt zwei Poly-
nome f und g , wobei f invertierbar sein muss, und berechnet daraus das Polynom
h nach folgender Formel:

h = g / f (mod q )
h ist Alices öffentlicher Schlüssel, f (bzw. f -1 ) der private. Man kann zeigen, dass
unter den gegebenen Rahmenbedingungen g und f eindeutig bestimmt sind, wenn
h und q gegeben sind (wäre es nicht so, dann gäbe es zu einem öffentlichen
Schlüssel mehrere private, was nicht erwünscht ist). Die Formel, nach der h
berechnet wird (Teilen zweier Polynome modulo q ), gilt als Einwegfunktion.
Wäre dies nicht der Fall, dann wäre das Verfahren leicht zu knacken. Wie bei
anderen asymmetrischen Verfahren ist diese Einwegfunktion-Eigenschaft jedoch
nicht bewiesen, sondern nur eine begründete Vermutung.
Zur Verschlüsselung benötigt Bob zunächst Alices öffentlichen Schlüssel h .
Seine Nachricht m kodiert er als Polynom. Außerdem generiert er ein zufälliges
Polynom b , das als Blendpolynom bezeichnet wird (einen zufälligen Bestandteil
gibt es auch bei DSA und ElGamal, jedoch nicht bei RSA). Die Verschlüsselung
erfolgt nach folgender Formel: