Cryptography Engineering, Teil 1: Zur Theorie des Advanced Encryption Standard

 –  3 Kommentare

Ob verschlüsseltes HTTPS, bargeldloser Zahlungsverkehr oder digitaler Personalausweis, die Kryptografie hat die digitale Welt fest im Griff. Die Mathematik dahinter ist spannend und teils ästhetisch, aber auch bisweilen kompliziert. Sie in einer lauffähigen Software zu bändigen, ist eine faszinierende Kunst. Doch wie wandelt sich eine mathematische Theorie in eine effiziente Computeranwendung? Antworten liefert diese nun startende Artikelreihe.

Wer sich mit der Literatur zur Kryptografie befasst, stellt schnell fest, dass sie ein tiefer Graben durchzieht. Die meisten Werke sind entweder mathematisch fundiert und detailliert, aber anwendungsfern, oder sie sind algorithmisch orientiert, aber in den mathematischen Grundlagen schwach. Nur wenige Ausnahmen schaffen es, den Bogen von der mathematischen Theorie bis zur IT-Anwendung zu spannen wie Johannes Buchmann in seiner Einführung in die Kryptografie [1]. Die Situation an Universitäten ist häufig vergleichbar.

Doch selbst wer sich auf die Pfade der wenigen mathematisch fundierten und dennoch algorithmisch talentierten Praktiker begibt, wird anfangs ein wenig konsterniert feststellen, dass Kryptografie auch so ein starker Tobak ist. Selbst algorithmische Ausarbeitungen in der Literatur gehen selten über die Möglichkeiten des Pseudocodes hinaus. Konkrete Zielplattformen mit ihren individuellen, teils speziellen Hardwareeigenschaften finden kaum Beachtung.

An der Stelle sei nun ein Spagat gewagt. Dieser und weitere Teile befassen sich mit dem Feld des Cryptography Engineering, der Disziplin also, die Kryptografie in Anwendungen umsetzt. Anhand des Advanced Encryption Standard (AES) zeigt der Autor konkrete Implementierungen in Software für aktuelle PC- und Server-Systeme mit mindestens 32-Bit-Integer-Rechenwerken, für 8-Bit-Microcontroller (Atmel AVR ATmega) und Smartphones (Android). Die zu beantwortende Frage wird sein: Wie kommt man von einer Spezifikation zu einer effizient laufenden Implementierung auf der jeweiligen Plattform?

Mathematische Grundlagen

Bevor der Leser sich jedoch an eine der praktischen Umsetzungen heranwagen kann, heißt es in diesem Artikel, die mathematischen Grundlagen in Form des AES-Algorithmus zu verstehen. Die dahinter stehende Spezifikation ist ein hervorragendes Beispiel für eine verständliche und nachvollziehbare Dokumentation eines Algorithmus. Der AES-Algorithmus operiert über dem endlichen Körper GF(2^8). Wenn man diesen Körper mit einem den meisten besser bekannten mathematischen Körper, den reellen Zahlen ℝ vergleicht, fallen zwei Dinge ins Auge. Einerseits hat der endliche Körper GF(2^8) nur eine endliche Anzahl an Elementen, im Gegensatz zum Körper der reellen Zahlen, der eine unendliche Anzahl an Elementen besitzt. GF(2^8) hat 2^8 = 256 Elemente. Andererseits funktionieren bei GF(2^8) Addition und Multiplikation anders, als man das von "normalen" Zahlen, wie den reellen Zahlen, gewohnt ist. Wie jeder mathematische Körper sind auch in GF(2^8) die Operationen Addition und Multiplikationen definiert. In dem Fall aber nicht als die Summe oder das Produkt einfacher Zahlen, wie es von den reellen Zahlen her bekannt ist.

Die Elemente von GF(2^8) lassen sich als Polynome auffassen. Sie haben die allgemeine Form:

p(x) = a_7 * x^7 + a_6 * x^6 + a_5 * x^5 + a_4 * x^4 + a_3 * x^3 
+ a_2 * x^2 + a_1 * x^1 + a_0 * x^0

Die Koeffizienten a_i des Polynoms (ebenso wie die x-Werte) sind boolesche Zahlen, können also nur den Wert 0 oder 1 angeben. Sie definieren somit, ob der Term des i. Grads a_i * x^i im betrachteten Polynom p(x) vorhanden ist oder nicht. Der Grad i der Variablen x des jeweiligen Terms (Exponent von x) definiert die Position des booleschen Werts.

Damit lassen sich die Polynome auch als Bitfelder notieren. Mit dem Koeffizienten ist definiert, ob das Bit gesetzt ist oder nicht. Der Grad der Variablen x bestimmt die Position des Bits. Das Polynom x^7 + x^5 + x^4 + x lässt sich somit äquivalent als Bitfeld 10110010 darstellen.

Da GF(2^8) 256 Elemente umfasst, lassen sich die Elemente in einem Byte als Bitfeld darstellen. Die Bytewerte 0 bis 255 repräsentieren also die Elemente von GF(2^8) in Bitfelddarstellung. Damit ist man in der Lage, die Elemente auf normale Bytes abzubilden und im Computer darzustellen.

Die Addition in GF(2^8) erfolgt durch Addition der Polynome. Das heißt: Die Koeffizienten der Polynome der Variablen vom gleichen Grad werden addiert. Da die Koeffizienten boolesche Zahlen sind, resultiert die Addition in einem exklusiven Oder, also einer XOR-Operation (eXclusive OR). Für die Bitfelddarstellung in einem Byte heißt das nichts anderes, als dass die beiden zu addierenden Bytes bitweise XOR-verknüpft werden. Die Addition der Elemente 10110010 und 01110001 in GF(2^8)ergibt somit 10110010 XOR 01110001 = 11000011.

Da in der Booleschen Algebra die Addition und ihre Umkehrung, die Subtraktion, als XOR identisch sind, folgt unweigerlich, dass das auch in GF(2^8) so ist. Mit anderen Worten: Plus und Minus sind in GF(2^8) identische Operatoren.