ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

AES (ang. Advanced Encryption Standard)

  • Ogólny opis
  • Algorytm
  • Schematy blokowe
  • Funkcje matematyczne
  • Implementacja
AES jest nowoczesnym blokowym szyfrem symetrycznym, jednym z najbardziej popularnych szyfrów na świecie. Został opublikowany w 1997 roku przez Vincent'a Rijmen'a i Joan'a Daemen'a, a następnie przyjęty jako standard federalny w USA w roku 2002.
Szyfr blokowy z kluczem symetrycznym
Długość klucza = 128 lub 192 lub 256 bitów
Długość bloku = 128 bitów
W ostatnich latach (2005-2010) opublikowanych zostało szereg prac naukowych, opisujących możliwe ataki na niektóre implementacje algorytmu AES, ale przedstawione instrukcje łamania dotyczyły zwykle szczególnych przypadków i nie stanowiły zagrożenia dla ogólnej oceny jakości szyfrowania AES, który wciąż uważany jest za bezpieczny i efektywny szyfr.

Do szyfrowania i deszyfrowania danych za pomocą AES wykorzystywany jest sekretny klucz o długości 128 lub 192 lub 256 bitów. W zależności od długości klucza wykonywana jest inna ilość rund szyfrujących.

Szyfrowanie w AES

W procesie szyfrowania dane wejściowe (tekst jawny) dzielone są na bloki 128-bitowe. Bloki przedstawiane są jako macierze 4 bajty × 4 bajty szeregowane kolumnami (ang. column-major), nazywane stanami (ang. state) lub macierzami stanu. Dla każdego bloku danych (czyli dla każdej macierzy stanu) wykonywane są następujące operacje:

  1. Przygotowanie podkluczy: generowany jest jeden podklucz początkowy, a następnie po kolejnym jednym podkluczu dla każdej rundy szyfrującej (patrz niżej).
  2. Runda inicjująca: każdy bajt w bloku danych jest dodawany do odpowiadającego mu bajtowi pierwszego podklucza za pomocą sumowania XOR.
  3. Następuje określona liczba rund szyfrujących. Ilość powtórzeń zależy od długości sekretnego klucza:
    -  9 powtórzeń dla klucza 128-bitowego,
    - 11 powtórzeń dla klucza 192-bitowego,
    - 13 powtórzeń dla klucza 256-bitowego.

    W każdej rundzie szyfrującej wykonywane są następujące operacje:
    1. Każdy bajt danych jest zastępowany innym bajtem, na podstawie z góry zdefiniowanej tabeli (ang. lookup table), zwanej S-Box'em Rijndael'a (ang. Rijndael's S-Box). Jest to tak zwana operacja SB, z ang. Substitute Bytes. Konstrukcja tabeli ma gwarantować nieliniowość przekształcenia (a więc i całego szyfrowania).
    2. Przesunięcie bajtów w trzech ostatnich macierzach stanu w lewo. Bajty w pierwszym wierszu nie są przesuwane. Bajty w drugim wierszu macierzy są przesuwane o jedną pozycję w lewo, w trzecim wierszu o dwie pozycje, a w czwartym wierszu o trzy pozycje w lewo. Skrajnie lewe bajty z każdego wiersza przechodzą na skrajnie prawą pozycję w tym samym wierszu. Operacja ta nosi skrót SR, z ang. Shift Rows).
    3. Operacja MC, z ang. Mix Columns, czyli mnożenie kolumn: wszystkie kolumny macierzy stanu są mnożone przez stałą macierz o wielkości 4 bajty × 4 bajty.
    4. Operacja AR, z ang. Add Round Key: dodanie XOR wszystkich bajtów bloku danych do bajtów podklucza właściwego dla danej rundy. Podklucze, podobnie jak bloki danych, mają po 16 bajtów długości.
  4. Runda kończąca: wykonywane są te same operacje co w normalnych rundach szyfrujących, z wyjątkiem operacji mnożenia kolumn, która w Rundzie Kończącej jest pomijana.

Generowanie klucza w AES

Algorytm AES używa sekretnego symetrycznego klucza o długości 128, 192 albo 256 bitów (czyli odpowiednio 16, 24 lub 32 bajtów). W celu zaszyfrowania każdego bloku danych, klucz musi zostać wcześniej rozszerzony, czyli do oryginalnych otrzymanych bajtów muszą zostać dopisane kolejne:

