Advanced Encryption Standard

**Tekniska data**
Källa: FIPS-197^[1]
Namn	AES
Kryptotyp	Substitution-permutation
Blockstorlek	128 bit
Nyckellängder	128, 192, 256 bit

Advanced Encryption Standard (AES) är en standardiserad krypteringsalgoritm fastslagen av NIST den 26 november 2001. Standarden bygger på krypteringsalgoritmen Rijndael framtagen av belgarna dr Joan Daemen och dr Vincent Rijmen. Namnet Rijndael är en sammanslagning av deras namn.

AES är ett symmetriskt blockkrypto konstruerat för att kunna använda krypteringsnycklar med längderna 128, 192 och 256 bit där varje variant benämns AES-128, AES-192, respektive AES-256.^[1]

Både AES och föregångaren DES är substitutions-permutationskrypton men AES är till skillnad från DES inte ett Feistelkrypto. AES bygger därmed på förvanskning av texten genom en serie av omväxlande substitutioner och permutationer, där varje substitution-permutation är en iteration eller runda (engelska round). Antalet rundor varierar beroende på nyckellängden: AES-128 har 10 rundor, AES-192 har 12 rundor och AES-256 har 14 rundor. En runda består av fyra steg: byte substitution, radskiftning, kolumnblandning och nyckeladdition. Undantaget är sista rundan där man hoppar över kolumnblandningen; innan man över huvud taget börjar med rundorna måste man emellertid genomföra en nyckelexpansion.

AES är vinnaren av en internationellt utlyst tävling för att få fram en modern kryptoalgoritm. Till följd av tävlingsreglerna är algoritmerna väl genomlysta och dokumenterade, dessutom befriade från patent eller andra immaterialrättsliga begränsningar. Utöver att vara baserad på en bra krypteringsalgoritm är Advanced Encryption Standard dessutom förhållandevis enkel att implementera i mjuk- eller hårdvara. Detta var också ett av kriterierna för att få delta i tävlingen.

AES är inte till fullo symmetriskt, i så måtto att kryptering respektive dekryptering utförs på för all del liknande, men inte exakt samma vis. Ovan nämnda kolumnblandning (matrismultiplikation) är dessutom mer beräkningsintensiv vid krypteringen än vid dekrypteringen; följaktligen behöver också AES något mer processorkraft vid kryptering av data, än vid dekrypteringen av dessa data. Det finns emellertid inget som hindrar att man växlar algoritmerna, och använder dekrypteringsalgoritmen för kryptering, och krypteringsalgoritmen för dekryptering.

Algoritmen

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Advanced Encryption Standard.

Nyckelexpansion

Innan man kan börja med rundorna måste nyckeln expanderas till olika nycklar för varje runda. För att göra det ska följande algoritm utövas:

Definiera rc_i enligt följande tabell:

i (decimalt)	1	2	3	4	5	6	7	8	9	10
rc_i (hexadecimalt)	01	02	04	08	10	20	40	80	1b	36

Definiera även:

l - nyckelns storlek i ord (32 bitar): 4 ord på 128 bitar, 6 ord på 192 bitar och 8 ord på 256 bitar.
k₀, k₁, k₂ etc.: orden i den ursprungliga nyckeln
n - hur många nya nycklar som behövs: 11 nycklar för 128 bitar, 13 för 192 bitar och 15 för 256 bitar.
w₀, w₁, w₂ etc.: orden i den nya, expanderade nyckeln.

Definiera även r(x) som ett teckenskifte åt vänster och s(x) som alla tecken utbytta genom S-boxen (som förklaras längre ner):

$\operatorname {r} ({\begin{bmatrix}b_{0}&b_{1}&b_{2}&b_{3}\end{bmatrix}})={\begin{bmatrix}b_{1}&b_{2}&b_{3}&b_{0}\end{bmatrix}}$

$\operatorname {s} ({\begin{bmatrix}b_{0}&b_{1}&b_{2}&b_{3}\end{bmatrix}})={\begin{bmatrix}\operatorname {S} (b_{0})&\operatorname {S} (b_{1})&\operatorname {S} (b_{2})&\operatorname {S} (b_{3})\end{bmatrix}}$

Den expanderade nyckeln definieras som följande, där i går från 0 till 4n-1:

