Advanced Encryption Standard

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Advanced Encryption Standard
Ilustracja
Rodzaj algorytmu Szyfr blokowy
Data stworzenia 1998
Autorzy Vincent Rijmen, Joan Daemen
Wielkość bloku wejściowego 128 bitów
Wielkość bloku wyjściowego 128 bitów
Długość klucza 128, 192, 256 [bit]
Liczba rund zależna od klucza:
  • 10 dla 128-bitowego
  • 12 dla 192-bitowego
  • 14 dla 256-bitowego

Advanced Encryption Standard (krócej AES, nazwa oryginalna: Rijndael[1][2]) – symetryczny szyfr blokowy przyjęty przez NIST jako standard FIPS-197[3] w wyniku konkursu ogłoszonego w roku 1997. W 2001 roku został przyjęty jako standard[4].

AES jest oparty na algorytmie Rijndaela[2], którego autorami są belgijscy kryptografowie, Joan Daemen i Vincent Rijmen. Zaprezentowali oni swoją propozycję szyfru Instytucji NIST w ramach ogłoszonego konkursu[5]. Rijndael jest rodziną szyfrów o różnych długościach klucza oraz różnych wielkościach bloków.

W przypadku AES-a, NIST wybrał trzy algorytmy z rodziny Rijndaela, z których każdy miał tą samą wielkość bloku (128 bitów), ale miały różne długości klucza: 128, 192 i 256 bitów.

AES został przyjęty przez rząd amerykański i obecnie jest używany na całym świecie. Jest on następcą algorytmu DES[6], opracowanego w 1977. AES jest szyfrem symetrycznym, tzn. do szyfrowania i do odszyfrowywania wykorzystywany jest ten sam klucz.

W Stanach Zjednoczonych, AES został ogłoszony przez NIST jako PUB 197 (FIPS 197) 26 listopada 2001[4].; przed tym wydarzeniem co 5 lat odbywały się procesy normalizacji, w trakcie których piętnaście różnych rozwiązań było prezentowanych i ulepszanych.

AES stał się standardem rządu federalnego 26 maja 2002, gdy został zaaprobowany przez Sekretarza Handlu. Szyfr ten jest dostępny w wielu różnych pakietach. Ponadto jest pierwszym (i jedynym) dostępnym publicznie szyfrem, który był zatwierdzony i wykorzystywany przez NSA do ochrony ściśle tajnych informacji. Nazwa Rijndael jest kombinacją nazwisk twórców szyfru.

Standardy[edytuj | edytuj kod]

AES jest zdefiniowany w standardach:

  • FIPS PUB 197: Advanced Encryption Standard (AES) (ogłoszony 26 listopada 2001.)[7]
  • ISO/IEC 18033-3: Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers[8]

Konkurs[edytuj | edytuj kod]

Bezpośrednią przyczyną rozpisania konkursu była niewystarczająca siła algorytmu DES. W roku 1997 organizacja EFF była w stanie złamać wiadomość zaszyfrowaną DES-em w ciągu 3 dni sprzętem o wartości 250 tysięcy dolarów; obecnie można złamać DES-a jeszcze szybciej i taniej.

Do finału konkursu zakwalifikowało się pięć algorytmów szyfrujących (Rijndael, RC6, Mars, Serpent oraz Twofish), ze szczególnym wskazaniem na algorytm Rijndael. Możliwe jest w nim użycie kluczy o długościach 128, 192 i 256 bitów i operuje on na blokach danych o długości 128 bitów (oryginalna specyfikacja Rijndael dopuszczała również bloki 192- i 256-bitowe).

Algorytm[edytuj | edytuj kod]

AES bazuje na zasadzie, zwanej siecią substytucji-permutacji. Wykazuje się dużą szybkością pracy zarówno w przypadku sprzętu komputerowego, jak i oprogramowania[9]. W przeciwieństwie do swego poprzednika, algorytmu DES, AES nie używa Sieci Feistela. AES posiada określony rozmiar bloku – 128 bitów, natomiast rozmiar klucza wynosi 128, 192, lub 256 bitów. Funkcja substytucyjna ma bardzo oryginalną konstrukcję, która uodparnia ten algorytm na znane ataki kryptoanalizy różnicowej i liniowej.

Odmiany algorytmu Rijndael niebędące standardem AES, w zależności od długości klucza i bloku danych wykonują 12 lub 14 rund szyfrujących[10].

AES operuje na macierzy bajtów o wymiarach 4×4, nazywaną stanem. Jednak niektóre wersje algorytmu dysponują większym rozmiarem bloku oraz dodatkowymi kolumnami w macierzy. Większość obliczeń AES'a dokonywanych jest w konkretnym Ciele skończonym.

Przykładowo, jeżeli mamy 16 bajtów, b0,b1,...,b15, są one reprezentowane w przedstawionej macierzy:

Rozmiar klucza używany w algorytmie określa liczbę powtórzeń transformacji, które przekształcają dane wejściowe (czyli tekst jawny) w dane wyjściowe (szyfrogram). Liczba cykli powtórzeń jest następująca:

  • 10 cykli powtórzeń dla klucza 128-bitowego;
  • 12 cykli powtórzeń dla klucza 192-bitowego;
  • 14 cykli powtórzeń dla klucza 256-bitowego.

