Распределение простых чисел в натуральном ряду и оценка rsa шифра



Скачать 431.27 Kb.
Дата18.04.2019
Размер431.27 Kb.
#6038
Название файлаСРО-3.docx
Учебное заведениеЕвразийский Национальный Университет

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

ЕВРАЗИЙСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

имени Л.Н.Гумилева

ФИЗИКО-ТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА КОСМИЧЕСКОЙ ТЕХНИКИ И ТЕХНОЛОГИЙ



СРОhttp://rud.exdat.com/pars_docs/tw_refs/705/704246/704246_html_m2d0b2a2c.png

Тема: Распределение простых чисел в натуральном ряду и оценка 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]. Суть модели состоит в следующем. Предположим, что существует некая общедоступная функция обладающая такими свойствами:

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

  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 с ненулевой вероятностью возвращает «плохие» ключи. Чтобы учесть его, требуется лишь прибавить эту вероятность к правой части неравенства.
Скачать 431.27 Kb.

Поделитесь с Вашими друзьями:

Похожие:

Распределение простых чисел в натуральном ряду и оценка rsa шифра icon" Исследование законов распределения и свойств потоков вызовов"
Рассчитать потери и опасное время используя распределение Эрланга и Биномиальное распределение. Сделать выводы
Распределение простых чисел в натуральном ряду и оценка rsa шифра iconПонятие о системах счисления
Потребность в записи чисел появилась в очень древние времена, как только люди научились считать. Известно множество способов представления...
Распределение простых чисел в натуральном ряду и оценка rsa шифра iconВозникновение чисел в нашей жизни не случайность. История чисел увлекательна и загадочна
Ничего не было, поэтому считать им было нечего. Постепенно они стали приручать скот, возделывать поля; появилась торговля, и тут...
Распределение простых чисел в натуральном ряду и оценка rsa шифра iconЛекция 1 Введение в математический анализ Предмет математики. Переменные и постоянные величины, множества. Множество действительных чисел
Математика – наука о пространственных формах и количественных отношениях реального мира. (Энгельс). Среди других наук математика...
Распределение простых чисел в натуральном ряду и оценка rsa шифра iconКурсоваяработа по мдк. 04. 02 Основы анализа бухгалтерской отчетности Тема работы: Оценка финансового состояния: оценка платежеспособности, финансовой устойчивости ао «сезам»
Тема работы: Оценка финансового состояния: оценка платежеспособности, финансовой устойчивости ао «сезам»
Распределение простых чисел в натуральном ряду и оценка rsa шифра iconРешение вычисление годовой процентной ставки формула для вычисления годовой процентной ставки по формуле простых процентов
Мюнхен выдало февраля 015 г кредит концерну X на сумму 000 000 €. Срок погашения кредита наступает августа 1016 г. Концерн обязался...
Распределение простых чисел в натуральном ряду и оценка rsa шифра icon• объем выпуска продукции в натуральном выражении
Влияние корпоративной культуры на повышение эффективности деятельности предприятия Полищук Елена Васильевна, аспирант Столичная финансово-гуманитарная...
Распределение простых чисел в натуральном ряду и оценка rsa шифра iconПедагогическая оценка
Функции педагогической оценки – согласно Б. Г. Ананьеву, педагогическая оценка выполняет две главные функции
Распределение простых чисел в натуральном ряду и оценка rsa шифра icon«Распределение доходов и проблема социального неравенства»»

Распределение простых чисел в натуральном ряду и оценка rsa шифра iconУтверждено на заседании кафедры
Охватывает распределение: +Межтерриториальные




База данных защищена авторским правом ©refnew.ru 2022
обратиться к администрации

    Главная страница
Контрольная работа
Курсовая работа
Теоретические основы
Методические указания
Методические рекомендации
Лабораторная работа
Рабочая программа
Общая характеристика
Теоретические аспекты
Учебное пособие
Практическая работа
История развития
Самостоятельная работа
Пояснительная записка
Дипломная работа
Методическая разработка
Общие положения
Экономическая теория
Исследовательская работа
Физическая культура
Методическое пособие
Федеральное государственное
Общая часть
Теоретическая часть
Направление подготовки
Общие сведения
Конституционное право
Техническое задание
Управления государственных
Общие вопросы
государственное бюджетное
Образовательная программа
Организация работы
Выпускная квалификационная
Российская академия
Понятие сущность
Правовое регулирование
Усиление колониальной
реакция казахского
Техническое обслуживание
Основная часть
программное обеспечение
Обеспечение безопасности
прохождении производственной
Экономическая безопасность
образовательное частное
Теория государства
курсовая работа
академия народного
Административное право
Название дисциплины