Лабораторная работа № 2. Криптоанализ методов простой подстановки
Простейшие шифры подстановки (substitution) реализуют замену каждого символа исходного текста на один из символов алфавита шифротекста. В общем случае подстановочный шифр описывается таблицей подстановки, состоящей из двух строк и n столбцов. Количество столбцов таблицы подстановки соответствует количеству различных символов в алфавите исходного текста. Верхняя строка таблицы подстановки содержит все возможные символы исходного текста, а нижняя – соответствующие им символы шифротекста.
Моноалфавитные шифры характеризуются однозначным соответствием символов исходного текста и символов шифротекста. В случае когда алфавиты исходного текста и шифротекста состоят из одного и того же множества символов, алфавит шифротекста представляет собой простую перестановку лексикографического порядка символов в алфавите исходного текста. При выполнении шифрования каждый символ исходного текста заменяется соответствующим ему символом шифротекста.
Таблица подстановки, описывающая моноалфавитный шифр, преобразующий строчные буквы русского алфавита, будет состоять из 33 столбцов, что соответствует количеству букв в алфавите. Рассмотрим такую таблицу на следующем примере:
| а | б | в | г | д | е | ё | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ъ | ы | ь | э | ю | я |
| е | л | ц | н | й | и | в | а | ш | у | ь | т | с | я | ф | ы | э | ж | о | р | к | ч | м | ъ | х | п | м | б | г | ё | з | щ | д |
В соответствии с приведённой таблицей шифрование строки
«знание – сила» будет выполнено следующим образом:
«з» → «ш»;
«н» → «ф»;
…
«a» → «e».
В результате шифрования будет получен шифротекст «шфефуи – оусе».
Таблица подстановки, описывающая ключ моноалфавитного шифра, преобразующего ASCII-коды (однобайтовые значения), будет состоять из 256 столбцов. Таблица подстановки для шифра, осуществляющего подстановку 32-битных значений, будет состоять из 232 столбцов, что уже вызовет сложности её хранения и передачи. По этой причине на практике вместо таблиц подстановок используются функции подстановки, аналитически описывающие соответствие между порядковыми номерами символов исходного текста в алфавите исходного текста и порядковыми номерами символов шифротекста в алфавите шифротекста.
Предположим, алфавит исходного текста М состоит из n символов
М= { a 0, a 1, ..., an }, тогда алфавит шифротекста C будет представлять собой
n- символьный алфавит С= { f (a 0), f (a 1), ..., f (an)}, где функция f, выполняющая отображение М ® C, и будет являться функцией подстановки. В общем случае функция подстановки любого моноалфавитного шифра может быть задана в виде полинома степени t:
Ek (a) = (k 0 + k 1∙ a + k 2∙ a 2 +... + kt –1∙ at –1+ kt ∙ at) mod n. (1)
Примеры простейших моноалфавитных шифров простой подстановки:
Шифр Цезаря. Строки таблицы подстановки для шифра Цезаря представляют собой сдвинутые друг относительно друга на l позиций алфавиты исходного текста. Сам Цезарь использовал для шифрования величину сдвига l = 3. Функция подстановки для шифра Цезаря будет задаваться полиномом нулевой степени:
Ek (a) = (a + k) mod n. (2)
Атбаш
Шифр простой замены, использованный для еврейского алфавита и получивший оттуда своё название. Шифрование происходит заменой первой буквы алфавита на последнюю, второй на предпоследнюю (алеф (первая буква) заменяется на тав (последнюю), бет (вторая) заменяется на шин (предпоследняя); из этих сочетаний шифр и получил своё название). Шифр Атбаш для английского алфавита:
| Исходный алфавит: | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
| Алфавит замены: | Z Y X W V U T S R Q P O N M L K J I H G F E D C B A |
Шифр с использованием кодового слова
Шифр с использованием кодового слова является одним из самых простых как в реализации, так и в расшифровывании. Идея заключается в том, что выбирается кодовое слово, которое пишется впереди, затем выписываются остальные буквы алфавита в своем порядке. Шифр с использованием кодового слова WORD.
| Исходный алфавит: | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
| Алфавит замены: | W O R D A B C E F G H I J K L M N P Q S T U V X Y Z |
Как мы видим, при использовании короткого кодового слова мы получаем очень и очень простую замену. Также мы не можем использовать в качестве кодового слова с повторяющимися буквами, так как это приведёт к неоднозначности расшифровки, то есть двум различным буквам исходного алфавита будет соответствовать одна и та же буква шифрованного текста.
Поскольку для моноалфавитных шифров каждый символ исходного текста при шифровании может заменяться одним единственным символом шифротекста, для криптоанализа данных шифров возможно применение анализа частот встречаемости символов в шифротексте. Данная атака основана на том факте, что в естественных языках частоты встречаемости различных букв могут существенно отличаться. Так, в английском языке наиболее часто встречаемой является буква «e», а наименее встречаемой – буква «z». Зная типичную частоту встречаемости каждого из символов алфавита исходного текста, можно воссоздать использованную при шифровании таблицу постановки, ставя каждому из символов исходного текста в соответствие символ шифротекста, частота встречаемости которого в зашифрованном тексте является наиболее близкой к типичной частоте встречаемости символа алфавита исходного текста.
Подстановочные шифры, называемые полиалфавитными, используют более чем одну таблицу подстановки. Использование нескольких таблиц (алфавитов) обеспечивает возможность нескольких вариантов подстановки символов исходного сообщения, что повышает криптостойкость шифра.
Классическим полиалфавитным шифром является шифр Виженера (Vigenere Cipher). Так же как и в случае шифра Цезаря, данный шифр может быть задан таблицами подстановки, состоящими из n столбцов, где n – размер алфавита исходного текста. Количество таблиц подстановки для случая шифра Виженера будет равняться m, где m – длина ключевого слова (период ключа). Ключевое слово задаёт количество символов, на которое смещены относительно исходного алфавиты шифротекста в каждой из m таблиц подстановок.
Рассмотрим работу шифра Виженера на простом примере. Пусть дано ключевое слово «MOUSE». Тогда правила подстановки будут задаваться 5-ю таблицами, которые для компактности можно объединить в одну.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L |
| O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N |
| U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T |
| S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R |
| E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D |
Пусть необходимо зашифровать текст «CRYPTOGRAPHY AND DATA SECURITY». Сперва запишем символы ключевого слова под символами исходного текста. Поскольку ключ в методе Виженера – периодический, повторим ключевое слово столько раз, сколько нам потребуется, чтобы закрыть весь исходный текст.
CRYPTOGRAPHY AND DATA SECURITY
MOUSE MOUSEMOUSEMOUSEMOUSEMOUSE
Каждый из символов ключа указывает, которую из таблиц подстановки нам необходимо использовать для подстановки рассматриваемого символа исходного текста. Символ ключа «M» указывает, что соответствующий символ шифротекста необходимо выбирать из таблицы подстановки, алфавит шифротекста в которой сдвинут относительно алфавита исходного текста на
Pos(«M») – Pos(«A») = 12 позиций. Таким образом, первому символу исходного текста будет соответствовать символ шифротекста «C». Проведя аналогичную процедуру для всех символов исходного текста, получим искомый шифротекст:
«OFSHXAULSTTM SRP XSXM MWGGFCLC».
Как видно из примера, в результате шифрования по методу Виженера символы исходного текста «P» и «H» были преобразованы в один и тот же подстановочный элемент «T». Таким образом, отсутствует однозначное соответствие между символами исходного и зашифрованного текстов, что делает применение атаки на шифротекст путём частотного анализа «в лоб» невозможным.
Поскольку ключ шифратора Виженера является периодическим, зашифрованный текст можно представить как m текстов, зашифрованных по методу Цезаря. В рассмотренном примере для текста «CRYPTOGRAPHY AND DATA SECURITY» символы с позициями 1, 6,..., 26 шифровались по методу Цезаря с ключом k = 12; символы с позициями 2, 7,..., 27 – ключом k = 14; с позициями 3, 8,..., 28 – ключом k = 20; с позициями 4, 9,..., 29 – ключом k = 18; с позициями 5, 10,..., 30 – ключом k = 4.
C RYPT O GRAP H Y AN D DAT A SEC U RITY
k = 12 («M»): C O H D A U
k = 14 («O»): R G Y - - R
k = 20 («U»): Y R - D S I
k = 18 («S»): P A A A E T
k = 4 («E»): T P N T C Y
Таким образом, зная длину ключевого слова шифра Виженера (период ключа), можно произвести взлом шифротекста, выполнив анализ частот встречаемости символов в отдельности для каждого из m компонентов шифротекста.
Одним из методов определения длины ключевого слова, использованного при шифровании текста по методу Виженера, является метод Касиски (Kasiski).
Данный метод основан на предположении, что наличие повторяющихся
l -грамм (l -символьных последовательностей) в зашифрованном тексте будет в большинстве случаев обусловлено наличием соответствующих повторяющихся l -грамм в исходном тексте. Предполагается, что случайное появление в шифротексте повторяющихся l -грамм маловероятно.
Одинаковым l -граммам, присутствующим в исходном тексте, будут соответствовать одинаковые l -граммы, расположенные на тех же позициях в шифротексте, только в том случае, если при шифровании они будут преобразованы с использованием тех же l символов ключа. Это условие будет выполняться для всех повторяющихся l -грамм, расположенных друг от друга на расстояниях, кратных длине ключевого слова шифра.
Тест Касиски состоит из следующих шагов:
1. Анализируется шифротекст на предмет присутствия в нём повторяющихся l -грамм.
2. Для каждой из встретившихся в шифротексте более одного раза
l -граммы вычисляются расстояния между её соседними вхождениями.
3. Вычисляется наибольший общий делитель полученного на предыдущем шаге множества расстояний с учётом того, что среди найденных повторений l -грамм могут в незначительном количестве присутствовать случайные повторения. Полученное значение и будет являться длиной ключевого слова.
Эксперименты показывают, что данный метод является достаточно эффективным при анализе зашифрованных текстов на русском и английском языках в случае, если в тексте присутствуют повторяющиеся l -граммы длиной в три и более символов.
Задания
1. Реализовать программное средство, осуществляющее шифрование и дешифрование текстового файла с использованием шифров простой замены, содержащего текст на заданном языке. Реализовать подбор ключа.
Вариант 1. Шифр Цезаря. Английский алфавит.
Вариант 2. Шифр Цезаря. Русский алфавит.
Вариант 3. Атбаш. Английский алфавит.
Вариант 4. Атбаш. Русский алфавит.
Вариант 5. Шифр с использованием кодового слова. Английский алфавит.
Вариант 6. Шифр с использованием кодового слова. Русский алфавит.
2. Реализовать программное средство, реализующее шифрование текста по методу Вижинера.
3. Реализовать программное средство, осуществляющее криптоанализ зашифрованного по методу Виженера текста. Для криптоанализа использовать тест Касиски.
4. Провести экспериментальное исследование зависимости вероятности успешного проведения атаки по методу Касиски от длины шифротекста.
5. Провести экспериментальное исследование зависимости вероятности успешного проведения атаки по методу Касиски от длины использованного при шифровании ключевого слова.
ПРИЛОЖЕНИЕ 1. Частотность букв английского языка.
| A 0.08167 B 0.01492 C 0.02782 D 0.04253 E 0.12702 F 0.0228 G 0.02015 | H 0.06094 I 0.06966 J 0.00153 K 0.00772 L 0.04025 M 0.02406 N 0.06749 | O 0.07507 P 0.01929 Q 0.00095 R 0.05987 S 0.06327 T 0.09056 U 0.02758 | V 0.00978 W 0.0236 X 0.0015 Y 0.01974 Z 0.00074 |
ПРИЛОЖЕНИЕ 2. Частотность букв русского языка.
| А 0.07821 Б 0.01732 В 0.04491 Г 0.01698 Д 0.03103 Е 0.08567 Ё 0.0007 | Ж 0.01082 З 0.01647 И 0.06777 Й 0.01041 К 0.03215 Л 0.04813 М 0.03139 | Н 0.0685 О 0.11394 П 0.02754 Р 0.04234 С 0.05382 Т 0.06443 У 0.02882 | Ф 0.00132 Х 0.00833 Ц 0.00333 Ч 0.01645 Ш 0.00775 Щ 0.00331 Ъ 0.00023 | Ы0.01854 Ь 0.02106 Э 0.0031 Ю 0.00544 Я 0.01979 |