Введение в основы современных шифров с симметричным ключом

Блочные шифры как групповые математические перестановки

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

Полноразмерные ключевые шифры

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

Полноразмерные ключевые блочные шифры транспозиции. Такой ключевой шифр перемещает биты, не изменяя их значения, так что может быть смоделирован как перестановка n -мерного объекта с множеством n! таблиц перестановки, в которых ключ определяет, какая таблица используется Алисой и Бобом. Мы должны иметь n! возможных ключей, и такой ключ должен иметь длину $$\left\lceil {{{\log }_2}n!} \right\rceil$$ бит.

Пример 7.3

Покажите модели и множество таблиц перестановки для блочного шифра транспозиции на 3 бита, где размер блока — 3 бита.

Решение

Множество таблиц перестановки имеет 3! = 6 элементов, как показано на рис. 7.2. Ключ должен быть длиной $$\left\lceil {{{\log }_2}n!} \right\rceil$$ = 3 бита. Заметим, что хотя ключ на 3 бита может выбрать 23 = 8 различных отображений, мы используем только 6 из них.

(рис 7.2) Блочный шифр транспозиции в виде перестановки

Полноразмерные ключевые блочные шифры подстановки.Такие шифры не перемещают биты — они заменяют биты. На первый взгляд кажется, что полноразмерный ключевой шифр подстановки не может быть смоделирован как перестановка. Однако мы можем применить модель перестановки для шифра подстановки, если сможем декодировать входную информацию и кодировать выходную. Декодирование здесь означает преобразование n -разрядного целого числа в строку 2n -бит с единственной единицей 1 и 2n–1 нулями. Позиция единственной единицы указывает значение целого числа в упорядоченной последовательности позиций строки от 0 до 2n – 1. Поскольку новая входная информация имеет всегда единственную единицу, шифр может быть смоделирован как перестановка 2n! объектов.

Пример 7.4

Покажите модель и множество таблиц перестановки для шифра подстановки блока на 3 бита.

Решение

Три входных исходных текста могут быть обозначены целыми числами от 0 до 7. Это может быть закодировано как строка, содержащая 8 битов с единственной единицей. Например, комбинация 000 может быть закодирована как 00000001 (первая единица справа); комбинация 101 может быть закодирована как 00100000 (шестая единица справа). Рисунок 7.3 показывает модель и множество таблиц перестановки. Заметим, что число элементов в закодированном множестве намного больше, чем число элементов в шифре транспозиции (8! = 40 320). Ключ — также намного более длинный $$\left\lceil {{{\log }_2}40320} \right\rceil = 16$$ бит. Хотя ключ на 16 битов может определить 65 536 различных отображений, используются только 40 320.

(рис 7.3) Блочный шифр подстановки моделируется как шифр перестановки Полноразмерный ключ — это n -разрядный шифр транспозиции или блочный шифр подстановки. Они могут быть смоделированы как шифры перестановки, но размеры их ключа различны: для шифра транспозиции ключ длиной — .

Групповая перестановка. Факт, что полноразмерная ключевая транспозиция или шифр подстановки/перестановки показывает, что если шифрование (или дешифрование) использует больше чем одну любую комбинацию из этих шифров, результат эквивалентен операции групповой перестановки. Как уже обсуждалось в лекциях 5-6, две или больше каскадных перестановки могут всегда быть заменены единственной перестановкой. Это означает, что бесполезно иметь $${2^{{2^{70}}}}$$ больше чем один каскад полноразмерных ключевых шифров, потому что эффект тот же самый, как и при наличии единственного шага.

Шифры ключа частичного размера

Фактические шифры не могут использовать полноразмерные ключи, потому что размер ключа становится несуразно большим, особенно для блочного шифра подстановки. Например, общий шифр подстановки – DES — (см. лекцию 11) применяет 64 -разрядный блочный шифр. Если бы проектировщики DES использовали полноразмерный ключ, он был бы $${\log _2}\left( {{2^{64}}!} \right){\text{ }} = {\text{ }}{2^{70}}$$ битов. На практике ключ для DES — только 56 битов, что является очень маленьким фрагментом полноразмерного ключа. Это означает, что DES использует только 256 отображений из приблизительно $${2^{{2^{70}}}}$$ возможных отображений.

Группа перестановки. Зададим себе вопрос: можно ли установить, что многоступенчатая транспозиция с частичным ключом или подстановка — это группа перестановки с композицией операций? Ответ на этот вопрос чрезвычайно важен, потому что он говорит нам о том, является ли многоступенчатая версия с частичным шифром таким же средством шифрования, как и сам шифр. Этот факт позволяет достигнуть большей степени безопасности (см. обсуждение многократной DES в лекции 11).

Частичный ключевой шифр – это группа, если это — подгруппа соответствующего размера ключа шифра. Другими словами, если полноразмерный ключевой шифр — это группа G = <M, o>, где М. — множество отображений и (o) — композиция операций, то шифр с ключом частичного размера должен представлять подгруппу H = <N, o>, где N — подмножество М с теми же самыми операциями.

Например, было доказано, что многоступенчатый DES с 56 -битовым ключом не является группой, потому что подгруппа с 256 отображениями не может быть создана из группы с 264! отображениями.

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

Шифры без ключа

Хотя использование отдельно шифра без ключа фактически бесполезно, возможно их применение в качестве компонентов ключевых шифров,

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

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

Компоненты современного блочного шифра

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

P -блок (блок перестановки) подобен традиционному шифру транспозиции символов. Он перемещает биты. В современных блочных шифрах мы можем найти три типа P -блоков: прямые P -блоки, P -блоки расширения и P -блоки сжатия, что и показано на рис. 7.4.

(рис 7.4) Три типа P-блоков

Рисунок 7.4 показывает прямой P -блок $$5 \times 5$$, P -блок сжатия $$5 \times 3$$ и P -блок расширения $$3 \times 5$$. Рассмотрим каждый из них более подробно.

Прямые P-блоки.Прямой P -блок с n входами и n выходами – это перестановка с n! возможными отображениями.

Пример 7.5

Рисунок 7.5 показывает все 6 возможных отображений P -блока $$3 \times 3$$.

(рис 7.5) Возможные отображения P-блока 3x3

Хотя P -блок может использовать ключ, чтобы определить одно из n! отображений, обычно P -блоки – без применения ключа, то есть отображение задано заранее. Если P -блок задан заранее и замонтирован в аппаратных средствах или если он реализован в программном обеспечении, таблицы перестановок задают правило отображения. Во втором случае входы в таблице указывают в позиции, в которых указаны позиции выходов. Таблица 7.1 дает пример таблицы перестановок, когда n равно 64.

Пример таблицы перестановки для прямого P-блока

58	50	42	34	26	18	10	02	60	52	44	36	28	20	12	04
62	54	46	38	30	22	14	06	64	56	48	40	32	24	16	08
57	49	41	33	25	17	09	01	59	51	43	35	27	19	11	03
61	53	45	37	29	21	13	05	63	55	47	39	31	23	15	07

Таблица 7.1 имеет 64 табличных входа, которые фиксируют соответствие 64 информационным входам. Позиция (индекс) входа соответствует выходу. Например, первый табличный вход содержит номер 58. Это означает, что первый выход будет соответствовать 58 -му входу. Поскольку последний табличный вход — 7, это означает, что, 64 -й выход будет соответствовать седьмому информационному входу, и так далее.

Пример 7.6

Составьте таблицу перестановки для прямого P -блока 8 x 8, которая перемещает два средних бита (биты 4 и 5 ) во входном слове к двум крайним битам (биты 1 и 8 ) выходного слова. Относительные позиции других битов не изменяются.

Решение

