Распределение простых чисел в натуральном ряду и оценка 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Тема. Число І цифра Написання цифри Послідовність чисел від 0 до 10. Віднімання рівних чисел. Додавання й віднімання нуля. Розв’язування прикладів на додавання й віднімання. Геометричне поняття: круг

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




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

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