S-блок (информатика)

Об s-блоке химических элементов см. s-элементы.

S-блок (англ. s-box от substitution-box), «блок подстановок» — функция в коде программы или аппаратная система, принимающая на входе n бит, преобразующая их по определённому алгоритму и возвращающая на выходе m бит. n и m не обязательно равны.

S-блоки используются в блочных шифрах.

В электронике можно непосредственно применять схему, приведённую на рисунке. В программировании же создают таблицы замен (подстановочные таблицы, таблицы подстановок). Оба этих подхода являются эквивалентными, то есть данные, зашифрованные на компьютере, можно расшифровать на электронном устройстве и наоборот.

S-блок называется идеальным (англ. perfect s‑box), если значения выходных бит вычисляются бент-функцией на основе значений входных бит и любая линейная комбинация выходных бит является бент-функцией от входных бит.

Программная реализация

Программная реализация s‑блока работает следующим образом:

• читается значение на входе (аргумент функции);
• выполняется поиск прочитанного значения по таблице;
• по определённому правилу выбирается ячейка таблицы; из ячейки читается выходное значение; выходное значение возвращается из функции.

Используемая таблица называется «таблицей замен» или «таблицей подстановок». Таблица может:

• быть неизменной (фиксированной) (англ. static);
• генерироваться на основе ключа (англ. dynamic).

Например, для шифра (алгоритма) DES используется фиксированная таблица, а для шифров Blowfish и Twofish таблица создаётся на основе ключа.

Пример. Рассмотрим работу с таблицей пятого s‑блока (<math>S_5</math>) шифра DES. Пятый s‑блок принимает на входе 6 бит (<math>n=6</math>), а на выходе возвращает 4 бита (<math>m=4</math>). Пронумеруем входные биты слева направо от 1 до 6. Таблица подстановок имеет следующий вид:

S5		Значения 2‑го, 3‑го, 4‑го и 5‑го бит на входе
		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Значения 1‑го и 6‑го бит на входе	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

Пусть на вход подаются биты "011011". Найдём биты на выходе.

• 1‑й и 6‑й биты на входе равны «01».
• 2‑й, 3‑й, 4‑й и 5‑й биты на входе равны «1101».
• На пересечении строки «01» и столбца «1101» находим ячейку «1001» — значения бит на выходе.

Аппаратная реализация

Аппаратная реализация s‑блока (см. рис.) состоит из следующих устройств:

• дешифратор;
• система коммутаторов;
• шифратор.

Дешифратор — устройство, преобразующее n‑разрядный двоичный сигнал в одноразрядный сигнал по основанию <math>2^n</math>.

Например, для s-блока, изображённого на рисунке, дешифратор выполняет преобразование трёхразрядного сигнала (<math>n=3</math>) в восьмиразрядный (<math>2^3=8</math>).

Система коммутаторов — внутренние соединения, выполняющие перестановку бит. Если m=n, количество соединений равно <math>2^n</math>. Каждый входной бит отображается в выходной бит, расположенный в том же или ином разряде. Если число входов n и выходов m не равно, от каждого выхода дешифратора может идти ноль, одно, два или более соединений. Это же справедливо и для входов шифратора.

Для s-блока, изображённого на рисунке, <math>n=m=3</math>, число соединений равно <math>2^n=2^3=8</math>.

Шифратор — устройство, переводящее сигнал из одноразрядного <math>2^n</math>-ричного в n‑разрядный двоичный.

Для s‑блока, изображённого на рисунке, можно составить следующую таблицу замен (таблицу подстановок).

	0	1	2	3	4	5	6	7
Значение на входе дешифратора	0002=010	0012=110	0102=210	0112=310	1002=410	1012=510	1102=610	1112=710
Номер выхода дешифратора (по рисунку), на котором установлено значение 1 (на других выходах установлено значение 0)	0	1	2	3	4	5	6	7
Номер входа шифратора (по рисунку), на котором установлено значение 1 (на других входах установлено значение 0)	3	0	1	4	6	7	2	5
Значение на выходе шифратора	0112=310	0002=010	0012=110	1002=410	1102=610	1112=710	0102=210	1012=510

Пример. Пусть на входы шифратора, изображённого на рисунке, подаётся число 110₂ (см. рисунок). Так как десятичное представление двоичного числа 110₂ равно 6₁₀, на 6‑м выходе шифратора будет значение 1, а на других выходах — значение 0 (см. рисунок). С помощью системы коммутаторов значение 1 будет передано на 2‑й вход дешифратора (перестановка бит). Так как двоичное представление десятичного числа 2₁₀ равно 010₂, на выходах дешифратора будет число 010₂ (см. рисунок).

Применение

S-блоки используются в блочных шифрах при выполнении симметричного шифрования для сокрытия статистической связи между открытым текстом и шифротекстом.