Wszystkie rundy składają się z kilku kroków, z których każdy rozłożony jest na cztery podobne (lecz nie identyczne) etapy. Jeden z tych etapów jest zależny od szyfrowania samego klucza.

Wykonując operacje w odwrotnej kolejności używając tego samego klucza, można przekształcić szyfrogram z powrotem w tekst jawny.

Wysokopoziomowy opis algorytmu[edytuj | edytuj kod]

  1. Rozszerzenie klucza – z głównego klucza algorytmu "tworzy się" kolejne klucze. AES wymaga osobnego klucza 128-bitowego dla każdej rundy, plus jeden dodatkowy.
  2. runda wstępna
    1. Dodawanie klucza rundy – każdy bajt macierzy stanu jest mieszany z blokiem rundy za pomocą operatora bitowego XOR.
  3. Rundy
    1. Zamiana Bajtów – nieliniowa zamiana, podczas której każdy bajt jest zamieniany innym.
    2. Zamiana Wierszy – etap transpozycji, podczas którego trzy ostatnie wiersze macierzy stanu są cyklicznie zmieniane określoną ilość razy.
    3. Mieszanie Kolumn – Operacja odnosi się do kolumn macierzy. Polega na łączeniu czterech bajtów w każdej kolumnie.
    4. Dodaj klucz rundy
  4. Final Round (brak operacji Mieszania Kolumn)
    1. Zamiana Bajtów
    2. Zamiana Wierszy
    3. Dodaj klucz rundy.

Kryptoanaliza[edytuj | edytuj kod]

W 2006 opublikowana została praca, w której twierdzi się, że AES nie jest w pełni odporny na atak XSL, ale oszacowanie ilości koniecznych obliczeń obarczone jest dużą niepewnością, w związku z tym oceny, na ile skuteczny jest ten atak, są różne[11].

W 2009 opublikowane zostały dwa nowe ataki z użyciem kluczy pokrewnych (key related attack) redukujące złożoność AES-256 do [12]. Wobec licznie pojawiających się nowych i mało prawdopodobnych ataków na AES w 2010 roku, Vincent Rijmen opublikował ironiczny artykuł opisujący "atak nazwany praktycznym"[13].

W grudniu 2009 opublikowano atak na niektóre sprzętowe implementacje AES umożliwiający odtworzenie klucza ze złożonością przez zastosowanie różnicowej analizy błędów (differential fault analysis)[14].

Zużycie zasobów sprzętowych[edytuj | edytuj kod]

Duża szybkość działania oraz niskie zużycie pamięci były głównymi kryteriami, na podstawie których wybierano algorytm. Algorytm AES funkcjonuje prawidłowo na szerokim zakresie urządzeń – zarówno na 8-bitowych kartach mikroprocesorowych jak i na komputerach o wysokiej mocy obliczeniowej.

W przypadku mikroprocesorów klasy Pentium Pro, szyfrowanie za pomocą AES'a wymaga 18 cykli zegara na każdy bajt[15],, co jest równoznaczne z wydajnością rzędu 11 MB/s dla procesora 200 MHz. Z kolei na procesorze klasy Pentium M o szybkości 1.7 GHz wydajność wynosi ok. 60 MB/s.

Na procesorach Intel Core i3/i5/i7, AMD APU a także na procesorach AMD FX wspierających zestaw instrukcji AES, wydajność może przekroczyć 700 MB/s na każdy wątek[16].

Przypisy[edytuj | edytuj kod]

  1. Rijndael. [dostęp 9 marzec 2015].
  2. a b Joan Daemen, Vincent Rijmen: AES Proposal: Rijndael. National Institute of Standards and Technology, 9 marzec 2003. [dostęp 21 luty 2013]. s. 1.
  3. FIPS-197: Advanced Encryption Standard. NIST.
  4. a b Announcing the ADVANCED ENCRYPTION STANDARD (AES). W: Federal Information Processing Standards Publication 197 [on-line]. United States National Institute of Standards and Technology (NIST), 26 listopad 2001. [dostęp 2 październik 2012].
  5. U.S. Selects a New Encryption Technique. „New York Times”. 
  6. Harold B. Westlund. NIST reports measurable success of Advanced Encryption Standard. „Journal of Research of the National Institute of Standards and Technology”. 
  7. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
  8. ISO/IEC 18033-3: Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers.
  9. Bruce Schneier, John Kelsey, Doug Whiting, David Wagner i inni. The Twofish Team's Final Comments on AES Selection. , May 2000. 
  10. Mirek Sopek: Szyfr Rijndael/AES.
  11. Nowe ataki na szyfry. 2006.
  12. Nowy atak na AES-256. IPSec.pl, 1 lipca 2009.
  13. Vincent Rijmen: Practical-Titled Attack on AES-128 Using Chosen-Text Relations. 2010.
  14. Dhiman Saha, Debdeep Mukhopadhyay, Dipanwita RoyChowdhury: A Diagonal Fault Attack on the Advanced Encryption Standard. 2009.
  15. Bruce Schneier, John Kelsey, Doug Whiting, David Wagner i inni. Performance Comparisons of the AES submissions. , 1999-02-01. [dostęp 2010-12-28]. 
  16. Grant McWilliams: Hardware AES Showdown – VIA Padlock vs. Intel AES-NI vs. AMD Hexacore. 6 July 2011. [dostęp 2013-08-28].

Linki zewnętrzne[edytuj | edytuj kod]