Основные определения. P.S
Модели криптографических систем
Шифротекст - результат операции шифрования. Часто также используется вместо термина «криптограмма», хотя последний подчёркивает сам факт передачи сообщения, а не шифрования.
Процесс применения операции шифрования к шифротексту называется перешифровкой.
Свойства шифротекста
При рассмотрении шифротекста как случайной величины , зависящей от соответствующих случайных величин открытого текста 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.
09.07.2003
Что такое шифрование?
Шифрование используется человечеством с того самого момента, как появилась первая секретная информация, т. е. такая, доступ к которой должен быть ограничен. Это было очень давно - так, один из самых известных методов шифрования носит имя Цезаря, который если и не сам его изобрел, то активно им пользовался (см. врезку ).
Криптография обеспечивает сокрытие смысла сообщения и раскрытие его расшифровкой с помощью специальных алгоритмов и ключей. Ключ понимается нами как конкретное секретное состояние параметров алгоритмов шифрования и дешифрования. Знание ключа дает возможность прочтения секретного сообщения. Впрочем, как вы увидите ниже, далеко не всегда незнание ключа гарантирует то, что сообщение не сможет прочесть посторонний человек.
Процесс вскрытия шифра без знания ключа называется криптоанализом. Время, необходимое для взлома шифра, определяется его криптостойкостью. Чем оно больше, тем «сильнее» алгоритм шифрования. Еще лучше, если изначально вообще нельзя выяснить, достижим ли результат взлома.
Основные современные методы шифрования
Среди разнообразнейших способов шифровании можно выделить следующие основные методы:
- Алгоритмы замены или подстановки - символы исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой криптостойкости.
- Алгоритмы перестановки - символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.
- Алгоритмы гаммирования - символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов "имя пользователя.pwl", в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUp-доступа в Интернет и т.д.).
Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.
- Алгоритмы, основанные на сложных математических преобразованиях исходного текста по некоторой формуле. Многие из них используют нерешенные математические задачи. Например, широко используемый в Интернете алгоритм шифрования RSA основан на свойствах простых чисел.
Симметричные и асимметричные криптосистемы
Прежде чем перейти к отдельным алгоритмам, рассмотрим вкратце концепцию симметричных и асимметричных криптосистем. Сгенерировать секретный ключ и зашифровать им сообщение - это еще полдела. А вот как переслать такой ключ тому, кто должен с его помощью расшифровать исходное сообщение? Передача шифрующего ключа считается одной из основных проблем криптографии.
Оставаясь в рамках симметричной системы (так она названа оттого, что для шифрования и дешифрования подходит один и тот же ключ), необходимо иметь надежный канал связи для передачи секретного ключа. Но такой канал не всегда бывает доступен, и потому американские математики Диффи, Хеллман и Меркле разработали в 1976 г. концепцию открытого ключа и асимметричного шифрования. В таких криптосистемах общедоступным является только ключ для процесса шифрования, а процедура дешифрования известна лишь обладателю секретного ключа.
Например, когда я хочу, чтобы мне выслали сообщение, то генерирую открытый и секретный ключи. Открытый посылаю вам, вы шифруете им сообщение и отправляете мне. Дешифровать сообщение могу только я, так как секретный ключ я никому не передавал. Конечно, оба ключа связаны особым образом (в каждой криптосистеме по-разному), и распространение открытого ключа не разрушает криптостойкость системы.
В асимметричных системах должно удовлетворяться следующее требование: нет такого алгоритма (или он пока неизвестен), который бы из криптотекста и открытого ключа выводил исходный текст. Пример такой системы - широко известная криптосистема RSA.
Алгоритм RSA
Алгоритм RSA (по первым буквам фамилий его создателей Rivest-Shamir-Adleman) основан на свойствах простых чисел (причем очень больших). Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.
Для начала выберем два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита).
Определим параметр n как результат перемножения p и q . Выберем большое случайное число и назовем его d , причем оно должно быть взаимно простым с результатом умножения (p -1)*(q -1) .
Отыщем такое число e, для которого верно соотношение
(e*d) mod ((p -1)*(q -1)) = 1
(mod - остаток от деления, т. е. если e, умноженное на d, поделить на ((p -1)*(q -1)) , то в остатке получим 1).
Открытым ключом является пара чисел e и n , а закрытым - d и n .
При шифровании исходный текст рассматривается как числовой ряд, и над каждым его числом мы совершаем операцию
C(i)= (M(i) e) mod n.
В результате получается последовательность C(i) , которая и составит криптотекст. Декодирование информации происходит по формуле
M(i) = (C(i) d) mod n.
Как видите, расшифровка предполагает знание секретного ключа.
Давайте попробуем на маленьких числах.
Установим p=3, q=7 . Тогда n=p*q=21. Выбираем d как 5. Из формулы (e*5) mod 12=1 вычисляем e=17 . Открытый ключ 17, 21 , секретный - 5, 21 .
Зашифруем последовательность «12345»:
C(1)= 1 17 mod 21= 1
C(2)= 2 17 mod 21 =11
C(3)= 3 17 mod 21= 12
C(4)= 4 17 mod 21= 16
C(5)= 5 17 mod 21= 17
Криптотекст - 1 11 12 16 17.
Проверим расшифровкой:
M(1)= 1 5 mod 21= 1
M(2)= 11 5 mod 21= 2
M(3)= 12 5 mod 21= 3
M(4)= 16 5 mod 21= 4
M(5)= 17 5 mod 21= 5
Как видим, результат совпал.
Криптосистема RSA широко применяется в Интернете. Когда вы подсоединяетесь к защищенному серверу по протоколу SSL, устанавливаете на свой ПК сертификат WebMoney либо подключаетесь к удаленному серверу с помощью Open SSH или SecureShell, то все эти программы применяют шифрование открытым ключом с использованием идей алгоритма RSA. Действительно ли эта система так надежна?
Конкурсы по взлому RSA
С момента своего создания RSA постоянно подвергалась атакам типа Brute-force attack (атака методом грубой силы, т. е. перебором). В 1978 г. авторы алгоритма опубликовали статью, где привели строку, зашифрованную только что изобретенным ими методом. Первому, кто расшифрует сообщение, было назначено вознаграждение в размере 100 долл., но для этого требовалось разложить на два сомножителя 129-значное число. Это был первый конкурс на взлом RSA. Задачу решили только через 17 лет после публикации статьи.
Криптостойкость RSA основывается на том предположении, что исключительно трудно, если вообще реально, определить закрытый ключ из открытого. Для этого требовалось решить задачу о существовании делителей огромного целого числа. До сих пор ее аналитическими методами никто не решил, и алгоритм RSA можно взломать лишь путем полного перебора. Строго говоря, утверждение, что задача разложения на множители сложна и что взлом системы RSA труден, также не доказано.
Полученное в результате обработки хэш-функцией текста сообщения число шифруется по RSA-алгоритму на закрытом ключе пользователя и посылается адресату вместе с письмом и экземпляром открытого ключа. Адресат с помощью открытого ключа отправителя выполняет ту же хэш-функцию над пришедшим сообщением. Если оба числа равны, это означает, что сообщение подлинное, а если был изменен хотя бы один символ, то числа не совпадут.
Один из самых распространенных в России почтовых клиентов, программа The Bat!, обладает встроенными возможностями добавлять цифровые подписи к письмам (обратите внимание на пункт меню Privacy при редактировании письма). Подробнее об этой методике читайте в статье (см. «Мир ПК», № 3/02).
 |
