Задача обеспечения секретности.

Шифры подстановок. Примеры.

Подстановочным шифром называется шифр, в котором каждый символ открытого текста в шифротексте заменяет другим символом.

К таким шифрам относится шифр Цезаря, Афинный шифр, Атбаш.

Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря — один из самых простых и наиболее широко известных методов шифрования.

Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется буквой находящейся на некоторое постоянное число позиций левее или правее него в алфавите. Например, в шифре со сдвигом 3 А была бы заменена на Г, Б станет Д, и так далее.

Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами.

Шифрование с использованием ключа . Буква «С» «сдвигается» на три буквы вперёд и становится буквой «Ф». Твёрдый знак, перемещённый на три буквы вперёд, становится буквой «Э», и так далее.

Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами.

 

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Шифрование

В этом примере необходимо зашифровать сообщение "ATTACK AT DAWN", используя упомянутое выше соответствие между буквами и числами, и значения , и , так как в используемом алфавите 26 букв. Только на число наложены ограничения, так как оно должно быть взаимно простым с 26. Возможные значения : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25^[3]. Значение может быть любым, только если не равно единице, так как это сдвиг шифра. Итак, для нашего примера функция шифрования . Первый шаг шифрования — запись чисел, соответствующих каждой букве сообщения.

сообщение

A

T

T

А

C

K

A

T

D

A

W

N

Теперь, для каждого значения найдем значение . После нахождения значения для каждого символа возьмем остаток от деления на 26. Следующая таблица показывает первые четыре шага процесса шифрования.

сообщение

A

T

T

А

C

K

A

T

D

A

W

N

Последний шаг процесса шифрования заключается в подстановке вместо каждого числа соответствующей ему буквы. В этом примере шифротекст будет "EJJEKIEJNESR". Таблица ниже показывает все шаги по шифрованию сообщения аффинным шифром.

сообщение

A

T

T

А

C

K

A

T

D

A

W

N

шифротекст

E

J

J

E

K

I

E

J

N

E

S

R

Расшифрование

Для расшифрования возьмем шифротекст из примера с шифрованием. Функция расшифрования будет , где , и . Для начала запишем численные значения для каждой буквы шифротекста, как показано в таблице ниже.

шифротекст

E

J

J

E

K

I

E

J

N

E

S

R

Теперь рассчитаем для каждого необходимо рассчитать и взять остаток от деления этого числа на 26. Следующая таблица показывает результат этих вычислений.

шифротекст

E

J

J

E

K

I

E

J

N

E

S

R

Последний шаг операции расшифрования для шифротескста — поставить в соответствие числам буквы. Сообщение после расшифрования будет "ATTACKATDAWN". Таблица ниже показывает выполнение последнего шага.

шифротекст

E

J

J

E

K

I

E

J

N

E

S

R

сообщение

A

T

T

А

C

K

A

T

D

A

W

N

«Атба́ш» (ивр. אתב"ש‎) — простой шифр подстановки для иврита. Правило шифрования состоит в замене «i»-й буквы алфавита буквой с номером «n» − «i» + 1, где «n» — число букв в алфавите. Пример для латинского алфавита выглядит так:

Исходный текст: abcdefghijklmnopqrstuvwxyzЗашифрованный текст: ZYXWVUTSRQPONMLKJIHGFEDCBA

 

Шифры перестановок. Пример

Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки (ШП).

Зная подстановку, задающую преобразование, можно осуществить как шифрование, так и расшифрование текста. Например, если для преобразования используется подстановка

 

1 2 3 4 5 6

5 2 3 1 4 6

 

и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА.

Попробуйте расшифровать сообщение НЧЕИУК, полученное в результате преобразования с помощью указанной выше подстановки.

Зная метод математической индукции, легко убедиться в том, что существует n (n факториал n! = n*(n-1)) вариантов заполнения нижней строки таблицы (1). Таким образом, число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины n, меньше либо равно n!. (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах!).

С увеличением числа n значение n! факториал растет очень быстро:

Таблица 1.1 – Значения N! для первых 10 натуральных чисел

Примером ШП, предназначенного для зашифрования сообщений длины n, является шифр, в котором в качестве множества ключей взято множество всех подстановок степени n, а соответствующие им преобразования шифра задаются, как было описано выше. Число ключей такого шифра равно n!

Для использования на практике такой шифр неудобен, так как при больших значениях n приходится работать с длинными таблицами.

Широкое распространение получили фигуры перестановки, использующие некоторую геометрическую фигуру. Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного маршрута, а затем по ходу другого выписывается с нее. Такой шифр называется маршрутнойперестановкой. Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего поочередно слева направо и справа налево. Выписывать же сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх.

Зашифруем, например, указанным способом фразу:

ПРИМЕР МАРШРУТНОЙ ПЕРЕСТАНОВКИ

используя прямоугольник размера 47 Зашифрованная фраза выглядит так:

 

МАСТЕРРЕШРНОЕРМИУПВКЙТРПНОИ

 

Теоретически маршруты могут быть значительно более изощренными, однако запутанность маршрутов усложняет использование таких шифров.

Для использования шифра, называемого поворотной решеткой, изготавливается трафарет из прямоугольного листа клетчатой бумаги размера 2m2k клеток. В трафарете вырезано mk клеток так, что при наложении его на лист чистой бумаги того же размера четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.

Буквы сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений в заранее установленном порядке.

Пример шифрования. Пусть в качестве ключа используется решетка 610, приведенная на рис. 1. 1.

Зашифруем с ее помощью текст

 

ШИФРРЕШЕТКАЯВЛЯЕТСЯ ЧАСТНЫМЛУЧАЕМШИФРАМАРШРУТНОЙ ПЕРЕСТАНОВКИ

 

Наложив решетку на лист бумаги, вписываем первые 15 (по числу вырезов) букв сообщения ШИФРРЕШЕТКАЯВЛЯ….. Сняв решетку, мы увидим текст, представленный на рис. 1. 2. Поворачиваем решетку на 180. В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис. 1. 3. Затем поворачиваем решетку на другую сторону и зашифровываем остаток текста аналогичным образом (рис. 1.4, 1.5).

Получатель сообщения, имеющий точно такую же решетку, без труда прочтет исходный текст, наложив решетку на шифротекст по порядку четырьмя способами. Можно доказать, что число возможных трафаретов, то есть количество ключей шифра решетка, составляет Т = 4^mk. Этот шифр предназначен для сообщений длины n = 4mk. Число всех перестановок в тексте такой длины составит (4mk)!, что во много раз больше числа Т. Однако, уже при размере трафарета 88 число возможных решеток превосходит 4 миллиарда

Шифром вертикальной перестановки (ШВП) называется широко распространенная разновидность шифра маршрутной перестановки. В нем используется прямоугольник, в котором сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,1,4,7,2,6,3), и с его помощью надо зашифровать сообщение:

 

ВОТ ПРИМЕР ШИФРА ВЕРТИКАЛЬНОЙ

ПЕРЕСТАНОВКИ

 

Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом:

Теперь, выбирая столбцы в порядке, заданном ключом и выписывая последовательно буквы каждого из них сверху вниз, получаем такую криптограмму:

 

ОРЕЬЕРФИЙА-МААЕО-ТШРНСИВЕВЛРВИРКПН-ПИТОТ-

 

Число ключей ШВП не более m!, где m – число столбцов таблицы. Как правило, m гораздо меньше, чем длина текста n (сообщение укладывается в несколько строк по m букв), а значит, и m! много меньше n!.

В случае, когда ключ ШВП не рекомендуется записывать, его можно извлекать из какого либо запоминающегося слова или предложения. Для этого существует много способов. Наиболее распространенный состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет ПЕРЕСТАНОВКА. Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появление нумеруется последовательно слева направо. Поэтому второе вхождение буквы А получает номер 2. Поскольку буквы Б в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ:

 

П Е Р Е С Т А Н О В К А

9 4 10 5 11 12 1 7 8 3 6 2

Шифр Вернама

Шифр Вернама, или одноразовый блокнот, был изобретен в 1917 году Мейджором Джозефом Моборном (Major Joseph Mauborn) и Гильбертом Вернамом (Gilbert Vernam) из AT&T (American Telephone & Telegraph). В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом. Первоначально это была одноразовая лента для телетайпов. Отправитель использовал каждый символ ключа для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю n (мощность алфавита) символа открытого текста и символа ключа из одноразового блокнота. Каждый символ ключа используется только один раз и для единственного сообщения, иначе даже если использовать блокнот размером в несколько гигабайт, при получении криптоаналитиком нескольких текстов с перекрывающимися ключами он сможет восстановить исходный текст. Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции. если шифротексты смещены правильно, соотношение совпадений резко возрастет. С этой точки зрения криптоанализ не составит труда. Если же ключ не повторяется и случаен, то криптоаналитик, перехватывает он тексты или нет, всегда имеет одинаковые знания. Случайная ключевая последовательность, сложенная с неслучайным открытым текстом, дает совершенно случайный криптотекст, и никакие вычислительные мощности не смогут это изменить.

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

Главным недостатком данной системы является то, что для каждого бита переданной информации должен быть заранее подготовлен бит ключевой информации, причем эти биты должны быть случайными. При шифровании большого объема данных это является серьезным ограничением. Поэтому данная система используется только для передачи сообщений наивысшей секретности. По слухам "горячая линия" между США и СССР шифровалась с помощью одноразового блокнота. Многие сообщения советских шпионов были зашифрованы с использованием одноразовых блокнотов. Эти сообщения нераскрыты сегодня, и не будут раскрыты никогда (если не найдется способа вернуться в прошлое и достать эти блокноты:)

Чтобы обойти проблему предварительной передачи секретного ключа большого объема, инженеры и изобретатели придумали много остроумных схем генерации очень длинных потоков псевдослучайных цифр из нескольких коротких потоков в соответствии с некоторым алгоритмом. Получателя шифрованного сообщения при этом необходимо снабдить точно таким же генератором, как и у отправителя. Но такие алгоритмы добавляющих регулярности в шифротекст, обнаружение которых может помочь аналитику дешифровать сообщение. Один из основных методов построения подобных генераторов заключается в использовании двух или более битовых лент, считанные с которых данные побитно складываются для получения "смешанного" потока. Например, простая одноразовая лента может быть заменена двумя циклическими лентами, длины которых являются простыми или взаимно простыми числами. Так как в этом случае длины лент не имеют общих множителей, полученный из них поток имеет период повторения, равный произведению их длин: две ленты, имеющие длину 1000 и 1001 соответственно, дают в результате составной поток с периодом 1000x1001=1001000 цифр. Ленты циркулируют через сумматор, который складывает по модулю два считанные с них цифры. Выход сумматора служит ключом, используемым для зашифрования сообщения. Поэтому важно, чтобы составной поток превышал по длине все вместе взятые сообщения, которые могут быть переданы за разумный период времени. Поскольку побитовый сумматор является линейным устройством, он изначально криптографически слаб, но может быть усилен большим количеством различных способов. Другой способ - указание местонахождения ключа как места в книге, например,Дональд Э. Кнут Искусство Программирования Том 2. Получисленные алгоритмы. Третье издание. стр 83, 3-й абзац. Все символы, входящие в алфавит, начиная с этого места используются как одноразовый ключ для какого-либо сообщения. Но в данном случае ключ не будет случайным и может быть использована информация о частотах распределения букв.

Как не удивительно, но класс шифров Вернама - единственный класс шифров, для которого может быть доказана (и была доказана Шенноном) невскрываемость в абсолютном смысле этого термина.

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

Уровни атаки.

Атака зашифрованного текста

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

Атака выборного шифра

Эта атака не подразумевает, что дешифровальщик может выбирать шифр; это означает, что имеется некоторое знание относительно отношений между различными шифрами - эта - довольно неясная атака и практически не используется.

Метод "резиновой дубинки"

Дешифровальщик угрожает кому-то, пока не получит шифр. Очень часто используется взяточничество называемое покупкой ключа. Эта критическая, и очень мощная атака и зачастую лучший способ узнать алгоритм.

Модели атак

Традиционная модель атаки строится по принципу "один к одному" (Рис.1.) или "один ко многим" (Рис.2.), т.е. атака исходит из одного источника. Разработчики сетевых средств защиты (межсетевых экранов, систем обнаружения атак и т.д.) ориентированы именно на традиционную модель атаки. В различных точках защищаемой сети устанавливаются агенты (сенсоры) системы защиты, которые передают информацию на центральную консоль управления. Это облегчает масштабирование системы, простоту удаленного управления и т.д. Однако такая модель не справляется с относительно недавно (в 1998 году) обнаруженной угрозой - распределенными атаками.

Рисунок1.Отношение "один к одному"

Рисунок 2. Отношение "один ко многим"

В модели распределенной или скоординированной (distributed или coordinated attack) атаки используются иные принципы. В отличие от традиционной модели, использующей отношения "один к одному" и "один ко многим", в распределенной модели используются отношения "много к одному" и "много ко многим" (рис.3 и 4 соответственно).

Рисунок 3. Отношение "многие к одному"

 

Рисунок 4. Отношение "многие ко многим"

Распределенные атаки основаны на "классических" атаках типа "отказ в обслуживании", которые будут рассмотрены ниже, а точнее на их подмножестве, известном как Flood- или Storm-атаки (указанные термины можно перевести как "шторм", "наводнение" или "лавина"). Смысл данных атак заключается в посылке большого количества пакетов на заданный узел или сегмент сети (цель атаки), что может привести к выведению этого узла или сегмента из строя, поскольку он "захлебнется" в лавине посылаемых пакетов и не сможет обрабатывать запросы авторизованных пользователей. По такому принципу работают атаки SYN-Flood, Smurf, UDP Flood, Targa3 и т.д. Однако в том случае, если пропускная способность канала до цели атаки превышает пропускную способность атакующего или целевой узел некорректно сконфигурирован, то к "успеху" такая атака не приведет. Например, с помощью этих атак бесполезно пытаться нарушить работоспособность своего провайдера. В случае же распределенной атаки ситуация коренным образом меняется. Атака происходит уже не из одной точки Internet, а сразу из нескольких, что приводит к резкому возрастанию трафика и выведению атакуемого узла из строя. Например, по данным России-Онлайн в течение двух суток, начиная с 9 часов утра 28 декабря 2000 г. крупнейший Internet-провайдер Армении "Арминко" подвергался распределенной атаке. В данном случае к атаке подключились более 50 машин из разных стран, которые посылали по адресу "Арминко" бессмысленные сообщения. Кто организовал эту атаку, и в какой стране находился хакер - установить было невозможно. Хотя атаке подвергся в основном "Арминко", перегруженной оказалась вся магистраль, соединяющая Армению с всемирной паутиной. 30 декабря благодаря сотрудничеству "Арминко" и другого провайдера - "АрменТел" - связь была полностью восстановлена. Несмотря на это компьютерная атака продолжалась, но с меньшей интенсивностью.

Шифратор Джефферсона.

В начале XIX века криптография обогатилась замечательным изобретением. Его автор - государственный деятель, первый государственный секретарь, а затем и президент США Томас Джефферсон. Свою систему шифрования он назвал "дисковым шифром". Этот шифр реализовывался с помощью специального устройства, которое впоследствии назвали шифратором Джефферсона. Конструкция шифратора может быть вкратце описана следующим образом. Деревянный цилиндр разрезается на 36 дисков (в принципе, общее количество дисков может быть и иным). Эти диски насаживаются на одну общую ось таким образом, чтобы они могли независимо вращаться на ней. На боковых поверхностях каждого из дисков выписывались все буквы английского алфавита в произвольном порядке. Порядок следования букв на различных дисках - различный. На поверхности цилиндра выделялась линия, параллельная его оси. При шифровании открытый текст разбивался на группы по 36 знаков, затем первая буква группы фиксировалась положением первого диска по выделенной линии, вторая - положением второго диска и т. д. Шифрованный текст образовывался путем считывания последовательности букв с любой линии параллельной выделенной. Обратный процесс осуществлялся на аналогичном шифраторе: полученный шифртекст выписывался путем поворота дисков по выделенной линии, а открытый текст отыскивался среди параллельных ей линий путем прочтения осмысленного возможного варианта. Хотя теоретически этот метод позволял предположить появление различных вариантов открытого сообщения, но, как показал накопившийся к тому времени опыт, это маловероятно: осмысленный текст читался только по одной из возможных линий. Шифратор Джефферсона реализует ранее известный шифр многоалфавитной замены. Частями его ключа являются порядок расположения букв на каждом диске и порядок расположения этих дисков на общей оси. Общее количество ключей огромно:= (4?1026)36.

Это изобретение стало предвестником появления так называемых дисковых шифраторов, нашедших широкое распространение в развитых странах в XX веке. Шифратор, совершенно аналогичный шифратору Джефферсона, использовался в армии США во время II Мировой войны. Однако при жизни Джефферсона судьба его изобретения сложилась неудачно. Будучи госсекретарем, сам Джефферсон продолжал использовать традиционные коды (номенклаторы) и шифры типа шифра Виженера. Он очень осторожно относился к своему изобретению и считал, что его нужно основательно проанализировать. С этой целью он длительное время поддерживал связь с математиком Р. Паттерсоном. В результате обмена информацией Паттерсон предложил свой собственный шифр, который, по его мнению, являлся более надежным, чем шифр Джефферсона. Он представлял собой шифр вертикальной перестановки с введением "пустышек". По стойкости он значительно уступал шифру Джефферсона, однако тот принял доводы своего оппонента и признал его шифр более приемлемым для использования. Таким образом, Джефферсон сам не оценил всей глубины своего собственного изобретения.

Требования

Полная утрата всех статистических закономерностей исходного сообщения является важным требованием к симметричному шифру. Для достижения такого шифр должен иметь «эффект лавины» — сильное изменение шифроблока при 1битном изменении входных
данных (в идеале должны меняться значения 1/2 бит шифроблока).

Также важным требованием является отсутствие линейности (то есть условия f(a) xor f(b) = f(a xor b)), в противном случае облегчается применение дифференциального криптоанализа к шифру.

Общая схема

В настоящее время симметричные шифры — это:

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

Результатом повторения раундов является лавинный эффект — нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.

 поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-86 в режиме гаммирования), запущенного в специальном режиме.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

Типичным способом построения алгоритмов симметричного шифрования является сеть Фейстеля. Алгоритм строит схему шифрования на основе функции F(D, K), где D — порция данных, размеров вдвое меньше блока шифрования, а K — «ключ прохода» для данного прохода. От функции не требуется обратимость — обратная ей функция может быть неизвестна. Достоинства сети Фейстеля — почти полное совпадение дешифровки с шифрованием (единственное отличие — обратный порядок «ключей прохода» в расписании), что сильно облегчает аппаратную реализацию.

Операция перестановки перемешивает биты сообщения по некоему закону. В аппаратных реализациях она тривиально реализуется как перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна — f(a) xor f(b) == f(a xor b)

Операции подстановки выполняются как замена значения некоей части сообщения (часто в 4, 6 или 8 бит) на стандартное, жестко встроенное в алгоритм иное число путем обращения к константному массиву. Операция подстановки привносит в алгоритм нелинейность.

Зачастую стойкость алгоритма, особенно к дифференциальному криптоанализу, зависит от выбора значений в таблицах подстановки (S-блоках). Как минимум считается нежелательным наличие неподвижных элементов S(x) = x, а также отсутствие влияния какого-то бита входного байта на какой-то бит результата — то есть случаи, когда бит результата одинаков для всех пар входных слов, отличающихся только в данном бите.

Параметры алгоритмов

Параметры:

 стойкость

 длина ключа

 число раундов

 длина обрабатываемого блока

 сложность аппаратной/программной реализации

SP-сеть и шифры Файстеля

Способ, которым следует сочетать принципы перемешивания и рассеивания для получения криптографической стойкости, можно описать следующим образом. Мы увидели, что перестановки общего вида не могут быть реализованы для больших значений n, скажем для n = 128, и поэтому мы должны ограничиваться схемами подстановки, имеющими подходящий размер… мы выбрали n = 4 в системе, разработанной в IBM и названной Lucifer. Хотя это может показаться слишком маленьким числом, такая подстановка может оказаться вполне эффективной, если ключ подстановки… выбран верно.Х. Файстель. Криптография и компьютерная безопасность.

Lucifer — проект фирмы IBM 70-х годов по созданию криптоустойчивого блочного шифра. В проекте участвовали, ставшие позднее известными криптографами Хорст Фейстель (англ. Horst Feistel) и Дон Копперсмит (англ. Don Coppersmith). Развития «Люцифера» привело к созданию алгоритма DES.

Первая версия алгоритма использовала блоки и ключи длиной по 48 бит и основывалась на SP-сетях. Последующая модификация алгоритма была запатентована в ноябре того же года (US Patent 3,796,830; Nov 1971), и использовала сеть Фейстеля. В патенте содержится как описание собственно самого алгоритма, так и сети Фейстеля. В этом шифре использовались 64-х разрядные ключи и 32-х битные блоки. И, наконец, последняя версия предложена в 1973 году и оперировала с 128-мибитными блоками и ключами.

Структура алгоритма Люцифер образца июня 1971 года представляет из себя «сендвич» из слоёв двух типов, используемыех по очереди - так называемые SP-сети(или подстановочно-перестановочная сеть). Первый тип слоя — P-блок разрядности 128 бит, за ним идёт второй слой, представляющий из себя 32 модуля, каждый из которых состоит их двух четырёхбитных S-блоков, чьи соответствующие входы закорочены и на них подаётся одно и то же значение с выхода предыдущего слоя. Но сами блоки подстановок различны (отличаются таблицами замен). На выход модуля подаются значения только с одного из S-блоков, какого конкретно определяется одним из битов в ключе, номер которого соответствовал номеру S-блока в структуре. Упрощённая схема алгоритма меньшей разрядности и неполным числом раундов приведена на рисунке. В ней используется 16 модулей выбора S-блоков(всего 32 S-блока), таким образом такая схема использует 16-битный ключ.

Рассмотрим теперь, как будет меняться шифротекст, в приведённом выше алгоритме, при изменении всего одного бита. Для простоты возьмём таблицы замен S-блоков такими, что если на вход S-блока подаются все нули, то и на выходе будут все нули. В силу нашего выбора S-блоков, если на вход шифрующего устройства подаются все нули, то и на выходе устройства будут все нули. В реальных системах такие таблицы замен не используются, так как они сильно упрощают работу криптоаналитика, но в нашем примере они наглядно иллюстрируют сильную межсимвольную взаимосвязь при изменении одного бита шифруемого сообщения. Видно, что благодаря первому P-блоку единственная единица сдвигается перемещается в центр блока, затем следующий нелинейный S-блок «размножает» её, и уже две единицы за счёт следующего P-блока изменяют своё положение и т.д. В конце устройства шифрования, благодаря сильной межсимвольной связи, выходные биты стали сложной функцией от входных и от используемого ключа. В среднем на выходе половина бит будет равна «0» и половина «1».

По своей сути сеть Фейстеля является альтернативой SP-сетям и используется намного шире. С теоретической точки зрения раундовая функция шифрования может быть сведена к SP-сети, однако сеть Фейстеля является более практичной, так как шифрование и дешифрование может вестись одним и тем же устройством, но с обратным порядком используемых ключей. Вторая и третья версия алгоритма(использующие сеть Фейстеля) оперировали над 32-битными блоками с 64-битным ключом и 128-битными блоками со 128-битными ключами. В последней(третьей) версии раундовая функция шифрования была устроена очень просто — сначала шифруемый подблок пропускался через слой 4-битных S-блоков(аналогично слоям в SP-сетях, только S-блок является константным и не зависит от ключа), затем к нему по модулю 2 добавлялся раундовый ключ, после чего результат пропускался через P-блок.

Файстель в своей статье представил способ организации шифра по Шеннону. Этот шифр обладал хорошими свойствами перемешивания и рассеивания. Для достижения вышеозначенного эффекта предлагалось использовать блоки подстановок и перестановок. Архитектура подобных шифров носит название SP-сети, от двух названий используемых в ней компонентов: S-box и P-box.

Данные представлялись в виде подблоков небольшого размера, например, в 3 или 4 бита. Затем использовалась заранее подготовленная таблица подстановки (например, рис. 4.4), названная Файстелем S-Box (от substitution – в английском языке обозначающего подстановку или замену) и окрещенная в русской терминологии S-блоком и узлом (иногда еще говорят, блоком) замены.

Подставляя значение входных данных в левую колонку таблицы, получаем соответствующее значение подстановки в правой колонке. Как в левой, так и в правой колонках все значения должны быть различны, иначе, заменив однажды данные в соответствии с таблицей, мы не сможем однозначно их восстановить позже.