Нам надо создать прямой P -блок с таблицей [4 1 2 3 6 7 8 5]. Относительные позиции бит 1, 2, 3, 6, 7 и 8 не меняются, но первый информационный выход связан с четвертым информационным входом, восьмой информационный выход — с пятым информационным входом.

P-блоки сжатия. P -блок сжатия – это P -блок с n входами и m выходами, где m <n. Некоторые из информационных входов блокированы и не связаны с выходом (см. рисунок 7.4). P -блоки сжатия, используемые в современных блочных шифрах, обычно являются безключевыми с таблицей перестановки, которая указывает правила перестановки бит. Нам надо учитывать, что таблица перестановок для P -блока сжатия имеет m табличных входов, но в содержании каждого табличного входа – от 1 до n, и некоторые из них могут отсутствовать (те информационные входы, которые блокированы). Таблица 7.2 показывает пример таблицы перестановки для P -блока сжатия $$32 \times 24$$. Обратите внимание, что входы 7, 8, 9, 16, 23, 24 и 25 блокированы.

Пример таблицы перестановки 32х24

01	02	03	21	22	26	27	28	29	13	14	17
18	19	20	04	05	06	10	11	12	30	31	32

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

P-блок расширения — P -блок с n входами и m выходами, где m> n. Некоторые из входов связаны больше чем с одним выходом (см. рис. 7.4). P -блоки расширения, используемые в современных блочных шифрах, обычно без ключа. Правила перестановки бит указываются в таблице. Таблица перестановки для P -блока расширения имеет m табличных входов, но m – n входов (те входы, которые связаны больше чем с одним информационным выходом). Таблица 7.3 показывает пример таблицы перестановки для P -блока расширения 12 16. Обратите внимание, что каждый из 1, 3, 9 и 12 соединен с двумя выходами.

Пример таблиц перестановки 12х16

01

09

10

11

12

01

02

03

03

04

05

06

07

08

09

12

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

Обратимость.Прямой P -блок является обратимым. Это означает, что мы можем использовать прямой P -битовый шифр и дешифровать его. Таблицы перестановки, однако, должны быть обратимыми по отношению друг к другу. В лекциях 5-6 мы видели, как можно получить обратную таблицу перестановки.

Пример 7.7

Рисунок 7.6 показывает, как изменить таблицу перестановки в случае одномерной таблицы.

(рис 7.6) Изменение таблицы перестановки

P -блоки сжатия и расширения необратимы. В P -блоках сжатия вход может быть отброшен в процессе шифрования; алгоритм дешифрования не имеет ключа, чтобы восстановить отброшенный бит. В P -блоке расширения вход в процессе шифрования может быть отображен более чем в один выход; алгоритм дешифрования не имеет ключа и не определяет тем самым, какие из нескольких входов отображены в данном выходе. Рисунок 7.7 демонстрирует оба случая.

(рис 7.7) P-блоки сжатия и расширения как необратимые компоненты

Рисунок 7.7 также показывает, что P -блок сжатия не является обратным шифром P -блока расширения и наоборот. Это означает, что если мы используем P -блок сжатия для шифрования, мы не сможем использовать P -блок расширения для дешифрования и наоборот. Однако, как будет показано позже в этой лекции, есть шифры, которые применяют P -блоки сжатия или расширения для шифрования; но их эффективность хуже, чем у некоторых других способов.

Прямой P -блок является обратимым, а P -блоки сжатия и расширения — нет.

S-блоки

S-блок (блок подстановки) можно представить себе как миниатюрный шифр подстановки. Этот блок может иметь различное число входов и выходов. Другими словами, вход к S -блоку может быть n -битовым словом, а выход может быть m разрядным словом, где m и n — не обязательно одинаковые числа. Хотя S -блок может быть ключевым или без ключа, современные блочные шифры обычно используют S -блоки без ключей, где отображение от информационных входов к информационным выходам заранее определено.

S -блок — m x n модуль подстановки, где m и n не обязательно равны.

Линейный и нелинейный S-блоки. В S -блоке с n входами и m выходами мы обозначим входы x0, x1,…., xn и выходы y1 ,..., ym. Соотношения между входами и выходами могут быть представлены как система уравнений

y1 = f1 (x1,x2,…,xn)

y2 = f2 (x1,x2,…,xn)

….

ym = fm (x1,x2,…,xn)

В линейном S-блоке вышеупомянутые соотношения могут быть выражены как

$$y_{1} = a_{1,1}x_{1} \oplus a_{1,2}x_{2} \oplus \dots \oplus a_{1,n}x_{n} \\ y_{2} = a_{2,1}x_{1} \oplus a_{2,2}x_{2} \oplus \dots \oplus a_{2,n}x_{n} \\ \dots \\ y_{m} = a_{m,1}x_{1} \oplus a_{m,2}x_{2} \oplus \dots \oplus a_{m,n}x_{n}$$

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

Пример 7.8

В S -блоке с тремя входами и двумя выходами мы имеем

$$y_{1} = x_{1} \oplus x_{2} \oplus x_{3} y_{2} = x_{1}$$

S -блок линеен, потому что a1,1 = a1,2 = a1,3 = a2,1=1 и a2 ,2 = a2 ,3 = 0. Эти соотношения могут быть представлены матрицами, как показано ниже:

$$\left( \begin{array}{c} y_{1} \\ y_{2} \end{array} \right) = \left( \begin{array}{c} 111 \\ 100 \end{array} \right) \times \left( \begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \end{array} \right)$$

Пример 7.9

В S -блоке с тремя входами и двумя выходами мы имеем

y1 = (x1)3 + x2    y2  = (x1) + x1x2 + x3

где умножение и сложение проводится в GF(2). S -блок нелинеен, потому что нет линейных соотношений между входами и выходами.

Пример 7.10

Следующая таблица определяет отношения между входами/выходами для S -блока размера $$3 \times 2$$. Крайний левый бит входа определяет строку; два самых правых бита входа определяют столбец. Два бита выхода – это значение на пересечении секции выбранной строки и столбца.

Обратимость. S -блоки — шифры подстановки, в которых отношения между входом и выходом определены таблицей или математическим соотношением. S -блок может быть или может не быть обратимым. В обратимом S -блоке число входных битов должно быть равным числу бит выхода.

Пример 7.11

Рисунок 7.8 показывает пример обратимого S -блока. Одна из таблиц используется в алгоритме шифрования; другая таблица — в алгоритме дешифрования. В каждой таблице крайний левый бит входа определяет строку; следующие два бита определяют столбец. Выход — это значение на пересечении строки и столбца.

Например, если вход к левому блоку — 001, выход — 101. Вход 101 в правой таблице дает выход 001. Это показывает, что эти две таблицы позволяют получить обратный результат по отношению друг к другу.

Исключающее или

Важный компонент в большинстве блоков шифрования — операция ИСКЛЮЧАЮЩЕЕ ИЛИ: Как мы уже обсуждали в лекции 7, операции сложения и вычитания в GF(2n) выполняется с помощью одной и той же операции, называемой ИСКЛЮЧАЮЩЕЕ ИЛИ или ( XOR ):

(рис 7.8) Таблицы S-блока для примера 7.11

Свойства. Пять свойств операции ИСКЛЮЧАЮЩЕЕ ИЛИ в поле GF(2n) делают эту операцию очень удобной для использования в блочном шифре.

1. Замкнутость. Это свойство гарантирует, что в результате этой операции два n -битовых слова дают другое n -битовое слово.

2. Ассоциативность. Это свойство позволяет нам использовать больше чем одно ИСКЛЮЧАЮЩЕЕ ИЛИ, которые можно вычислять в любом порядке.

$$x \oplus (y \oplus z) \leftrightarrow (x \oplus y) \oplus z$$

