 Architektura „gąbki” w algorytmie Keccak | |
| Rodzaj algorytmu | |
|---|---|
| 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
edytujKonkurs 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
edytujAlgorytm 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” (ang. 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 liczby bitów w pojedynczym bloku przy pomocy prostego schematu dopełniania zwanego „101”: do ciągu danych wejściowych w postaci 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
edytujDostępne są implementacje w językach: C/C++, Java, VHDL, Python[5], Rust[6], Cryptol[7], .NET C#, PHP[8].
Przypisy
edytuj- ↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. National Institute of Standards and Technology, 2012.
- ↑ Trzydziestu kandydatów do SHA-3. IPSec.pl, 4 listopada 2009. [dostęp 2012-10-09]. [zarchiwizowane z tego adresu (11 lutego 2011)].
- ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak sponge function family.
- ↑ Thomas Pornin: Comparative Performance Review of the SHA-3 Second-Round Candidates. 2010.
- ↑ Software and other files. The Keccak sponge function family.
- ↑ libOctavo/octavo.
- ↑ Alfonso De Gregorio: Untwisted: A Cryptol Implementation of Keccak – Part 1. 2011. [dostęp 2012-10-09]. [zarchiwizowane z tego adresu (2013-04-07)].
- ↑ PHP: hash - Manual [online], www.php.net [dostęp 2026-02-11] (ang.).
