Понятие криптосистемы с открытым ключом. Основные криптосистемы с открытым ключом и их особенности. Криптоанализ систем шифрования, основанных на сложности задачи дискретного логарифмирования. Метод экспоненциального ключевого обмена Диффи-Хеллмана.
Аннотация к работе
В этом году американскими математиками Вайтфилдом Диффи, Мартином Хеллманом и Ральфом Меркле была представлена идеология криптосистемы с открытым ключом Кардинальное отличие криптосистемы с открытым ключом (по другой терминологии, несимметричной системы) от симметричной системы состоит в том, что в криптосистемах с открытым ключом процедура зашифровывания становится общедоступной. Понятие ключа разбивается на две части (включает теперь два понятия): ключ открытый, и ключ секретный. Именно как раз в допущении того, что нахождение ключа расшифровывания по известному ключу зашифровывания может быть сложно-вычислимой задачей, и заключается идея, которая определила дальнейшее направление развития криптографии.Криптографическая система с открытым ключом - система шифрования, при которой открытый ключ передается по открытому каналу связи, и используется для шифрования сообщения, а для расшифрования сообщения используется секретный ключ. Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций f(x), что по известному x довольно просто найти значение f(x), тогда как определение x из f(x) сложно в смысле теории. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. § Вычислительно легко создавать пару (открытый ключ, закрытый ключ); Если А хочет послать сообщение В, он шифрует сообщение, используя открытый ключ В KUB;A выбирает большое целое число х, вычисляет Х=gx mod n и передает Х участнику Б. Б в свою очередь выбирает большое целое число y, вычисляет Y=gy mod n и передает Y участнику А. Действительно, злоумышленник может узнать такие параметры алгоритма, как n, g, X, Y, но вычислить по ним значения x или y - задача, требующая очень больших вычислительных мощностей и времени (последнее утверждение верно при использовании сверхбольших чисел, размером более 768 бит). На практике при использовании данного алгоритма рекомендуется выбирать ключи размером 768, 1024 и 1536 бит. Процедуры генерации ключей, шифрования и дешифрования для этого алгоритма представлены на рис.Это алгоритмы “index-calculus”, использующие факторную базу. Первый такой алгоритм был предложен Адлеманом и имеет временную сложность при вычислении дискретного логарифма в простом поле (, где ). Алгоритм решета числового поля, предложенный Широкауэром, при работает эффективнее различных модификаций метода COS; его временная сложность составляет порядка арифметических операций. Самый простой подход к генерации соотношений вида (1) - выбрать произвольный элемент , вычислить и с помощью перебора попытаться найти числа, удовлетворяющие соотношению: , где - простые числа, такие, что <В для некоторой границы В . Выделяются два основных этапа в работе алгоритмов: на первой, подготовительной стадии, формируется факторная база и на ее основе генерируется система линейных уравнений в кольце ; вид факторной базы (множество простых чисел, неприводимых многочленов или других объектов) и способы получения матрицы системы зависят от выбранного алгоритма.s = секретный ключ. s = 2 g = открытое простое число. g = 5 p = открытое простое число. p = 23 a = секретный ключ Алисы. a = 6 A = ga mod p = 8 b = секретный ключ Боба. b = 15 B = gb mod p = 19 B = 5b mod 23 = 19 s = 196 mod 23 = 2 s = 8b mod 23 = 2 s = 196 mod 23 = 8b mod 23 s = 2 A = 5a mod 23 = 8 s = 815 mod 23 = 2 s = 19a mod 23 = 2 s = 815 mod 23 = 19a mod 23 s = 2Выберем - случайное целое число такое,что . ii. Итак , открытым является тройка ,а закрытым ключом является число . c. Вычисляем число . e. Вычисляем число . f.2) Получаем цифровой эквивалент слова БЛОГИ я решил получить его с помошью вычисления их порядковых номеров в алфавите Цифровой эквивалент = 2(Б) 13(Л) 16(О) 4(Г) 10(И). Шифрование производится по формуле yi=xie mod N, где xi цифровой эквивалент букве, остальные значения получены выше. y1=27 mod 33=128 mod 33= 29 y2=137 mod 33=62748517 mod 33= 7 y3=167 mod 33=268435456 mod 33= 25 y4=47 mod 33=16384 mod 33= 16 y5=107 mod 33=10000000 mod 33= 10 После небольших мучений с калькулятором мы получаем: x1=293 mod 33=24389 mod 33= 2 x2=73 mod 33=343 mod 33= 13 x3=253 mod 33=15625 mod 33= 16 x4=163 mod 33=4096 mod 33= 4 x5=103 mod 33=1000 mod 33= 10Чтобы снизить вероятность непредсказуемого “обвала” вновь разработанного криптоалгоритма, необходимо заблаговременное проведение криптографических исследований. Разработка любого шифра предусматривает оценку его стойкости к достаточно разнообразным типам криптоаналитических нападений. Стойкость шифра рассматривается как разработчиком, так и критиком (криптоаналитиком). Оценки критика будут опровергнуты, если кто-либо найдет и укажет принятые криптоаналитиком существенные допущения, учет которых приводит к значительному увеличению сложности предлагаемого криптоаналитического нападения. Таким образом, если криптоаналитик предлагает корректный вариант атаки, который вычислительно реализуем по оценкам, то практическая проверка должна быть положительной.
План
Содержание
Содержание
Введение
Глава 1. Криптосистемы с открытым ключом
1.1 Понятие криптосистемы с открытым ключом
1.2 Основные криптосистемы с открытым ключом и их особенности
Глава 2. Методы криптоанализа асимметричных криптосистем
2.1 Криптоанализ систем шифрования, основанных на сложности задачи дискретного логарифмирования
2.2 Криптоанализ систем шифрования, основанных на сложности задачи факторизации
Практика
1) Метод экспоненциального ключевого обмена Диффи-Хеллмана
2) Алгоритм Эль-Гамаля
3) Алгоритм RSA
Заключение
Список литературы
Введение
1976 год считается годом рождения несимметричной криптографии. В этом году американскими математиками Вайтфилдом Диффи, Мартином Хеллманом и Ральфом Меркле была представлена идеология криптосистемы с открытым ключом
Кардинальное отличие криптосистемы с открытым ключом (по другой терминологии, несимметричной системы) от симметричной системы состоит в том, что в криптосистемах с открытым ключом процедура зашифровывания становится общедоступной. Это, однако, не означает как в традиционных системах шифрования, что общедоступной является и процедура расшифровывания. Понятие ключа разбивается на две части (включает теперь два понятия): ключ открытый, и ключ секретный. Общедоступный открытый ключ используется для зашифровывания, но расшифровывание может осуществить только тот, кто владеет секретным ключом.
Именно как раз в допущении того, что нахождение ключа расшифровывания по известному ключу зашифровывания может быть сложно-вычислимой задачей, и заключается идея, которая определила дальнейшее направление развития криптографии.
Но наравне с криптографией шло развитие и криптоанализа - другого противоположного раздела криптологии, предметом которого является разработка методов взлома новых криптографических алгоритмов с целью выявления их надежности. Результатом возникновения каждого нового метода криптоанализа является пересмотр оценок безопасности шифров, что в свою очередь, влечет необходимость создания более стойких шифров.
Целью курсовой работы является анализ надежности алгоритмов ассиметричных методов шифрования.
Первая глава работы будет посвящена описанию существующих алгоритмов и их особенностей.
Во второй главе будут описаны методы криптоанализа, основанные на особенностях систем шифрования с открытым ключом.
Вывод
Чтобы снизить вероятность непредсказуемого “обвала” вновь разработанного криптоалгоритма, необходимо заблаговременное проведение криптографических исследований. Разработка любого шифра предусматривает оценку его стойкости к достаточно разнообразным типам криптоаналитических нападений. Как относиться к заявляемым оценкам стойкости с учетом того, что их получение обычно является довольно сложной задачей? Это зависит от того, кто дает оценку. Стойкость шифра рассматривается как разработчиком, так и критиком (криптоаналитиком). Оценки разработчика шифра можно считать корректными, если он делает некоторые допущения в пользу криптоаналитика. Оценки разработчика будут опровергнуты, если кто-либо укажет другой способ криптоанализа, для которого вычислительная сложность получается меньше заявляемой.
Оценки критика являются корректными, если он не занижает значение стойкости по предлагаемому им лучшему методу криптоанализа. Оценки критика будут опровергнуты, если кто-либо найдет и укажет принятые криптоаналитиком существенные допущения, учет которых приводит к значительному увеличению сложности предлагаемого криптоаналитического нападения. Таким образом, если криптоаналитик предлагает корректный вариант атаки, который вычислительно реализуем по оценкам, то практическая проверка должна быть положительной.
В обоих случаях риск того, что оценки будут скомпрометированы, тем меньше, чем больше специалистов анализировали алгоритм, чем выше их квалификация и чем больше времени они уделили анализу. Поэтому открытая публикация криптоалгоритмов, их исследование и публичное обсуждение являются необходимыми.
Для уменьшения возможного ущерба, вызванного несвоевременной заменой криптоалгоритма, потерявшего свою стойкость, желательна периодическая перепроверка стойкости криптоалгоритма. То обстоятельство, что любую задачу отыскания способа раскрытия некоторой конкретной криптосистемы можно переформулировать как привлекательную математическую задачу, при решении которой удается использовать многие методы той же теории сложности, теории чисел и алгебры, привело к раскрытию многих криптосистем. С развитием математики и средств вычислительной техники стойкость криптоалгоритма может только уменьшаться. Если влияние роста мощности компьютеров на стойкость алгоритмов еще можно предсказать с той или иной степенью точности (до настоящего момента каждое десятилетие скорость вычислений вырастала на порядок), то оценить перспективы научного прогресса не под силу даже ученым-криптографам с мировым именем. Так, в 1977 году Рон Ривест заявил, что разложение на множители 125-разрядного числа потребует 40 квадриллионов лет. Однако уже в 1994 г. было факторизовано число, состоящее из 129 двоичных разрядов!
В курсовой работе был сделан обзор основных криптосистем, основанных на использовании открытого ключа, и приведены методы криптоанализа, основанные на сложности задач дискретного логарифмирования и факторизации.
Список литературы
1. Завгородний В.И. - Комплексная защита информации в компьютерных системах. - М.: «Логос», 2003;
2. Савельева А.А. - Исследование эффективности алгоритмов дискретного логарифмирования, использующих факторную базу. - М.: «ГУВШЭ», 2007;