3. Коммутативность. Это свойство позволяет нам менять местами операторы (входную информацию), не изменяя результат (выходную информацию).

$$x \oplus y \leftrightarrow y \oplus x$$

4. Существование нулевого (тождественного) элемента. Нулевой элемент для операции ИСКЛЮЧАЮЩЕЕ ИЛИ – слово, которое состоит из всех нулей, или (00... 0). Это подразумевает, что существует слово с нейтральными элементами, которое при проведении операции не изменяет слово.

$$x \oplus (00….00) = x$$

Мы используем это свойство в шифре Файстеля, который рассмотрим позже в этой лекции.

5. Существование инверсии. В поле GF(2n) каждое слово есть аддитивная инверсия самого себя. Это подразумевает, что проведение операции ИСКЛЮЧАЮЩЕЕ ИЛИ слова с самим собой приводит к нулевому элементу:

$$x \oplus x = (00\dots 0)$$

Мы также используем это свойство в шифре Файстеля, который рассмотрим позже в этой лекции.

Дополнение. Операция дополнения — одноместная операция (один информационный вход и один информационный выход), которая инвертирует каждый бит в слове. 0 -вой бит меняет на 1 (единичный) бит; 1 (единичный) бит меняет на 0 -вой бит. Нас интересует операции с дополнением относительно операции ИСКЛЮЧАЮЩЕЕ ИЛИ. Если $$\bar x$$ — дополнение "x", тогда верны следующие два соотношения:

$$x \oplus \bar x = (11 \ldots 1)$$ и $$x \oplus (11 \ldots 1) = \bar x$$

Мы также используем эти свойства позже в этой лекции, когда будем обсуждать безопасность некоторых шифров.

Инверсия. Инверсия компонента в шифре имеет смысл, если компонент представляет одноместную операцию (один вход и один выход). Например, P -блок без ключа или S -блок без ключа могут быть обратимыми, потому что они имеют один вход и один выход. Операция ИСКЛЮЧАЮЩЕЕ ИЛИ — бинарная операция. Инверсия операции ИСКЛЮЧАЮЩЕЕ ИЛИ может иметь смысл, только если один из входов зафиксирован (один и тот же при шифровании и дешифровании). Например, если один из входов — ключ, который обычно является одним и тем же в шифровании и дешифровании, тогда операция ИСКЛЮЧАЮЩЕЕ ИЛИ является обратимой, как показано на рис. 7.9.

(рис 7.9) Обратимость операции ИСКЛЮЧАЮЩЕЕ ИЛИ

На рисунке 7.9 свойство аддитивной инверсии подразумевает, что

$$y = x \oplus k x = k \oplus y$$

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

Циклический сдвиг

Другой компонент, применяемый в некоторых современных блочных шифрах, – операция циклического сдвига. Смещение может быть влево или вправо. Круговая операция левого сдвига сдвигает каждый бит в n -битовом слове на k позиции влево; крайние левые k -биты удаляются слева и становятся самыми правыми битами. Круговая операция правого сдвига сдвигает каждый бит в n -битовом слове на k позиций вправо; самые правые k -биты справа удаляются и становятся крайними левыми битами. Рисунок 7.10 показывает и левые и правые операции в случае, где n = 8 и k = 3.

Циклическая операция сдвига смешивает биты в слове и помогает скрыть образцы в первоначальном слове. Хотя число позиций, на которые биты будут сдвинуты, может использоваться как ключ, циклическая операция сдвига обычно – без ключа; значение k устанавливается и задается заранее.

Обратимость. Циклическая операция левого сдвига – инверсия операции правого сдвига. Если одна из них используется для шифрования, другая может применяться для дешифрования.

Свойства. Операция циклического сдвига имеет два свойства, которые нам надо знать.

Первая — это смещение по модулю n. Другими словами, если k = 0 или k = n, никакого смещения не происходит. Если k является большим, чем n, тогда входная информация сдвинута на k mod n бит. Второе свойство, операция циклического сдвига над соединением операций - есть группа. Это означает, что если смещение делается неоднократно, то одно и то же значение может появиться несколько раз..

(рис 7.10) Циклический сдвига 8 битового слова налево или направо

Замена

Операция замены — специальный случай операции циклического сдвига, где k = n/2 означает, что эта операция возможна, только если n — четный номер. Поскольку сдвиг влево n/2 — то же самое, что сдвиг n/2 вправо, эта операция является обратимой. Операция замены для шифрования может быть полностью раскрыта операцией замены для дешифрации. Рисунок 7.11 иллюстрируетт операцию замены для слова на 8 битов.

(рис 7.11) Операция замена в 8 битовом а слове

Разбиение и объединение

Две других операции, применяемые в некоторых блочных шифрах, — разбиение и объединение. Разбиение обычно разделяет n -битовое слово в середине, создавая два слова равной длины. Объединение связывает два слова равной длины, чтобы создать n -битовое слово. Эти две операции инверсны друг другу и могут использоваться как пара, чтобы уравновесить друг друга. Если одна используется для шифрования, то другая — для дешифрования. Рисунок 7.12 показывает эти две операции для случая n = 8.

Составные шифры

Шеннон ввел понятие составные шифры. Составной шифр – комплекс, который объединяет подстановку, перестановку и другие компоненты, рассмотренные в предыдущих разделах.

(рис 7.12) Операции разбиение и объединения с 8 - битовым словом

Рассеивание и перемешивание

Идея Шеннона в представлении составного шифра должна была дать возможность блочным шифрам иметь две важных свойства: рассеяние и перемешивание. Рассеивание должно скрыть отношения между зашифрованным текстом и исходным текстом. Это собьет с толку противника, который использует статистику зашифрованного текста, чтобы найти исходный текст. Рассеивание подразумевает, что каждый символ (символ или бит) в зашифрованном тексте зависит от одного или всех символов в исходном тексте. Другими словами, если единственный символ в исходном тексте изменен, несколько или все символы в зашифрованном тексте будут также изменены.

Рассеивание скрывает отношения между зашифрованным текстом и исходным текстом.

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

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

Раунды

Распыление и перемешивание могут быть достигнуты использованием повторения составных шифров, где каждая итерация — комбинация S -блоков, P -блоков и других компонентов. Каждая итерация называется раундом.Блочный шифр использует ключевой список,или генератор ключей, который создает различные ключи для каждого раунда от ключа шифра. В N -раундном шифре, чтобы создать зашифрованный текст, исходный текст шифруется N раз; соответственно, зашифрованный текст расшифровывается N раз. Текст, созданный на промежуточных уровнях (между двумя раундами), называется средним текстом.Рисунок 7.13 показывает простой составной шифр с двумя раундами. На практике составные шифры имеют больше чем два раунда. На рис. 7.13 в каждом раунде проводятся три преобразования:

а. 8 -битовый текст смешивается с ключом, чтобы сделать символы текста равновероятными (скрыть биты, используя ключ) — "отбелить" текст (whiting). Это обычно делается с помощью операции ИСКЛЮЧАЮЩЕЕ ИЛИ слова на 8 битов с ключом на 8 битов.

б. Выходы "отбеливателя" разбиты на четыре группы по 2 бита и подаются в четыре S -блока. Значения битов изменяются в соответствии с построением S -блоков в этом преобразовании.

c. Выходы S -блоков поступают в P -блок, при этом биты переставлены так, чтобы в следующем раунде результат каждого блока поступил на различные входы.

(рис 7.13) Составнной шифр, состоящий из двух раундов

Рассеивание, которое показано на упрощенном рис. 7.13 как составной шифр, используя комбинацию S -блоков и P -блоков, может гарантировать рассеивание.

