МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РЕСПУБЛИКИ КАЗАХСТАН
ЕВРАЗИЙСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ
имени Л.Н.Гумилева
ФИЗИКО-ТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ
КАФЕДРА КОСМИЧЕСКОЙ ТЕХНИКИ И ТЕХНОЛОГИЙ
СРО
Тема: Распределение простых чисел в натуральном ряду и оценка RSA шифра.
Выполнили: Саясат Н.Ж.
Суендиков А.К.
Проверил: Игембаев Б.А.
АСТАНА 2018
Для построения современных криптосистем необходимы очень большие простые числа. Например, в системе RSA и различных системах, основанных на задаче дискретного логарифмирования в конечных полях, требуются «случайные» простые числа, записи которых в десятичной системе счисления состоят из сотен цифр. Первый существенный успех в изучении распределения простых чисел связан с именем русского учёного П. Л. Чебышёва (1821—1894), который совершенно элементарными методами выяснил истинный порядок роста функции π(x), именно: доказал существование таких положительных констант a и b, что для всех x > 2 выполняются неравенства
В 1845 году французский математик Ж. Бертран, анализируя таблицы простых чисел << 3 000 000 в связи со своими исследованиями по теории групп, высказал предположение, с тех пор известное как Постулат Бертрана. При n > 4 в интервале (n, 2n−2) содержится хотя бы одно простое число. Вскоре этот постулат был доказан Чебышёвым в его знаменитой работе «О простых числах» («Memoire sur les nombres premiers», 1850 год).
Весьма подробно рассмотрена широко распространенная криптосистема с открытым ключом – криптосистема RSA. На примере этой криптосистемы показано применение почти всех рассмотренных нами понятий и методов теории чисел. В полном объеме доказана корректность алгоритма RSA. Описан способ ускорения процедуры расшифровывания. Рассмотрены вопросы сопоставления сложностей взлома криптосистемы RSA и проблемы факторизации. Уделено внимание правильному выбору параметров криптосистемы. Описана достаточно сложная атака на криптосистему RSA – атака Винера. Кроме того, предложены две учебные версии криптосистемы RSA, предназначенные для наглядного и более глубокого изучения проблем программной реализации этой криптосистемы.
RSA – наиболее популярная криптосистема с открытым ключом. Алгоритм RSA, первый из алгоритмов шифрования с открытым ключом, достойно выдержал испытание временем. Этот алгоритм основывается на задаче RSA. Напомним, что она сводится к поиску простых делителей больших натуральных чисел. Можно утверждать, что крипто- стойкость алгоритма RSA базируется на сложности проблемы факторизации, но не в полной мере, поскольку задачу RSA можно решать, не прибегая к разложению модуля на множители. Пусть пользователь А считает нужным разрешить всем желающим отправлять ему конфиденциальные сообщения, расшифровать которые способен только он. Тогда А подбирает два больших простых числа р и q. Держа их в секрете, А публикует их произведение N = p·q, которое называют модулем алгоритма. Кроме того, А выбирает число Е, удовлетворяющее соотношению
Выбор параметров проводится по аналогии со случаем 16-битового модуля, однако эта процедура более трудоемкая.
Безопасность RSA-KEM может быть проанализирована в модели случайного оракула (Random Oracle Model, далее RO)[2]. Суть модели состоит в следующем. Предположим, что существует некая общедоступная функция обладающая такими свойствами:
-
На каждый новый аргумент функция отвечает новым значением и записывает пару (аргумент, значение) в таблицу.
-
Если аргумент уже встречался, то функция обратится к своей таблице и вернет значение, соответствующее этому аргументу.
Доказательство основано на предположении, что KDF является случайным оракулом, и что решение обратной задачи RSA невозможно (проще говоря, RSA нельзя взломать). Для любого алгоритма генерации ключа для RSA (то есть алгоритма, возвращающего n, e и d), всегда выполнено n >= nBound (то есть nBound наименьшая допустимая граница для чисел n), и для каждого злоумышленника A справедливо:
где {\displaystyle qD} — это максимальное число запросов к оракулу, которое может сделать злоумышленник для попытки разгадать шифр{\displaystyle A} A, AdvantageRSA-KEM(A) = |Pr[b*-b] - 1/2| — предсказательная способность А, AdvantageRSA(A') обозначает вероятность успешного решения инверсной задачи RSA. Нужно заметить, что приведенное выше неравенство не учитывает тот факт, что в реальности {\displaystyle RSAKeyGen}RSAKeyGen с ненулевой вероятностью возвращает «плохие» ключи. Чтобы учесть его, требуется лишь прибавить эту вероятность к правой части неравенства.
Поделитесь с Вашими друзьями: |