| Рис. 3 |
Криптография
Криптография - наука о принципах, средствах и методах преобразования информации для защиты ее от несанкционированного доступа и искажения. В последнее время она развивается очень и очень бурно. Это бесконечная увлекательная гонка, требующая много времени и сил: криптоаналитики взламывают алгоритмы, которые еще недавно были стандартами и повсеместно использовались. Кстати, недавно математики Дэн Голдстон (США) и Кем Илдирим (Турция) доказали первую закономерность в распределении простых чисел (до сих пор таких закономерностей не замечали). Простые числа располагаются на числовой оси некоторыми скоплениями, что несколько облегчает их поиск.
Математические исследования, ведущиеся во всем мире, постоянно приводят все к новым и новым открытиям. Как знать, может быть, мы стоим на пороге взлома алгоритма RSA или других криптосистем, основанных на нерешенных математических задачах.
Олег Бунин - специалист по разработке ПО для крупных Интернет-проектов, сотрудник компании «Рамблер», http://www..htm ).
Система шифрования Цезаря
Пример алгоритма замены - система шифрования Цезаря. Этот метод основан на замене каждой буквы сообщения на другую путем смещения от исходной на фиксированное количество символов. Попробуйте расшифровать четверостишие Омара Хайяма (время выполнения - 10 минут).
РЛЗЬ ЁМЭЙЗ АВБЖУ ИЙЗАВЛУ, БЖЩЛУ ЖЩЭЗЬЖЗ ЖЮЁЩЕЗ, ЭЫЩ ЫЩАЖФО ИЙЩЫВЕЩ БЩИЗЁЖВ ЭЕШ ЖЩРЩЕЩ: ЛФ ЕМРСЮ ЪЗЕЗЭЩГ, РЮЁ РЛЗ ИЗИЩЕЗ ЮКЛУ, В ЕМРСЮ ЬМЭУ ЗЭВЖ, РЮЁ ЫЁЮКЛЮ К ДЮЁ ИЗИЩЕЗ.
Успели? Привожу «отгадку»:
Чтоб мудро жизнь прожить, знать надобно немало,
Два важных правила запомни для начала:
Ты лучше голодай, чем что попало есть,
И лучше будь один, чем вместе с кем попало.
Ключ для расшифровки: сдвигаем на семь символов (берем седьмой) влево по алфавиту. Алфавит закольцован. Регистр символов не учитывается.
Windows и пароли
Как Windows шифрует пароли?
Система берет пароль, преобразует его в верхний регистр, обрезает до 14 символов, затем делит их на две половины по 7, шифрует каждую по отдельности и так сохраняет, что несколько упрощает взлом. Кстати, когда будете придумывать пароль, имейте в виду, что комбинация длиннее 14 символов имеет мало смысла.
Конкурс AES (Advanced Encryption Standard)
В 80-х гг. в США приняли стандарт симметричного шифрования для внутреннего применения - DES ((Data Encryption Standard, подобный стандарт есть и в России). Но в 1997 г., когда стало понятно, что 56-битового ключа DES недостаточно для надежной криптосистемы, Американский институт стандартизации объявил конкурс на новый стандартный алгоритм. Из 15 вариантов был выбран лучший: бельгийский алгоритм Rijndael (его название составлено из фамилий авторов - Rijmen и Daemen, читается как «Рэйндал». Этот алгоритм уже встроен в различные криптографические средства, поставляемые на рынок). Другими финалистами конкурса стали MARS, RC6, Serpent, TwoFish. Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.
Криптографические хэш-функции
Криптографические хэш-функции преобразуют входные данные любого размера в строку фиксированного размера. Для них чрезвычайно сложно найти:
- два разных набора данных с одинаковым результатом преобразования (стойкость к коллизиям); например, количество арифметических операций, необходимых для того, чтобы найти блок данных, также имеющий краткое сообщение для хэш-функции MD5, составляет приблизительно 2 64;
- входное значение по известному результату хэширования (необратимость); для MD5 предполагаемое количество операций, необходимых для вычисления исходного сообщения, равно 2 128.
Криптографические системы с открытыми ключами шифрования позволяют пользователям осуществлять безопасную передачу данных по незащищенному каналу без какой-либо предварительной подготовки. Такие криптосистемы должны быть асимметричными в том смысле, что отправитель и получатель имеют различные ключи, причем ни один из них не может быть выведен из другого с помощью вычислений. В этих системах фазы шифрования и дешифрования отделены и защита сообщения обеспечивается без засекречивания ключа шифрования, поскольку он не используется при дешифровании.
С помощью открытого ключа шифрования пользователь 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; вторая, называемая разложением - это задача их нахождения. Рассмотрим обе эти задачи. Первый детерминистический тест. Этот тест основан на малой теореме Ферма, которая утверждает, что если p - простое число, то a p-1 1 (mod p) для всех a, 1 Таким образом, тест состоит в выборе числа а, меньшего b и проверке b на принадлежность классу простых чисел согласно условию a b-1 1 (mod b) в соответствии с приведенным выражением. Практически требуется проверить только несколько значений a. Выбор а, равным 3, позволяет выявить все составные числа. Тем не менее известно, что этот тест пропускает составные числа Кармайкла (например число 561 =3 х 11 х 17). Второй детерминистический тест. Разделим число “b” последовательно на 2, 3, ..., . Если при каком-нибудь делении мы получим нулевой остаток, то число “b” составное, а делитель и частное являются его сомножителями; в противном случае b - простое. Поскольку необходимо выполнить делений, то время проверки простоты числа “b” равно O(). Этот очень медленный экспоненциальный тест не только определяет является ли число простым, но и находит сомножители составного числа. Третий детерминистический тест. Число “b” просто тогда и только тогда, когда b | {(b-1)! + 1}. Факториал (b-1)! и проверка делимости (b-1)!+1 для больших “b” уничтожает всякий интерес к этому тесту. Если `b" имеет 100 десятичных цифр, то (b-1)! состоит примерно из 100 102 цифр. Все приведенные выше тесты были детерминистическими. Это означает, что для заданного числа “b” мы всегда получаем ответ, является ли оно простым или составным. Если заменить слово «всегда» на «с некоторой вероятностью», то оказывается возможным построить вероятностные тесты, которые называют также тестами псевдопростоты. Первый вероятностный тест. Этот тест позволяет выявить все составные числа Кармайкла. Выбирается случайное число a в диапазоне от 1 до b-1 и проверяется выполнение условий. (a, b) = 1, J(a, b) a (b-1)/2 (mod b), где J(a, b) символ Якоби. Символ Якоби определяется следующими соотношениями: J(a, p) = 1, если x 2 a (mod p) имеет решения в Z p , J(a, p) = -1, если x 2 a (mod p) не имеет решения в Z p , где Z p - кольцо вычетов по модулю p. Если b - простое число, условия приведенные выше, всегда выполняются, а если b - составное, то они не выполняются с вероятностью. Поэтому выполнение k тестов гарантирует, что ответ неправилен с вероятностью 2 -k . Второй вероятностный тест. Поскольку число b, которое должно быть простым, всегда нечетное, то его можно представить в виде где s - четное число. Затем в тесте выбирается случайным образом число a в диапазоне от 1 до b-1 и проверяется выполнение условий 1 (mod b) для 0 < j Оба теста используются для проверки числа на принадлежность классу простых и требуют порядка О(log 2 b) операций над большими числами. Третий вероятностный тест. Для заданного b выбираем случайным образом m, 1 Вероятность того, что выдается ответ “b - составное число”, равна вероятности того, что m | b. Если d(b) число делителей b и m - случайно выбрано в пределах 1 Это очень слабый тест. Четвертый вероятностный тест. Для заданного “b” выбираем случайным образом m, 1 Если b составное число, то количество чисел m Пятый вероятностный тест. Это тест сильной псевдопростоты. Пусть заданы b и m. Пусть где t - нечетное число и рассмотрим числа для (x r - наименьший по абсолютной величине остаток по модулю b). Если либо x 0 = 1, либо найдется индекс i, i Докажем это от противного. Предположим, что b - нечетное простое число. Покажем по индукции, что 1 (mod b) для, что будет противоречить условию теоремы. Очевидно, что это справедливо для r = S по теореме Ферма. Предполагая справедливость утверждения для i, нетрудно видеть, что оно справедливо для i-1, потому что равенство влечет за собой, что возводимое в квадрат число равно ±1. Но -1 не подходит по условию (иначе бы тест выдал ответ "не удалось определить"). Доказано, что если b - составное число, то вероятность того, что тест выдаст ответ "b - составное число" не меньше . Разложение на множители больших целых чисел. С задачей о нахождении делителей больших простых чисел дело обстоит гораздо хуже, чем с проверкой простоты. Ниже приводится метод, который является наиболее сильным из известных. Метод основывается на идее Лежандра, если U 2 V 2 (mod b) 0 Пусть мы хотим разложить на множители число b. Пусть n = - максимальное число, не превосходящее, и вычислим числа a k = (n + k) 2 - b для небольших k (числа k могут быть и отрицательными). Пусть {q i , i = 1, 2, …, j} - множество небольших простых чисел, которые могут делить выражение вида x 2 - b (т.е. b является квадратом по модулю q i). Такое множество обычно называется мультипликативной базой В. Запомним все числа a k , которые могут быть разложены по мультипликативной базе, т.е. записаны в виде Такие ak называются В-числами. С каждым В-числом ak связывается вектор показателей Если мы найдем достаточно много В-чисел, чтобы множество соответствующих векторов показателей было линейно зависимо по модулю 2 (любое множество из j+2 В-чисел обладает этим свойством), то можно будет представить нулевой вектор в виде суммы векторов показателей некоторого множества S, скажем Определим целые числа i = 0, 1, …, j, Из сказанного выше следует, что U 2 V 2 (mod b) и (U-V, b) может быть нетривиальным делителем b. Дешифрование итерациями выполняется следующим образом. Противник подбирает число j, для которого выполняется следующее соотношение: Т. е. противник просто проводит j раз зашифрование на открытом ключе перехваченного шифротекста. Это выглядит следующим образом: (С e) e) e ..) e (mod n)=С e j(mod n)). Найдя такое j, противник вычисляет C e (j-1)(mod n) (т.е. j-1 раз повторяет операцию зашифрования) - это значение и есть открытый текст M. Это следует из того, что С e j(mod n)=(C e (j-1)(mod n))e=C. Т. е. некоторое число C e (j-1)(mod n) в степени e дает шифротекст С. А это открытый текст M. Пример. p=983, q=563, e=49, M=123456. C=M 49 (mod n)=1603, C497(mod n)=85978, C498(mod n)=123456, C499(mod n)=1603. 10.3.1. Системы шифрования
Среди
криптографических систем, обеспечивающих сохранение информации в тайне,
наибольшее распространение получили системы шифрования информации. Рассмотрим
обобщенную модель системы шифрования представленную на рис. 10.6. Источник
сообщений генерирует сообщения , которые необходимо сохранить в тайне
от нарушителя при передаче по незащищенному каналу. В системе имеется
защищенный от нарушителя источник ключевой информации, который вырабатывает
некоторый ключ ,
предназначенный для шифрования сообщений отправителем сообщений и ключ , предназначенный для
дешифрования криптограмм получателем. Ключи шифрования и дешифрования связаны
друг с другом и позволяют восстановить сообщение из криптограммы. Сформированная
ключевая информация передается по защищенному каналу ее доставки. Под
защищенным будем понимать канал передачи информации, в котором нарушитель не
способен на успешные атаки. Отправитель сообщений шифрует сообщение по ключу , используя шифрующее
преобразование . Образованная
криптограмма передается
по незащищенному каналу передачи информации получателю. На приеме получатель
способен из криптограммы однозначно восстановить сообщение по ключу , используя дешифрующее
преобразование . Для
однозначного восстановления сообщения из криптограммы требуется, чтобы
дешифрующее преобразование являлось обратным к шифрующему
преобразованию при
использовании ключей и соответственно . Системы
шифрования информации разделяются на два больших класса: симметричные и
несимметричные. Система шифрования информации называется симметричной, если для
любой допустимой пары ключей вычислительно просто определить один
ключ, зная другой, т.е. из можно вычислить и, зная , «легко» определить . В таких системах
оба ключа должны быть секретными. Во многих симметричных системах ключ
шифрования совпадает с ключом дешифрования: . Поэтому симметричные криптосистемы иногда
называют одноключевыми системами или системами с секретным ключом. Система
шифрования информации называется несимметричной, если для любой допустимой пары
ключей вычислительно
невозможно определить ключ дешифрования , зная ключ шифрования . В несимметричной системе
шифрования ключ шифрования может быть несекретным (открытым), известным
для всех, включая нарушителя. Поэтому такие криптосистемы иногда называют
системами с открытым ключом или двухключевыми системами. В таких системах
должна обеспечиваться секретность ключа дешифрования . Несимметричные
системы шифрования удобны для практического использования тем, что при доставке
ключей отправителям сообщений не надо обеспечивать секретность ключевой информации
шифрования сообщений. Известно
, что максимальная степень защищенности информации от чтения достигается,
если произвольные передаваемые сообщения и наблюдаемые нарушителем
соответствующие им криптограммы статистически независимы: Для
приближения характеристик реальных шифраторов к характеристикам идеального
используют сжатие сообщений до шифрования и рандомизацию шифруемых сообщений. Идея
рандомизации заключается в уменьшении избыточности шифруемых сообщений за счет
специального кодирования, обеспечивающего равную вероятность появления
символов, но длина сообщений при этом увеличивается. Основной
характеристикой шифра является криптостойкость, которая обычно определяется
интервалом времени, необходимым для раскрытия шифра. К шифрам, используемым для
криптографической защиты информации, предъявляется ряд требований: В
той или иной мере этим требованиям отвечают шифры перестановок, шифры замены,
шифры гаммирования и шифры, основанные на аналитических преобразованиях
шифруемых данных . Шифрование
перестановкой заключается в том, что символы исходного текста переставляются по
определенному правилу в пределах некоторого блока этого текста. При достаточной
длине блока, в пределах которого осуществляется перестановка, и сложном,
неповторяющемся порядке перестановки можно достигнуть приемлемой для простых
практических приложений стойкости шифра. Шифрование
заменой (подстановкой) заключается в том, что символы исходного текста
заменяются символами того же или другого алфавита в соответствии с заранее
обусловленной схемой замены. Возможны моно- и многоалфавитные подстановки. В
случае моноалфавитных подстановок каждый символ исходного текста преобразуется
в символ шифрованного текста по одному и тому же закону. При многоалфавитной
подстановке преобразование меняется от символа к символу. Для обеспечения
высокой криптостойкости требуется использование сложных ключей. Шифрование
гаммированием заключается в том, что символы исходного текста складываются с
символами некоторой псевдослучайной последовательности, именуемой гаммой шифра.
Примером может служить, поразрядное сложение сообщения и гаммы при формировании криптограммы
. На приеме
необходимо генерировать такую же псевдослучайную последовательность () тогда дешифрование
будет осуществляться на основе следующего преобразования: . Стойкость
шифрования определяется в основном длиной (периодом) неповторяющейся части
гаммы шифра. Поскольку с помощью ЭВМ можно генерировать гамму шифра очень
большой длины, то данный способ является одним из основных для шифрования
информации в автоматизированных системах.
.
Загрузка...