а. В первом раунде бит 8, после проведения операции ИСКЛЮЧАЮЩЕЕ ИЛИ с соответствующими битами ключа K1, изменяет два бита (биты 7 и 8 ) через S -блок 4. Бит 7 переставлен и становится битом 2 ; бит 8 переставлен и становится битом 4. После первого раунда бит 8 изменяет биты 2 и 4. Во втором раунде бит 2 после проведения операции ИСКЛЮЧАЮЩЕЕ ИЛИ с соответствующими битами ключа K2 изменяет два бита (биты 1 и 2 ) через S -блок 1. Бит 1 – переставлен и становится битом 6 ; бит 2 переставлен и становится битом 1. Бит 4 после проведения операции ИСКЛЮЧАЮЩЕЕ ИЛИ с соответствующим битом в K2 изменяет биты 3 и 4. Бит 3 остается, бит 4 переставлен и становится битом 7. После второго раунда из 8 бит изменены биты 1, 3, 6 и 7.

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

Перемешивание. На рисунке 7.14 показано, как изменение единственного бита в исходном тексте вызывает изменение многих битов в зашифрованном тексте. Рисунок 7.14 также доказывает нам, что свойство перемешивания может быть получено с помощью составного шифра. Четыре бита зашифрованного текста, биты 1, 3, 6 и 7 преобразованы с помощью трех битов в ключах (бит 8 в K1 и битах 2 и 4 в K2 ). Прохождение в обратном направлении показывает, что каждый бит ключа в каждом раунде затрагивает несколько битов в зашифрованном тексте. Отношения между битами зашифрованного текста и ключевыми битами показаны в затененных прямоугольниках.

(рис 7.14) Рассеивание и перемешивание в блочном шифре

Практические шифры. Чтобы улучшить рассеивание и перемешивание, практические шифры используют крупные блоки данных, больше S -блоков и больше раундов. Очевидно, что некоторое увеличение числа раундов при использовании большого числа S -блоков может создать лучший шифр, в котором зашифрованный текст выглядит все более как случайное n -битовое слово. Таким образом, отношения между зашифрованным текстом и исходным текстом будут полностью скрыты (рассеяны). Увеличение числа раундов увеличивает число ключей раундов, что лучше скрывает отношения между зашифрованным текстом и ключом.

Два класса составных шифров

Современные блочные шифры — все составные, но они разделены на два класса. Шифры в первом классе используют и обратимые, и необратимые компоненты. Эти шифры упоминаются обычно как шифры Файстеля. Блочный шифр DES (DATA ENCRYPTION STANDARD), обсуждаемый в лекции 11, — хороший пример шифра Файстеля. Шифры во втором классе применяют только обратимые компоненты. Обращаем ваше внимание на шифры в этом классе как шифры не-Файстеля (из-за отсутствия другого названия). Блочный шифр AES (ADVANCED ENCRYPTION STANDARD), обсуждаемый в лекциях 12-13, — хороший пример шифра не-Файстеля.

Шифры Файстеля

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

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

Первая идея. Чтобы лучше понять шифр Файстеля, давайте посмотрим, как мы можем использовать один и тот же необратимый компонент в алгоритмах дешифрования и шифрования. Эффекты необратимого компонента в алгоритме шифрования могут быть отменены в алгоритме дешифрования, если мы используем операцию ИСКЛЮЧАЮЩЕЕ ИЛИ, как показано на рис. 7.15.

(рис 7.15) Первая идея в разработке шифра Файстеля

В шифровании ключ поступает на вход необратимой функции f (K), которая является одним из слагаемых оператора ИСКЛЮЧАЮЩЕГО ИЛИ с исходным текстом. Результат становится зашифрованным текстом. Мы будем называть комбинацию функции и операции ИСКЛЮЧАЮЩЕЕ ИЛИ смесителем (из-за отсутствия другого названия). Смеситель играет важную роль в более поздних вариантах шифра Файстеля.

Поскольку ключ один и тот же в шифровании и дешифровании, мы можем доказать, что два алгоритма инверсны друг другу. Другими словами, если C2 = C1 (любое изменение в зашифрованном тексте в течение передачи), то P2 = P1.

$$Шифрование: C_{1} = P_{1} \oplus f(K) \\ Дешифрование: P_{2} = C_{2} \oplus f (K) = C_{1} \oplus f (K) = P_{1} \oplus f (K) \oplus f (K) = P_{1} \oplus (00\dots 0) = P_{1}$$

Обратите внимание, что использовались два свойства операции ИСКЛЮЧАЮЩЕЕ ИЛИ (существование инверсии и существование нулевого кода).

Уравнения, показанные выше, доказывают, что хотя смеситель имеет неконвертируемый элемент, сам смеситель является самоконвертируемым.

Пример 7.12

Это тривиальный пример. Имеется исходный текст и зашифрованный текст, каждый 4 бита длиной, и ключ 3 бита длиной. Предположим, что функция извлекает первый и третий биты ключа, интерпретирует биты как десятичный номер, находит квадрат этого числа и интерпретирует результат как 4 -битовую двоичную последовательность. Покажите результаты шифрования и дешифрования, если первоначальный исходный текст — 0111, и ключ — 101.

Решение

Функция извлекает первые и третьи биты ключа и получается в результате 11 в двоичном виде или 3 в десятичном отображении. Результат возведения во вторую степень (квадрат) — 9, в двоичном отображении 1001.

$$Шифрование: C = P \oplus f (K) = 0111 \oplus 1001 = 1110 \\ Дешифрование: P = C \oplus f (K) = 1110 \oplus 1001 = 0111.\ Совпадет\ с\ исходным\ текстом\ P$$

Функция f (101) = 1001 является неконвертируемой, но операция ИСКЛЮЧАЮЩЕЕ ИЛИ позволяет нам использовать функцию и в алгоритмах дешифрования, и в шифровании. Другими словами, функция является неконвертируемой, но смеситель будет самоконвертируемым.

Усовершенствование. Попробуем улучшить нашу первую идею, чтобы приблизиться к шифру Файстеля. Мы знаем, что должны применить вход к неконвертируемому элементу (функции), но мы не будем использовать только ключ. Мы задействуем также вход к функции, чтобы применить ее для шифрования части исходного текста и дешифрования части зашифрованного текста. Ключ может использоваться как второй вход к функции. Этим способом наша функция становится сложным элементом с некоторыми неключевыми элементами и некоторыми ключевыми элементами. Чтобы достичь цели, разделим исходный текст и зашифрованный текст на два блока равной длины – левый ( L ) и правый ( R ). Правый блок вводится в функцию, а левый блок складывается с помощью операции ИСКЛЮЧАЮЩЕЕ ИЛИ с выходом функции. Мы должны запомнить, что входы к функции должны точно совпадать в шифровании и дешифровании. Это означает, что правая секция исходного текста до шифрования и правая секция зашифрованного текста после дешифрования будут совпадать. Другими словами, секция должна войти в шифрование и выйти из дешифрования неизмененной. Рисунок 7.16 иллюстрирует идею.

(рис 7.16) Усовершенствование предыдущей схемы Файстеля

Алгоритмы шифрование и дешифрования инверсны друг другу. Предположим, что L3 = L2 и R3 = R2 (в зашифрованном тексте в течение передачи не произошло изменений).

$$R_{4} = R_{3} = R_{2} = R_{1}\\ L_{4} = L_{3} \oplus f(R_{3},K) = L_{2} \oplus f(R_{2},K) = L_{1} \oplus f(R_{1},K) \oplus f (R_{1},K) = L_{1}$$

Исходный текст, используемый в алгоритме шифрования, — это текст, правильно восстановленный алгоритмом дешифрования.

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

Первое: увеличим число раундов. Второе: добавим новый элемент в каждый раунд — устройство замены. Эффект устройства замены в раунде шифрования компенсируется эффектом устройства замены в раунде дешифрования. Однако это позволяет нам менять левые и правые половины в каждом раунде. Рисунок 7.17 иллюстрирует новый вариант шифра Файстеля с двумя раундами.

