📄Работа №77610
Тема: Методы факторизации натуральных чисел
Тип работы
Дипломные работы, ВКР
Предмет
информационные системы
Объем:
52 листов
Год:
2016
Просмотров:
394
4330
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Глава 1. Анализ предметной области 5
1.1. Методы криптографии 5
1.2. Ассиметричные системы шифрования 5
1.3. Алгоритм Диффи-Хеллмана обмена ключами [16] 6
1.4. Система шифрования Эль-Гамаля [12] 8
1.5. Алгоритм RSA [24] 9
1.6. Задачи вычисления закрытого ключа при наличии открытого [11] 11
1.6.1. Дискретное логарифмирование в конечной группе [13] 12
1.6.2. Дискретное логарифмирование в группе точек эллиптической кривой 12
1.6.3. Факторизация чисел 12
Глава 2. Субэкспоненциальные алгоритмы 14
2.1. Метод Диксона 14
2.2. Метод квадратичного решета [1] 17
2.3. Метод Ленстры [4,5] 19
Глава 3. Реализация алгоритмов 22
Глава 4. Сравнение и анализ полученных результатов 26
Заключение 29
Список литературы 31
Приложение 1. Таблицы результатов 34
Приложение 2. Листинг
Глава 1. Анализ предметной области 5
1.1. Методы криптографии 5
1.2. Ассиметричные системы шифрования 5
1.3. Алгоритм Диффи-Хеллмана обмена ключами [16] 6
1.4. Система шифрования Эль-Гамаля [12] 8
1.5. Алгоритм RSA [24] 9
1.6. Задачи вычисления закрытого ключа при наличии открытого [11] 11
1.6.1. Дискретное логарифмирование в конечной группе [13] 12
1.6.2. Дискретное логарифмирование в группе точек эллиптической кривой 12
1.6.3. Факторизация чисел 12
Глава 2. Субэкспоненциальные алгоритмы 14
2.1. Метод Диксона 14
2.2. Метод квадратичного решета [1] 17
2.3. Метод Ленстры [4,5] 19
Глава 3. Реализация алгоритмов 22
Глава 4. Сравнение и анализ полученных результатов 26
Заключение 29
Список литературы 31
Приложение 1. Таблицы результатов 34
Приложение 2. Листинг
📖 Введение
В современном мире в условиях глобальной информатизации компьютерные технологии имеют широкое распространение практически во всех сферах жизни человечества. В связи с этим одной из опасных угроз является угроза несанкционированного доступа к информации [25], и для противодействия этому применяются разные методы и средства, в частности, криптографическая защита данных.
Имеется два вида криптографических алгоритмов: симметричные [15], в которых один ключевой элемент довольно легко вычисляется при наличии второго, помимо этого быстро происходит преобразование данных, и несимметричные [10]. Их особенность - наличие двух ключей, при этом вычисление одного, если имеется другой, является вычислительно сложной задачей.
В качестве этих задач выступают:
1. задача дискретного логарифмирования [3,6] в группе точек эллиптической кривой;
2. задача дискретного логарифмирования в конечной группе (алгоритм Диффи-Хеллмана);
3. факторизация натуральных чисел (алгоритм шифрования RSA).
В настоящее время активно ведутся исследования в области алгоритмов факторизации. Факторизация натурального числа [2,4] - это его разложение на множители. Постоянно проводятся различные конференции по данной тематике, достигаются новые рекорды в поисках множителей, находятся решения текущих проблем теории чисел и ставятся новые. В двухтысячных годах было разложено 512-битное число. Прошло почти 10 лет (2009г.), и был установлен рекорд по разложению числа размером 768 бит с помощью метода
Дипломная работа посвящена сравнительному анализу методов факторизации натуральных чисел. Задача факторизации актуальна тем, что выступает основой ряда алгоритмов безопасности, использующих открытые ключи шифрования (RSA [27] и некоторые других). Криптостойкость шифров базируется на предположении, что не существует быстрых алгоритмов факторизации, которые за короткое время позволили бы взломать код, а если это и получится сделать через некоторое время, то данные потеряют актуальность.
В ходе работы были поставлены следующие задачи:
• рассмотреть алгоритмы факторизации натуральных чисел, имеющих
субэкспоненциальную сложность: алгоритм Диксона, метод
квадратичного решета, метод Ленстры [14];
• разработать программный комплекс, осуществляющий разложение чисел на простые множители данными алгоритмами;
• провести общую оценку методов;
• на основе полученных результатов выявить их преимущества и
недостатки.
Имеется два вида криптографических алгоритмов: симметричные [15], в которых один ключевой элемент довольно легко вычисляется при наличии второго, помимо этого быстро происходит преобразование данных, и несимметричные [10]. Их особенность - наличие двух ключей, при этом вычисление одного, если имеется другой, является вычислительно сложной задачей.
В качестве этих задач выступают:
1. задача дискретного логарифмирования [3,6] в группе точек эллиптической кривой;
2. задача дискретного логарифмирования в конечной группе (алгоритм Диффи-Хеллмана);
3. факторизация натуральных чисел (алгоритм шифрования RSA).
В настоящее время активно ведутся исследования в области алгоритмов факторизации. Факторизация натурального числа [2,4] - это его разложение на множители. Постоянно проводятся различные конференции по данной тематике, достигаются новые рекорды в поисках множителей, находятся решения текущих проблем теории чисел и ставятся новые. В двухтысячных годах было разложено 512-битное число. Прошло почти 10 лет (2009г.), и был установлен рекорд по разложению числа размером 768 бит с помощью метода
Дипломная работа посвящена сравнительному анализу методов факторизации натуральных чисел. Задача факторизации актуальна тем, что выступает основой ряда алгоритмов безопасности, использующих открытые ключи шифрования (RSA [27] и некоторые других). Криптостойкость шифров базируется на предположении, что не существует быстрых алгоритмов факторизации, которые за короткое время позволили бы взломать код, а если это и получится сделать через некоторое время, то данные потеряют актуальность.
В ходе работы были поставлены следующие задачи:
• рассмотреть алгоритмы факторизации натуральных чисел, имеющих
субэкспоненциальную сложность: алгоритм Диксона, метод
квадратичного решета, метод Ленстры [14];
• разработать программный комплекс, осуществляющий разложение чисел на простые множители данными алгоритмами;
• провести общую оценку методов;
• на основе полученных результатов выявить их преимущества и
недостатки.
✅ Заключение
В ходе дипломной работы были рассмотрены основные методы криптографии. Были изучены основные ассиметричные алгоритмы шифрования, такие как протокол Диффи-Хеллмана, схема шифрования Эль¬Гамаля и криптосистема RSA. Разобраны атаки, основанные на факторизации чисел. В частности, реализованы и проанализированы алгоритмы факторизации натуральных чисел, имеющих субэкспоненциальную сложность: алгоритм Диксона, метод квадратичного решета, метод Ленстры.
Проведены вычислительные эксперименты на числах разной размерности, на основе которых были выявлены преимущества и недостатки данных методов. Все три метода довольно быстро, за доли секунды, раскладывают числа малой размерности (до 32 бит). При этом каждый метод имеет свои особенности. Метод Ленстры при увеличении факторизуемого числа дольше вычисляет множители. Однако, если один из множителей сравнительно небольшой, разложение происходит быстрее. Метод квадратичного решета показывает хорошие результаты, близкие к методу Ленстры. Алгоритм Диксона требует гораздо больше времени на вычисления и сильно зависит от выбора матрицы, составленной из соответствующих векторов.
Существует немало различных методов факторизации, однако при определенной длине ключ имеет высокую стойкость к факторизации. Таким образом задача модификации текущих алгоритмов факторизации вполне актуальна. Кроме этого не менее актуальной стоит задача создания новых алгоритмов. Основные направления модификации - распараллеливание вычислительных задач (актуально к факторизации на эллиптических кривых), использование быстрых вычислений, оптимизация процесса вычислений, применение новых алгоритмов и другие. Из графиков и полученных выше результатов видно, что наиболее лучшими кандидатами для модификации являются метод Ленстры и метод квадратичного решета.
Исследование существующих в настоящее время методов факторизации позволит изучить, проанализировать и найти недостатки и вероятные пути улучшения существующих алгоритмов факторизации. При исследовании алгоритмов важно выделить особые блоки алгоритма и их модифицировать.
Проведены вычислительные эксперименты на числах разной размерности, на основе которых были выявлены преимущества и недостатки данных методов. Все три метода довольно быстро, за доли секунды, раскладывают числа малой размерности (до 32 бит). При этом каждый метод имеет свои особенности. Метод Ленстры при увеличении факторизуемого числа дольше вычисляет множители. Однако, если один из множителей сравнительно небольшой, разложение происходит быстрее. Метод квадратичного решета показывает хорошие результаты, близкие к методу Ленстры. Алгоритм Диксона требует гораздо больше времени на вычисления и сильно зависит от выбора матрицы, составленной из соответствующих векторов.
Существует немало различных методов факторизации, однако при определенной длине ключ имеет высокую стойкость к факторизации. Таким образом задача модификации текущих алгоритмов факторизации вполне актуальна. Кроме этого не менее актуальной стоит задача создания новых алгоритмов. Основные направления модификации - распараллеливание вычислительных задач (актуально к факторизации на эллиптических кривых), использование быстрых вычислений, оптимизация процесса вычислений, применение новых алгоритмов и другие. Из графиков и полученных выше результатов видно, что наиболее лучшими кандидатами для модификации являются метод Ленстры и метод квадратичного решета.
Исследование существующих в настоящее время методов факторизации позволит изучить, проанализировать и найти недостатки и вероятные пути улучшения существующих алгоритмов факторизации. При исследовании алгоритмов важно выделить особые блоки алгоритма и их модифицировать.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.