Crypto-IT

• Długość bloku = 128 bitów
• Długość klucza = 128 lub 192 lub 256 bitów

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.

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.

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.

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:

• klucz 128-bitowy (16-bajtowy) jest rozszerzany do 176 bajtów.
• klucz 192-bitowy (24-bajtowy) jest rozszerzany do 208 bajtów.
• klucz 256-bitowy (32-bajtowy) jest rozszerzany do 240 bajtów.

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.

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.

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.

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.

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.

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.

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

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: