imported>DasFlutenDuten: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-10-22T18:58:59Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

Der '''MixColumns-Schritt''' ist ein Rechenschritt im [[Advanced Encryption Standard|Rijndael]]-Algorithmus (AES).

MixColumns ist eine lineare Operation auf vier Bytes (einer Spalte) des Datenblocks, der durch Rijndael verschlüsselt wird. Sie ersetzt diese vier Bytes durch vier daraus berechnete Ergebnisbytes, die jeweils von jedem der Eingabebytes abhängen, was [[Diffusion (Kryptologie)|Diffusion]] innerhalb der Spalte bewirkt. Je Runde der Verschlüsselung wird jede Spalte des Datenblocks einmal durch MixColumns bearbeitet.

[[Datei:AES-MixColumns.svg|320px|mini|Im <code>MixColumns</code> Schritt wird jede Spalte des Datenblocks mit ''c(x)'' verknüpft.]]

== Die Matrizenmultiplikation ==

In diesem Schritt findet eine [[Matrizenmultiplikation]] eines Spaltenvektors des Datenblocks mit einer [[MDS-Code|MDS-Matrix]] statt.

:<math>\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}</math>

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

== Der Galois-Körper des Rijndael ==
Der Galois-Körper des Rijndael ist der [[Galois-Körper]] <math>GF(2^8)</math>.

<math>GF(2^8)</math> ist die Menge aller [[Polynom]]e maximal 7. Grades mit Koeffizienten aus dem [[Restklassenkörper]] <math>\mathbb F_2 = \mathbb Z/2\mathbb Z</math>.

Ein allgemeines Polynom aus <math>GF(2^8)</math> besitzt die Form
<math>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).</math>
Wie leicht nachzuvollziehen ist, lässt sich jedes dieser Polynome durch ein [[Byte]] repräsentieren, wobei jeweils das <math>i</math>-te [[Bit]] den Koeffizienten <math>a_i</math> repräsentiert.

Die Addition <math>\oplus</math> auf <math>GF(2^8)</math> ist analog zum Körper <math>\mathbb F_2</math> 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:

:<math>(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</math>

Die Multiplikation(<math>\cdot</math>) findet [[modulo]] des [[Irreduzibles Polynom|irreduziblen Polynoms]] <math>x^8 + x^4 + x^3 + x + 1</math> statt. Hierzu multipliziert man die beiden Polynome und berechnet dann Mittels einer [[Polynomdivision]] den Divisionsrest.

== Beispiel ==

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

:<math>\begin{pmatrix}2 & 3 & 1 & 1\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2 \end{pmatrix} \begin{pmatrix} \mathrm{d4} \\ 32 \\ \mathrm{f4} \\ \mathrm{ae} \end{pmatrix} = \begin{pmatrix}b_{0,i} \\ b_{1,i} \\ b_{2,i}\\b_{3,i} \end{pmatrix}</math>

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

Die Terme <math> 1 \cdot \mathrm{f4} = \mathrm{f4}</math> sowie <math>1 \cdot \mathrm{ae} = \mathrm{ae}</math> sind trivial.

:<math>\begin{align} 2 \cdot \mathrm{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}</math>

:<math display="inline">\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}</math>

Daraus ergibt sich mit [[XOR]]: <math>b_{0,1} = b3 + 56 + \mathrm{f4} + \mathrm{ae} = \mathrm{bf}</math>

== Die Umkehrung des MixColumns Schrittes ==

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]]):

:<math>\begin{pmatrix}E & B & D & 9\\ 9 & E & B & D\\ D & 9 & E & B\\ B & D & 9 & E \end{pmatrix}</math>

da

:<math>\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}</math>

== Möglichkeiten zur Implementierung ==

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

Die Multiplikation mit <math>1</math> ist trivial. Die Multiplikation mit <math>x</math> bedeutet in der Binärdarstellung eine Verschiebung um 1 Bit nach links (die Moduloberechnung muss noch gesondert betrachtet werden), und die Multiplikation mit <math>(x+1)</math> lässt sich in eine Multiplikation mit <math>x</math> und anschließende Addition mit sich selbst aufspalten.
Falls ein Überlauf stattfindet, so muss man das Zwischenergebnis noch mit <math>1b
</math> 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.

<syntaxhighlight lang="c">
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};
}
}
</syntaxhighlight>

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

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

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

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

:<math>a \cdot b = e^{\ln(a \cdot b)} = e^{\ln(a) + \ln(b)}</math>

Für <math>a = 0 \vee b = 0</math> gilt <math>a \cdot b = 0</math>

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 <math>GF(2^8)</math> effektiv implementieren. Die Tabelle kann entweder zur Laufzeit berechnet werden – mit obiger Funktion bietet sich der Generator 3 an – oder im Quellcode vorliegen.

<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>

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

<pre>
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*
</pre>
<pre>
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*
</pre>

== Weblinks ==
* [http://www.codeplanet.eu/tutorials/cpp/51-advanced-encryption-standard.html#aes_operations_mixcolumns Tutorial über die AES-Verschlüsselung]
* [http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf FIPS PUB 197: the official AES standard] ([[Portable Document Format|PDF]] file; 273 kB)

[[Kategorie:Advanced Encryption Standard]]

Rijndael MixColumns - Versionsgeschichte

imported>DasFlutenDuten: /* growthexperiments-addlink-summary-summary:1|0|0 */