728 x 90

, i

Bezpieczeństwo ponad wszystko – Advanced Encryption Standard

Bezpieczeństwo ponad wszystko – Advanced Encryption Standard

Wstęp

AES (Advanced Encryption Standard) to symetryczny szyfr blokowy oparty na algorytmie Rijndael’a, którego twórcami są Joan Daemen i Vincent Rijmen. Ich praca została wybrana podczas konkursu, ogłoszonego przez NIST (National Institute of Standards and Technology), na nowy standard szyfrowania w roku 1997. Konkurs ten był otwarty, co oznacza, że swoją pracę mógł zgłosić każdy. Społeczność kryptologów została zachęcona przez NIST do wykonania prób ataków i kryptolanaliz zgłoszonych algorytmów. Na ich podstawie NIST ogłosiło wyniki. Zgodnie z wymaganiami szyfr miał przetwarzać 128-bitowe bloki danych i generować klucze o długości 128, 192 lub 256-bitów, miał być równie bezpieczny jak 3-DES, ale jednocześnie efektywniejszy od niego. Głównymi kryteriami, na podstawie których wybrano zwycięzcę było niskie zużycie pamięci oraz duża szybkość działania. Rijndael wyróżnił się dobrą wydajnością podczas implementacji w różnych środowiskach oraz systemach operacyjnych.

AES to szyfr symetryczny, oznacza to, że do szyfrowania i deszyfrowania jest używany ten sam klucz. Z reguły takie szyfry działają szybciej niż kryptosystemy klucza publicznego. Szyfry symetryczne zwykle opierają się na operacjach permutacji i substytucji kolejnych bitów danych z paru bloków, a nie na trudnych do rozwiązania problemach matematycznych, jak jest w przypadku algorytmów asymetrycznych.

AES jest podobny do swojego poprzednika DES, który obecnie jest uznawany za łatwy do złamania, ze względu na podatność na kryptoanalizę liniową oraz różnicową. Oba te algorytmy szyfrują i deszyfrują poprzez wykonywanie określonej liczby rund czyli powtarzalnego algorytmu szyfrującego. Uściślając, w szyfrach blokowych dane są dzielone na równej długości partie i szyfrowane kolejno przez określone dla algorytmu funkcje. Algorytmy blokowe działają w sposób deterministyczny, a ich funkcje w sposób pseudolosowy. Do deszyfracji wiadomości stosowane są funkcje odwrotne.

Wstep do struktur używanych w AES

Na początek należy zadać sobie pytanie – czym dokładnie jest ciało K? Przede wszystkim jest to struktura algebraiczna (K, +, *), więc każde jego działanie jest działaniem wewnętrznym. Oznacza to, że wynik każdej funkcji dwuargumentowej, odwzorującej elementy należącę do ciała, należy do tej samej struktury. Co więcej, ma ono w sobie dwa działania: addytywne i multipliktywne, a zbiór z każdym z tych działań tworzy grupę przemienną, a działanie multiplikatywne jest rozdzielne względem addytywnego.

Grupa

To taka struktura algebraiczna (G, +), której działanie jest łączne, a także istnieje element neutralny i odwrotny.
Działanie jest łączne, gdy:

Element neutralny e ∈ G to taki element, dla którego:

Element przeciwny $a^{-1}  \in G$ to taki element, spełniający warunek:

Grupa jest grupą przemienną, gdy:

Opisane powyżej działanie jest działaniem addytywnym (dodawaniem), dla działania multiplikatywnego (mnożenia) własności grupy są analogiczne.
W przypadku grupy addytywnej elementem przeciwnym jest –a, natomiast w przypadku multiplikatywnej mówi się o elemencie odwrotnym $a^-1$
Wiedząc już, czym jest grupa, możemy przejść do ciała.
W tym przypadku jego elementem neutralnym dodawania jest 0, a mnożenia 1. Nie są to jednak znane nam powszechnie wartości, a jedynie symbole, pod którymi może kryć się zupełnie inna wartość, niż można się spodziewać.

Działanie * jest rozdzielne względem +, gdy:

Ciała Galoisa

Ciało Galoisa jest to struktura o określonej liczbie elementów, z tego też powodu jest nazywane również ciałem skończonym. Warunkiem koniecznym istnienia jest posiadanie $p^m$ elementów, gdzie p ∈ P, m ∈ Z

Przykłady

1) GF(11)
2) GF(81)=GF(3^4)
3) GF(256)=GF(2^8)
Ciała skończone GF(2^m) dzielimy na dwa podtypy:
1) m=1  =>  GF(p) – ciała proste
2) m>1 – ciała rozszerzone, w kryptologii szczególnie ważne GF(2^m)

Arytmetyka ciał prostych

Elementami GF(p) są 0,1,…,p-1

a) Niech a,b ∈ GF(p), c ∈ R

$a+b=c mod p$

b) Element odwrotny a ∈ GF(p) to:

$a·a^{-1}=1 mod p$

Arytmetyka ciał rozszerzonych

Element $GF (2^m)$ jest wielomianem postaci:

 

Przykład

Niech $GF(2^3)$ wtedy wielomianem $A(x) \in GF(2^3)$ jest:

Dodawanie i Odejmowanie w Ciele Rozszerzonym

Są to operacje równoważne w ciele o charakterystyce 2. Ponieważ: $-1 / / mod 2 = 1$. Działanie to określamy następującym wzorem:
Ponadto spełnione jest równanie określone w matematyce jako “Freshman’s dream” czyli (a+b)^m=a^m+b^m

Mnożenie w Ciele Rozszerzonym