(рис 7.17) Окончательный вариант шифра Файстеля с двумя раундами

Обратите внимание, что есть два ключа раундов: K1 и K2. Ключи используются в обратном порядке в шифровании и дешифровании.

Поскольку два смесителя инверсны друг другу и устройства замены инверсны друг другу, очевидно, что шифрование и дешифрование также инверсны друг другу. Однако мы можем доказать этот факт, используя отношения между левыми и правыми секциями в каждом шифре. Другими словами, если L6 = L1 и R6 = R1, предположим, что L4 = L3 и R4 = R3 (шифрованный текст не изменился при передаче). Вначале докажем это для промежуточного текста:

$$L_{5} = R_{4} \oplus f(L_{4}, K_{2}) = R_{3} \oplus f(R_{2}, K_{2}) = L_{2} \oplus f(R_{2}, K_{2}) \oplus f(R_{2}, K_{2}) = L_{2} \\ R_{5} = L_{4} = L_{3} = R_{2}$$

Тогда просто доказать равенство для двух блоков исходного текста.

$$L_{6} = R_{5} \oplus f(L_{5}, K_{1}) = R_{2} \oplus f(L_{2}, K_{1}) = L_{1} \oplus f(R_{1}, K_{1}) \oplus f(R_{1}, K_{1}) = L_{1} \\ R_{6} = L_{5} = L_{2} = R_{1}$$

Шифры не-Файстеля

Шифр не-Файстеля использует только обратимые компоненты. Компонент в исходном тексте имеет соответствующий компонент в шифре. Например, S -блоки должны иметь равное число входов и выходов, чтобы быть совместимыми. Не позволяется никакое сжатие или расширение P -блоков, потому что они станут необратимыми. В шифре не-Файстеля нет потребности делить исходный текст на две половины, как мы видели в шифрах Файстеля.

Рисунок 7.13 можно рассматривать как графическую иллюстрацию принципа шифра не-Файстеля, потому что единственные компоненты в каждом раунде — самообратимые операции ИСКЛЮЧАЮЩЕЕ ИЛИ, S -блоки $$2 \times 2$$, которые могут спроектированы, чтобы быть обратимыми, и прямые P -блоки, которые обратимы, если использована соответствующая таблица перестановки. Поскольку каждый компонент является обратимым, то можно показать, что и каждый раунд является обратимым. Мы только должны применять ключи раундов в обратном порядке. Шифрование использует ключи раундов K1 и K2. Алгоритм дешифрования должен пользоваться ключами раундов K2 и K1.

Атаки на блочные шифры

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

Дифференциальный криптоанализ

Идею относительно дифференциального криптоанализа предложили Эли Бихам и Ади Шамир. Это — атака с выборкой исходного текста. Ева может каким-либо образом получить доступ к компьютеру Алисы и завладеть выборочно частью исходного текста и соответствующего зашифрованного текста. Цель состоит в том, чтобы найти ключ шифра Алисы.

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

Предположим, что шифр состоит только из одной операции ИСКЛЮЧАЮЩЕЕ ИЛИ, как показано на рис. 7.18. Не зная значения ключа, Ева может легко найти отношения между разностями исходного текста и разностями зашифрованного текста. Если разность исходного текста мы обозначим $$P_{1}\oplus P_{2}$$ и разность зашифрованного текста мы обозначим $$C_{1}\oplus C_{2}$$, приведенные следующие преобразования доказывают, что $$C_{1}\oplus C_{2} = P_{1}\oplus P_{2}$$:

$$C_{1} = P_{1} \oplus K C_{2} = P_{2} \oplus K \to C_{1} \oplus C_{2} = P_{1} \oplus K \oplus P_{2} \oplus K = P_{1} \oplus P_{2}$$

Однако этот пример нереалистичен; модемные блочные шифры не настолько просты.

(рис 7.18) Диаграмма для примера 7.13

В примере 7.13 мы добавляем один S -блок, как показано на рис. 7.19.

(рис 7.19) Диаграмма для примера 7.14

Хотя эффект шифрования ключом не действует, когда мы используем разности между двумя X и двумя P $$(X_{1}\oplus X_{2} = P_{1}\oplus P_{2})$$, существование S -блока мешает Еве найти и определенные отношения между разностями исходного текста и разностями зашифрованного текста. Однако возможно установить вероятностные отношения. Ева может составить таблицу 7.4, которая показывает для разности исходного текста, сколько можно создать разностей зашифрованного текста — шифр. Обращаем внимание, что таблица сделана по информации, которая произведенеа с учетом таблицы входа-выхода S -блока по рис. 7.19, потому что $$P_{1}\oplus P_{2} = X_{1}\oplus X_{2}.$$

Дифференциальная таблица для входов и выходов для шифра в примере 7.14

	C1 $$\oplus$$ C2
P1 $$\oplus$$ P2		00	01	10	11
	000	8
	001	2	2		4
	010	2	2	4
	011		4	2	2
	100	2	2	4
	101		4	2	2
	110	4		2	2
	111			2	6

Поскольку размер ключей — 3 бита, может быть восемь случаев для каждой разности во вводе. Таблица показывает, что если входная разность — (000) 2, разность выхода — всегда (00) 2. С другой стороны, таблица показывает, что если входная разность — (100) 2, то имеется два случая разностей выхода (00)2, два случая разностей выхода (01)2 и четыре случая разностей выхода (01)2.

Пример 7.15

Эвристический результат примера 7.14 может создать вероятностную информацию для Евы, как показано в таблице 7.5. Входы в таблице соответствуют вероятностям появления. Разности с нулевой вероятностью никогда не будут возникать.

Дифференциальная таблица для входов и выходов для шифра в примере 7.15

	00	01	10	11
000	1	0	0	0
001	0,25	0,25	0	0,50
010	0,25	0,25	0,50	0
011	0	0,50	0,25	0,25
100	0,25	0,25	0,50	0
101	0	0,50	0,25	0,25
110	0,50	0	0,25	0,25
111	0	0	0,25	0,75

Как мы увидим позже, Ева теперь располагает достаточным количеством информации, чтобы начать ее атаку. Таблица показывает, что вероятности распределены неоднородно из-за слабости в структуре S -блока. Таблица 7.5 упоминается иногда как дифференциальная таблица распределения или профайл ИСКЛЮЧАЮЩЕЕ ИЛИ.

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

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

Пример 7.16

Рассматривая таблицу 7.5, Ева знает, что если $$P_{1}\oplus P_{2}= 001$$, то $$C_{1}\oplus C_{2}= 11$$ с вероятностью 0,50 ( 50 процентов). Она пробует взять C1 = 00 и получает P1 = 010 (атака с выборкой зашифрованного текста). Она еще пробует C2 = 11 и получает P2 = 011 (другая атака с выборкой зашифрованного текста). Теперь она пробует вернуться к анализу, основанному на первой паре, P1 и C1:

$$С_{1} = 00 \to X_{1}= 001\ или\ X_{1}= 111 \\ Если\ X_{1}= 001 \to K = X_{1} \oplus P_{1} =011. \to Если\ X_{1}= 111 \to K = X_{1} \oplus P_{1} = 101$$

Используя пару P2 и C2, получим

$$С_{2} = 11 \to X_{2} = 000\ или\ X_{1} = 110 \\ Если\ X_{2} = 000 \to K = X2 \oplus P2 = 011 \to Если\ X_{12} = 110 \to K = X2 \oplus P2 = 101$$

