Традиционные шифры с симметричным ключом

Мультипликативные шифры

В мультипликативном шифре алгоритм шифрования применяет умножение исходного текста ключом, а алгоритм дешифрования применяет деление зашифрованного текста ключом, как показано на рис. 4.10. Однако поскольку операции проводятся в Z26, дешифрование здесь означает умножение на мультипликативную инверсию ключа. Обратите внимание, что ключ должен принадлежать набору Zn* — это гарантирует, что шифрование и дешифрование инверсны друг другу.

Пример 4.7

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

Решение

Ключ должен быть в Z26*. Это множество имеет только 12 элементов: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.

Пример 4.8

Мы используем мультипликативный шифр, чтобы зашифровать сообщение "hello" с ключом 7. Зашифрованный текст "XCZZU".

Исходный текст  h           07	Шифрование (07 x 07) mod 26    Шифр. Текст 23            X
Исходный текст  e           04	Шифрование (04 x 07) mod 26    Шифр. Текст 02            C
Исходный текст  l           11	Шифрование (11 x 07) mod 26    Шифр. Текст 25            Z
Исходный текст  l           11	Шифрование (11 x 07) mod 26    Шифр. Текст 25            Z
Исходный текст  o           14	Шифрование (14 x 07) mod 26    Шифр. Текст 20            U

Мы можем комбинировать аддитивные и мультипликативные шифры, чтобы получить то, что названо аффинным шифром — комбинацией обоих шифров с парой ключей. Первый ключ используется мультипликативным шифром, второй — аддитивным шифром. Рисунок 4.11 доказывает, что афинный шифр — фактически два шифра, применяемые один за другим. Мы могли бы показать только одну комплексную операцию для шифрования или дешифрования, такую, как $$C = (P \times {k_1} + {k_2})\bmod 26$$ и $$P = ((C-{k_2}) \times {k_1}^{ - 1})\bmod 26$$. Однако мы использовали временный результат ( T ) и указали две отдельных операции, показав тем самым, что всякий раз, когда мы используем комбинацию шифров, нужно убедиться, что каждый из них имеет инверсию на другой стороне линии и что они используются в обратном порядке в шифровании и дешифровании. Если сложение — последняя работа в шифровании, то вычитание должно быть первым в дешифровании.

При аффинном шифре отношение между исходным текстом P и шифрованным текстом C определяется, как это показано ниже.

C = (P x k1 + k2 ) mod 26   P = ((C – k2) x k1-1) mod 26
где k1-1 мультипликативная инверсия k1, а(– k2)–аддитивная инверсия k2

Пример 4.9

Аффинный шифр использует пару ключей, в которой первый ключ из Z26*, а второй — из Z26. Область существования ключей равна $$26 \times 12 = 312 $$.

Пример 4.10

Используйте аффинный шифр, чтобы зашифровать сообщение "hello" с ключевой парой (7, 2).

Решение

Мы используем 7 для мультипликативного ключа и 2 для аддитивного ключа. Получаем "ZEBBW".

P:  h           07	Шифрование (07 x 07+2) mod 26   C: 25            Z
P:  e           04	Шифрование (04 x 07+2) mod 26   C: 04            E
P:  l           11	Шифрование (11 x 07+2) mod 26   C: 01            B
P:  l           11	Шифрование (11 x 07+2) mod 26   C: 01            B
P:  o           14	Шифрование (14 x 07+2) mod 26   C: 22            W

Пример 4.11

Используйте аффинный шифр, чтобы расшифровать сообщение "ZEBBW" с ключевой парой (7, 2) в модуле 26.

Решение

Чтобы найти символы исходного текста, прибавим аддитивную инверсию от $$(-2) \equiv 24\left( {\bmod 26} \right)$$ к полученному зашифрованному тексту. Потом умножим результат на мультипликативную инверсию от $${7^{ - 1}} \equiv 15\left( {\bmod 26} \right) $$. Поскольку 2 имеет аддитивную инверсию в Z26 и 7 имеет мультипликативную инверсию в Z26*, исходный текст — точно тот, что мы использовали в примере 4.10.

