Rijndael MixColumns

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der MixColumns-Schritt ist ein Schritt im Rijndael-Algorithmus (AES).

Im MixColumns Schritt, wird jede Spalte des State mit c(x) verknüpft.

Die Matrizenmultiplikation[Bearbeiten]

In diesem Schritt findet eine Matrizenmultiplikation eines Spaltenvektors des States mit einer MDS-Matrix statt, damit alle 4 Eingabebytes jedes Ausgabebyte beeinflussen.

\begin{pmatrix}2 & 3 & 1 & 1\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2 \end{pmatrix} \begin{pmatrix}a_{0,i} \\ a_{1,i} \\ a_{2,i}\\a_{3,i} \end{pmatrix}  = \begin{pmatrix}b_{0,i} \\ b_{1,i} \\ b_{2,i}\\b_{3,i} \end{pmatrix}

Die Arithmetik findet allerdings nicht auf den Natürlichen Zahlen statt, sondern auf dem Galois-Körper des Rijndael.

Der Galois-Körper des Rijndael[Bearbeiten]

Der Galois-Körper des Rijndael ist der Galois-Körper GF(2^8).

GF(2^8) ist die Menge aller Polynome maximal 7.Grades mit Koeffizienten aus dem Restklassenkörper \mathbb F_2 = \mathbb Z/2\mathbb Z.

Ein allgemeines Polynom aus GF(2^8) besitzt die Form a_7 x^7 + a_6x^6 + a_5x^5, + a_4x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 \ \ (a_i \in \mathbb F_2). Wie leicht nachzuvollziehen ist, lässt sich jedes dieser Polynome durch ein Byte repräsentieren, wobei jeweils das i-te Bit den Koeffizienten a_i repräsentiert.

Die Addition \oplus auf GF(2^8) ist analog zum Körper \mathbb F_2 als XOR-Verknüpfung definiert, sie findet koeffizientenweise bzw. bitweise statt. Die Subtraktion entspricht der Addition da die XOR-Verknüpfung ihre eigene Umkehrfunktion ist. Beispiel:

(x^5 + x^4 + x^3) - (x^7+x^5+ x^3+ x + 1) = (x^5 + x^4 + x^3) + (x^7+x^5+ x^3+ x + 1) = x^7 + x^4 + x + 1

Die Multiplikation(\cdot) findet modulo des irreduziblen Polynoms x^8 + x^4 + x^3 + x + 1 statt. Hierzu multipliziert man die beiden Polynome und berechnet dann Mittels einer Polynomdivision den Divisionsrest, wobei beachtet werden muss, dass Addition und Subtraktion XOR-Verknüpfungen darstellen.

Beispiel[Bearbeiten]

Beispielhaft wird nun die Berechnung von b_{0,1} mit \begin{pmatrix}a_{0,i} \\ a_{1,i} \\ a_{2,i}\\a_{3,i} \end{pmatrix} = \begin{pmatrix} d4\\ 32\\ f4\\ ae \end{pmatrix} durchgeführt. Zahlen sind, wenn nicht anders angegeben, hexadezimal.

\begin{pmatrix}2 & 3 & 1 & 1\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2 \end{pmatrix} \begin{pmatrix} d4 \\ 32 \\ f4 \\ ae \end{pmatrix} = \begin{pmatrix}b_{0,i} \\ b_{1,i} \\ b_{2,i}\\b_{3,i} \end{pmatrix}

Daraus folgt b_{0,1} = (2 \cdot d4) + (3 \cdot 32) + (1 \cdot f4) + (1 \cdot ae)

Die Terme  1 \cdot f4 = f4 sowie 1 \cdot ae = ae sind trivial.

\begin{align} 2 \cdot d4 & = 00000010_2 \cdot 11010100_2 \\ & = x \cdot (x^7 + x^6 + x^4 + x^2) \\ & = (x^8 + x^7 + x^5 + x^3)\ \bmod\ (x^8 + x^4 + x^3 + x + 1) \\ & = 110101000_2\ \bmod\ 100011011_2 \\ & = 110101000_2\ + 100011011_2\\ & = 010110011_2 = b3 \end{align}