Pierwsze bajty rozszerzonego klucza stanowią wszystkie bajty oryginalnego klucza sekretnego. W celu uzyskania kolejnych bajtów klucza rozszerzonego należy wykonać szereg operacji, numerując kolejne iteracje od 1. Poniższe kroki powtarza się, aż do uzyskania pożądanej liczby bajtów. Dla uproszczenia notacji, przyjęto, że oryginalna długość klucza sekretnego (przed rozszerzeniem) w bajtach wynosi n.

  1. Utworzenie 4 kolejnych bajtów klucza:
    1. Przepisanie 4 ostatnich bajtów aktualnego rozszerzonego klucza do tymczasowego wektora 4-bajtowego.
    2. Wykonanie rotacji bajtów w wektorze o jedną pozycję w lewo. Skrajnie lewy bajt należy przepisać na skrajnie prawą pozycję.
    3. Zastąpienie każdego bajtu w wektorze innym bajtem, bazując na S-Box'ach Rijndael'a (ang. Rijndael's S-Box).
    4. Operacja Rcon: zsumowanie XOR najbardziej lewego bajtu w wektorze z dwójką podniesioną do potęgi (numer aktualnej iteracji - 1).
    5. Zsumowanie XOR otrzymanego 4-bajtowego wektora z 4-bajtowym blokiem zaczynającym się n bajtów przed aktualnym końcem klucza, a następnie dopisanie wyniku na koniec rozszerzanego klucza. W ten sposób otrzymuje się nowe 4 bajty rozszerzanego klucza.
  2. Utworzenie 12 kolejnych bajtów klucza przez trzykrotne powtórzenie poniższych kroków:
    1. Przepisanie 4 ostatnich bajtów tworzonego klucza do tymczasowego wektora 4-bajtowego.
    2. Zsumowanie XOR powyższego wektora z 4-bajtowym blokiem zaczynającym się n bajtów przed aktualnym końcem rozszerzanego klucza i dodanie wyniku na koniec rozszerzonego klucza.
  3. Jeśli oryginalny sekretny klucz jest 256-bitowy, to należy wykonać poniższe kroki w celu utworzenia 4 kolejnych bajtów klucza:
    1. Przepisanie 4 ostatnich bajtów tworzonego klucza do tymczasowego wektora 4-bajtowego.
    2. Zastąpienie każdego bajtu w wektorze innym bajtem, bazując na S-Box'ach Rijndael'a (ang. Rijndael's S-Box).
    3. Zsumowanie XOR otrzymanego 4-bajtowego wektora z 4-bajtowym blokiem zaczynającym się n bajtów przed aktualnym końcem rozszerzanego klucza i dodanie wyniku na koniec rozszerzonego klucza.
  4. Jeśli oryginalny sekretny klucz jest 128-bitowy, to należy pominąć poniższe kroki. Jeśli oryginalny sekretny klucz jest 192-bitowy, to należy wykonać poniższe kroki 2 razy. Jeśli oryginalny sekretny klucz jest 256-bitowy, to należy wykonać poniższe kroki 3 razy.
    1. Przepisanie 4 ostatnich bajtów tworzonego klucza do tymczasowego wektora 4-bajtowego.
    2. Zsumowanie XOR powyższego wektora z 4-bajtowym blokiem zaczynającym się n bajtów przed aktualnym końcem rozszerzanego klucza i dodanie wyniku na koniec rozszerzonego klucza.
  5. Zwiększenie numeru aktualnej iteracji o 1.

Deszyfrowanie w AES

W czasie procesu deszyfrowania, zaszyfrowany tekst traktowany jest jako wejście do algorytmu. Należy wykonać analogiczne, odwrócone operacje, co w czasie szyfrowania:

  1. Odwrócone podstawianie bajtów (ISB).
  2. Przesuwanie bajtów w wierszach macierzy stanu w prawą stronę (ISR).
  3. Sumowanie XOR bajtów macierzy stanu z bajtami podklucza (IAR).
  4. Odwrócone mnożenie kolumn (IMC).

Podklucze używane w każdej iteracji podczas deszyfrowania danych, powinny być są brane w odwrotnej kolejności niż w czasie szyfrowania.

Szybkość działania AES

W celu przyspieszenia działania aplikacji, można zdecydować się na wcześniejsze przeliczenie wszystkich funkcji zawartych w różnych rundach algorytmu AES, a następnie zastąpienie tych obliczeń zwykłym podstawianiem danych z uzyskanych tabel.

Wadą tego rozwiązania jest znaczne zwiększenie rozmiaru aplikacji. Wielkość kodu aplikacji może wzrosnąć z kilku do kilkudziesięciu kilobajtów, w zależności od długości używanego sekretnego klucza.

We wszystkich operacjach szyfru AES przedstawionych poniżej, bajty przedstawione są w zapisie szesnastkowym. Każdy znak reprezentuje 4 bity.
Podstawienie w S-Box'ach Rijndael'a
W S-Box'ach Rijndael'a każdy bajt wejściowy jest zastępowany przez nowy bajt, wskazany przez tabelę. Podstawienia w S-Box'ach zostały tak dobrane, aby zapewnić jak największą nieliniowość przekształcenia, a wraz z tym nieliniowość całego szyfrowania AES.

Poniżej przedstawiona jest tabela, z której odczytuje się zmienione bajty danych. W wierszach należy odszukać wartość bardziej znaczącej połówki wejściowego bajtu, a w kolumnach wartość mniej znaczącej połówki wejściowego bajtu. Na przecięciu wybranego wiersza i kolumny można odczytać wartość nowego bajtu.

S-Box Rijndael'a
x0
x1
x2
x3
x4
x5
x6
x7
x8
x9
xA
xB
xC
xD
xE
xF
0x
637c777bf26b6fc53001672bfed7ab76
1x
ca82c97dfa5947f0add4a2af9ca472c0
2x
b7fd9326363ff7cc34a5e5f171d83115
3x
04c723c31896059a071280e2eb27b275
4x
09832c1a1b6e5aa0523bd6b329e32f84
5x
53d100ed20fcb15b6acbbe394a4c58cf
6x
d0efaafb434d338545f9027f503c9fa8
7x
51a3408f929d38f5bcb6da2110fff3d2
8x
cd0c13ec5f974417c4a77e3d645d1973
9x
60814fdc222a908846eeb814de5e0bdb
Ax
e0323a0a4906245cc2d3ac629195e479
Bx
e7c8376d8dd54ea96c56f4ea657aae08
Cx
ba78252e1ca6b4c6e8dd741f4bbd8b8a
Dx
703eb5664803f60e613557b986c11d9e
Ex
e1f8981169d98e949b1e87e9ce5528df
Fx
8ca1890dbfe6426841992d0fb054bb16

Na przykład, w miejsce bajtu 3F zostanie zwrócony nowy bajt o wartości 75.

Podczas deszyfrowania wiadomości stosuje się odwrócone S-Box'y (ang. Inverse S-Box), które można otrzymać wprost z oryginalnych S-Box'ów.

Odwrócony S-Box Rijndael'a
x0
x1
x2
x3
x4
x5
x6
x7
x8
x9
xA
xB
xC
xD
xE
xF
0x
52096ad53036a538bf40a39e81f3d7fb
1x
7ce339829b2fff87348e4344c4dee9cb
2x
547b9432a6c2233dee4c950b42fac34e
3x
082ea16628d924b2765ba2496d8bd125
4x
72f8f66486689816d4a45ccc5d65b692
5x
6c704850fdedb9da5e154657a78d9d84
6x
90d8ab008cbcd30af7e45805b8b34506
7x
d02c1e8fca3f0f02c1afbd0301138a6b
8x
3a9111414f67dcea97f2cfcef0b4e673
9x
96ac7422e7ad3585e2f937e81c75df6e
Ax
47f11a711d29c5896fb7620eaa18be1b
Bx
fc563e4bc6d279209adbc0fe78cd5af4
Cx
1fdda8338807c731b11210592780ec5f
Dx
60517fa919b54a0d2de57a9f93c99cef
Ex
a0e03b4dae2af5b0c8ebbb3c83539961
Fx
172b047eba77d626e169146355210c7d
Mnożenie kolumn macierzy stanu
Każda kolumna macierzy stanu jest mnożona przez stałą macierz o wymiarach 4bajty x 4bajty. Wynikiem mnożenia każdej z czterech kolumn jest nowa kolumna, zawierająca 4 zmienione bajty danych.

Operacje mnożenia zaprezentowana jest poniżej. Przemnożenie kwadratowej macierzy przekształceń z kolumną c daje w wyniku kolumnę r z nowymi wartościami.

Mnożenie kolumn
 x 
 c0 
 c1 
 c2 
 c3 
 = 
 r0 
 r1 
 r2 
 r3 

Podczas deszyfrowania, w tym kroku używana jest macierz odwrotna:

Macierz odwrotna
Operacja Rcon
Podczas generowania bajtów sekretnego klucza, w każdej iteracji pierwszy bajt z aktualnego czterobajtowego wektora tymczasowego jest sumowany za pomocą operacji XOR z dwójką podniesioną do potęgi o jeden mniejszą niż aktualny numer iteracji. Operacja podnoszenia do potęgi jest działaniem modulo.

Wartości te mogą być obliczane na bieżąco podczas działania aplikacji lub być zakodowane w tabeli i zapisane w pamięci programu.

Potęgi x = 0x02
i01234567891011121314
xi01020408102040801b366cd8ab4d9a
Strona w trakcie budowy.