Postępujemy jak w przypadku zwykłego mnożenia wielomianów, jednak gdy stopień wyjdzie poza ciało skończone, należy obliczyć resztę z dzielenia

Schemat szyfrowania

Szyfrowanie jest procesem obszernym i w zależności od długości klucza składa się z różnej liczby rund. Odpowiednio dla klucza K:

Schemat budowy AES

Schemat blokowy algorytmu AES

Byte Substitution Layer

W rzeczywistości rolę tego bloku pełni S-Box. Przyjmuje on 8 bitów, i zwraca je w przemieszanej kolejności.

Ważne jest aby każdy z 16. S-Boxów był identyczny pod względem działania. W środku każdego takiego elementu znajdują się dwa bloki.

Pierwszy z nich czyli ” $GF(2^8)$ inverse ” stanowi operację na wspomnianych i wytłumaczonych ciałach Galois’a. Elementem odwracalnym dla elementu a nazywamy element spełniający następujący warunek:

Jest on spełniony dla każdego przypadku, a wynika to z definicji ciała skończonego, które jest szczególnym przypadkiem dziedziny całkowitości. Aby znaleźć element odwrotny w ciele skończonym, należy zastosować rozszerzony algorytm Euklidesa.

Odwracanie elementu

Pamiętając, że wartości szyfrowane ( bity ) tworzą wielomiany należące do ciała skończonego. Także element odwrotny należy do ciała.

Przy czym P(x) jest nieredukowalnym wielomianem AES. W każdym ciele istnieje kilka takich elementów. Aby obliczyć element odwrotny stosujemy rozszerzony algorytm Euklidesa.

Rozszerzony algorytm Euklidesa

Celem algorytmu jest znalezienie liczb x i y, znając a oraz b spełniających następujące równanie:Celem algorytmu jest znalezienie liczb x i y, znając a oraz b spełniających następujące równanie:

$ax+by=gcd(a,b)$

Aby je obliczyć stosujemy następująca zasadę

gdzie:

algorytm zatrzymuje się gdy . Następnie wykonujemy podstawienia używając kolejnych elementów z wyników działania algorytmu Euklidesa
Jednak aby uprościć działanie możemy się posłużyć tablicą, z jakiej korzysta S-Box, dla ciała GF(2^8)

Wartości w niej prezentowane są w postaci heksadecymalnej. Tzn. że mając wielomian A(x)=x^7+x^6+x reprezentowany w postaci binarnej jako: 11000010 = 0xC2 ponieważ 0x2=0010, a 0xC=0011. Stąd wybieramy z tabeli odpowiedni element dla pary (x,y)=(C,2). Po poprawnym odczycie otrzymujemy:

Zachodzi wtedy następująca równość:

Affine Mapping 

gdzie bi spełniają warunek jest elementem odwrotnym dla ai natomiast bi wartością zwracaną przez S-Boxa.

ShiftRows Layer

W bloku tym wiersze są przesuwane w następujący sposób:
1) Wiersz pierwszy pozostaje bez zmian
2) Wiersz drugi jest przesuwany o jedno miejsce w lewo
3) Wiersz drugi jest przesuwany o dwa miejsca w lewo
4) Wiersz drugi jest przesuwany o trzy miejsca w lewo

Mix Column Layer

W sekcji tej nastepuje wymieszanie kolumn. Według poniższego schematu:

Mnożąc macierze otrzymujemy następujące równanie:

Znaczenie 01,02,03

Key Addition Layer

Wiadomość 16 bajtowa oraz równej długości podlegają operacji XOR.

a xor b = a+b mod 2

Key Schedule

Mieszanie wartości klucza AES

W procesie tym w każdej rundzie klucz jest odpowiednio zmieniany, dzieje się to tak jak przedstawiono na schematycznej grafice. Dzięki operacji Xor przeprowadzanej wielokrotnie oraz funkcji G, bezpieczeństwo algorytmu znacząco wzrasta.

Deszyfrowanie

Schemat blokowy deszyfrowania

Schemat budowy deszyfratora

Inverse MixColumn Sublayer

Warto pamiętać, że dodawanie jest jednoznaczne z operację XOR w przypadku gdy zmienne przyjmują postać tylko binarną.

Inverse ShiftRows Sublayer

Przekształcamy bity zgodnie z poniższą regułą:

Inverse Byte Substitution Layer

S-Box jest ma zawartą w sobie funkcję, która jest bijekcją. Korzystając z tego faktu możemy stworzyć funkcję odwrotną, tzn. spełniającą następującą zależność:S-Box jest ma zawartą w sobie funkcję, która jest bijekcją. Korzystając z tego faktu możemy stworzyć funkcję odwrotną, tzn. spełniającą następującą zależność:

$x=f^-1 ( f(x) )$

Stąd ponieważ funkcja mapowania jest “na” możemy stworzyć Inverse S-Box do odszyfrowania wiadomości. Podobnie jak w szyfrowaniu korzystamy z specjalnej tabeli oraz funkcji mapującej.

Następnie odwracamy otrzymany wektor i otrzymujemy wiadomość napisaną tekstem jawnym.

Decryption Key Schedule

Postępujemy tak samo jak w przypadku szyfracji, używamy klucza odwrotnie. To znaczy do pierwszej rundy ostatniego podklucza, do drugiej przedostatniego itd.

Bibliografia

  • Understanding Cryptography – Christof Paar,Jan Pelzl
  • The Design of Rijndael AES – The Advanced Encryption Standard – Joan Daernen, Vincent Rijrnen
  • An introduction to mathematical cryptography -Jeffrey Hoffstein Jill Pipher Joseph H. Silverman
  • Obrazek tytułowy : pixelbay.com

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

Inne artykuły