Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра. Понятие стойкости шифра является центральным для криптографии. Важнейшим для развития криптографии был результат К. Шеннона о существовании и единственности абсолютно стойкого шифра. Но абсолютно стойкий шифр на практике, как правило, неприменим, поэтому для защиты своей информации законные пользователи вынуждены применять неабсолютно стойкие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты, то есть противник с неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр. Вопрос только в том, хватит ли у него сил, средств и времени для разработки и реализации соответствующих алгоритмов.
В этой ситуации желательно, получить теоретическую оценку стойкости, то есть, например, доказать, что никакой противник не сможет вскрыть выбранный шифр, скажем, за 10. К сожалению, математическая теория еще не дает нужных теорем — они относятся к нерешенной проблеме нижних оценок вычислительной сложности задач.
Поэтому у пользователя остается единственный путь — получение практических оценок стойкости. Этот путь состоит в том, чтобы определить от какого противника мы собираемся защищать информацию, а также какие силы и средства он сможет применить для его вскрытия. Затем, мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра, а наилучший из этих алгоритмов использовать для практической оценки стойкости шифра. В общем случае все оценки стойкости системы должны вестись в предположении, что криптоаналитику известен алгоритм шифрования, но он незнает ключа на котором зашифровано конкретное сообщение. Противник также может знать некоторые характеристики открытых текстов, например, общую тематику сообщений, некоторые стандарты, форматы и т. д.
|
|
Итак, стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации криптоаналитиков, атакующих шифр. Такую процедуру иногда называют проверкой стойкости. Имеется несколько показателей криптостойкости, среди которых основные:
² количество всех возможных ключей;
² среднее время, необходимое для кpиптоанализа.
В данной работе мы будем защищатся от пассивной атаки с известной шифрограммой, когда противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов. Задача криптоаналитика заключается с том, чтобы раскрыть исходные тексты и вычислить ключ.
Для этого рекомендуется использовать один из двух простейших методов вскрытия шифра
1. Статистическую атаку.
2. Силовую атаку.
Рассмотрим в чем они состоят.
Криптоаналитическая статистическая атака
Криптоаналитическая статистическаяатака применима толькопротив систем одноалфавитной замены, главным недостатком которых является возможность взлома шифртекста на основе анализа частот появления букв. Такая атаканачинается с подсчета частот появления символов:
² определяется число появлений каждой буквы в шифртексте.
² полученное распределение частот букв в шифртексте сравнивается с распределением частот букв в алфавите исходных сообщений, например в английском.
|
|
² буква с наивысшей частотой появления в шифртексте заменяется на букву с наивысшей частотой появления в английском языке и т.д.
По закону больших чисел вероятность успешного вскрытия системы шифрования повышается с увеличением длины шифртекста.
Силовая атака
Силовая атака заключается в подборе ключа шифрования путем перебора подряд всех возможных ключей вплоть до нахождения истинного. В отличие от всех других методов эта атака применима для всех типов шифров, но она имеет максимальную сложность реализации и, соответственно, требует максимальных затрат времени и средств.
Алгоритм криптоанализа заключается в следующем: определяется множество всех возможных ключей шифрования для данной криптосистемы и для каждого ключа выполняются шаги:
² Дешифрование известного шифртекста на этом ключе;
² Анализ «осмысленности» полученного предполагаемого открытого текста, например путем поиска соответствующих слов в словаре возможных сообщений;
² Принятие решения об истинности найденного ключа на основе результатов предыдущих шагов дешифрования.
Данный метод работает тем медленнее, чем больше длина шифртекста, используемого для криптоанализа.
Задания
3.1. Лабораторная работа №1
Тема: симметричные криптосистемы.
Цель работы: Разработать криптографическую защиту информации, содержащейся в файле данных, с помощью алгоритма шифрования, указанного в варианте. Для этого:
1. Разработать алгоритмы шифрования и дешифрования блока (потока) открытого текста заданной длины из алфавита Z n на заданном ключе с помощью метода, указанного в варианте(Если это позволяет алгоритм, длину блока взять кратной 8 бит).
|
|
2. Определить алфавит криптосистемы (открытого текста и шифртекста). Если алфавит не задан в варианте, выбрать его самостоятельно, так, чтобы он включал в себя символы используемого в примере открытого текста. Например, русский, английский, ASCII. Поставить символам исходного алфавита в соответствие символы из алфавита Z n (n – основание алфавита).
3. Написать программу генерации случайных ключей шифра, оценить размерность ключевого пространства.
4. Написать програму, реализующую шифрование на заданном ключе открытого текста, состоящего из символов заданного алфавита. Открытый текст, ключ и шифртекст должны быть представлены отдельными файлами.
5. Написать програму для реализации алгоритма дешифрования полученного файла шифртекста при известном ключе.
6. Провести тестирование программ
- на коротких тестовых примерах.
- на текстах в несколько страниц
3.2. Лабораторная работа №2
Тема: криптоанализ симметричных криптосистем.
Провести эксперимент по определению практической стойкости, алгоритма, разработанного в лабораторной работе №1.
Считать, что противнику известен алгоритм шифрования. Выбрать наилучший с его точки зрения алгоритм подбора ключа и обосновать свой выбор. Использовать методы:
² анализа статистических свойств шифртекста (частот появления букв).
² силовую атаку (полный перебор ключей).
² другие (если есть более эффективные)
С помощью программы, реализующей выбранный алгоритм криптоанализа провести экперимент по вскрытию шифртекстов различного размера.
При использовании статистического криптоанализа использовать таблицы, приведенные в приложении или подсчитать частоты появления букв используемого алфавита в тексте, частью которого является текст примера.
Для проверки на «осмысленность» полученного текста создать мини-словарь из части слов, встречающихся в тексте примера.
Построить графики зависимости времени криптоанализа от параметров алгоритма шифрования (длины или других параметров ключа, размера шифртекста или др., в зависимости от алгоритмов шифрования и криптоанализа).
В результате эксперимента определить параметры алгоритма шифрования (размер передаваемого текста, размер и характеристики ключа, объем ключевого пространства и другие параметры алгоритма шифрования), необходимые для практической криптостойкости разработанного в лабораторной работе №1 алгоритма ширования.
Практической криптостойкостью в данной работе будем считать невозможность взлома шифра противником, имеющим в распоряжении один ПК мощности, равной мощности компьютера, на котором делалась работа и один час времени.
3.3. Лабораторная работа №3
Тема: Криптографические протоколы на основе асимметричных криптосистем..
Разработать алгоритмы, реализующие криптографические протоколы (см. вариант) взаимодействия удаленных абонентов на основе асимметричных криптосистем.
Написать программы, реализующие эти протоколы для всех участников. Значения модуля криптосистемы выбирать не менее 50 бит. Для вычислений с большими числами можно использовать специальные программы.
Для проверки чисел на простоту использовать комбинированный алгоритм на основе тестов Леманна или Рабина-Миллера
Хеширование выполнять на основе любого блочного симметричного алгоритма (например с использованием сети Фейстеля или алгоритма из предыдущих лаб. работ) по одной из схем, данных в лекциях.
Проверить правильность выполнения протокола для малых значений параметров криптосистемы (контрольный пример).
Продемонстрировать выполнение протокола для нормальных значений параметров криптосистемы.
Варианты
К лабораторным работам № 1-2
Основные варианты:
Вариант 1. Шифрующие таблицы с числовым ключом
Вариант 2. Шифр Гронсфельда с ключевым словом
Вариант 3. Алгоритм, реализующий идею «диска Альберти» для русского алфавита
Вариант 4. Шифр Цезаря с ключевым словом
Вариант 5. Шифрующие таблицы с перестановкой по ключу –размеру таблицы.
Вариант 6. Полибианский квадрат для русского алфавита.
Вариант 7. Шифр Гронсфельда с числовым ключом
Вариант 8. Шифр Кардано без поворотов.
Вариант 9. Шифр Плейфера
Вариант 10. Шифрующие таблицы с ключевым словом
Вариант 11. Шифр Цезаря многоалфавитный
Вариант 12. Шифр гаммирования с линейным конгруэнтным генератором ключей
Вариант 13. Аффинная система подстановок Цезаря
Вариант 14. Шифр Вижинера с числовым ключом
Вариант 15. Шифр Хилла для 3-грамм
Вариант 16. Шифрующие таблицы Трисемуса
Вариант 17. Шифр Вернама.
Вариант 18. Алгоритм, реализующий идею «диска Альберти» для английского алфавита
Вариант 19. Шифр Вижинера с ключевым словом
Вариант 20. Шифр гаммирования с генератором ключей на основе датчика случайных чисел
Вариант 21. Полибианский квадрат для английского алфавита.
Вариант 22. Шифрующие таблицы с двойной перестановкой по ключевому слову.
Вариант 23. Шифр Уинстона
Вариант 24. Шифрующие таблицы с двойной перестановкой по числовому ключу.
Дополнительные варианты ( повышенной сложности ):
Вариант 25. Магические квадраты
Вариант 26. Шифр Кардано с поворотами.
К лабораторной работе № 3
1. Протокол обмена секретным документом комбинированным методом шифрования на основе криптосистемы RSA.
2. Протокол двустороннего подписания контракта на основе алгоритма цифровой подписи ГОСТ Р 34.10-94.
3. Протокол обмена несекретным документом с цифровой подписью на основе алгоритма RSA.
4. Протокол обмена секретным документом, зашифрованным с помощью алгоритма RSA.
5. Протокол идентификации абонента с помощью алгоритма цифровой подписи DSA.
6. Протокол обмена несекретным документом с невидимой цифровой подписью на основе алгоритма RSA.
7. Протокол византийского соглашения для трех участников на основе схемы Шамира проверяемого разделения секрета.
8. Протокол генерации сеансового секретного ключа на основе криптосистемы RSA.
9. Протокол обмена несекретным документом с цифровой подписью на основе алгоритма Эль Гамаля.
10. Протокол обмена несекретным документом со слепой цифровой подписью на основе алгоритма RSA.
11. Протокол аутентификации Шнорра.
12. Протокол идентификации абонента с помощью алгоритма цифровой подписи RSA.
13. Протокол двустороннего подписания контракта на основе алгоритма цифровой подписи Эль Гамаля.
14. Протокол вычисления ключа доступа при разделении секрета между тремя участниками по схеме Шамира проверяемого разделения секрета.
15. Протокол обмена несекретным документом с цифровой подписью DSA.
16. Протокол двустороннего подписания контракта на основе алгоритма цифровой подписи RSA.
17. Протокол обмена несекретным документом с цифровой подписью на основе алгоритма ГОСТ Р 34.10-94.
18. Протокол обмена секретным документом с цифровой подписью на основе алгоритма RSA.
19. Протокол идентификации абонента с помощью алгоритма цифровой подписи ГОСТ Р 34.10-94.
20. Протокол «подбрасывания монеты по телефону».
21. Протокол экпоненциального ключевого обмена по методу Диффи-Хеллмана.
22. Протокол вычисления дискретного логарифма со скрытием информации от оракула.
23. Протокол обмена секретным документом комбинированным методом шифрования на основе экпоненциального ключевого обмена по методу Диффи-Хеллмана.
24. Протокол двустороннего подписания контракта на основе алгоритма цифровой подписи DSA.
25. Протокол идентификации абонента с помощью алгоритма цифровой подписи Эль Гамаля.
26. Протокол обмена секретным документом, зашифрованным с помощью алгоритма Эль Гамаля.
Приложение.
Приложение 1: Таблица вероятностей букв в русских текстах.
| буква | пробел | о | еилиё | а | и | н | т | с | р | в | л |
| вер-ть | 0,175 | 0,090 | 0,072 | 0,062 | 0,062 | 0,053 | 0,053 | 0,045 | 0,040 | 0,038 | 0,035 |
| буква | к | м | д | п | у | я | з | ы | б | ||
| вер-ть | 0,028 | 0,026 | 0,025 | 0,023 | 0,021 | 0,018 | 0,016 | 0,016 | 0,014 | 0,014 | 0,013 |
| буква | ъили ь | г | х | ж | ш | ю | ц | щ | э | ф | |
| вер-ть | 0,012 | 0,010 | 0,009 | 0,007 | 0,006 | 0,006 | 0,004 | 0,003 | 0,003 | 0,002 |
Приложение 2. Таблица вероятностей букв в английских текстах.
| буква | пр-л | е | t | а | о | n | i | s | r |
| вер-ть | 0,185 | 0,097 | 0,076 | 0,064 | 0,062 | 0,057 | 0,056 | 0,052 | 0,047 |
| буква | h | l | d | с | u | p | f | м | w |
| вер-ть | 0,04 | 0,031 | 0,028 | 0,025 | 0,018 | 0,018 | 0,018 | 0,017 | 0,016 |
| буква | y | в | g | v | к | q | x | j | z |
| вер-ть | 0,015 | 0,013 | 0,013 | 0,007 | 0,039 | 0,002 | 0,002 | 0,001 | 0,001 |