S-box - S-box
W kryptografii An skrzynki S ( podstawienie-box ), jest podstawowym składnikiem symetrycznego algorytmu kluczowych , które dokonuje podstawienia. W szyfrach blokowych są one zwykle używane do zaciemniania relacji między kluczem a tekstem zaszyfrowanym , zapewniając w ten sposób właściwość Shannona dotyczącą pomyłek . Matematycznie S-box jest wektorową funkcją Boole'a .
Zazwyczaj, skrzynka S wymaga pewnej liczby wejściowych bitów , m , i przekształca je w pewną liczbę bitów wyjściowych, n , gdzie n nie musi być równy m . M x n S pole może być realizowany jako tabeli przeglądowej, z 2 m słowa n bitów każdy. Zwykle używane są stałe tabele, jak w Data Encryption Standard (DES), ale w niektórych szyfrach tabele są generowane dynamicznie z klucza (np. algorytmy szyfrowania Blowfish i Twofish ).
Przykład
Dobrym przykładem stałej tabeli jest S-box z DES (S 5 ), mapujący 6-bitowe wejście na 4-bitowe wyjście:
S 5 | Środkowe 4 bity wejścia | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | ||
Zewnętrzne bity | 00 | 0010 | 1100 | 0100 | 0001 | 0111 | 1010 | 1011 | 0110 | 1000 | 0101 | 0011 | 1111 | 1101 | 0000 | 1110 | 1001 |
01 | 1110 | 1011 | 0010 | 1100 | 0100 | 0111 | 1101 | 0001 | 0101 | 0000 | 1111 | 1010 | 0011 | 1001 | 1000 | 0110 | |
10 | 0100 | 0010 | 0001 | 1011 | 1010 | 1101 | 0111 | 1000 | 1111 | 1001 | 1100 | 0101 | 0110 | 0011 | 0000 | 1110 | |
11 | 1011 | 1000 | 1100 | 0111 | 0001 | 1110 | 0010 | 1101 | 0110 | 1111 | 0000 | 1001 | 1010 | 0100 | 0101 | 0011 |
Biorąc pod uwagę 6-bitowe dane wejściowe, 4-bitowe dane wyjściowe można znaleźć, wybierając wiersz przy użyciu zewnętrznych dwóch bitów (pierwszy i ostatni bit), a kolumnę przy użyciu wewnętrznych czterech bitów. Na przykład wejście „ 0 1101 1 ” ma bity zewnętrzne „ 01 ” i bity wewnętrzne „1101”; odpowiedni wynik to „1001”.
Osiem S-boxów DES przez wiele lat było przedmiotem intensywnych badań w obawie, że w szyfrze mógł zostać umieszczony backdoor ( luka znana tylko jego projektantom). Kryteria projektowe S-box zostały ostatecznie opublikowane (w Coppersmith 1994 ) po publicznym odkryciu kryptoanalizy różnicowej , pokazując, że zostały one starannie dostrojone, aby zwiększyć odporność na ten konkretny atak. Biham i Shamir odkryli, że nawet niewielkie modyfikacje S-boxa mogą znacząco osłabić DES.
Analiza i właściwości
Przeprowadzono wiele badań nad projektowaniem dobrych S-boxów io wiele więcej wiadomo na temat ich wykorzystania w szyfrach blokowych niż w momencie wydania DES.
Każdy S-box, w którym dowolna liniowa kombinacja bitów wyjściowych jest wytwarzana przez wygiętą funkcję bitów wejściowych, jest określany jako doskonały S-box .
S-boxy można analizować za pomocą kryptoanalizy liniowej i kryptoanalizy różnicowej w postaci tabeli aproksymacji liniowej (LAT) lub transformaty Walsha i tabeli rozkładu różnic (DDT) lub tabeli i widma autokorelacji. Jego siłę można podsumować nieliniowością (zgięty, prawie zgięty) i różnicową jednorodnością (doskonale nieliniowa, prawie doskonale nieliniowa).
Zobacz też
- Bijection, wtrysk i surjekcja
- Funkcja logiczna
- Numer „Nic-up-my-sleeve”
- Skrzynka permutacyjna (P-box)
- Szyfr permutacyjny
- Rijndael S-box
- Szyfr podstawieniowy
Bibliografia
Dalsza lektura
- Kaisa Nyberg (1991). Idealne nieliniowe S-boxy (PDF) . Postępy w kryptologii - EUROCRYPT '91. Brighton . s. 378–386 . Źródło 2007-02-20 .
- Kowal miedziany, Don (1994). „Standard szyfrowania danych (DES) i jego siła przed atakami”. IBM Journal of Research and Development . 38 (3): 243-250. doi : 10.1147/rd.383.0243 .
- S. Mister i C. Adams (1996). Praktyczna konstrukcja S-box . Warsztaty na temat wybranych obszarów w kryptografii (SAC '96) Zapis warsztatu. Uniwersytet Królowej . s. 61-76. CiteSeerX 10.1.1.40.7715 .
- Schneiera, Bruce'a (1996). Kryptografia stosowana, wydanie drugie . John Wiley i Synowie . str. 296 -298, 349 ISBN 978-0-471-11709-4.
- Chuck Easttom (2018). „Uogólniona metodologia projektowania elementów nieliniowych w symetrycznych prymitywach kryptograficznych”. 2018 8. doroczne warsztaty i konferencja IEEE w zakresie informatyki i komunikacji (CCWC) . Warsztaty i konferencja IEEE Computing and Communication (CCWC), 8th Annual IEEE. IEEE . s. 444-449. doi : 10.1109/CCWC.2018.8301643 . Numer ISBN 978-1-5386-4649-6. S2CID 3659645 .