1976 год считается годом рождения несимметричной криптографии. В этом году американскими математиками Вайтфилдом Диффи, Мартином Хеллманом и Ральфом Меркле была представлена идеология криптосистемы с открытым ключом

Кардинальное отличие криптосистемы с открытым ключом (по другой терминологии, несимметричной системы) от симметричной системы состоит в том, что в криптосистемах с открытым ключом процедура зашифровывания становится общедоступной. Это, однако, не означает как в традиционных системах шифрования, что общедоступной является и процедура расшифровывания. Понятие ключа разбивается на две части (включает теперь два понятия): ключ открытый, и ключ секретный. Общедоступный открытый ключ используется для зашифровывания, но расшифровывание может осуществить только тот, кто владеет секретным ключом.

Именно как раз в допущении того, что нахождение ключа расшифровывания по известному ключу зашифровывания может быть сложно-вычислимой задачей, и заключается идея, которая определила дальнейшее направление развития криптографии.

Но наравне с криптографией шло развитие и криптоанализа - другого противоположного раздела криптологии, предметом которого является разработка методов взлома новых криптографических алгоритмов с целью выявления их надежности. Результатом возникновения каждого нового метода криптоанализа является пересмотр оценок безопасности шифров, что в свою очередь, влечет необходимость создания более стойких шифров.

Целью курсовой работы является анализ надежности алгоритмов ассиметричных методов шифрования.

Первая глава работы будет посвящена описанию существующих алгоритмов и их особенностей.

Во второй главе будут описаны методы криптоанализа, основанные на особенностях систем шифрования с открытым ключом.

Глава 1. Криптосистемы с открытым ключом

Первой системой с открытым ключом стал метод экспоненциального ключевого обмена Диффи - Хеллмана, разработанный в 1976 году. Метод предназначен для передачи секретного ключа симметричного шифрования. В обмене задействованы два участника А и Б (рис.3). Сначала они выбирают большие простые числа n и g<n (эти числа секретными не являются). Затем участник A выбирает большое целое число х, вычисляет Х=gx mod n и передает Х участнику Б. Б в свою очередь выбирает большое целое число y, вычисляет Y=gy mod n и передает Y участнику А. Б вычисляет K'=Xy mod n, А вычисляет K''=Yx mod n. Легко заметить, что K'=K''=gxy mod n, и это значение оба участника могут использовать в качестве ключа симметричного шифрования.

Размещено на http://www.allbest.ru/

Криптостойкость этого метода определяется трудоемкостью вычисления дискретного логарифма в конечном поле. Действительно, злоумышленник может узнать такие параметры алгоритма, как n, g, X, Y, но вычислить по ним значения x или y - задача, требующая очень больших вычислительных мощностей и времени (последнее утверждение верно при использовании сверхбольших чисел, размером более 768 бит). Метод легко можно обобщить на случай ключевого обмена для большего количества участников.

Размещено на http://www.allbest.ru/

Алгоритм Эль-Гамаля - асимметричный алгоритм шифрования, основанный на проблеме дискретного логарифмирования, разработан в 1985 г. Последовательность действий при генерации ключей, шифровании и дешифрации представлена на рис. 4.

Необходимо пояснить процедуру дешифрования. Так как axgkx mod p, то имеем:

Таким образом, кодируемое сообщение М разбивается на части, каждая из которых m интерпретируется как число в диапазоне [0 .. p-1], и выполняется операция шифрования согласно схеме на рис.4. На практике при использовании данного алгоритма рекомендуется выбирать ключи размером 768, 1024 и 1536 бит.

Алгоритм RSA был разработан в 1978 году. Алгоритм назван в честь авторов (Rivest, Shamir, Adleman). В основу криптостойкости RSA положена задача факторизации (разложения на множители) больших целых чисел.

Размещено на http://www.allbest.ru/

Процедуры генерации ключей, шифрования и дешифрования для этого алгоритма представлены на рис. 5.