$w_{i}={\begin{cases}k_{i}&{\text{om }}i<l\\w_{i-l}\oplus \operatorname {s} (\operatorname {r} (w_{i-1}))\oplus {\begin{bmatrix}rc_{i/l}&0&0&0\end{bmatrix}}&{\text{om }}i\geq l{\text{ och }}i\equiv 0{\pmod {l}}\\w_{i-l}\oplus \operatorname {s} (w_{i-1})&{\text{om }}i\geq l{\text{, }}l>6{\text{ och }}i\equiv 4{\pmod {l}}\\w_{i-l}\oplus w_{i-1}&{\text{annars}}\\\end{cases}}$

där $\oplus$ syftar på exklusiv eller-operatorn (XOR). Efter att man har gjort detta utövas en nyckeladdition med w₀-w₃ i de fyra kolumnerna i blocket innan den första teckensubstitutionen sker.

Teckensubstitution

Varje tecken (8 bitar) i blocket, här benämnt b₀ till b₁₅ ersätts med ett annat tecken, s(b_x), via en tabell, den så kallade S-boxen. Den ser ut så här (värden är hexadecimala):

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

Värdena i tabellen genereras genom att ta den multiplikativa inversen under den ändliga kroppen 2⁸. Sedan multipliceras inversen med denna matrismultiplikation

${\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&1\\1&1&1&1&1&0&0&0\\0&1&1&1&1&1&0&0\\0&0&1&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{bmatrix}}{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}+{\begin{bmatrix}1\\1\\0\\0\\0\\1\\1\\0\end{bmatrix}}$

där b₀-b₇ är bitarna i inversen från höger till vänster och s₀-s₇ är bitarna i det slutgiltiga resultatet. Varför just den här algoritmen valdes var för att göra matematiska samband så otydliga som möjligt, samt att det inte kan bli samma resultat som tecknet du började med.

Radskiftning

Varje rad i blocket skiftas ett visst antal steg. Den översta raden skiftar inte, raden under skiftas 1 tecken åt vänster, raden under det 2 tecken och den nedersta skiftas 3 tecken. Det ser ut så här:

${\begin{bmatrix}b_{0,0}&b_{0,1}&b_{0,2}&b_{0,3}\\b_{1,0}&b_{1,1}&b_{1,2}&b_{1,3}\\b_{2,0}&b_{2,1}&b_{2,2}&b_{2,3}\\b_{3,0}&b_{3,1}&b_{3,2}&b_{3,3}\\\end{bmatrix}}={\begin{bmatrix}a_{0,0}&a_{0,1}&a_{0,2}&a_{0,3}\\a_{1,1}&a_{1,2}&a_{1,3}&a_{1,0}\\a_{2,2}&a_{2,3}&a_{2,0}&a_{2,1}\\a_{3,3}&a_{3,0}&a_{3,1}&a_{3,2}\\\end{bmatrix}}$

där a_x,y är ett tecken ur det originella blocket och b_x,y är ett tecken ur det nya. Det här steget är mycket viktigt för att det grundar sig på rader istället för kolumner, så det förhindrar att kolumnerna krypteras var för sig och bildar fyra separata blockkrypton. Det är dessutom, tillsammans med kolumnblandningen, den viktigaste källan till diffusion inom kryptot.

Kolumnblandning

De fyra tecknen i en kolumn genomgår en matrismultiplikation:

${\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{bmatrix}}={\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\\\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\a_{2}\\a_{3}\end{bmatrix}}$

där varje multiplikation görs i den ändliga kroppen 2⁸. Det här steget utövas däremot inte under sista rundan. Meningen med det här steget är främst för att skapa diffusion och få bort matematiska samband.

Nyckeladdition

Nyckelexpansionen ovan genomförs, och man tar sedan en del av den expanderade nyckeln och använder XOR-operatorn för att kombinera dess tecken med tecknen i blocket. Detta steg utövas även en extra gång i början av kryptot, innan runda 1 börjar. XOR-operatorn är reversibel, vilket gör dekryptering enkelt.

Källor

^ [a b] ”Advanced Encryption Standard” (PDF). Federal Information Processing Standards Publications. National Institute of Standards and Technology. 2001. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf. Läst 19 juni 2017.

Externa länkar

Wikimedia Commons har media som rör Advanced Encryption Standard.

[Fips-197-1] [a b] ”Advanced Encryption Standard” (PDF). Federal Information Processing Standards Publications. National Institute of Standards and Technology. 2001. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf. Läst 19 juni 2017.

[1]