S-pudełko

W kryptografii S -box ( substitution-box ) jest podstawowym elementem algorytmów klucza symetrycznego , który dokonuje podstawienia. W szyfrach blokowych są one zwykle używane do ukrywania związku między kluczem a tekstem zaszyfrowanym , zapewniając w ten sposób właściwość dezorientacji Shannona . Z matematycznego punktu widzenia S-box jest wektorową funkcją boolowską .

Ogólnie rzecz biorąc, S-box pobiera pewną liczbę bitów wejściowych , m , i przekształca je w pewną liczbę bitów wyjściowych, n , gdzie n niekoniecznie jest równe m . S -box m × n można zaimplementować jako tablicę przeglądową zawierającą 2 ^m słów po n bitach. Zwykle używane są stałe tabele, jak w Data Encryption Standard (DES), ale w niektórych szyfrach tabele są generowane dynamicznie na podstawie klucza (np. algorytmy szyfrowania Blowfish i Twofish ).

Przykład

Dobrym przykładem stałej tabeli jest S-box z DES (S ₅ ), odwzorowujący 6-bitowe wejście na 4-bitowe wyjście:

S ₅		Środkowe 4 bity wejścia
S ₅		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Bity zewnętrzne	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

0 Biorąc pod uwagę 6-bitowe dane wejściowe, 4-bitowe dane wyjściowe można znaleźć, wybierając wiersz za pomocą dwóch zewnętrznych bitów (pierwszego i ostatniego) oraz kolumny za pomocą czterech wewnętrznych bitów. Na przykład wejście „ 1101 1 ” ma zewnętrzne bity „ 01 ” i wewnętrzne bity „1101”; odpowiednim wyjściem byłoby „1001”.

Analiza i właściwości

Kiedy DES został opublikowany po raz pierwszy w 1977 roku, kryteria projektowe jego S-boxów były utrzymywane w tajemnicy, aby uniknąć narażenia na szwank techniki kryptoanalizy różnicowej (która nie była jeszcze publicznie znana). W rezultacie badania nad tym, co składało się na dobre S-boxy, były wówczas rzadkie. Osiem S-boxów DES było raczej przedmiotem intensywnych badań przez wiele lat z obawy, że w szyfrze mógł zostać osadzony backdoor ( luka w zabezpieczeniach znana tylko jego projektantom). Ponieważ pola S są jedyną nieliniową częścią szyfru, narażenie ich na szwank naruszyłoby cały szyfr.

Kryteria projektowania S-box zostały ostatecznie opublikowane (w Coppersmith 1994 ) po publicznym ponownym odkryciu kryptoanalizy różnicowej, pokazując, że zostały one starannie dostrojone, aby zwiększyć odporność na ten konkretny atak, tak aby nie był lepszy niż brutalna siła . Biham i Shamir odkryli, że nawet niewielkie modyfikacje S-boxa mogą znacznie osłabić DES.

Każdy S-box, w którym dowolna liniowa kombinacja bitów wyjściowych jest tworzona przez zakrzywioną 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 transformacji Walsha i tabeli dystrybucji różnic (DDT) lub tabeli autokorelacji i widma. Jego siłę można podsumować nieliniowością ( zagięcie, prawie zagięcie) i jednorodnością różniczkową (doskonale nieliniowa, prawie idealnie nieliniowa).

Zobacz też

Dalsza lektura

Kaisa Nyberg (1991). Doskonałe nieliniowe S-boxy (PDF) . Postępy w kryptologii - EUROCRYPT '91. Brighton . s. 378–386 . Źródło 2007-02-20 . ^{[ stały martwy link ]}
S. Mister i C. Adams (1996). Praktyczny projekt S-box . Warsztaty dotyczące wybranych obszarów kryptografii (SAC '96) Zapis warsztatów. Uniwersytet Królowej . s. 61–76. CiteSeerX 10.1.1.40.7715 .
Schneier, Bruce (1996). Kryptografia stosowana, wydanie drugie . John Wiley & Synowie . s. 296 –298, 349. ISBN 978-0-471-11709-4 .

Chuck Easttom (2018). „Uogólniona metodologia projektowania elementów nieliniowych w symetrycznych prymitywach kryptograficznych”. 2018 IEEE 8. doroczne warsztaty i konferencja na temat informatyki i komunikacji (CCWC) . Warsztaty i konferencja IEEE Computing and Communication (CCWC), 2018 IEEE 8th Annual. IEEE . s. 444–449. doi : 10.1109/CCWC.2018.8301643 . ISBN 978-1-5386-4649-6 . S2CID 3659645 .

Linki zewnętrzne