C: 25  ->    Z	Дешифрование (07 x 07 - 2) mod 26     P: 07  ->    h         
C: 04  ->    E	Дешифрование (04 x 07 - 2) mod 26     P: 04  ->    e          
C: 01  ->    B	Дешифрование (11 x 07 - 2) mod 26     P: 11  ->    l
C: 01  ->    B	Дешифрование (11 x 07 - 2) mod 26     P: 11  ->    l           
C: 22  ->    W	Дешифрование (14 x 07 - 2) mod 26     P: 14  ->    o

Пример 4.12

Аддитивный шифр — частный случай аффинного шифра, при котором k1 = 1. Мультипликативный шифр — частный случай аффинного шифра, в котором k2 = 0.

Криптоанализ аффинного шифра

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

PWUFFOGWCHFDWIWEJOUUNJORSMDWRHVCMWJUPVCCG

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

Для того чтобы найти ключ, Ева использует следующую стратегию:

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

e -> W	04 -> 22	(04 x k1+k2) = 22 (mod 26)
t- -> C     19 -> 02	(19 x k1+k2) = 02 (mod 26)

Как мы узнали в лекции 4, эти два уравнения сравнения могут быть решены (могут быть найдены значения k1, и k2 ). Однако этот ответ неприемлем, потому что k1 = 16 не может быть первой частью ключа. Его значение, 16, не имеет мультипликативной инверсии в Z26*.

b. Ева теперь пробует использовать результат второго набора данных:

e -> W	04 -> 22	(04 x k1+k2) = 22 (mod 26)
t- -> C     19 -> 05	(19 x k1+k2) = 05 (mod 26)

Квадратная матрица и ее инверсия — те же самые, что и в предыдущем примере. Теперь Ева получает k1 = 11 и k2 = 4, эта пара является приемлемой, потому что k1 имеет мультипликативную инверсию в Z26*. Она пробует пару ключей (19, 22), которые являются инверсией пары (11, 4), и расшифровывает сообщение. Исходный текст

Best time of the year is spring when flower bloom
Самое лучшее время года — весна, когда цветут цветы

Моноалфавитный шифр подстановки

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

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

Пример 4.13

Мы можем использовать ключ, показанный на рисунке 4.12, чтобы зашифровать сообщение

This message is easy to encrypt but hard to find the key
(это сообщение просто зашифровать, но трудно найти ключ, которым зашифрован текст)

Зашифрованное сообщение имеет вид

ICFVQRVVNEFVRNVSIYRGAHSLIOJICNHTIYBFGTICRXRS

Криптоанализ

Размер ключевого пространства для моноалфавитного шифра подстановки — число перестановок из 26, т.е. 26! (почти $$4 \times {10^{26}}$$ ). Это делает атаку грубой силы чрезвычайно трудной для Евы, даже если она использует мощный компьютер. Однако она может применить статистическую атаку, основанную на частоте символов. Шифр не изменяет частоту употребления символов.

Многоалфавитные шифры

В многоалфавитной подстановке каждое появление символа может иметь различную замену. Отношения между символом в исходном тексте и символом в зашифрованном тексте — "один ко многим". Например, "a" может быть зашифровано как "D" в начале текста, но как "N" — в середине. Многоалфавитные шифры имеют преимущество: они скрывают частоту появления символа основного языка. Ева не может использовать статистическую частоту отдельного символа, чтобы взломать зашифрованный текст.

Чтобы создать многоалфавитный шифр, мы должны сделать каждый символ зашифрованного текста зависящим от соответствующего символа исходного текста и позиции символа исходного текста в сообщении. Это подразумевает, что наш ключ должен быть потоком подключей, в которых каждый подключ так или иначе зависит от позиции символа исходного текста, который используется для выбора подключа шифрования. Другими словами, мы должны иметь ключевой поток k = (k1, k2, k3.….), в котором ki применяется, чтобы зашифровать i -тый символ в исходном тексте и создать i -тый символ в зашифрованном тексте.

Автоключевой шифр