На этапе генерации ключей формируется пара ключей: закрытый d и открытый e. Шифрование данных должно начинаться с его разбиения на блоки L размером k=[log2 (n)] бит каждый, чтобы блок L можно было рассматривать как целое число в диапазоне [0.. n-1].

Основная задача криптоаналитика при взломе этого шифра - узнать закрытый ключ d. Для этого он должен выполнить те же действия, что и получатель при генерации ключа - решить в целых числах уравнение ed + y (p-1)(q-1) =1 относительно d и y. Однако, если получателю известны входящие в уравнение параметры p и q, то криптоаналитик знает только число n - произведение p и q. Следовательно, ему необходимо произвести факторизацию числа n, то есть разложить его на множители. Для решения задачи факторизации к настоящему времени разработано множество алгоритмов, наиболее известными из них являются метод квадратичного решета и метод эллиптических кривых. Но для чисел большой размерности (около 1024 бит и более) это очень трудоемкая задача.

DSA (Digital Signature Algorithm) - алгоритм цифровой подписи, принятый в 1994 году в качестве стандарта США на ЭЦП и действовавший до 2001 г., представляет собой один из вариантов схемы Эль-Гамаля.

Национальный институт стандартов и технологии NIST, вместе с АНБ, разработал алгоритм SHA (Secure Hash Algorithm - алгоритм стойкого хеширования), требуемый для обеспечения стойкости алгоритма цифровой подписи DSA. По предположениям Microsoft, алгоритм SHA-2, предусматривающий генерацию хеш-значений длиной 256, 384 и 512 разрядов, еще на протяжение нескольких лет будет оставаться стойким, но в конечном счете будет заменен.

Ряд успешных атак на системы, основанные на сложности дискретного логарифмирования в конечных полях, привел к тому, что стандарты ЭЦП России и США в 2001 году были обновлены: переведены на эллиптические кривые. Алгоритмы ЭЦП при этом не изменились, однако вместо элементов конечного поля они оперируют эллиптическими числами, т.е. решениями уравнения эллиптических кривых над указанными конечными полями, а роль операции возведения в степень в конечном поле выполняет операция взятия кратной точки эллиптической кривой.

Специальный выбор типа эллиптической кривой позволяет не только во много раз усложнить задачу взлома схемы ЭЦП, но и уменьшить рабочий размер блоков данных. Старый российский стандарт ЭЦП оперирует 1024-битовыми блоками, а новый, основанный на эллиптических кривых, -- 256-битовыми, и при этом обладает большей стойкостью.

EC-DSA (Elliptic Curve Digital Signature Algorithm) - это классический алгоритм DSA, «переведенный» на эллиптические кривые. Стандарт FIPS 186-2 предусматривает 256- и 284-битный рабочий размер блоков данных, но Microsoft также поддерживает 521-разрядные ключи.

Как известно, далеко не все присутствующие на рынке криптографические средства обеспечивают обещанный уровень защиты. Системы и средства защиты информации (СЗИ) характеризуются тем, что для них не существует простых и однозначных тестов, позволяющих убедиться в надежной защите информации. Например, чтобы проверить работоспособность системы связи, достаточно провести ее испытания. Тем не менее, успешное завершение этих испытаний не дает возможность сделать вывод, что встроенная подсистема защиты информации тоже является работоспособной. Часто задача определения эффективности СЗИ при использовании криптографических методов защиты оказывается даже более трудоемкой, чем разработка СЗИ, т.к. требует наличия специальных знаний и более высокой квалификации, чем задача разработки. Как правило, анализ нового криптографического алгоритма является новой научной, а не инженерной задачей.

Повышение производительности вычислительной техники и появление новых видов атак на шифры ведет к понижению стойкости известных криптографических алгоритмов. Для уменьшения возможного ущерба, вызванного несвоевременной заменой потерявшего свою стойкость криптоалгоритма, необходима периодическая перепроверка стойкости криптоалгоритмов, которая включает в себя как разработку новых методов криптоанализа, так и повышение эффективности существующих методов.