Анализ n-разрядного s-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений велико (<math>2^n</math>). На практике «блок подстановок» используется как элемент более сложных систем.

S-блоки используются в следующих шифрах:

• AES (англ. advanced encryption standard) — шифр, являющийся стандартным на территории США;
• ГОСТ 28147-89 — отечественный стандарт шифрования данных;
• DES (англ. data encryption standard) — шифр, являвшийся стандартным на территории США до принятия AES;
• Blowfish;
• Twofish.

Безопасность

При проектировании s‑блока особое внимание следует уделять составлению «таблицы подстановок». Многие годы исследователи искали закладки (уязвимости, известные только создателям) в таблицах подстановок восьми s‑блоков шифра DES. Авторы DES рассказали о том, чем руководствовались при составлении таблиц подстановок. Результаты дифференциального криптоанализа шифра DES показали, что числа в таблицах подстановок были тщательно подобраны так, чтобы увеличить стойкость DES к определённым видам атак. Бихам и Шамир обнаружили, что даже небольшие изменения в таблицах могут значительно ослабить DES.

Литература

• Kaisa Nyberg (англ.) (1991). "Perfect nonlinear s-boxes" (PDF). Advances in cryptology - Eurocrypt (англ.) 1991: 378–386. Проверено 2007-02-20. 

• S. Mister and C. Adams (англ.) (1996). "[citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7715 Practical s-box design]" (PostScript). Workshop on Selected areas in cryptography (англ.) (SAC 1996). Workshop record: 61–76. Проверено 2007-02-20. 

• Schneier Bruce. Applied cryptography. Second edition. — John Wiley & Sons, 1996. — P. 296–298, 349. — ISBN 0-471-11709-9.

• Easttom, Chuck (2014). «A guideline for creating cryptographic s-boxes» (www.academia.edu/9192148/CREATING_CRYPTOGRAPHIC_S-BOXES_A_Guideline_for_Designing_Cryptographic_S-Boxes_by_Chuck_Easttom).

См. также

• Rijndael s-box (англ.)
• Биекция
• Булева функция
• Nothing up my sleeve number
• Шифр подстановки
• Permutation box (англ.) (англ. p-box)

Ссылки