Чтобы понять зависимость ключа от позиции, обсудим простой многоалфавитный шифр, названный "автоключевым". В этом шифре ключ — поток подключей, в котором каждый подключ используется, чтобы зашифровать соответствующий символ в исходном тексте. Первый подключ — определенное заранее значение, тайно согласованное Алисой и Бобом. Второй подключ — значение первого символа исходного текста (между 0 и 25 ). Третий — i -тое значение второго исходного текста. И так далее.

P = P1 P2 P3…..	
C = C1 C2 C3…..	
K = (k1,P1, P2, P3,…..)
Шифрование Ci = (Pi + ki) mod 26          
Дешифрование Pi = (Ci – ki) mod 26

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

Пример 4.14

Предположим, что Алиса и Боб согласились использовать автоключевой шифр с начальным ключевым значением k1 = 12. Теперь Алиса хочет передать Бобу сообщение "Attack is today" ("Атака — сегодня"). Шифрование проводится символ за символом. Каждый символ в исходном тексте сначала заменяется его значением целого числа, как показано на рис. 4.8, первый подключ прибавляется, чтобы создать первый символ зашифрованного текста. Остальная часть ключа создается по мере чтения символов исходного текста. Обратите внимание, что шифр является многоалфавитным, потому что эти три появления "a" в исходном тексте зашифрованы различно. Три возникновения "t" также зашифрованы различно.

Криптоанализ

Автоключевой шифр действительно скрывает статистику частоты отдельного символа. Однако он так же уязвим при атаке с помощью грубой силы, как и аддитивный шифр. Первый подключ может быть только одним из 25 значений (1 - 25). Мы нуждаемся в многоалфавитных шифрах, которые не только скрывают характеристики языка, но и имеют большие множества ключей.

Шифр Плейфера

Другой пример многоалфавитного шифра — Шифр Плейфера, использовавшийся британской армией в течение Первой мировой войны. Ключ засекречивания в этом шифре сделан из 25 букв алфавита, размещенных в матрице $$5 \times 5$$ (буквы I и J рассматриваются при шифровании как одинаковые). С помощью различных соглашений о размещении букв в матрице можно создать много различных ключей засекречивания. Одно из возможных соглашений показано на рисунке 4.13.

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

Шифр использует три правила для шифрования:

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

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

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

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

P = P1P2P3…..	
C = C1C2C3…..	
k = [(k1,k2), (k3,k4),…..]
Шифрование Ci =  ki                
Дешифрование Pi = ki

Пример 4.15

Пусть нам надо зашифровать исходный текст "hello", использующий ключи на рис. 4.13. Когда мы группируем буквы по парам, мы получаем "he, ll,o". Мы должны вставить x между двумя l (эль), после чего получим "he, lx, lo". Мы имеем

he -> EC	   lx -> QZ	    lo -> BX
Исходный текст: hello        Зашифрованный текст:  ECQZBX

Мы можем видеть из этого примера, что наш шифр — фактически многоалфавитный шифр: два появления l (эль) зашифрованы как "Q" и "B".

Криптоанализ шифра Плейфера

Очевидно, атака грубой силы шифра Плейфера очень трудна. Размер домена — 25! (факториал 25 ). Кроме того, шифровка скрывает частоту отдельных букв.

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

Шифр Виженера

Один интересный вид многоалфавитного шифра был создан Блезом де Виженером, французским математиком шестнадцатого столетия. Шифр Виженера использует различную стратегию создания потока ключей. Поток ключей — повторение начального потока ключа засекречивания длины m, где мы имеем 1 < m < 26. Шифр может быть описан следующим образом: (k1, k2, …., km) — первоначальный ключ засекречивания, согласованный Алисой и Бобом.

P = P1P2P3…..	
C = C1C2C3…..	
k = [(k1,k2), (k3,k4),…..]
Шифрование Ci =  ki                
Дешифрование Pi = ki

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

Пример 4.16

Посмотрим, как мы можем зашифровать сообщение "She is listening (Она слушает) ", используя ключевое слово на 6 символов "PASCAL". Начальный поток ключей — это (15, 0, 18, 2, 0, 11). Поток ключей — повторение этого начального потока ключей (столько раз, сколько необходимо).

Пример 4.17

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

