Galois Eindige Velden en de Advanced Encryption Standard (AES)
Opmerkelijk is dat leden van een veld van grootte $p^n$ equivalent zijn aan polynomen van een graad tot $n$, met coëfficiënten gekozen uit gehele getallen modulo $p$ (een "veld met karakteristiek $p$"). We kunnen bijvoorbeeld de voor de hand liggende keuze maken en getallen zoals 0 of 1 representeren met het polynoom 0 of 1. Tot zover is het eenvoudig, maar het getal 2 is problematisch omdat we alleen coëfficiënten modulo $p$ kunnen hebben. Daarom verhogen we een macht van het polynoom naar $x$, en kiezen we "2 = 10 = 1x + 0". Dit resulteert in een eenvoudige correspondentie tussen de bits in een binaire representatie van een getal en de termen van het overeenkomstige veldpolynoom.
| Getal | Binair | GF($2^8$) Polynoom | Vereenvoudigd |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 10 | 1x + 0 | x |
| 3 | 11 | 1x + 1 | x + 1 |
| 4 | 100 | 1x² + 0x + 0 | x² |
| 5 | 101 | 1x² + 0x + 1 | x² + 1 |
| 8 | 1000 | 1x³ + 0x² + 0x + 0 | x³ |
| 16 | 10000 | 1x⁴ + 0x³ + 0x² + 0x + 0 | x⁴ |
| 21 | 10101 | 1x⁴ + 0x³ + 1x² + 0x + 1 | x⁴ + x² + 1 |
Gelukkig is deze wiskundige structuur er enkel om de waarden van de substitutietabellen te berekenen of om eenvoudige verschuif- en XOR-bewerkingen te motiveren. We hoeven tijdens de uitvoering ("runtime") zeker niet constant getallen naar polynomen te converteren, en we evalueren de polynomen nooit daadwerkelijk voor een specifieke $x$.
Optelling in Eindige Velden
We kunnen bepalen hoe optelling in een eindig veld werkt door de onderliggende polynomen op te tellen. Bijvoorbeeld: 1 + 2 = 1 + 10 = (1) + (1x + 0) = 1x + 1 = 11 = 3
Omdat we echter alleen enkelvoudige bit-polynoomcoëfficiënten hebben, geldt: 2 + 2 = 10 + 10 = (1x + 0) + (1x + 0) = 2x = 0x = 0
Vanwege deze binaire wraparound bij één bit, blijkt dat in GF($2^8$) optelling, aftrekking en XOR allemaal dezelfde operatie zijn. Dit lijkt een radicale afwijking van normale optelling, maar in een circuit komt dit simpelweg overeen met het negeren van de carry-bits bij elke optelling van één bit.
Hieronder volgt een optellingstabel voor GF($2^4$), een eindig veld van 4 bits (één hexadecimaal cijfer):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
| 1 | 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 | 9 | 8 | b | a | d | c | f | e |
| 2 | 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 | a | b | 8 | 9 | e | f | c | d |
| 3 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 | b | a | 9 | 8 | f | e | d | c |
| 4 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | c | d | e | f | 8 | 9 | a | b |
| 5 | 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 | d | c | f | e | 9 | 8 | b | a |
| 6 | 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 | e | f | c | d | a | b | 8 | 9 |
| 7 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | f | e | d | c | b | a | 9 | 8 |
| 8 | 8 | 9 | a | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 9 | 9 | 8 | b | a | d | c | f | e | 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
| a | a | b | 8 | 9 | e | f | c | d | 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
| b | b | a | 9 | 8 | f | e | d | c | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
| c | c | d | e | f | 8 | 9 | a | b | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
| d | d | c | f | e | 9 | 8 | b | a | 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
| e | e | f | c | d | a | b | 8 | 9 | 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
| f | f | e | d | c | b | a | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Net als bij Sudoku moet elke output in elke rij en kolom precies één keer voorkomen om te garanderen dat er inversen bestaan.
Vermenigvuldiging in Eindige Velden
Vermenigvuldiging in een eindig veld werkt hetzelfde als vermenigvuldiging van polynomen: 2 2 = 10 10 = (1x + 0) (1x + 0) = x x = x² = 1x² + 0x + 0 = 100 = 4
Dit werkt prima, behalve bij het genereren van polynoomgraden die hoger zijn dan $n$. Bijvoorbeeld: $16 \times 16 = x^4 \times x^4 = x^8$, wat buiten de grenzen van GF($2^8$) valt. Om dit op te lossen "reduceren" we hogere graden door veelvouden van een "reducerend polynoom" af te trekken. Voor AES is dit $x^8 + x^4 + x^3 + x + 1$ (in hex: 0x11b). Er zijn veel keuzes voor reducerende polynomen (ze moeten "irreducibel" zijn, het polynomium-equivalent van een priemgetal), maar het blijkt dat ze enkel de getallen permuteren en de onderliggende wiskundige structuur niet veranderen.
In dit geval trekken we het reducerende polynoom één keer af: 16 16 = x⁴ x⁴ = x⁸ = x⁸ - (x⁸ + x⁴ + x³ + x + 1) = -(x⁴ + x³ + x + 1)
Aangezien elk element zijn eigen additieve inverse is, wordt dit: ... = x⁴ + x³ + x + 1 = 11011 = 27
Merk op dat een even getal maal een even getal op deze manier een oneven getal kan opleveren.
De reductie-operatie geeft vermenigvuldiging in een eindig veld een vreemde dynamiek. Hieronder staat de hexadecimale vermenigvuldigingstabel met 256 vermeldingen voor vermenigvuldiging met 2 (1x + 0) in GF($2^8$):
0x00,0x02,0x04,0x06,0x08,0x0a,0x0c,0x0e,0x10,0x12,0x14,0x16,0x18,0x1a,0x1c,0x1e,
0x20,0x22,0x24,0x26,0x28,0x2a,0x2c,0x2e,0x30,0x32,0x34,0x36,0x38,0x3a,0x3c,0x3e,
0x40,0x42,0x44,0x46,0x48,0x4a,0x4c,0x4e,0x50,0x52,0x54,0x56,0x58,0x5a,0x5c,0x5e,
0x60,0x62,0x64,0x66,0x68,0x6a,0x6c,0x6e,0x70,0x72,0x74,0x76,0x78,0x7a,0x7c,0x7e,
0x80,0x82,0x84,0x86,0x88,0x8a,0x8c,0x8e,0x90,0x92,0x94,0x96,0x98,0x9a,0x9c,0x9e,
0xa0,0xa2,0xa4,0xa6,0xa8,0xaa,0xac,0xae,0xb0,0xb2,0xb4,0xb6,0xb8,0xba,0xbc,0xbe,
0xc0,0xc2,0xc4,0xc6,0xc8,0xca,0xcc,0xce,0xd0,0xd2,0xd4,0xd6,0xd8,0xda,0xdc,0xde,
0xe0,0xe2,0xe4,0xe6,0xe8,0xea,0xec,0xee,0xf0,0xf2,0xf4,0xf6,0xf8,0xfa,0xfc,0xfe,
0x1b,0x19,0x1f,0x1d,0x13,0x11,0x17,0x15,0x0b,0x09,0x0f,0x0d,0x03,0x01,0x07,0x05,
0x3b,0x39,0x3f,0x3d,0x33,0x31,0x37,0x35,0x2b,0x29,0x2f,0x2d,0x23,0x21,0x27,0x25,
0x5b,0x59,0x5f,0x5d,0x53,0x51,0x57,0x55,0x4b,0x49,0x4f,0x4d,0x43,0x41,0x47,0x45,
0x7b,0x79,0x7f,0x7d,0x73,0x71,0x77,0x75,0x6b,0x69,0x6f,0x6d,0x63,0x61,0x67,0x65,
0x9b,0x99,0x9f,0x9d,0x93,0x91,0x97,0x95,0x8b,0x89,0x8f,0x8d,0x83,0x81,0x87,0x85,
0xbb,0xb9,0xbf,0xbd,0xb3,0xb1,0xb7,0xb5,0xab,0xa9,0xaf,0xad,0xa3,0xa1,0xa7,0xa5,
0xdb,0xd9,0xdf,0xdd,0xd3,0xd1,0xd7,0xd5,0xcb,0xc9,0xcf,0xcd,0xc3,0xc1,0xc7,0xc5,
0xfb,0xf9,0xff,0xfd,0xf3,0xf1,0xf7,0xf5,0xeb,0xe9,0xef,0xed,0xe3,0xe1,0xe7,0xe5De eerste helft van de tabel is identiek aan normale vermenigvuldiging van gehele getallen, maar halverwege wordt de reductie noodzakelijk en beginnen de resultaten te variëren, vooral in de lage bits.
Hier is een vermenigvuldigingstabel voor GF($2^4$), met een reducerend polynoom van 0x13 == 10011 == $x^4 + x + 1$.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
| 2 | 0 | 2 | 4 | 6 | 8 | a | c | e | 3 | 1 | 7 | 5 | b | 9 | f | d |
| 3 | 0 | 3 | 6 | 5 | c | f | a | 9 | b | 8 | d | e | 7 | 4 | 1 | 2 |
| 4 | 0 | 4 | 8 | c | 3 | 7 | b | f | 6 | 2 | e | a | 5 | 1 | d | 9 |
| 5 | 0 | 5 | a | f | 7 | 2 | d | 8 | e | b | 4 | 1 | 9 | c | 3 | 6 |
| 6 | 0 | 6 | c | a | b | d | 7 | 1 | 5 | 3 | 9 | f | e | 8 | 2 | 4 |
| 7 | 0 | 7 | e | 9 | f | 8 | 1 | 6 | d | a | 3 | 4 | 2 | 5 | c | b |
| 8 | 0 | 8 | 3 | b | 6 | e | 5 | d | c | 4 | f | 7 | a | 2 | 9 | 1 |
| 9 | 0 | 9 | 1 | 8 | 2 | b | 3 | a | 4 | d | 5 | c | 6 | f | 7 | e |
| a | 0 | a | 7 | d | e | 4 | 9 | 3 | f | 5 | 8 | 2 | 1 | b | 6 | c |
| b | 0 | b | 5 | e | a | 1 | f | 4 | 7 | c | 2 | 9 | d | 6 | 8 | 3 |
| c | 0 | c | b | 7 | 5 | 9 | e | 2 | a | 6 | 1 | d | f | 3 | 4 | 8 |
| d | 0 | d | 9 | 4 | 1 | c | 8 | 5 | 2 | f | b | 6 | 3 | e | a | 7 |
| e | 0 | e | f | 1 | d | 3 | 2 | c | 9 | 7 | 6 | 8 | 4 | a | b | 5 |
| f | 0 | f | d | 2 | 9 | 6 | 4 | b | 1 | e | c | 3 | 8 | 7 | 5 | a |
Deze tabel wordt gegenereerd door de volgende code:
// Bitwise ("peasant") multiplication, using galois addition
for (int bit=3; bit>=0; bit--) {
if (b & (1 << bit))
c = c ^ (a << bit);
}
// Reduce back into galois field (can also be folded into above loop)
int irr = 0x13; // represents reduction polynomial
int high = 0x10; // high bit of above
for (int bit=3; bit>=0; bit--) {
if (c & (high << bit)) // if that bit is set
c = c ^ (irr << bit); // galois "subtract" it off
}Voor GF($2^8$), het AES-veld, is de vermenigvuldigingstabel vergelijkbaar. Merk op dat voorwaartse vermenigvuldiging een kort algoritme is, maar dat het vreemd genoeg niet-lineair genoeg is waardoor delen in een eindig veld moeilijk is. Meestal wordt er een tabel met multiplicatieve inversen gebouwd, waarna men vermenigvuldigt met de inverse. Men kan zowel vermenigvuldiging als deling efficiënt uitvoeren door een tabel van logaritmen en antilogaritmen te maken. Tabellen werken voor deze velden omdat er slechts 256 elementen zijn.
Operaties van AES
Elke ronde van AES bestaat uit de volgende operaties op een 4x4 raster van bytes:
- S-box: Elke byte in het raster gaat door een S-box. Dit bestaat uit een multiplicatieve inverse, gevolgd door een affiene transformatie (een reeks optellingen en vermenigvuldigingen met 0 of 1). De affiene transformatie lost het probleem met 0 op (geen multiplicatieve inverse, dus bij conventie $1/0 = 0$) en bemoeilijkt de wiskunde zodat multiplicatieve inversen niet simpelweg aan elkaar geregen kunnen worden.
- ShiftRows: Verschuift elke byte horizontaal in het 4x4 raster. Rij $i$ wordt circulair verschoven met $i$ bytes.
- MixColumns: Berekent een lineaire transformatie op elke kolom. Een lineaire transformatie is een reeks vermenigvuldigingen en optellingen in het eindige veld. De gebruikte matrix is inverteerbaar, dus er bestaat een inverse operatie. De matrix is zo gekozen dat elke outputbyte verandert als een enkele inputbyte verandert.
- Round Keys: Tot slot worden de round keys toegevoegd aan elke byte (dezelfde operatie als XOR in een eindig veld).
Waarom deze aanpak?
De grote voordelen van het werken in een eindig veld zijn:
- Getallen blijven klein: Alles in GF($2^8$) is altijd één byte, zelfs na vermenigvuldiging of deling.
- Inversen bestaan: Voor elke operatie bestaat een inverse, wat decryptie mogelijk maakt. Dit is superieur aan simpelere modulaire rekenkunde met een macht van twee als modulus, waarbij vermenigvuldiging met 2 de hoogste bit doet verloren gaan.
- Begrepen wiskunde: De wiskunde is goed begrepen en stamt uit de jaren 1830. Dit maakt het eenvoudig om goede mengfuncties te kiezen en verkleint de kans dat iemand je verrast met een nieuwe analysetechniek.
- Combinatorische rijkdom: Er zijn voldoende operaties om deze op rijke manieren te combineren. AES combineert deling in de eerste helft van de S-box, een transpose in de row shift, en matrixoperaties tijdens MixColumns en de tweede helft van de S-box. Matrixoperaties commuteren niet met elkaar, en de transpose en deling voorkomen dat men de matrices simpelweg met elkaar kan vermenigvuldigen.
Ter vergelijking: als je alleen optelling gebruikt, heb je een shift-cijfer, ongeacht hoeveel operaties je uitvoert. Als je alleen optelling en vermenigvuldiging gebruikt, heb je een lineair cijfer, ongeacht het aantal operaties.
Voor de volledige technische details en voorbeelden kan men kijken in FIPS 197, en het Rijndael AES-paper is relatief leesbaar en bevat details over de motivatie achter het ontwerp.
Groetjes,