\begin{align} 3 \cdot 32 & = 00000011_2 \cdot 00110010_2 \\ & = (x + 1) \cdot (x^5 + x^4 + x) \\ & = (x^6 + x^5 + x^2 + x^5 + x^4 + x)\ \bmod\ (x^8 + x^4 + x^3 + x + 1) \\ & = (x^6 + x^4 + x^2 + x)\ \bmod\ (x^8 + x^4 + x^3 + x + 1) \\ & = 01010110_2\ \bmod\ 100011011_2 \\ & = 01010110_2 = 56 \end{align}

Daraus ergibt sich mit XOR: b_{0,1} = b3 + 56 + f4 + ae = bf

Die Umkehrung des MixColumns Schrittes[Bearbeiten]

Die Entschlüsselung kann in diesem Schritt in derselben Weise erfolgen wie die Verschlüsselung. Allerdings muss man hierzu mit der inversen Matrix multiplizieren. Sie lautet (Zahlen hexadezimal):

\begin{pmatrix}E & B & D & 9\\ 9 & E & B & D\\ D & 9 & E & B\\ B & D & 9 & E \end{pmatrix}

da

\begin{pmatrix}2 & 3 & 1 & 1\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2 \end{pmatrix} \begin{pmatrix}E & B & D & 9\\ 9 & E & B & D\\ D & 9 & E & B\\ B & D & 9 & E \end{pmatrix}  = \begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{pmatrix}

Möglichkeiten zur Implementierung[Bearbeiten]

Dadurch, dass im Rijndael bei der Verschlüsselung nur Multiplikationen mit 1, x oder (x+1) stattfinden, lässt sich der Algorithmus sehr effizient und einfach am Computer implementieren.

Die Multiplikation mit 1 ist trivial. Die Multiplikation mit x bedeutet in der Binärdarstellung eine Verschiebung um 1 Bit nach links (die Moduloberechnung muss noch gesondert betrachtet werden), und die Multiplikation mit (x+1) lässt sich in eine Multiplikation mit x und anschließende Addition mit sich selbst aufspalten. Falls ein Überlauf stattfindet, so muss man das Zwischenergebnis noch mit 1b
XOR-verknüpfen, um das richtige Ergebnis zu erhalten.

Folgender C-Code dient nur als Beispiel für eine mögliche einfache Implementierung und stellt keine sichere Referenzimplementierung dar.

unsigned char mul123(unsigned char a, unsigned char b){
  if(b==1)
    return a;
  else if(b==2)
  {
    unsigned char c = a << 1;
    if(a & 0x80)
      c ^= 0x1b;
    return c;
  }
  else if(b==3)
  {
    return mul123(a, 2) ^ a;
  }
  else exit{EXIT_FAILURE};
}

Bei der Entschlüsselung bedarf es allerdings auch der Multiplikation mit anderen Zahlen, wo der obenstehende Ansatz nutzlos wird.

Für geeignetes e \in GF(2^8) gilt exp: GF(2^8)\backslash\{0\} \to GF(2^8)\backslash\{0\}, x \mapsto e^x ist bijektiv. Die Umkehrfunktion heiße ln. Ein solches geeignetes x nennt man einen Generator, Beispiele hierfür wären die 3 oder die 5, es gibt allerdings noch einige weitere.

Beweis: Da GF(2^8) endlich, lässt sich das durch nachrechnen überprüfen.

Da exp bijektiv ist, gilt für a,b \in GF(2^8)\backslash\{0\}:

a \cdot b = e^{ln(a \cdot b)} = e^{ln(a) + ln(b)}

Für a = 0 \vee b = 0 gilt a \cdot b = 0

Erzeugen wir uns nun für die Multiplikation eine Exponential- und Logarithmustabelle für einen Generator, so können wir mit Hilfe dieser die allgemeine Multiplikation auf GF(2^8) effektiv implementieren. Die Tabelle kann entweder zur Laufzeit berechnet werden - mit obiger Funktion bietet sich der Generator 3 an - oder im Quellcode vorliegen.

unsigned char RijndaelGaloisMul(unsigned char a, unsigned char b){
  if(a && b) //falls a != 0 und b != 0
    return exp_table[(ln_table[a] + ln_table[b]) % 0xff];
  else
    return 0;
}

Nachfolgend die Exponential- und Logarithmustabelle für den Generator 3:

Potenzen:                              
  | *0  *1  *2  *3  *4  *5  *6  *7  *8  *9  *a  *b  *c  *d  *e  *f |
----------------------------------------------------------------------
0*| 01  03  05  0f  11  33  55  ff  1a  2e  72  96  a1  f8  13  35 |0*
1*| 5f  e1  38  48  d8  73  95  a4  f7  02  06  0a  1e  22  66  aa |1*
2*| e5  34  5c  e4  37  59  eb  26  6a  be  d9  70  90  ab  e6  31 |2*
3*| 53  f5  04  0c  14  3c  44  cc  4f  d1  68  b8  d3  6e  b2  cd |3*
4*| 4c  d4  67  a9  e0  3b  4d  d7  62  a6  f1  08  18  28  78  88 |4*
5*| 83  9e  b9  d0  6b  bd  dc  7f  81  98  b3  ce  49  db  76  9a |5*
6*| b5  c4  57  f9  10  30  50  f0  0b  1d  27  69  bb  d6  61  a3 |6*
7*| fe  19  2b  7d  87  92  ad  ec  2f  71  93  ae  e9  20  60  a0 |7*
8*| fb  16  3a  4e  d2  6d  b7  c2  5d  e7  32  56  fa  15  3f  41 |8*
9*| c3  5e  e2  3d  47  c9  40  c0  5b  ed  2c  74  9c  bf  da  75 |9*
a*| 9f  ba  d5  64  ac  ef  2a  7e  82  9d  bc  df  7a  8e  89  80 |a*
b*| 9b  b6  c1  58  e8  23  65  af  ea  25  6f  b1  c8  43  c5  54 |b*
c*| fc  1f  21  63  a5  f4  07  09  1b  2d  77  99  b0  cb  46  ca |c*
d*| 45  cf  4a  de  79  8b  86  91  a8  e3  3e  42  c6  51  f3  0e |d*
e*| 12  36  5a  ee  29  7b  8d  8c  8f  8a  85  94  a7  f2  0d  17 |e*
f*| 39  4b  dd  7c  84  97  a2  fd  1c  24  6c  b4  c7  52  f6  01 |f*

Logarithmen:
  | *0  *1  *2  *3  *4  *5  *6  *7  *8  *9  *a  *b  *c  *d  *e  *f |
----------------------------------------------------------------------
0*| --  00  19  01  32  02  1a  c6  4b  c7  1b  68  33  ee  df  03 |0*
1*| 64  04  e0  0e  34  8d  81  ef  4c  71  08  c8  f8  69  1c  c1 |1*
2*| 7d  c2  1d  b5  f9  b9  27  6a  4d  e4  a6  72  9a  c9  09  78 |2*
3*| 65  2f  8a  05  21  0f  e1  24  12  f0  82  45  35  93  da  8e |3*
4*| 96  8f  db  bd  36  d0  ce  94  13  5c  d2  f1  40  46  83  38 |4*
5*| 66  dd  fd  30  bf  06  8b  62  b3  25  e2  98  22  88  91  10 |5*
6*| 7e  6e  48  c3  a3  b6  1e  42  3a  6b  28  54  fa  85  3d  ba |6*
7*| 2b  79  0a  15  9b  9f  5e  ca  4e  d4  ac  e5  f3  73  a7  57 |7*
8*| af  58  a8  50  f4  ea  d6  74  4f  ae  e9  d5  e7  e6  ad  e8 |8*
9*| 2c  d7  75  7a  eb  16  0b  f5  59  cb  5f  b0  9c  a9  51  a0 |9*
a*| 7f  0c  f6  6f  17  c4  49  ec  d8  43  1f  2d  a4  76  7b  b7 |a*
b*| cc  bb  3e  5a  fb  60  b1  86  3b  52  a1  6c  aa  55  29  9d |b*
c*| 97  b2  87  90  61  be  dc  fc  bc  95  cf  cd  37  3f  5b  d1 |c*
d*| 53  39  84  3c  41  a2  6d  47  14  2a  9e  5d  56  f2  d3  ab |d*
e*| 44  11  92  d9  23  20  2e  89  b4  7c  b8  26  77  99  e3  a5 |e*
f*| 67  4a  ed  de  c5  31  fe  18  0d  63  8c  80  c0  f7  70  07 |f*

Weblinks[Bearbeiten]