Пример 4.18

Разобрав пример 4.18, мы убедимся, что аддитивный шифр — частный случай шифра Виженера, в котором m = 1.

Список Виженера

Другой способ рассмотрения шифров Виженера — с помощью того, что названо списком Виженера (Vigenere tableau) и показано в таблице 4.3.

Первая строка показывает символы исходного текста, который будет зашифрован. Первая колонка содержит столбец символов, которые используются ключом. Остальная часть таблицы показывает символы зашифрованного текста. Чтобы найти зашифрованный текст для исходного текста "she listening", используя слово "PASCAL" как ключ, мы можем найти "s" в первой строке, "P" в первом столбце, на пересечении строки и столбца — символ из зашифрованного текста "H". Находим "h" в первой строке и "A" во втором столбце, на пересечении строки и столбца — символ "H" из зашифрованного текста. И повторяем те же действия, пока все символы зашифрованного текста не будут найдены.

Криптоанализ шифра Виженера

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

Пример 4.19

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

LIOMWGFEGGDVWGHHCQUCRHRWAGWIOWQLKGZETKKMEVLWPCZVG'TH VTSGXQOVGCSVETQLTJSUMVWVEUVLXEWSLGFZMVVWLGYHCUSWXQH - KVGSHEEVFLCFDGVSUMPHKIRZDMPHHBVWVWJWIXGFWLTSHGJOUEEHH- VUCFVGOWICQLIJSUXGLW

Тест Казиского на повторение сегментов на три символа приводит к результатам, показанным в таблице 4.4.

Наибольший делитель - 4, что означает длину ключа, пропорциональную 4. Сначала пробуем m = 4. Делим зашифрованный текст на четыре части. Часть C1 состоит из символов 1, 5, 9...; часть C2 состоит из символов 2, 6, 10..., и так далее. Используем статистическую атаку каждой части отдельно. Перебираем расшифровывающиеся части по одному символу одновременно, чтобы получить целый исходный текст.

Если исходный текст не имеет смысла, попробуем с другим m.

В рассматриваемом случае исходный текст имеет смысл (читаем по столбцам).

Перевод этого текста приведен ниже.

Шифр Хилла

Другой интересный пример многоалфавитного шифра — шифр Хилла, изобретенный Лестером С. Хиллом. В отличие от других многоалфавитных шифров, которые мы уже рассмотрели, здесь исходный текст разделен на блоки равного размера. Блоки зашифрованы по одному таким способом, что каждый символ в блоке вносит вклад в шифрование других символов в блоке. По этой причине шифр Хилла принадлежит к категории шифров, названных блочными шифрами. Другие шифры, которые мы изучали до сих пор, принадлежат к категории, называемой шифры потока. Отличие между шифрами блока и шифрами потока обсуждаются в конце этой лекции.

В шифре Хилла ключ — квадратная матрица размера $$m \times m$$., в котором m. является размером блока. Если мы вызываем ключевую матрицу K, то каждый элемент ki,j определяется матрицей, как показано на рис. 4.15.

Покажем, как получается один блок зашифрованного текста. Если мы обозначим m символов блоков исходного текста P1, P2 ..., Pm, соответствующие символы в блоках зашифрованного текста будут C1, C2 , ..., Cm. Тогда мы имеем

C1 = P1k11+P2k21+……+Pmkm1
C2 = P1k12+P2k22+……+Pmkm2
………………………………………………………
Cm = P1k1m+ P2k2m +……+ Pmkmm

Уравнения показывают, что каждый символ зашифрованного текста, такой, как C1, зависит от символов всего исходного текста в блоке (P1, P2,..., Pm). Однако мы должны знать, что не все квадратные матрицы имеют мультипликативные инверсии в Z26, так что Алиса и Боб должны быть осторожны в выборе ключа. Боб не сможет расшифровать зашифрованный текст, передаваемый Алисой, если матрица не имеет мультипликативной инверсии.

Пример 4.20