• [www.quadibloc.com/crypto/co4513.htm John Savard's "Questions of S-Box Design"]
• [www.sans.org/reading_room/whitepapers/vpns/s-box-modifications-effect-des-like-encryption-systems_768 Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems"]

Отрывок, характеризующий S-блок (информатика)

– Вот он угол перекресток, где Захар извозчик стоит; вот он и Захар, и всё та же лошадь. Вот и лавочка, где пряники покупали. Скоро ли? Ну!
– К какому дому то? – спросил ямщик.
– Да вон на конце, к большому, как ты не видишь! Это наш дом, – говорил Ростов, – ведь это наш дом! Денисов! Денисов! Сейчас приедем.
Денисов поднял голову, откашлялся и ничего не ответил.
– Дмитрий, – обратился Ростов к лакею на облучке. – Ведь это у нас огонь?
– Так точно с и у папеньки в кабинете светится.
– Еще не ложились? А? как ты думаешь? Смотри же не забудь, тотчас достань мне новую венгерку, – прибавил Ростов, ощупывая новые усы. – Ну же пошел, – кричал он ямщику. – Да проснись же, Вася, – обращался он к Денисову, который опять опустил голову. – Да ну же, пошел, три целковых на водку, пошел! – закричал Ростов, когда уже сани были за три дома от подъезда. Ему казалось, что лошади не двигаются. Наконец сани взяли вправо к подъезду; над головой своей Ростов увидал знакомый карниз с отбитой штукатуркой, крыльцо, тротуарный столб. Он на ходу выскочил из саней и побежал в сени. Дом также стоял неподвижно, нерадушно, как будто ему дела не было до того, кто приехал в него. В сенях никого не было. «Боже мой! все ли благополучно?» подумал Ростов, с замиранием сердца останавливаясь на минуту и тотчас пускаясь бежать дальше по сеням и знакомым, покривившимся ступеням. Всё та же дверная ручка замка, за нечистоту которой сердилась графиня, также слабо отворялась. В передней горела одна сальная свеча.
Старик Михайла спал на ларе. Прокофий, выездной лакей, тот, который был так силен, что за задок поднимал карету, сидел и вязал из покромок лапти. Он взглянул на отворившуюся дверь, и равнодушное, сонное выражение его вдруг преобразилось в восторженно испуганное.
– Батюшки, светы! Граф молодой! – вскрикнул он, узнав молодого барина. – Что ж это? Голубчик мой! – И Прокофий, трясясь от волненья, бросился к двери в гостиную, вероятно для того, чтобы объявить, но видно опять раздумал, вернулся назад и припал к плечу молодого барина.
– Здоровы? – спросил Ростов, выдергивая у него свою руку.
– Слава Богу! Всё слава Богу! сейчас только покушали! Дай на себя посмотреть, ваше сиятельство!
– Всё совсем благополучно?
– Слава Богу, слава Богу!
Ростов, забыв совершенно о Денисове, не желая никому дать предупредить себя, скинул шубу и на цыпочках побежал в темную, большую залу. Всё то же, те же ломберные столы, та же люстра в чехле; но кто то уж видел молодого барина, и не успел он добежать до гостиной, как что то стремительно, как буря, вылетело из боковой двери и обняло и стало целовать его. Еще другое, третье такое же существо выскочило из другой, третьей двери; еще объятия, еще поцелуи, еще крики, слезы радости. Он не мог разобрать, где и кто папа, кто Наташа, кто Петя. Все кричали, говорили и целовали его в одно и то же время. Только матери не было в числе их – это он помнил.
– А я то, не знал… Николушка… друг мой!
– Вот он… наш то… Друг мой, Коля… Переменился! Нет свечей! Чаю!
– Да меня то поцелуй!
– Душенька… а меня то.
Соня, Наташа, Петя, Анна Михайловна, Вера, старый граф, обнимали его; и люди и горничные, наполнив комнаты, приговаривали и ахали.
Петя повис на его ногах. – А меня то! – кричал он. Наташа, после того, как она, пригнув его к себе, расцеловала всё его лицо, отскочила от него и держась за полу его венгерки, прыгала как коза всё на одном месте и пронзительно визжала.
Со всех сторон были блестящие слезами радости, любящие глаза, со всех сторон были губы, искавшие поцелуя.
Соня красная, как кумач, тоже держалась за его руку и вся сияла в блаженном взгляде, устремленном в его глаза, которых она ждала. Соне минуло уже 16 лет, и она была очень красива, особенно в эту минуту счастливого, восторженного оживления. Она смотрела на него, не спуская глаз, улыбаясь и задерживая дыхание. Он благодарно взглянул на нее; но всё еще ждал и искал кого то. Старая графиня еще не выходила. И вот послышались шаги в дверях. Шаги такие быстрые, что это не могли быть шаги его матери.
Но это была она в новом, незнакомом еще ему, сшитом без него платье. Все оставили его, и он побежал к ней. Когда они сошлись, она упала на его грудь рыдая. Она не могла поднять лица и только прижимала его к холодным снуркам его венгерки. Денисов, никем не замеченный, войдя в комнату, стоял тут же и, глядя на них, тер себе глаза.
– Василий Денисов, друг вашего сына, – сказал он, рекомендуясь графу, вопросительно смотревшему на него.
– Милости прошу. Знаю, знаю, – сказал граф, целуя и обнимая Денисова. – Николушка писал… Наташа, Вера, вот он Денисов.
Те же счастливые, восторженные лица обратились на мохнатую фигуру Денисова и окружили его.
– Голубчик, Денисов! – визгнула Наташа, не помнившая себя от восторга, подскочила к нему, обняла и поцеловала его. Все смутились поступком Наташи. Денисов тоже покраснел, но улыбнулся и взяв руку Наташи, поцеловал ее.
Денисова отвели в приготовленную для него комнату, а Ростовы все собрались в диванную около Николушки.
Старая графиня, не выпуская его руки, которую она всякую минуту целовала, сидела с ним рядом; остальные, столпившись вокруг них, ловили каждое его движенье, слово, взгляд, и не спускали с него восторженно влюбленных глаз. Брат и сестры спорили и перехватывали места друг у друга поближе к нему, и дрались за то, кому принести ему чай, платок, трубку.
Ростов был очень счастлив любовью, которую ему выказывали; но первая минута его встречи была так блаженна, что теперешнего его счастия ему казалось мало, и он всё ждал чего то еще, и еще, и еще.
На другое утро приезжие спали с дороги до 10 го часа.
В предшествующей комнате валялись сабли, сумки, ташки, раскрытые чемоданы, грязные сапоги. Вычищенные две пары со шпорами были только что поставлены у стенки. Слуги приносили умывальники, горячую воду для бритья и вычищенные платья. Пахло табаком и мужчинами.
– Гей, Г'ишка, т'убку! – крикнул хриплый голос Васьки Денисова. – Ростов, вставай!
Ростов, протирая слипавшиеся глаза, поднял спутанную голову с жаркой подушки.
– А что поздно? – Поздно, 10 й час, – отвечал Наташин голос, и в соседней комнате послышалось шуршанье крахмаленных платьев, шопот и смех девичьих голосов, и в чуть растворенную дверь мелькнуло что то голубое, ленты, черные волоса и веселые лица. Это была Наташа с Соней и Петей, которые пришли наведаться, не встал ли.
– Николенька, вставай! – опять послышался голос Наташи у двери.
– Сейчас!
В это время Петя, в первой комнате, увидав и схватив сабли, и испытывая тот восторг, который испытывают мальчики, при виде воинственного старшего брата, и забыв, что сестрам неприлично видеть раздетых мужчин, отворил дверь.
– Это твоя сабля? – кричал он. Девочки отскочили. Денисов с испуганными глазами спрятал свои мохнатые ноги в одеяло, оглядываясь за помощью на товарища. Дверь пропустила Петю и опять затворилась. За дверью послышался смех.
– Николенька, выходи в халате, – проговорил голос Наташи.
– Это твоя сабля? – спросил Петя, – или это ваша? – с подобострастным уважением обратился он к усатому, черному Денисову.
Ростов поспешно обулся, надел халат и вышел. Наташа надела один сапог с шпорой и влезала в другой. Соня кружилась и только что хотела раздуть платье и присесть, когда он вышел. Обе были в одинаковых, новеньких, голубых платьях – свежие, румяные, веселые. Соня убежала, а Наташа, взяв брата под руку, повела его в диванную, и у них начался разговор. Они не успевали спрашивать друг друга и отвечать на вопросы о тысячах мелочей, которые могли интересовать только их одних. Наташа смеялась при всяком слове, которое он говорил и которое она говорила, не потому, чтобы было смешно то, что они говорили, но потому, что ей было весело и она не в силах была удерживать своей радости, выражавшейся смехом.
– Ах, как хорошо, отлично! – приговаривала она ко всему. Ростов почувствовал, как под влиянием жарких лучей любви, в первый раз через полтора года, на душе его и на лице распускалась та детская улыбка, которою он ни разу не улыбался с тех пор, как выехал из дома.
– Нет, послушай, – сказала она, – ты теперь совсем мужчина? Я ужасно рада, что ты мой брат. – Она тронула его усы. – Мне хочется знать, какие вы мужчины? Такие ли, как мы? Нет?
– Отчего Соня убежала? – спрашивал Ростов.
– Да. Это еще целая история! Как ты будешь говорить с Соней? Ты или вы?
– Как случится, – сказал Ростов.
– Говори ей вы, пожалуйста, я тебе после скажу.
– Да что же?
– Ну я теперь скажу. Ты знаешь, что Соня мой друг, такой друг, что я руку сожгу для нее. Вот посмотри. – Она засучила свой кисейный рукав и показала на своей длинной, худой и нежной ручке под плечом, гораздо выше локтя (в том месте, которое закрыто бывает и бальными платьями) красную метину.
– Это я сожгла, чтобы доказать ей любовь. Просто линейку разожгла на огне, да и прижала.
Сидя в своей прежней классной комнате, на диване с подушечками на ручках, и глядя в эти отчаянно оживленные глаза Наташи, Ростов опять вошел в тот свой семейный, детский мир, который не имел ни для кого никакого смысла, кроме как для него, но который доставлял ему одни из лучших наслаждений в жизни; и сожжение руки линейкой, для показания любви, показалось ему не бесполезно: он понимал и не удивлялся этому.
– Так что же? только? – спросил он.
– Ну так дружны, так дружны! Это что, глупости – линейкой; но мы навсегда друзья. Она кого полюбит, так навсегда; а я этого не понимаю, я забуду сейчас.
– Ну так что же?
– Да, так она любит меня и тебя. – Наташа вдруг покраснела, – ну ты помнишь, перед отъездом… Так она говорит, что ты это всё забудь… Она сказала: я буду любить его всегда, а он пускай будет свободен. Ведь правда, что это отлично, благородно! – Да, да? очень благородно? да? – спрашивала Наташа так серьезно и взволнованно, что видно было, что то, что она говорила теперь, она прежде говорила со слезами.
Ростов задумался.
– Я ни в чем не беру назад своего слова, – сказал он. – И потом, Соня такая прелесть, что какой же дурак станет отказываться от своего счастия?
– Нет, нет, – закричала Наташа. – Мы про это уже с нею говорили. Мы знали, что ты это скажешь. Но это нельзя, потому что, понимаешь, ежели ты так говоришь – считаешь себя связанным словом, то выходит, что она как будто нарочно это сказала. Выходит, что ты всё таки насильно на ней женишься, и выходит совсем не то.
Ростов видел, что всё это было хорошо придумано ими. Соня и вчера поразила его своей красотой. Нынче, увидав ее мельком, она ему показалась еще лучше. Она была прелестная 16 тилетняя девочка, очевидно страстно его любящая (в этом он не сомневался ни на минуту). Отчего же ему было не любить ее теперь, и не жениться даже, думал Ростов, но теперь столько еще других радостей и занятий! «Да, они это прекрасно придумали», подумал он, «надо оставаться свободным».