S-бокс

В криптографии ( S-блок блок подстановки ) является базовым компонентом алгоритмов симметричного ключа , который выполняет замену. В блочных шифрах они обычно используются для сокрытия связи между ключом и зашифрованным текстом , обеспечивая тем самым Шеннона свойство путаницы . Математически S-блок является нелинейным ^[1] векторная булева функция . ^[2]

В общем, S-блок принимает некоторое количество входных битов m n и преобразует их в некоторое количество выходных битов n , где не обязательно равно m . ^[3] S-блок m n × 2 может быть реализован как справочная таблица с ^м слова по n бит каждое. Обычно используются фиксированные таблицы, как в стандарте шифрования данных (DES), но в некоторых шифрах таблицы генерируются динамически на основе ключа (например, алгоритмы шифрования Blowfish и Twofish ).

Пример

Хорошим примером фиксированной таблицы является S-box из DES (S5 ₎ , преобразующий 6-битный вход в 4-битный выход:

С ₅		Средние 4 бита ввода
С ₅		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Внешние биты	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

Учитывая 6-битный входной сигнал, 4-битный выходной сигнал находится путем выбора строки, используя два внешних бита (первый и последний бит), и столбца, используя внутренние четыре бита. Например, вход « 0 1101 1 » имеет внешние биты « 01 » и внутренние биты «1101»; соответствующий результат будет «1001». ^[4]

Анализ и свойства

Когда DES был впервые опубликован в 1977 году, критерии проектирования его S-блоков держались в секрете, чтобы не поставить под угрозу технику дифференциального криптоанализа (которая еще не была публично известна). В результате исследования того, что делает S-box хорошими, в то время были скудными. Скорее, восемь S-блоков DES были предметом интенсивного изучения в течение многих лет из-за опасений, что бэкдор ( уязвимость в шифр мог быть заложен , известная только его разработчикам). Поскольку S-блоки являются единственной нелинейной частью шифра, их компрометация приведет к компрометации всего шифра. ^[5]

Критерии проектирования S-box были в конечном итоге опубликованы (в Coppersmith 1994 ) после публичного повторного открытия дифференциального криптоанализа, показывая, что они были тщательно настроены для повышения устойчивости к этой конкретной атаке, так что это было не лучше, чем грубая сила . Бихам и Шамир обнаружили, что даже небольшие модификации S-box могут значительно ослабить DES. ^[6]

Любой S-блок, в котором любая линейная комбинация выходных битов создается изогнутой функцией входных битов, называется идеальным S-блоком . ^[7]

S-блоки можно анализировать с помощью линейного криптоанализа и дифференциального криптоанализа в форме таблицы линейной аппроксимации (LAT), преобразования Уолша и таблицы распределения различий (DDT) или таблицы и спектра автокорреляции. Его силу можно суммировать по нелинейности (изогнутая, почти изогнутая) и дифференциальной однородности (совершенно нелинейная, почти идеально нелинейная). ^[8]^[9]^[10]^[2]

См. также

Ссылки

^ Daemen & Rijmen 2013 , с. 22.
↑ Перейти обратно: Перейти обратно: ^а ^б Карлет, Клод (2010), Хаммер, Питер Л.; Крама, Ив (ред.), «Векторные логические функции для криптографии» , Булевы модели и методы в математике, информатике и инженерии , Энциклопедия математики и ее приложений, Кембридж: Cambridge University Press, стр. 398–470, ISBN 978-0-521-84752-0 , получено 30 апреля 2021 г.
^ Чандрасекаран, Дж.; и др. (2011). «Подход, основанный на хаосе, для улучшения нелинейности в конструкции S-блока криптосистем с симметричным ключом» . В Меганатане, Северная Каролина; и др. (ред.). Достижения в области сетей и коммуникаций: Первая международная конференция по компьютерным наукам и информационным технологиям, CCSIT 2011, Бангалор, Индия, 2–4 января 2011 г. Материалы, Часть 2 . Спрингер. п. 516. ИСБН 978-3-642-17877-1 .
^ Бухманн, Йоханнес А. (2001). «5. ДЕЗ». Введение в криптографию (Источник 2. печат. изд.). Нью-Йорк, штат Нью-Йорк [ua]: Springer. стр. 119–120 . ISBN 978-0-387-95034-1 .
^ Копперсмит, Д. (май 1994 г.). «Стандарт шифрования данных (DES) и его защита от атак» . Журнал исследований и разработок IBM . 38 (3): 243–250. дои : 10.1147/rd.383.0243 . ISSN 0018-8646 .
^ «Модификации S-box и их влияние на DES-подобные системы шифрования» Гарджуло. Архивировано 20 мая 2012 г. на Wayback Machine. п. 9.
^ РФК 4086.Раздел 5.3 «Использование S-блоков для микширования»
^ Привет, Ховард М. «Учебное пособие по линейному и дифференциальному криптоанализу» (PDF) .
^ «S-Box и их алгебраические представления — Справочное руководство Sage 9.2: Криптография» . doc.sagemath.org . Проверено 30 апреля 2021 г.
^ Сааринен, Маркку-Юхани О. (2012). «Криптографический анализ всех 4 × 4-битных S-блоков». В Мири, Али; Водене, Серж (ред.). Избранные области криптографии . Конспекты лекций по информатике. Том. 7118. Берлин, Гейдельберг: Springer. стр. 118–133. дои : 10.1007/978-3-642-28496-0_7 . ISBN 978-3-642-28496-0 .

Дальнейшее чтение

Кайса Нюберг (1991). Совершенные нелинейные S-блоки . Достижения в криптологии – EUROCRYPT '91. Брайтон . стр. 378–386. дои : 10.1007/3-540-46416-6_32 .
С. Мистер и К. Адамс (1996). Практичный дизайн S-box . Семинар по избранным областям криптографии (SAC '96). Запись семинара. Королевский университет . стр. 61–76. CiteSeerX 10.1.1.40.7715 .
Шнайер, Брюс (1996). Прикладная криптография, второе издание . Джон Уайли и сыновья . стр. 296–298 , 349. ISBN. 978-0-471-11709-4 .

Чак Исттом (2018). «Обобщенная методология проектирования нелинейных элементов в симметричных криптографических примитивах». 8-й ежегодный семинар и конференция IEEE по вычислительной технике и связи (CCWC) , 2018 г. стр. 444–449. дои : 10.1109/CCWC.2018.8301643 . ISBN 978-1-5386-4649-6 . S2CID 3659645 .

Источники

Дэмен, Джоан; Реймен, Винсент (9 марта 2013 г.). «Функции каменщика». Конструкция Rijndael: AES — расширенный стандарт шифрования (PDF) . Springer Science & Business Media. стр. 22–23. ISBN 978-3-662-04722-4 . OCLC 1259405449 .

Внешние ссылки

[FOOTNOTEDaemenRijmen201322-1] Daemen & Rijmen 2013 , с. 22.

[:0-2] Перейти обратно: Перейти обратно: ^а ^б Карлет, Клод (2010), Хаммер, Питер Л.; Крама, Ив (ред.), «Векторные логические функции для криптографии» , Булевы модели и методы в математике, информатике и инженерии , Энциклопедия математики и ее приложений, Кембридж: Cambridge University Press, стр. 398–470, ISBN 978-0-521-84752-0 , получено 30 апреля 2021 г.

[chandra-516-3] Чандрасекаран, Дж.; и др. (2011). «Подход, основанный на хаосе, для улучшения нелинейности в конструкции S-блока криптосистем с симметричным ключом» . В Меганатане, Северная Каролина; и др. (ред.). Достижения в области сетей и коммуникаций: Первая международная конференция по компьютерным наукам и информационным технологиям, CCSIT 2011, Бангалор, Индия, 2–4 января 2011 г. Материалы, Часть 2 . Спрингер. п. 516. ИСБН 978-3-642-17877-1 .

[4] Бухманн, Йоханнес А. (2001). «5. ДЕЗ». Введение в криптографию (Источник 2. печат. изд.). Нью-Йорк, штат Нью-Йорк [ua]: Springer. стр. 119–120 . ISBN 978-0-387-95034-1 .

[5] Копперсмит, Д. (май 1994 г.). «Стандарт шифрования данных (DES) и его защита от атак» . Журнал исследований и разработок IBM . 38 (3): 243–250. дои : 10.1147/rd.383.0243 . ISSN 0018-8646 .

[6] «Модификации S-box и их влияние на DES-подобные системы шифрования» Гарджуло. Архивировано 20 мая 2012 г. на Wayback Machine. п. 9.

[7] РФК 4086.Раздел 5.3 «Использование S-блоков для микширования»

[8] Привет, Ховард М. «Учебное пособие по линейному и дифференциальному криптоанализу» (PDF) .

[9] «S-Box и их алгебраические представления — Справочное руководство Sage 9.2: Криптография» . doc.sagemath.org . Проверено 30 апреля 2021 г.

[10] Сааринен, Маркку-Юхани О. (2012). «Криптографический анализ всех 4 × 4-битных S-блоков». В Мири, Али; Водене, Серж (ред.). Избранные области криптографии . Конспекты лекций по информатике. Том. 7118. Берлин, Гейдельберг: Springer. стр. 118–133. дои : 10.1007/978-3-642-28496-0_7 . ISBN 978-3-642-28496-0 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]