Использование матриц позволяет Алисе зашифровать весь исходный текст. В этом случае исходный текст $$-l \times m$$ — матрица, в которой l является номером блоков. Например, исходный текст "code is ready" ("код готов"), может быть представлен как матрица $$3 \times 4$$ при добавлении дополнительного фиктивного символа "z" к последнему блоку и удалении пробелов; зашифрованный текст выглядит как "OHKNIHGKLISS". Боб может расшифровать сообщение, используя инверсную матрицу-ключ. Шифрование и дешифрование показано на рис. 4.16.

Криптоанализ шифров Хилла

Криптоанализ только для зашифрованного шифрами Хилла текста труден. Во-первых, атака грубой силы при шифре Хилла чрезвычайно сложна, потому что матрица-ключ — $$m \times m$$. Каждый вход может иметь одно из 26 значений. Во-первых, это означает размер ключа $${26^{m \times m}}$$. Однако, не все матрицы имеют мультипликативную инверсию. Поэтому область существования ключей все же не такая огромная.

Во-вторых, шифры Хилла не сохраняют статистику обычного текста. Ева не может провести анализ частоты отдельных букв из двух или трех букв. Анализ частоты слов размера m мог бы cработать, но очень редко исходный текст имеет много одинаковых строк размера m. Ева, однако, может провести атаку на шифр, используя метод знания исходного текста, если она знает значение m и знает пары "исходный текст/зашифрованный текст", по крайней мере m блоков. Блоки могут принадлежать тому же самому сообщению или различным сообщениям, но должны быть различны. Ева может создать две $$m \times m$$. матрицы, P (обычный текст) и C (зашифрованный текст), в котором соответствующие строки представляют известные пары обычного/зашифрованного текста. Поскольку C = PK, Ева может использовать отношения K = CP-1, чтобы найти ключ, если P является обратимым. Если P не является обратимым, то Ева должна задействовать различные наборы m пар обычного/зашифрованного текста.

Если Ева не знает значение m, она может попробовать различные значения при условии, что m не является очень большим.

Пример 4.21

Предположим, что Ева знает, что m = 3. Она перехватила три пары блока исходного/зашифрованного текста (не обязательно из того же самого сообщения), как показано на рис. 4.17.

Она составляет матрицы P и C из этих пар. Поскольку в данном случае матрица P обратима, она инвертирует эту матрицу и умножает ее на C, что дает матрицу ключей K, как это показано на рис. 4.18.

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

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

Одна из целей криптографии — идеальная секретность. Исследования Шеннона показали, что идеальная секретность может быть достигнута, если символы исходного текста зашифрованы с помощью ключа, выбранного случайно из некоторой области ключей. Например, аддитивный шифр может быть легко взломан, потому что используется один и тот же ключ. Но даже и этот шифр может быть идеальным, если ключ, который применяется для шифрования каждого символа, выбран случайно из множества ключей (00, 01, 02.... 25): если первый символ зашифрован с помощью ключа 04, второй символ — с помощью ключа 02, третий — с помощью ключа 21, и так далее. Атака "только для зашифрованного текста" становится невозможна. Если передатчик изменяет ключ, используя каждый раз иную случайную последовательность целых чисел, другие типы атак также будут невозможны.

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

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

Роторный шифр

Хотя шифры одноразового блокнота не применяются на практике, один шаг от него к более защищенному шифру — роторный шифр. Он возвращается к идее моноалфавитной подстановки, но меняет принцип отображения исходного текста в символы зашифрованного текста для каждого символа исходного текста. Рисунок 4.19 показывает упрощенный пример роторного шифра.

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

Начальная установка (позиция) ротора — ключ засекречивания между Алисой и Бобом — это зашифрованный первый символ исходного текста. Используя начальную установку, второй символ зашифрован после того, как проведено первое вращение (на рис. 4.19 — это поворот на 1/6 круга, на реальной установке — поворот на 1/26 ), и так далее.

Слово с тремя буквами, такими как "bee", зашифровано как "BAA", если ротор неподвижен (моноалфавитный шифр подстановки), но оно будет зашифровано как "BCA", если он вращается (роторный шифр). Это показывает, что роторный шифр — многоалфавитный шифр, потому что два появления того же самого символа исходного текста зашифрованы как различные символы.

