SHA-3

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
SHA-3
SpongeConstruction.svg
Architektura "gąbki" w algorytmie Keccak
Rodzaj algorytmu kryptograficzna funkcja skrótu
Data stworzenia 2012
Autorzy Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche


SHA-3 (Secure Hash Algorithm 3) — kryptograficzna funkcja skrótu wyłoniona w 2012 roku w ramach konkursu ogłoszonego przez amerykański NIST[1].

Historia[edytuj | edytuj kod]

Konkurs na SHA-3 rozpoczął się w 2009 roku. Zgłoszono do niego 30 kandydatów[2]. W 2012 roku NIST wyłonił jako zwycięzcę algorytm Keccak[3].

Charakterystyka[edytuj | edytuj kod]

Algorytm Keccak charakteryzuje się wyższą wydajnością niż SHA-2 zarówno w implementacjach sprzętowych jak i programowych (różnica sięga 25-80% w zależności od procesora i implementacji)[4]. Keccak ma architekturę "gąbki" (sponge construction) — bloki wejściowe są stopniowo "wchłaniane" w kolejnych etapach i mieszane z dużym rejestrem stanu. Blok wyjściowy jest konstruowany w podobny sposób, przez "wyciskanie" kolejnych fragmentów danych wyjściowych z rejestru stanu, wielokrotnie go mieszając pomiędzy wyciskanymi blokami. Wchłanianie i wyciskanie odbywa się na małej części rejestru stanu, poprzez wykonanie funkcji binarnej alternatywy wykluczającej (xor) z danymi wejściowymi, lub odczyt tej samej małej części przy odczycie danych wyjściowych. Pozostała część stanu nigdy nie jest bezpośrednio używana do konstrukcji danych wyjściowych, ani nie oddziałuje bezpośrednio z danymi wejściowymi.

Funkcja mieszająca stanu (funkcja f na rysunku), składa się z wielokrotnej aplikacji funkcji rundy (do 24 razy w przypadku największej wersji algorytmu). Każda runda z kolei, składa się z kompozycji 5 prostych i wydajnych w implementacji funkcji, które dokonują odwracalnych permutacji, rotacji, mieszań albo dyfuzji. Ostatnia z tych funkcji w rundzie, dodatkowo jest parametryzowana stałą wartością zależną od numeru rundy (i wersji algorytmu), w celu usunięcia symetrii z funkcji rundy.

Dane wejściowe są dopełniane do całkowitej wielokrotności liczy bitów w pojedynczym bloku, przy pomocy prostego schematu dopełniana zwanego 101: Do ciągu danych wejściowych w postacji ciągu binarnego, dopisz bit o wartości 1, następnie bity o wartości 0, aż do przedostatniego bitu w pełnym bloku, następnie dopisz bit o wartości 1 dopełniając blok całkowicie.

Implementacje[edytuj | edytuj kod]

Dostępne są implementacje w językach

Przypisy

  1. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. National Institute of Standards and Technology, 2012.
  2. Trzydziestu kandydatów do SHA-3. IPSec.pl, 4 listopada 2009.
  3. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak sponge function family.
  4. Thomas Pornin: Comparative Performance Review of the SHA-3 Second-Round Candidates. 2010.
  5. Software and other files. The Keccak sponge function family.
  6. Alfonso De Gregorio: Untwisted: A Cryptol Implementation of Keccak – Part 1. 2011.