Два испытания показывают, что K = 011 или K =101. Хотя Ева не уверена, какое из них точное значение ключа, она знает, что самый правый бит — 1 (общий бит между двумя значениями). Продолжая атаку, можно учитывать, что самый правый бит в ключе – 1. Таким образом можно определить другие биты в этом ключе.

Общая процедура. Современные блочные шифры имеют большую сложность, чем, та, которую мы обсуждали в этом разделе. Кроме того, они могут содержать различное количество раундов. Ева может использовать следующую стратегию:

Поскольку каждый раунд содержит одни и те же операции, Ева может создать таблицу дифференциальных распределений (профайл ИСКЛЮЧАЮЩЕГО ИЛИ) для каждого S -блока и комбинировать их, чтобы создать распределение для каждого раунда.

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

Ева может теперь делать список исходных текстов для атак, основанных на таблице распределений на втором шаге. Заметим, что таблица в шаге 2 только помогает Еве выбирать меньшее количество пар "исходный текст / зашифрованный текст"

Ева выбирает зашифрованный текст и находит соответствующий исходный текст. Затем она анализирует результат, чтобы найти некоторые биты в ключе.

Ева повторяет шаг 4, чтобы найти больше битов в ключе.

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

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

Линейный криптоанализ

Линейный криптоанализ был представлен Митцури Мацуи (Mitsuru Matsui) в 1993 году. Анализ использует атаки знания исходного текста (в отличии от атак с выборкой исходного текста в дифференциальном криптоанализе). Полное обсуждение этой атаки базируется на некоторых понятиях теории вероятностей, которые находятся за рамками этой книги. Чтобы рассмотреть главную идею этой атаки, предположим, что шифр состоит из одного раунда, как показано на рис. 7.20, где c0,с1 и c2 представляют три бита на выходе и xQ, x1 и x2 представляют три бита на входе S -блока.

S -блок — линейное преобразование, в котором каждый вывод является линейной функцией ввода, как мы обсуждали ранее в этой лекции. С этим линейным компонентом мы можем создать три линейных уравнения между исходным текстом и битами зашифрованного текста, как показано ниже:

(рис 7.20) Простой шифр с линейным S-блоком $$c_{0} = p_{0} \oplus k_{0} \oplus p_{1} \oplus k_{1} \\ c_{1} = p_{0} \oplus k_{0} \oplus p_{1} \oplus k_{1} \oplus p_{2} \oplus k_{2} \\ c_{2} = p_{1} \oplus k_{1} \oplus p_{2} \oplus k_{2} \oplus$$

Решая систему уравнений для трех неизвестных, мы получаем

$$k_{1} = (p_{1}) \oplus (c_{0} \oplus c_{1} \oplus c_{2}) \\ k_{2} = (p_{2}) \oplus (c_{0} \oplus c_{1}) \\ k_{0} = (p_{0}) \oplus (c_{1} \oplus c_{2})$$

Это означает, что три атаки типа "знания исходного текста" могут найти значения k1, и k2. Однако реальные блочные шифры не так просты, как этот; они имеют больше компонентов, и S -блоки не линейны.

Линейная аппроксимация. В некоторых современных блочных шифрах может случиться, что некоторые S -блоки не полностью нелинейные; тогда они могут быть в вероятностном смысле аппроксимированы некоторыми линейными функциями. Вообще, задавая исходный и зашифрованный текст в n бит и ключ m бит, мы ищем некоторые уравнения, имеющие вид

$$(k_{0} \oplus k_{1} \oplus \dots \oplus k_{x}) = (p_{0} \oplus p_{1} \oplus \dots \oplus p_{y}) \oplus (c_{0} \oplus c_{1} \oplus \dots \oplus c_{z})$$

7.2. Современные шифры потока

В лекциях 5-6 мы кратко обсуждали разницу между традиционными шифрами потока и традиционными блочными шифрами. Подобные отличия существуют также между современными шифрами потока и современными блочными шифрами. В современном шифре потока шифрование и дешифрование проводятся r бит одновременно. Мы имеем поток бит исходного текста P = pn… p2p1, поток бит зашифрованного текста C = cn ... c2 c1, и ключевой поток бит K = k n ... k2k1, в которых pi ci, и ki — это r -битные слова. Шифрование — ci = E (ki,pi), и дешифрование — pi = D (ki, ci), как показывает рис. 7.21.

(рис 7.21) Шифр потока

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

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

Рассматривая рис. 7.21, можно предположить, что главная проблема в современных шифрах потока — как генерировать ключевой поток K = kn….. k2k1. Современный шифр потока можно разделить на две обширные категории: синхронный и несинхронный.

Синхронные шифры потока

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

В синхронном шифре потока ключ независим от исходного текста или зашифрованного текста.

Одноразовый блокнот

Наиболее простой и самый безопасный тип синхронного шифра потока назван шифром одноразового блокнота, или, по имени изобретателя, "шифром Вернама". Шифр одноразового блокнота использует ключевой поток, который беспорядочно выбран для каждой шифровки. Алгоритмы шифрования и дешифрования применяют единственную операцию — ИСКЛЮЧАЮЩЕЕ ИЛИ. Шифры, которые базируются на свойствах операции ИСКЛЮЧАЮЩЕЕ ИЛИ, обсуждались ранее. В них алгоритмы шифрования и дешифрования инверсны друг другу. Важно, что в этом шифре операция ИСКЛЮЧАЮЩЕЕ ИЛИ используется только для одного бита одновременно. Другими словами, операция производится над словом не более чем из одного бита и полем GF (2). Заметим, что также нужно иметь безопасный канал для того, чтобы Алиса могла передать ключевую последовательность потока Бобу (рис. 7.22).

(рис 7.22) Одноразовый блокнот

Одноразовый блокнот — идеальный шифр. Он совершенен. Нет метода, который дал бы противнику возможность распознать ключ или статистику зашифрованного текста и исходного текста. Нет никаких соотношений между исходным и зашифрованным текстами. Другими словами, зашифрованный текст – настоящий случайный поток битов, даже если получить некоторые образцы исходного текста. Ева не может нарушить шифр, если она не попробует все возможные случайные ключевые потоки, которые были бы 2n, если размер исходного текста — n -битовый. Однако при этом есть проблема. Передатчик и приемник для того, чтобы совместно использовать одноразовый блокнот ключей, должны установить соединение каждый раз, когда они хотят обменяться информацией. Они должны, так или иначе, договориться о случайном ключе. Так что этот совершенный и идеальный шифр очень трудно реализовать.

Пример 7.17

Какой вид имеет зашифрованный текст при использовании шифра одноразового блокнота в каждом из следующих случаев?

а. Исходный текст состоит из n нулей.

б. Исходный текст состоит из n единиц.

в. Исходный текст состоит из чередующихся нулей и единиц.

г. Исходный текст — случайная строчка бит.

Решение

a. Поскольку $$0\oplus k_{i} = k_{i}$$, то поток зашифрованного текста совпадет с ключевым потоком. Если ключ случайный, зашифрованный текст также случайный. Отрывки исходного текста в зашифрованном тексте не сохраняются.

b. Поскольку $$1\oplus k_{i} = k_{i}$$, где $${\bar k_i}$$ является дополнением, поток зашифрованного текста — дополнение ключевого потока. Если ключевой поток случайный, то зашифрованный текст также случайный, отрывки исходного текста не сохраняются в зашифрованном тексте.

c. В этом случае каждый бит в потоке зашифрованного текста является или тем же самым, что и в ключевом потоке, или его дополнением. Поэтому результат — также случайный, если ключевой поток случайный.

d. В данном случае зашифрованный текст явно случайный, потому что проведение операции ИСКЛЮЧАЮЩЕЕ ИЛИ двух случайных битов в результате дает случайный поток бит.

Регистр сдвига с обратной связью