Роторный шифр является стойким к атаке грубой силы, как моноалфавитный шифр подстановки, потому что Ева должна найти первое множество отображений среди возможных 26! (факториал). Роторный шифр является намного более стойким к статистической атаке, чем моноалфавитный шифр подстановки, потому что в нем не сохраняется частота употребления буквы.

Машина "Энигма"

Машина "Энигма" была первоначально изобретена в Сербии, но была изменена специалистами немецкой армии и интенсивно использовалась в течение Второй Мировой Войны. Машина базировалась на принципе шифров ротора. Рисунок 4.20 показывает упрощенную схему построения машины.

Ниже перечислены главные компоненты машины.

Кодовая книга — справочник шифров

Чтобы использовать "Энигму", была издана кодовая книга, которая в течение каждого дня дает несколько параметров настройки, включая:

a. три ротора, которые должны быть выбраны из пяти доступных;

b. порядок, в котором эти роторы должны быть установлены;

c. параметры установок для коммутационной панели;

d. код с тремя буквами дня.

Процедура шифровавшая Сообщения

Чтобы зашифровать сообщение, оператор должен последовательно сделать шаги, перечисленные ниже:

Процедура для расшифровки сообщения

Чтобы расшифровывать сообщение, оператор должен сделать следующие шаги:

Криптоанализ

Мы знаем, что "Энигма" во время войны была взломана, хотя германская армия и остальная часть мира не знала об этом факте еще несколько десятилетий после того. Вопрос: как такой сложный шифр был атакован? Хотя немецкий язык весьма сложен, союзники, так или иначе, получили некоторые копии машин. Следующим шагом был поиск параметров установки в течение каждого дня и кода, передаваемого для инициализации роторов для каждого сообщения. Изобретение первого компьютера помогло союзникам преодолеть эти трудности. Подробное изображение машины "Энигма" и ее криптоанализ может быть найден на сайтах, посвященных этой машине.

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

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

Шифры перестановки без использования ключа

Простые шифры перестановки, которые применялись в прошлом, не использовали ключ. Есть два метода для перестановки символов. В первом методе текст записывается в таблице столбец за столбцом и затем передаётся строка за строкой. Во втором методе текст написан в таблицы строка за строкой и затем передаётся столбец за столбцом.

Пример 4.22

Хороший пример шифра без использования ключа — шифр изгороди (rail fence cipher). В этом шифре исходный текст размещен на двух линиях как зигзагообразный шаблон (что может рассматриваться как столбец за столбцом таблицы, которая имеет две строки); зашифрованный текст составляется при чтении шаблона строка за строкой. Например, чтобы передать сообщение "Meet me at the park" ( "Встречай меня в парке" ), Алиса пишет Бобу:

Алиса создает зашифрованный текст "MEMATEAKETETHPR", посылая первую строку, сопровождаемую второй строкой. Боб получает зашифрованный текст и разделяет его пополам (в этом случае вторая половина имеет на один символ меньше). Первая половина формы — первая строка; вторая половина — вторая строка. Боб читает результат по зигзагу. Поскольку нет никакого ключа и номер строк установлен ( 2 ), криптоанализ зашифрованного текста был бы очень прост для Евы. Все, что она должна знать, — это то, что используется шифр изгороди.

Пример 4.23

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

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

Пример 4.24

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

Второй символ в исходном тексте передвинулся на пятую позицию в зашифрованном тексте; третий символ передвинулся на девятую позицию; и так далее. Хотя символы переставлены, они сами являются шаблонами: (01, 05, 09, 13), (02, 06, 10, 14), (03, 07, 11, 15) и (04, 08, 12). В каждой секции разность между двумя смежными номерами — 4.

Ключевые шифры перестановки

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

Пример 4.25

Алиса должна передать Бобу сообщение "Enemy attacks tonight" ( "Вражеские атаки сегодня вечером" ). Алиса и Боб согласились разделить текст на группы по пять символов и затем переставить символы в каждой группе. Ниже показана группировка после добавления фиктивного символа в конце, чтобы сделать последнюю группу одинаковой по размеру с другими.

Enemy atttac kston ightz

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

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

