 |
|
Криптоанализ методов простой подстановки
Содержание
1. Криптоанализ методов простой подстановки. 4
Задания. 7
2. Потоковые криптосистемы.. 9
Задания. 13
3. Роторные криптосистемы.. 14
Задания. 17
4. Симметричные криптосистемы. Алгоритм IDEA.. 18
Задания. 21
5. Арифметика чисел большой разрядности. 22
Алгоритм сложения. 22
Алгоритм умножения. 22
Деление. 24
Задания. 25
6. Асимметричные криптосистемы. Алгоритм RSA.. 26
Задания. 29
7. Электронная цифровая подпись. 30
Алгоритм безопасного хеширования SHA-1. 30
Алгоритм цифровой подписи RSA.. 32
Задания. 34
8. Криптосистемы на основе эллиптических кривых. 35
Алгоритм обмена ключами в эллиптической группе. 37
Алгоритм ЭЦП на основе эллиптических кривых (ECDSA) 37
Задания. 38
Криптоанализ методов простой подстановки
Простейшие шифры подстановки (substitution) реализуют замену каждого символа исходного текста на один из символов алфавита шифротекста. В общем случае подстановочный шифр описывается таблицей подстановки, состоящей из двух строк и n столбцов. Количество столбцов таблицы подстановки соответствует количеству различных символов в алфавите исходного текста. Верхняя строка таблицы подстановки содержит все возможные символы исходного текста, а нижняя – соответствующие им символы шифротекста.
Моноалфавитные шифры характеризуются однозначным соответствием символов исходного текста и символов шифротекста. В случае когда алфавиты исходного текста и шифротекста состоят из одного и того же множества символов, алфавит шифротекста представляет собой простую перестановку лексикографического порядка символов в алфавите исходного текста. При выполнении шифрования каждый символ исходного текста заменяется соответствующим ему символом шифротекста.
Таблица подстановки, описывающая моноалфавитный шифр, преобразующий строчные буквы русского алфавита, будет состоять из 33 столбцов, что соответствует количеству букв в алфавите. Рассмотрим такую таблицу на следующем примере:
| а | б | в | г | д | е | ё | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ъ | ы | ь | э | ю | я |
| е | л | ц | н | й | и | в | а | ш | у | ь | т | с | я | ф | ы | э | ж | о | р | к | ч | м | ъ | х | п | м | б | г | ё | з | щ | д |
В соответствии с приведённой таблицей шифрование строки
«знание – сила» будет выполнено следующим образом:
«з» → «ш»;
«н» → «ф»;
…
«a» → «e».
В результате шифрования будет получен шифротекст «шфефуи – оусе».
Таблица подстановки, описывающая ключ моноалфавитного шифра, преобразующего ASCII-коды (однобайтовые значения), будет состоять из 256 столбцов. Таблица подстановки для шифра, осуществляющего подстановку 32-битных значений, будет состоять из 232 столбцов, что уже вызовет сложности её хранения и передачи. По этой причине на практике вместо таблиц подстановок используются функции подстановки, аналитически описывающие соответствие между порядковыми номерами символов исходного текста в алфавите исходного текста и порядковыми номерами символов шифротекста в алфавите шифротекста.
Предположим, алфавит исходного текста М состоит из n символов
М={a0, a1, ..., an}, тогда алфавит шифротекста C будет представлять собой
n-символьный алфавит С={f(a0), f(a1), ..., f(an)}, где функция f, выполняющая отображение М®C, и будет являться функцией подстановки. В общем случае функция подстановки любого моноалфавитного шифра может быть задана в виде полинома степени t:
Ek(a) = (k0 + k1∙a + k2∙a2 + ... + kt–1∙at–1+ kt∙at) mod n. (1)
Примером простейшего моноалфавитного шифра является шифр Цезаря. Строки таблицы подстановки для шифра Цезаря представляют собой сдвинутые друг относительно друга на l позиций алфавиты исходного текста. Сам Цезарь использовал для шифрования величину сдвига l = 3. Функция подстановки для шифра Цезаря будет задаваться полиномом нулевой степени:
Ek(a) = (a + k) mod n. (2)
Поскольку для моноалфавитных шифров каждый символ исходного текста при шифровании может заменяться одним единственным символом шифротекста, для криптоанализа данных шифров возможно применение анализа частот встречаемости символов в шифротексте. Данная атака основана на том факте, что в естественных языках частоты встречаемости различных букв могут существенно отличаться. Так, в английском языке наиболее часто встречаемой является буква «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
MOUSEMOUSEMOUSEMOUSEMOUSEMOUSE
Каждый из символов ключа указывает, которую из таблиц подстановки нам необходимо использовать для подстановки рассматриваемого символа исходного текста. Символ ключа «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.
CRYPTOGRAPHY AND DATA SECURITY
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. Реализовать программное средство, осуществляющее шифрование и дешифрование текстового файла, содержащего текст на заданном языке.
2. Реализовать программное средство, осуществляющее криптоанализ зашифрованного по методу Виженера текста. Для криптоанализа использовать тест Касиски.
3. Провести экспериментальное исследование зависимости вероятности успешного проведения атаки по методу Касиски от длины шифротекста.
4. Провести экспериментальное исследование зависимости вероятности успешного проведения атаки по методу Касиски от длины использованного при шифровании ключевого слова.
ПРИЛОЖЕНИЕ 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 |