Одно усовершенствование к одноразовому блокноту — Регистр сдвига с обратной связью (FSR — Feedback Shift Register). FSR может быть реализован или в программном обеспечении, или в аппаратных средствах, но для простоты мы рассмотрим аппаратную реализацию. Регистр сдвига с обратной связью состоит из регистра сдвига и функции обратной связи, как показано на рис. 7.23.

(рис 7.23) Регистр сдвига с обратной связью (FSR)

Регистр сдвига – последовательность из m ячеек от b0 до bm-1, где каждая ячейка предназначена для сохранения единственного бита. Ячейки рассматриваются как n -битовое слово, называемое в начале "начальное значение" или источник. Всякий раз, когда необходимо получить бит на выходе (например, по сигналу в определенное время), каждый бит сдвигается на одну ячейку вправо. Это означает, что значение каждой ячейки присваивается правой соседней ячейке и принимает значение левой ячейки. Самая правая ячейка b0 считается выходом и дает выходное значение ( ki ). Крайняя левая ячейка, b_m-1, получает свое значение согласно значению информации функции обратной связи. Обозначаем выход функции с информацией обратной связи bm. Функция информации обратной связи определяет, какие значения имеют ячейки, чтобы вычислить bm. Регистр сдвига информации обратной связи может быть линейный или нелинейный.

Линейный регистр сдвига с обратной связью (LFSR). Примем, что bm — это линейная функция b0, b1,…..., bm-1, для которой

$$b_{m} = c_{m-1}b_{m-1} + \dots +c_{2}b_{2} + c_{1}b_{1} + c_{0}b_{0}\ (c_{0} \ne 0)$$

Линейный регистр сдвига с обратной связью работает с двоичными цифрами, поэтому умножение и сложение находятся в поле GF(2), так что значение Ci является или 1, или 0, но C0 должно быть 1, чтобы получить информацию обратной связи на выходе. Операция сложения – это операция ИСКЛЮЧАЮЩЕЕ ИЛИ. Другими словами,

$$b_{m} = c_{m-1}b_{m-1} \oplus \dots \oplus c_{2}b_{2} \oplus c_{1}b_{1} \oplus c_{0}b_{0}\ (c_{0} \ne 0)$$

Пример 7.18

Построим линейный регистр сдвига с обратной связью с 5 -ю ячейками, в которых $$b_{5} = b_{4}\oplus b_{2}\oplus b_{0}$$.

Решение

Если Сi = 0, bi не играет роли в вычислении bm, то это означает, что bi не связан с функцией информации обратной связи. Если c i = 1, bi включается в вычисление bm. В этом примере c1 и c3 — нули, это означает, что, мы имеем только три подключения. Рисунок 7.24 показывает схему линейного регистра сдвига с обратной связью.

(рис 7.24) Линейный регистр сдвига с обратной связью

Пример 7.19

Построим линейный регистр сдвига с обратной связью с 4 -мя ячейками, в которых $$b_{4} = b_{1}\oplus b_{0}$$. Покажите значение регистра после 20 операций (сдвигов), если исходное значение — (0001) 2.

Решение

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

(рис 7.25) Линейный регистр сдвига с обратной связью для примера 7.19

Таблица 7.6. показывает значение потока ключей. Для каждого перехода первое значение b4 вычисляется, а затем каждый бит сдвигается на одну ячейку вправо.

Текущее значение	b4	b3	b2	b1	b0	ki
Начальное значение	1	0	0	0	1
1	0	1	0	0	0	1
2	0	0	1	0	0	0
3	1	0	0	1	0	0
4	1	1	0	0	1	0
5	0	1	1	0	0	1
6	1	0	1	1	0	0
7	0	1	0	1	1	0
8	1	0	1	0	1	1
9	1	1	0	1	0	1
10	1	1	1	0	1	0
11	1	1	1	1	0	1
12	0	1	1	1	1	0
13	0	0	1	1	1	1
14	0	0	0	1	1	1
15	1	0	0	0	1	1
16	0	1	0	0	0	1
17	0	0	1	0	0	0
18	1	0	0	1	0	0
19	1	1	0	0	1	0
20	1	1	1	0	0	1

Заметим, что поток ключей — 1000100110101111 1001…… . Он выглядит, на первый взгляд, как случайная последовательность, но если просмотреть большое число транзакций (сдвигов), мы можем увидеть, что последовательности периодичны. Это повторение по 15 бит показано ниже.

Ключ потока генерирует с помощью линейного регистра сдвига с обратной связью псевдослучайную последовательность, в которой повторяются последовательности длиною N. Поток периодичен. Он зависит от схемы генератора и начальной информации и может быть не свыше 2m – 1. Каждая схема порождает m -битовые последовательности от содержащих все нули до содержащих все единицы. Однако если начальная последовательность состоит только из нулей, результат бесполезен — исходный текст был бы потоком из одних нулей. Поэтому такая начальная последовательность исключена.

Максимальный период последовательностей, которые генерируются с помощью линейного регистра сдвига с обратной связью, — .

В предыдущем примере максимальный период — ( 24 – 1 = 15 ). Чтобы достичь этой максимальной периодичности (наилучшей рандомизации), мы должны в первую очередь представить функцию обратной связи как характеристический полином с коэффициентами в поле GF(2).

bm = cm-1bm-1 + … + c1b1 + c0b0 -> xm = cm-1xm-1 + … + c1x1 + c0x0

Поскольку сложение и вычитание в этом поле одни и те же, все элементы могут быть перенесены в одну сторону, что дает полином степени m. (называемый характеристическим полиномом).

xm + cm-1xm-1 + … + c1x1 + c0x0 = 0

Линейный регистр сдвига с обратной связью имеет максимальный период 2m–1, если он имеет четное число ячеек, и характеристический полином — примитивный полином. Примитивный полином — неприводимый полином, который является делителем xe –1, где e — наименьшее целое число в форме e = 2k–1 и k >= 2. Примитивный полином получить нелегко. Полином выбирается случайно, а затем проверяется на примитивность. Однако существуют таблицы проверенных примитивных полиномов (см. приложение G).

Пример 7.20

Характеристический полином для линейного регистра сдвига с обратной связью в примере 7.19 — ( x4 + x + 1 ) — является примитивным полиномом. Таблица 5.1 (лекция 5) показывает, что это — неприводимый полином. Этот полином также делит (x7 + 1) = (x4 + x + 1) (x3 + 1), что означает e = 23 –1 = 7.

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

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

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

Нелинейный регистр сдвига с обратной связью. Линейный регистр сдвига с обратной связью уязвим главным образом из-за его линейности. Более устойчивый шифр потока может быть получен при использовании нелинейного регистра сдвига с обратной связью(NLFSR). Он имеет ту же самую структуру, что и линейный регистр сдвига с обратной связью, за исключением того, что bm — нелинейная функция b0,b1, ….,bm. Например, в 4 -битном нелинейном регистре сдвига с обратной связью структура определяется соотношением, показанным ниже, где операция AND означает поразрядную операцию И, а OR означает поразрядную операцию ИЛИ. Черточка над переменной означает инверсию.

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

Можно применить линейный регистр сдвига с обратной связью с максимальным периодом и затем скомбинировать его обратную связь с помощью нелинейной функции.

Несинхронные шифры потока

В несинхронном шифре потока каждый ключ в ключевом потоке зависит от предыдущего исходного текста или зашифрованного текста.

В несинхронном шифре потока ключ зависит либо от исходного текста, либо от зашифрованного текста.

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

7.3. Рекомендованная литература

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

Книги

[Sti06] и [PHS03] содержат полные сведения о P -блоках и S -блоках. Поточные шифры тщательно рассмотрены в [Sch99 ] и [Sal03]. [Sti06], [PHS03] и [Vau06] — полный и интересный анализ дифференциального и линейного криптоанализа.