EEMYN TAACT TKONS HITZG

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

Объединение двух подходов

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

Пример 4.26

Предположим, что Алиса снова зашифровывает сообщение в примере 4.25, на сей раз используя объединенный подход. Шифрование и дешифрование показано на рис. 4.21.

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

Ключи

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

Ключ шифрования — (3 1 4 5 2). Первый вход показывает, что столбец 3 (содержание) в источнике становится столбцом 1 (положение или индекс входа) в пункте назначения. Ключ дешифрования — (2 5 1 3 4). Первый вход показывает, что столбец 2 в источнике становится столбцом 1 в пункте назначения.

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

Использование матриц

Мы можем использовать матрицы, чтобы показать процесс шифрования/дешифрования для шифра перестановки. Исходный текст и зашифрованный текст — матрица $$l \times m$$., представляющая числовые значения символов; ключи — квадратные матрицы размера $$m \times m$$. В матрице перестановки каждая строка или столбец имеют строго одну единицу (1), и остальная часть значений — нули (0). Шифрование выполняется умножением матрицы исходного текста на ключевую матрицу, чтобы получить матрицу зашифрованного текста; дешифрование выполняется умножением зашифрованного текста на инверсию ключевой матрицы, после чего получаем исходный текст.

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

Пример 4.27

Рисунок 4.24 показывает процесс шифрования. Умножение матрицы $$4 \times 5$$ исходного текста на ключевую матрицу шифрования $$5 \times 5$$ дает матрицу зашифрованного текста $$4 \times 5$$. Матричная манипуляция требует изменения символов в примере 4.27 к их числовым значениям (от 00 до 25 ). Обратите внимание, что матричное умножение обеспечивает только перестановку столбцов; чтение и запись в матрицу должны быть обеспечены остальной частью алгоритма.

Криптоанализ шифров перестановки

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

Статистическая атака

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

Атака грубой силы

Ева, чтобы расшифровать сообщение, может попробовать все возможные ключи. Однако число ключей может быть огромно 1! + 2! + 3! + … + L!, где L — длина зашифрованного текста. Лучший подход состоит в том, чтобы попробовать отгадать число столбцов. Ева знает, что число столбцов делится на L. Например, если длина шифра — 20 символов, то $$20 = 1 \times 2 \times 2 \times 5$$. Это означает, что номером столбцов может быть комбинация этих коэффициентов (1, 2, 4, 5, 10, 20). Однако только один столбец и только одна строка — маловероятные варианты.

Пример 4.28

Предположим, что Ева перехватила сообщение зашифрованного текста "EEMYNTAACTTKONSHITZG". Длина сообщения L = 20, число столбцов может быть 1, 2, 4, 5, 10 или 20. Ева игнорирует первое значение, потому что это означает только один столбец и оно маловероятно.

a. Если число столбцов — 2, единственные две перестановки — (1,2) и (2, 1). Первое означает, что перестановки не было. Ева пробует вторую комбинацию. Она делит зашифрованный текст на модули по два символа "EE MY NT AA CT TK ON SH IT ZG". Затем она пробует переставлять каждый модуль из них, получая текст "ee ym nt aa tc kt no hs ti gz", который не имеет смысла.

b. Если номер столбцов — 4, тогда имеется 4! = 24 перестановки. Первая перестановка (1 2 3 4) означает, что не было никакой перестановки. Ева должна попробовать остальные. После испытания всех 23 возможностей Ева находит, что никакой исходный текст при таких перестановках не имеет смысла.

c. Если число столбцов — 5, тогда есть 5! = 120 перестановок. Первая (1 2 3 4 5) означает отсутствие перестановки. Ева должна попробовать остальные. Перестановка (2 5 13 4) приносит плоды — исходный текст "enemyattackstonightz", который имеет смысл после удаления фиктивной буквы z и добавления пробелов.

Атака по образцу

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

