Создание электронного обучающего средства по криптографии

     Одним из ярких представителей полиалфавитных шифров является шифр Виженера. Подробное  его описание изложено в главе 2 пункте «2.2.3. Шифр Виженера».

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

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

     Пример:

     Воспользуемся предыдущим примером. Пусть требуется  зашифровать фразу «ВОРОНА СЕЛА НА ВОРОТА», и ключевым словом является слово «ДОМ». Тогда получаем:

     ВОРОНАСЕЛАНАВОРОТА

     +

     ДОМВОРОНАСЕ ЛАНАВОР

     Е ЭЭ РЬ PATЛСТЛВ Ь Р РБР

      1.1.6. Математическая модель шифра замены

     Определим модель Σ_А=(X, K, Y, E, D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответственно: Х А^*, Y B^*, │А│= n, =m. Здесь и далее С^* обозначает множество слов конечной длины в алфавите С. Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентными в шифртексте, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из А^* и В^* соответственно.

     Пусть U={u₁,…,u_N} – множество возможных шифрвеличин, V={v₁,…,v_M} – множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты х Х, y Y можно было представить словами из U^*, V^* соответственно. Требование однозначности расшифрования влечет неравенства N ≥ n, M ≥ m, M ≥ N.

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

     Поскольку M ≥ N, множество V можно представить в виде объединения V= непересекающихся непустых подмножеств V⁽ⁱ⁾. Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V:

     V =

, α = , r N,

и соответствующее  семейство биекций φ_α : U → { }, для которых φ_α(u_i) = , i =

     Рассмотрим  также произвольное отображение  ψ: К × N → N_r^*, где N_r={1,2,…,r}, такое, что для любых k K, l N

     ψ(k, l) =

, N_r, j = .

     Назовем последовательность ψ(k, l) распределителем, отвечающим данным значениям k K, l N.

     Теперь  мы сможем определить правило зашифрования произвольного шифра замены. Пусть x X, x = x₁…x_l, x U, i = ; k K и ψ(k, l) = . Тогда Е_к(х) = y, где y = y₁…y_l, y_j (x_j), j = .

     В качестве y_j можно выбрать любой элемент множества (x_j). Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого рандомизатора типа игровой рулетки. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, так как = при i ≠ j.

      1.1.7. Классификация шифров замены

     Если  ключ зашифрования совпадает с ключом расшифрования: k₃=k_p, то такие шифры называют симметричными, если же k₃≠k_p – ассиметричными.

     В связи с указанным различием  в использовании ключей сделаем  еще один шаг в классификации:

     

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

     Для однозначных шифров замены справедливо свойство: ;

для многозначных шифров замены: .

     

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

     Если  для некоторого числа q N выполняются включения v_i B^q, i= , то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае – шифром разнозначной замены.

     

     В подавляющем большинстве случаев  используются шифры замены, для которых , для некоторого p N. При р = 1 говорят о поточных шифрах замены, при р > 1 – о блочных шифрах замены.

     

     Следующее определение. В случае r = 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены.

      

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

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

      1.1.8. Поточные шифры простой замены

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

     Помимо  явного задания (в виде двустрочной  записи) ключ может быть задан некоторой  формулой, как, например, для определяемого  ниже шифра Цезаря (который иногда также называют сдвиговым шифром) и аффинного шифра. При использовании этих шифров буквы алфавита А удобно отождествлять с их порядковыми номерами, так что, например, для латинского алфавита: a ≡ 0, b ≡ 1,…,z ≡ 25.

     Шифр  Цезаря

     X = Y = , K = Z₂₆. Для x = (x₁,…, x_l), y = (y₁,…, y_l), k K полагаем

     y = E_k(x) = (x₁ + k,…, x_l + k), x = D_k(y)= (y₁ + (26 – k),…,y_l+(26 – k)),

где + и  · – операции кольца вычетов  Z₂₆.

     Аффинный  шифр

     X = Y = , . Для k=(α, β) K, α ≠ 0, x = (x₁,…, x_l), y = (y₁,…, y_l), полагаем

y = E_k(x) =( α·x₁ + β,…, α·x_l + β), x = D_k(y)= (y₁ + (26 – β)·α^-1,…,y_l+(26 – β)·α^-1),

где + и  · – операции кольца Z₂₆, а α^-1 – элемент из мультипликативной группы , обратный к α.

     Пример:

     Зашифруем слово CRYPTOGRAPHY с помощью аффинного шифра, полагая k = (3,5). Данный ключ индуцирует следующую подстановку на Z₂₆: 

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

5 8 11 14 17 20 23 0 3 6 9 12 15 

13 14 15 16 17 18 19 20 21 22 23 24 25

18 21 24 1 4 7 10 13 16 19 22 25 2 

     Если  декодировать числа в буквы, то получим  следующее соответствие для букв:

A B C D E F G H I J K L M

F I L O R U X A D G J M P 

N O P Q R S T U V W X Y Z

S V Y B E H K N Q T W Z C 

     Слову CRYPTOGRAPHY соответствует числовая последовательность х=(2,17,24,15,19,14,9,17,0,15,7,24). Зашифровать открытый текст мы можем двумя способами. Во-первых, можно воспользоваться полученной подстановкой, заменяя каждую букву слова (найденную в верхней строке) ее образом в нижней строке: LEZYKVXEFYAZ. Во-вторых, можно вычислить значение функции зашифрования E_k(x), исходя из ее определения:

y = E_k(x) = (3·2 + 5, 3·17 + 5, 3·24 + 5, 3·15 + 5, 3·19 + 5, 3·14 + 5,

     3·9 + 5, 3·17 + 5, 3·0 + 5, 3·15 + 5, 3·7 + 5, 3·24 + 5)=

     =(11,4,25,24,10,21,23,4,5,24,0,25).

     В буквенном эквиваленте y совпадает с полученным ранее шифрованным текстом.

     Для расшифрования у следует вычислить 3^-1 в группе . Очевидно, что 3^-1=9. Теперь расшифруем у в соответствии с определением правила расшифрования: x = D_k(y)=((11+21) ·9, (4+21) ·9, (25+21)·9, (24+21) ·9, (10+21) ·9, (21+21) ·9, (23+21) ·9, (4+21) ·9, (5+21) ·9, (24+21) ·9, (0+21) ·9, (25+21) ·9) = (2,17,24,15,19,14,6,17,0,15,7,24).

     Здесь мы воспользовались определением операций сложения и умножения в кольце Z₂₆, заменяя результат обычных целочисленных вычислений остатком от деления на 26.

      1.1.9. Блочные шифры простой замены

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

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

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

     Буквы биграммы (i, j), i ≠ j (являющейся шифрвеличиной) находятся в данной таблице. При зашифровании биграмма (i, j) заменяется биграммой (k,l), где k и l определяются в соответствии с правилами 1-3.

1. Если i и j не лежат в одной строке или одном столбце, то их позиции образуют противоположные вершины прямоугольника. Тогда k и l – другая пара вершин, причем k – вершина, лежащая в той же строке, что и i.
2. Если i и j лежат в одной строке, то k и l – буквы той же строки, расположенные непосредственно справа от i и j соответственно. При этом если одна из букв – последняя в строке, то считается, что ее «правым соседом» является первая буква той же строки.
3. Аналогично, если i и j лежат в одном столбце, то они заменяются их «соседями снизу».