Сайты

Нижеследующие сайты дают более подробную информацию о темах, обсужденных в этой лекции.

http://en.wikipedia.org/wiki/FeisteL.cipher

http://www.quadibloc.com/crypto/co040906.htm

tigger.uic.edu/~jleon/mcs425-s05/handouts/feistal-diagram.pdf

7.4. Итоги

Традиционные шифры с симметричным ключом — шифры, ориентированные на символ. С появлением компьютера стали нужны шифры, ориентированные на биты.

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

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

Современные блочные шифры — обычно ключевые шифры подстановки, в которых ключ практически позволяет отображение всех возможных входов во все возможные выходы.

Современный блочный шифр состоит из комбинации P -блоков, модулей подстановки, S -блоков и некоторых других модулей.

P -блок (блок перестановки) подобен традиционному шифру транспозиции для символов. Есть три типа P -блоков: прямые P -блоки, P -блоки расширения и P -блоки сжатия.

S -блок (блок подстановки) можно представить себе как маленький блок шифра подстановки. Однако в S -блоке может быть различное число входов и выходов.

Операция ИСКЛЮЧАЮЩЕЕ ИЛИ — важный компонент в большинстве блочных шифров: она представляет операции сложения или вычитания в поле GF (2).

В современных блочных шифрах часто применяется операция циклического сдвига, в которой смещение может быть влево или вправо. Операция перестановки — специальный случай операции циклического сдвига, где k = n/2. Две других операции, применяемые в некоторых блочных шифрах, — разбиение и комбинирование.

Шеннон ввел понятие составного шифра. Составной шифр — сложный шифр, объединяющий S -блоки, P -блоки и другие компоненты, чтобы достигнуть рассеивания и перемешивания. Рассеивание скрывает отношения между исходным текстом и зашифрованным текстом, перемешивание скрывает отношения между ключом шифра и зашифрованным текстом.

Современные блочные шифры — все составные шифры, но они разделены на два класса: шифры не-Файстля и шифры Файстеля. Шифры Файстеля используют и обратимые, и необратимые компоненты. Шифры не-Файстля используют только обратимые компоненты.

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

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

Самый простой и самый безопасный тип синхронного шифра потока назван одноразовым блокнотом. Шифр одноразового блокнота использует ключевой поток ключей, который выбран беспорядочно для каждого шифрования. Алгоритмы шифрования и дешифрования используют операцию ИСКЛЮЧАЮЩЕЕ ИЛИ. Шифр одноразового блокнота не годится для практики, потому что ключ должен быть индивидуальным для каждого сеанса связи. Один из компромиссных вариантов одноразового блокнота — регистр сдвига с обратной связью (FSR), который может быть реализован в аппаратных средствах или программном обеспечении.

7.5. Вопросы и упражнения

Обзорные вопросы

Укажите различия между современным и традиционным шифрами с симметричным ключом.

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

Объясните, почему шифр подстановки можно представить себе как шифр транспозиции.

Перечислите некоторые компоненты современного блочного шифра.

Определите P -блок и перечислите его три варианта. Какой вариант является обратимым?

Определите S -блок и покажите необходимое условие обратимости S -блока.

Определите составной шифр и перечислите два класса составных шифров.

Укажите различие между рассеиванием и перемешиванием

Укажите различие между блочным шифром Файстеля и не-Файстеля.

Укажите различие между дифференциальным и линейным криптоанализом. Какой из них использует атаку выборки исходного текста? Какой из них использует также атаку знания исходного текста?

Укажите различие между синхронным и несинхронным шифрами потока.

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

Упражнения

Блок транспозиции имеет 10 входов и 10 выходов. Каков порядок группы перестановки? Каков размер ключевой последовательности?

Блок подстановки имеет 10 входов и 10 выходов. Каков порядок группы перестановки? Каков размер ключевой последовательности?

Покажите результат циркулярного левого сдвига на 3 бита на слове (1001101l) 2.

Покажите результат циркулярного правого сдвига на 3 бита на слове, полученном в пункте a.

Сравните результат пункта b с первоначальным словом пункта a.

Измените слово (10011011) 2 с помощью перестановки.

Измените слово, полученное по пункту a, с помощью перестановки

Сравните результаты пункта a и пункта b, чтобы показать, что перестановка — самообратимая операция.

Найдите результат следующих операций:

$$(01001101) \oplus (01001101)$$

$$(01001101) \oplus (10110010)$$

$$(01001101) \oplus (00000000)$$

$$(01001101) \oplus (11111111)$$

Расшифруйте слово 010, используя декодер $$3 \times 8$$.

Зашифруйте слово 00100000, используя кодирующее устройство $$8 \times 3$$.

Сообщение имеет 2000 символов. Оно будет зашифровано с использованием блочного шифра 64 битов. Найдите размер дополнения и номера блоков.

Покажите таблицу перестановки для прямого P -блока на рис. 7.4

Покажите таблицу перестановки для P -блока сжатия на рис. 7.4.

Покажите таблицу перестановки для P -блока расширения на рис. 7.4.

Покажите P -блок, определенный следующей таблицей:

8

1

2

3

4

5

6

7

Определите, является ли P -блок со следующей таблицей перестановки прямым P -блоком, P -блоком сжатия или P -блоком расширения.

1

1

2

3

4

4

Определите, является ли P -блок со следующей таблицей перестановки прямым P -блоком, P -блоком сжатия или P -блоком расширения.

1

3

5

6

7

Определите, является ли P -блок со следующей таблицей перестановки прямым P -блоком, P -блоком сжатия или P -блоком расширения.

1

2

3

4

5

6

Отношение вход-выход в $$2 \times 2$$

Покажите LFSR с характеристическим полиномом x5 + x2 + 1. Каков период получаемой последовательности?

Каков характеристический полином следующего LFSR? Каков максимальный период?

Покажите ключевой поток на 20 битов, сгенерированный от LFSR на рис. 7.25, если начальное значение — 1110.

Максимальная длина периода LFSR — 32. Сколько битов имеет регистр сдвига?

6 x 2 S -блок производит операцию ИСКЛЮЧАЮЩЕЕ ИЛИ с нечетными битами, чтобы получить левый бит выхода, и ИСКЛЮЧАЮЩЕЕ ИЛИ с четными битами, чтобы получить правый бит выхода. Если вход — 110010, что является выходом? Если вход — 101101, что является выходом?

Крайний левый бит 4 x 3 S -блока определяет смещение других трех бит. Если крайний левый бит равен 0, то три других бита перемещаются вправо на один бит. Если крайний левый бит — 1, три других бита перемещаются влево на один бит. Если вход — 1011, какой результат будет на выходе? Если вход — 0110, какой результат будет на выходе?

Напишите процедуру в псевдокоде для разбиения n -битового слова на два слова, каждое из которых состоит из n/2.

Напишите процедуру в псевдокоде для объединения двух n/2 -битовых слов в n -битовое слово.

Напишите процедуру в псевдокоде, которая переставляет левые и правые половины n -битового слова.

Напишите процедуру в псевдокоде, которая циклически сдвигает в n -разрядном слове на k бит влево или вправо, в соответствии с процедурой по п. 24.

Напишите процедуру в псевдокоде для P -блока, в котором перестановка определена таблицей.

Напишите процедуру в псевдокоде для S -блока, в котором вход-выход определен таблицей.

Напишите процедуру в псевдокоде, которая моделирует каждый раунд не-Файстеля, показанный на рис. 7.13.

Напишите процедуру в псевдокоде, которая моделирует каждый раунд шифра, показанный на рис. 7.17.

Напишите процедуру в псевдокоде, которая моделирует n -битовый LFSR.