То обстоятельство, что любую задачу отыскания способа раскрытия некоторой конкретной криптосистемы можно переформулировать как привлекательную математическую задачу, при решении которой удается использовать многие методы той же теории сложности, теории чисел и алгебры, привело к раскрытию многих криптосистем.

Практически все используемые алгоритмы асимметричной криптографии основаны задачах факторизации и дискретного логарифмирования в различных алгебраических структурах.

Глава 2. Методы криптоанализа асимметричных криптосистем

Задача дискретного логарифмирования считается более сложной, чем задача факторизации. Если будет найден полиномиальный алгоритм ее решения, станет возможным и разложение на множители (обратное не доказано).

Последние достижения теории вычислительной сложности показали, что общая проблема логарифмирования в конечных полях не может считаться достаточно прочным фундаментом. Наиболее эффективные на сегодняшний день алгоритмы дискретного логарифмирования имеют уже не экспоненциальную, а субэкспоненциальную временную сложность. Это алгоритмы “index-calculus”, использующие факторную базу.

Первый такой алгоритм был предложен Адлеманом и имеет временную сложность при вычислении дискретного логарифма в простом поле (, где ).

На практике алгоритм оказался недостаточно эффективным. Копперсмит, Одлыжко и Шреппель предложили алгоритм дискретного логарифмирования COS с эвристической оценкой сложности операций.

Алгоритм решета числового поля, предложенный Широкауэром, при работает эффективнее различных модификаций метода COS; его временная сложность составляет порядка арифметических операций.

Пусть G - мультипликативная абелева группа. Вычислить дискретный логарифм b по основанию а в группе G означает найти , при котором. Свойства дискретного логарифма во многом схожи со свойствами обычного логарифма в поле действительных чисел.

Например, выполняется тождество:

,

где - порядок группы, а - образующая.

Основная идея методов “index-calculus” заключается в том, что если

для некоторых элементов конечного поля , то

(1)

Получив достаточно много соотношений (1) (причем хотя бы одно из них должно включать элемент g, для которого известен), можно решить систему линейных уравнений относительно неизвестных и в кольце вычетов при условии, что количество неизвестных в уравнениях не слишком велико.

Самый простой подход к генерации соотношений вида (1) - выбрать произвольный элемент , вычислить и с помощью перебора попытаться найти числа, удовлетворяющие соотношению:

,

где - простые числа, такие, что < В для некоторой границы В . Если удалось найти такие числа, то u является гладким элементом с границей гладкости В.

Выделяются два основных этапа в работе алгоритмов: на первой, подготовительной стадии, формируется факторная база и на ее основе генерируется система линейных уравнений в кольце ; вид факторной базы (множество простых чисел, неприводимых многочленов или других объектов) и способы получения матрицы системы зависят от выбранного алгоритма.

На второй стадии (которая является общей для рассматриваемых алгоритмов) требуется получить решение этой системы. Интенсивные предварительные вычисления для каждого поля достаточно выполнить только один раз. Затем можно быстро вычислять различные дискретные логарифмы. Таким образом, все субэкспоненциальные методы дискретного логарифмирования в конечных полях сводятся к этой задаче решения систем линейных уравнений в кольцах вычетов.

Алгоритмов, осуществляющих дискретной логарифмирование на эллиптических кривых в общем случае хотя бы с субэкспоненциальной сложностью, на сегодняшний день не существует. Тем не менее, известны работы И.А. Семаева, в одной из которых рассматривается метод, идейно близкий методам логарифмирования в конечном поле Адлемана. В другой работе для эллиптических кривых специального вида (накладываются некоторые условия на модуль арифметики и на мощность группы точек) И.А. Семаев указал способ сведения с полиномиальной сложностью задачи логарифмирования в группе точек эллиптической кривой к задаче логарифмирования в некотором расширении простого поля. При этом используется так называемое спаривания Вейля, после чего можно применять известные субэкспоненциальные методы. Аналогичные результаты опубликованы за рубежом.

2.2 Криптоанализ систем шифрования, основанных на сложности задачи факторизации

1) Метод экспоненциального ключевого обмена Диффи - Хеллмана