Распределение простых чисел в натуральном ряду и оценка 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-битового модуля, однако эта процедура более трудоемкая.

1. 
   На каждый новый аргумент функция отвечает новым значением и записывает пару (аргумент, значение) в таблицу.
   
2. 
   Если аргумент уже встречался, то функция обратится к своей таблице и вернет значение, соответствующее этому аргументу.