1 -й символ в зашифрованном тексте получается из 3 -го символа исходного текста. 2 -й символ в зашифрованном тексте получается из 8 -го символа исходного текста. 20 -й символ в зашифрованном тексте получается из 17 -го символа исходного текста, и так далее. У нас имеются образцы в вышеупомянутом списке. Мы имеем пять групп: (3, 8, 13, 18), (1, 6, 11, 16), (4, 9, 14, 19), (5, 10, 15, 20) и (2, 7, 12, 17). Во всех группах разность между двумя смежными номерами — 5. Эта регулярность может использоваться криптоаналитиком, чтобы взломать шифр. Если Ева знает или может предположить число столбцов (в этом случае оно равняется 5 ), она может преобразовать зашифрованный текст в группы по четыре символа. Перестановка групп может обеспечить ключ к нахождению исходного текста.

Шифры c двойной перестановкой

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

Пример 4.29

Повторим пример 4.26, где использована двойная перестановка. Рисунок 4.25 показывает процесс.

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

13  16	05  07	03  06	10  20	18  04	10  12	01  09	15  17	08  11	19  02

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

4.4. Шифры потока и блочные шифры

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

Шифры потока

В шифрах потока шифрование делается в один момент времени над одним символом (таким, как буква или бит). Мы имеем поток исходного текста, поток зашифрованного текста и поток ключей. Обозначим исходный поток P, поток зашифрованного текста — C и поток ключей — K.

P = P1P2P3,…             
C = C1C2C3,…           
K = (k1k2k3,…)
C1 = Ek1(P1)    
C2 = Ek2(P2) 
C3 = Ek3(P3)…

Рисунок 4.26 показывает идею указанного ранее шифра потока. Символы обычного текста принимаются алгоритмом шифрования по одному. Символы зашифрованного текста также создаются по одному в один и тот же момент времени. Ключевой поток может быть создан многими способами. Это может быть поток с заранее определенными значениями; это может быть только одно значение, используемое алгоритмом. Значения могут зависеть от исходного текста или символов зашифрованного текста. Значения могут также зависеть от предыдущих ключевых значений.

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

Пример 4.30

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

Пример 4.31

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

Пример 4.32

Шифры Виженера — также шифры потока согласно определению. В этом случае ключ потока — повторение m значений, где m. — размер ключевого слова. Другими словами,

K = (k1,k2,….km,k1,k2,……km….)

Пример 4.33

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

Блочные шифры

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

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

Пример 4.34

Шифры Плейфера — блочные шифры. Размер блока — m = 2. Два символа зашифрованы вместе.

Пример 4.35

Шифры Хилла — блочные шифры. Блок исходного текста размера 2 или больше зашифрован, совместно используя единственный ключ (матрицу). В этих шифрах значение каждого символа в зашифрованном тексте зависит от всех значений символов в исходном тексте. Хотя ключ может быть получен из $$m \times m$$. значений, он рассматривается как единственный ключ.

Пример. 4.36

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

Комбинация

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

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

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

Книги

Несколько книг рассматривают классические шифры с симметричным ключом. [Kah96] и [Sin99] дают полную историю этих шифров. [Sti06], [Bar02], [Cou99], [Sta06], [Mao04] и [Garol] приводят хороший анализ технических деталей.

Сайты

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

4.6. Итоги

4.7. Набор для практики

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

Упражнения

NCJAEZRCLASJLYODEPRLYZRCLASJLCPEHZDTOPD

XPALASXYFGFUKPXUSOGEUTKCDGFXANMGNVS

ONHOVEJHWOBEVGWOCBWHNUGBLHGBGR

OTWEWNGWCBPQABIZVQAPMLJGZWTTQVOBQUMAPMIDGZCAB 
EQVBMZLZIXMLAXZQVOQVLMMXAVWEIVLLIZSNZWAB 
JQZLWNLMTQOPBVIUMLGWCBPAEQNBTGTMNBBPMVMAB

OTWEWNGWCBPQABIZVQAPMLJGZWTTQVOBQUMAPMIDGZCAB 
EQVBMZLZIXMLAXZQVOQVLMMXAVWEIVLLIZSNZWAB 
JQZLWNLMTQOPBVIUMLGWCBPAEQNBTGTMNBBPMVMAB

Зашифруйте сообщение "cryptography is fun" ( "криптография — забавно" ), используя этот новый шифр.