Современные алгоритмы шифрования. Шифрование и шифры. ENLiGHT Project
Модели криптографических систем
Шифротекст - результат операции шифрования. Часто также используется вместо термина «криптограмма», хотя последний подчёркивает сам факт передачи сообщения, а не шифрования.
Процесс применения операции шифрования к шифротексту называется перешифровкой.
Свойства шифротекста
При рассмотрении шифротекста как случайной величины , зависящей от соответствующих случайных величин открытого текста X и ключа шифрования Z, можно определить следующие свойства шифротекста:
· Свойство однозначности шифрования:
· Из цепных равенств следует
(из свойства однозначности расшифрования)
(из принципа независимости открытого текста от ключа и свойства однозначности шифрования)тогда
это равенство используется для вывода формулы расстояния единственности.
· Для абсолютно надёжной криптосистемы
То есть
Использование для криптоанализа
Шеннон в статье 1949 года «Теория связи в секретных системах» показал, что для некоторого случайного шифра теоретически возможно (используя неограниченные ресурсы) найти исходный открытый текст, если известно букв шифротекста, где - энтропия ключа шифра, r - избыточность открытого текста (в том числе с учётом контрольных сумм и т. д.), N - объём используемого алфавита.
Шифрование - обратимое преобразование информации в целях сокрытия от неавторизованных лиц, с предоставлением, в это же время, авторизованным пользователям доступа к ней. Главным образом, шифрование служит задачей соблюдения конфиденциальности передаваемой информации. Важной особенностью любого алгоритма шифрования является использование ключа, который утверждает выбор конкретного преобразования из совокупности возможных для данного алгоритма.
В целом, шифрование состоит из двух составляющих - зашифрование и расшифрование.
С помощью шифрования обеспечиваются три состояния безопасности информации:
· Конфиденциальность: шифрование используется для скрытия информации от неавторизованных пользователей при передаче или при хранении.
· Целостность: шифрование используется для предотвращения изменения информации при передаче или хранении.
· Идентифицируемость: шифрование используется для аутентификации источника информации и предотвращения отказа отправителя информации от того факта, что данные были отправлены именно им.
Зашифрование и расшифрование
Как было сказано, шифрование состоит из двух взаимно обратных процессов: зашифрование и расшифрование. Оба этих процесса на абстрактном уровне представимы математическими функциями, к которым предъявляются определенные требования. Математически данные, используемые в шифровании, представимы в виде множеств, над которыми построены данные функции. Иными словами, пусть существуют два множества, представляющее данные - M и C; и каждая из двух функций(шифрующая и расшифровывающая) является отображением одного из этих множеств в другое.
· Шифрующая функция:
· Расшифровывающая функция:
Элементы этих множеств - ~m и ~c являются аргументами соответствующих функций. Так же в эти функции уже включено понятие ключа. То есть тот необходимый ключ для шифрования или расшифрования является частью функции. Это позволяет рассматривать процессы шифрования абстрактно, вне зависимости от структуры используемых ключей. Хотя, в общем случае, для каждой из этих функций аргументами являются данные и вводимый ключ.
Если для шифрования и расшифрования используется один и тот же ключ , то такой алгоритм относят к симметричным. Если же из ключа шифрования алгоритмически сложно получить ключ расшифрования, то алгоритм относят к асимметричным, то есть к алгоритмам с открытым ключом.
· Для применения в целях шифрования эти функции, в первую очередь, должны быть взаимно обратными.
· Важной характеристикой шифрующей функции E является ее криптостойкость . Косвенной оценкой криптостойкости является оценка взаимной информации между открытым текстом и шифротекстом, которая должна стремиться к нулю.
Криптостойкость шифра
Криптографическая стойкость - свойство криптографического шифра противостоять криптоанализу, то есть анализу, направленному на изучение шифра с целью его дешифрования. Для изучения криптоустойчивости различных алгоритмов была создана специальная теория, рассматривающая типы шифров и их ключи, а также их стойкость. Основателем этой теории является Клод Шеннон. Криптостойкость шифра есть его важнейшая характеристика, которая отражает, насколько успешно алгоритм решает задачу шифрования.
Любая система шифрования, кроме абсолютно криптостойких, может быть взломана простым перебором всех возможных в данном случае ключей. Но перебирать придется до тех пор, пока не отыщется тот единственный ключ, который и поможет расшифровать шифротекст.
Абсолютно стойкие системы
Оценка криптоустойчивости шифра, проведенная Шенноном определяет фундаментальное требование к шифрующей функции E. Для наиболее криптоустойчивого шифра неопределенности (условная и безусловная), при перехвате сообщений, должны быть равны для сколь угодно большого числа перехваченных шифротекстов.
Таким образом, злоумышленник не сможет извлечь никакой полезной информации об открытом тексте из перехваченного шифротекста. Шифр, обладающий таким свойством, называется абсолютно стойким.
Требования к абсолютно стойким системам шифрования:
· Ключ генерируется для каждого сообщения (каждый ключ используется один раз).
· Ключ статистически надёжен (то есть вероятности появления каждого из возможных символов равны, символы в ключевой последовательности независимы и случайны).
· Длина ключа равна или больше длины сообщения.
Стойкость таких систем не зависит от того, какими возможностями обладает криптоаналитик. Однако практическое применение абсолютно стойких криптосистем ограничено соображениями стоимости таких систем и их удобства. Идеальные секретные системы обладают следующими недостатками:
· Шифрующая система должна создаваться с исключительно глубоким знанием структуры используемого языка передачи сообщений
· Сложная структура естественных языков крайне сложна и для устранения избыточности передаваемой информации может потребоваться крайне сложное устройство.
· Если в передаваемом сообщений возникает ошибка, то эта ошибка сильно разрастается на этапе кодирования и передачи, в связи со сложностью используемых устройств и алгоритмов.
Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) - система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.
Симметричные криптосистемы (также симметричное шифрование, симметричные шифры) - способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ. До изобретения схемы асимметричного шифрования единственным существовавшим способом являлось симметричное шифрование. Ключ алгоритма должен сохраняться в секрете обеими сторонами. Алгоритм шифрования выбирается сторонами до начала обмена сообщениями.
Учебный год
Теоретическая часть
1. Основные виды криптографических преобразований информации. Сущность каждого преобразования, области применения.
2. Представление системы шифрования графом, принцип единственности шифрования-дешифрования.
3. Математическая модель системы шифрования-дешифрования информации.
4. Стойкость системы шифрования, классификация систем шифрования по стойкости. Виды атак на систему шифрования.
5. Определение безусловно стойкой системы шифрования, утверждение о необходимых условиях существования безусловно стойкой системы.
6. Определение безусловно стойкой системы шифрования, утверждение о достаточных условиях существования безусловно стойкой системы.
7. Вычислительно стойкие системы шифрования, понятие о сложности криптоанализа, основные подходы к вскрытию криптографических систем, анализ атаки перебора ключей и атаки на основе статистики сообщения.
8. Блочный шифр, схема Файстеля, свойства блочного шифра.
9. Шифр замены, его свойства.
10. Шифр гаммирования и его свойства.
11. Моды (режимы работы) блоковых шифров, краткая характеристика режимов.
12. Стандарт шифрования ГОСТ Р34.12-2015, базовый алгоритм шифрования 64-битного блока.
13. Стандарт шифрования ГОСТ Р34.12-2015, базовый алгоритм шифрования 128-битного блока.
14. Стандарт шифрования ГОСТ Р34.13-2015, алгоритм шифрования в режиме простой замены, алгоритм шифрования в режиме гаммирования и гаммирования с обратной связью. Сравнение режимов.
15. Линейный рекуррентный регистр, алгебраические свойства линейной рекуррентной последовательности, анализ свойства предсказуемости.
16. Линейный рекуррентный регистр, статистические свойства линейной рекуррентной последовательности.
17. Принципы построения формирователей шифрующей гаммы (понятие эквивалентной линейной сложности, применение нелинейных узлов для повышения линейной сложности).
18. Шифр А5/1, характеристика шифра, принцип построения, применение.
19. Принцип построения и характеристики шифра AES.
20. Понятие односторонней функции, общий принцип построения криптографических систем с открытым ключом.
21. Понятие хэш-функции, требования, предъявляемые к криптографическим хэш-функциям.
22. Хэширующая функция согласно стандарту ГОСТ Р34.11-12, характеристика, принцип построения, применение.
23. Система шифрования Эль-Гамаля, атаки на систему.
24. Система шифрования РША, атаки на систему.
25. Определение, классификация, основные свойства, модель ЭП.
26. Схема ЭП РША.
27. Схема ЭП Эль-Гамаля.
28. ЭЦП по ГОСТР 34.10-12, общая характеристика, принцип формирования и проверки подписи.
29. Аутентификация сообщений в телекоммуникационных системах (модель системы имитозащиты, стратегии навязывания, показатели имитозащищенности).
30. Понятие ключевой хэш-функции. Класс строго-универсальных хэш-функций, примеры реализация этих хэш-функций.
31. Построение систем аутентификации с гарантированной вероятностью навязывания.
32. Построение системы аутентификации при многократной передаче сообщений.
33. Вычислительно-стойкие системы аутентификации.
34. Выработка имитовставки согласно ГОСТ Р34.12-2015.
35. Модель управления ключами в симметричных криптографических системах, характеристика жизненного цикла ключа.
36. Способы распределения ключей на основе взаимного обмена сообщениями между корреспондентами. Способ Диффи-Хеллмана.
37. Способы генерирования случайных чисел при формировании ключей.
38. Способы распределения ключей с использованием ЦРК на начальном этапе.
39. Способы распределения ключей с использованием ЦРК в интерактивном режиме. Протокол Нидхема-Шредера.
40. Принцип распределения открытых ключей.
41. Понятие инфраструктуры открытых ключей (PKI), состав, принцип взаимодействия элементов структуры.
42. Назначение, принцип формирования и характеристика сертификата открытого ключа.
Практическая часть
1. Зашифровать (расшифровать) сообщение в ручном режиме шифром подстановки, перестановки и гаммирования. Программа LR1_1.exe.
2. Расшифровать криптограмму на основе анализа ее статистики, используя программу CHANGE.EXE.
3. Найти коэффициент размножения ошибок при расшифровании криптограммы блочного подстановочно-перестановочного шифра с длиной блока 16 бит. Программа tst.
4. Расшифровать криптограмму подстановочно-перестановочного шифра путем полного перебора ключей, используя программу tst. Обосновать параметры принятия решения о правильной расшифровке.
5. Зашифровать 64-битное сообщение базовым алгоритмом шифрования ГОСТ Р 34.12-2015 г. (1 раунд)
6. Зашифровать сообщение длиной 128 бит, используя программу AES.exe. Проверить, что в первом преобразовании (операция SubBytes) используется обращение элемента в поле GF(2 8).
7. По характеристическому многочлену h(x) построить ЛРР (начальное заполнение 10…01) Определить период последовательности. Найти баланс, проверить свойства серий и окна. Результат проверить с помощью программы ЛРР 1.
8. Найти последовательность на выходе формирователя шифрующей гаммы, содержащего элементы ИЛИ, И-НЕ, Джеффа. Использую программу ЛРР 2, определить эквивалентную сложность последовательности. Построить эквивалентный ЛРР. Сделать выводы.
9. Выполнить следующие вычисления по разделу дискретной математики:
Найти наибольший общий делитель, используя алгоритм Евклида;
Вычислить a x modp, используя алгоритм быстрого возведения числа в степень;
Найти обратный элемент к числу по модулю p.
Найти функцию Эйлера от числа x;
10. - используя тест Ферма проверить, является ли число х простым, найти вероятность того, что проверка дает ошибочный результат.
11. Заданы параметры системы шифрования Эль-Гамаля a=4, p=11, закрытый ключ х=7 , зашифровать сообщение М= . Расшифровать криптограмму.
12. Заданы параметры системы шифрования РША p=11, q=13, зашифровать сообщение М=5. Расшифровать криптограмму.
13. Заданы параметры системы шифрования Эль-Гамаля a=4, p=11, закрытый ключ х=8, подписать сообщение, хэш-код которого h(М)= . Проверить подпись.
14. Заданы параметры системы шифрования РША p=11, q=13, подписать сообщение, хэш-код которого h(М)= 6. Проверить подпись.
15. Используя программу RSA, произвести шифрование файла большого размера безопасной криптосистемой РША и оценить время шифрования и дешифрования.
16. Используя программу RSA, произвести подписание сообщений и проверку подписи. Разрядность сообщения не менее 100 разрядов.
17. Задана эллиптическая кривая Е13(1,1). Найти точку С равную сумме двух точек , координаты точек и x 1 = , y 1 = , x 2 = , y 2 = . Найти противоположную точку . Вычислить точку , где k =3.
18. Сформировать аутентификатор для двоичного сообщения М =1010 на основе строго универсальных хэш-функций по алгоритму K 0 =0101, K 1 = (номер билета) . Вычисления в поле проводить по модулю неприводимого многочлена , b =4.
Криптографические системы с открытыми ключами шифрования позволяют пользователям осуществлять безопасную передачу данных по незащищенному каналу без какой-либо предварительной подготовки. Такие криптосистемы должны быть асимметричными в том смысле, что отправитель и получатель имеют различные ключи, причем ни один из них не может быть выведен из другого с помощью вычислений. В этих системах фазы шифрования и дешифрования отделены и защита сообщения обеспечивается без засекречивания ключа шифрования, поскольку он не используется при дешифровании.
С помощью открытого ключа шифрования пользователь i шифрует сообщение М и посылает пользователю j по незащищенному каналу передачи данных. Только пользователь j может выполнить дешифрование, чтобы восстановить M, поскольку только он знает секретный ключ дешифрования.
Среди асимметричных (открытых) криптосистем наиболее широкое распространение получила криптографическая система RSA. В этой системе получатель сообщения выбирает два больших простых числа p и q так, чтобы произведение n = pq находилось за пределами вычислительных возможностей. Исходное сообщение М может иметь произвольную длину в диапазоне 1 Исходный текст М восстанавливается из шифрованного C обратным преобразованием Получатель выбирает e и d так, чтобы выполнялись условия: где - функция Эйлера, равная (p - 1)(q - 1); (a, b) - наибольший общий делитель двух чисел. То есть e и d являются в мультипликативной группе обратными величинами в арифметике вычетов по mod . Очевидно, что главной целью криптографического раскрытия является определение секретного ключа (показателя степени при C - значения d). Известны три способа, которыми мог бы воспользоваться криптоаналитик, для раскрытия величины d по открытой информации о паре {e, n}. Факторизация n Разложение величины n на простые множители позволяет вычислить функцию и, следовательно, скрытое значение d, используя уравнение Различные алгоритмы такого разложения изложены в . Наиболее быстрый алгоритм, известный в настоящее время, может выполнить факторизацию n за число шагов порядка Анализ этого выражения показывает, что число n, имеющее 200 десятичных цифр, будет хорошо защищено от известных методов раскрытия. Прямое вычисление Другой возможный способ криптоанализа связан с непосредственным вычислением функции Эйлера без факторизации n. Прямое вычисление нисколько не проще факторизации n, поскольку позволяет после этого легко факторизовать n. Это можно видеть из следующего примера. Пусть x = p + q = n + 1 - , y = (p - q) 2 = x 2 - 4n. Зная, можно определить x и, следовательно, y, зная x и y, простые p и q можно определить из следующих соотношений: Прямая оценка d Третий способ криптоанализа состоит в непосредственном вычислении величины d. Аргументация этого способа основана на том, что, если d выбрано достаточно большим, чтобы простой перебор был неприемлем, вычисление d не проще факторизации n, поскольку, если d известно, то n легко факторизуется. Это можно показать следующим образом. Если d известно, то можно вычислить величину, кратную функции Эйлера, используя условие где k - произвольное целое число. Факторизацию n можно выполнить, используя любое значение, кратное . Дешифровщик, с другой стороны, может попытаться найти некоторую величину d", которая была бы эквивалентна скрытой величине d, использованной при разработке шифра. Если существует много таких d", то можно попытаться использовать прямой перебор, чтобы раскрыть шифр. Но все d" различаются множителем, равным и если этот множитель вычислен, то n можно факторизовать. Таким образом, нахождение d столь же сложно, что и факторизация n. Таким образом, основная задача криптоанализа асимметричных систем шифрования сводится, в основном, к задаче разложения на множители (факторизация). Эта задача является одной из основных в теории чисел и формулируется следующим образом: пусть нам дано целое число n>0, и требуется, если это возможно, найти два числа a и b, таких, что ab = n. На самом деле имеются две различные задачи: первая, называемая тестом на простоту - это проверка того, существуют ли такие a и b; вторая, называемая разложением - это задача их нахождения. Рассмотрим обе эти задачи. Первый детерминистический тест.