Актуальные способы оценки простоты чисел
Применение простых чисел в области защиты информации, вызванное изобретением криптографии с ассиметричным ключом, применяющейся в алгоритмах электронной цифровой подписи. Классы алгоритмов тестирования чисел на простоту. Вероятность ошибки теста.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 22.03.2018 |
| Размер файла | 45,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru//
Актуальные способы оценки простоты чисел
Раков Николай Борисович,
магистрант Юго-Западного государственного университета
На современном этапе развития информационного общества применение простых чисел получило широкое распространение в области защиты информации, прежде всего, это вызвано изобретением криптографии с ассиметричным ключом, применяющейся в алгоритмах электронной цифровой подписи, являющихся одним из основных областей, где нашли практическое применение простые числа. На данный момент размер простых чисел используемых при формировании цифровой подписи с использованием эллиптических кривых составляет: в соответствии сГОСТ Р 34.10-2012 не менее 254 бит (предлагается использование 512 битных ключей), а в ECDSA и стандарте подписи Германии не менее 160 бит [2]. Определить простоту чисел с такой разрядностью, посредством использования простых способов нахождения начального списка простых чисел (Решето Эратосфена, решето Сундарама и решето Аткина) вплоть до некоторого значения, не предоставляется возможным, вследствие низкой скорости работы данных алгоритмов и использования не малых вычислительных ресурсов системы.
Впрочем, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты.
Все существующие алгоритмы тестирования чисел на простоту можно разделить на два класса:
1. Вероятностные тесты, позволяют определить простоту числа с некоторой достаточно низкой вероятностью ошибки. Среди них можно выделить следующие, наиболее эффективные тесты простоты:
Тест Ферма - базируется на малой теореме Ферма. Весьма эффективен в обнаружении составных чисел, тем не менее, существуют составные числа, которые ведут себя как простые в малой теореме Ферма, не являясь при этом таковыми. Такие числа называются кармайкловыми.
Вероятность ошибки теста составляет ek, где k - число итераций теста, , где j(n) - Функция Эйлера, n -- проверяемое число. Рекомендуется совершать где-то 50 итераций данного теста.
Тест Соловея-Штрассена основан на различии между символами Якоби и Лежандра. Тест всегда корректно определяет, что простое числоявляется простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Вероятность ошибки составляет ek, где k - число итераций теста,. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные [4]. Улучшение алгоритма данного теста предложенное Балабановым А.А., Агафоновым А.Ф. и Рыку В.А,. за счет перехода к вычислению величины, являющейся обратной символу Якоби позволяет его ускорить, особенно при работе с числами порядка до 30 бит почти в 1000 раз [1]. Не смотря на это, достоверности теста Соловея-Штрассена не является достаточной, вместо него используется тест Миллера-Рабина.
Тест Миллера-Рабина также, как и предыдущие тесты, является вероятностным тестом, однако реализовывается на ЭВМ более эффективно чем тест Соловея-Штрассена, а также вероятность ошибки у теста Миллера-Рабина гораздо ниже чем у первых двух тестов. Обычно для опознания простого числа достаточно одной итерации теста, но все же рекомендуемое количество итераций должно быть порядка , где n -- проверяемое число. Вероятность ошибки теста на одной итерации составляет , то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза - для теста Ферма [3]. Теоретическая сложность вычислений всех выше перечисленных тестов оценивается как .
Вероятностные тесты в большинстве случаев применяют в связки с другими тестами (метод простого деления и тест Миллера-Рабина), а также между собой - тест BPSW на простоту чисел был получен благодаря объединению тестов Миллера-Рабина и Лукаса-Селфриджа, к алгоритму которого не было найдено ни одного контрпримера, равно как и не было найдено доказательство его абсолютной точности.
2. Детерминированные тесты - дают гарантированно точный ответ простое ли исследуемое число или нет. Не смотря на это не получили широкого практического применения вследствие сложности алгоритмов их реализации и ввиду того что они работают с определенными группами простых чисел (Мерсенна, Прота, Ферма и т. д.), за исключением теста Агравала-Каяла-Саксены, который на данный момент является единственным детерминированным, полиноминальным, универсальным тестом простоты чисел, время работы которого в соответствии с последними улучшениями алгоритма стремится к [5].
В криптографических алгоритмах одной из важнейших задач является умение быстро отличить простое число от составного. Вероятностные тесты, как ни посмотри, куда больше под стать данному требованию, их скорость не имеет себе равных среди детерминированных тестов, да и случай возникновения ошибки имеет настолько малый процент вероятности, что при проведении подряд нескольких таких тестов стремится к нулю. Тест на простоту Миллера-Рабина, является самым эффективным из вероятностных тестов, он в совокупности с методом «простого деления» зарекомендовал себя как наиболее используемый в криптографии, для тестирования больших случайных чисел на простоту, и самым используемым в алгоритмах формирования цифровой подписи. Тем не менее, в случае дальнейшей доработки и улучшения детерминированного тест Агравала-Каяла-Саксены (увеличения скорости его выполнения), он может занять лидирующую позицию среди тестов проверки простоты чисел.
простота число криптография тестирование
Литература
1. Балабанов А.А., Агафонов А.Ф., Рыку В.А. «Алгоритм быстрой генерации ключей в криптографической системе RSA»-- Вестник научно-технического развития, 2009 №7(23). -- С. 11.
2. ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».
3. Молдовян Н.А., Молдовян А.А. Введение в криптосистемы с открытым ключом. - СПб.: БХВ-Петербург, 2005. 288 с.: ил.
4. Ниссенбаум О.В., Овсянко А.Г. Криптографические методы защиты информации. Генерация больших простых чисел в криптосистемах с открытым ключом: Учебно-методическое пособие. - Тюмень: Издательство Тюменского государственного университета, 2009. - 41 с.
5. H. W. Lenstra jr. and Carl Pomerance, «Primality testing with Gaussian periods», version of April 12, 2011.
Размещено на Allbest.ru
...Подобные документы
История алгоритмов симметричного шифрования (шифрования с закрытым ключом). Стандарты на криптографические алгоритмы. Датчики случайных чисел, создание ключей. Сфера интересов криптоанализа. Системы электронной подписи. Обратное преобразование информации.
краткое изложение [26,3 K], добавлен 12.06.2013Поиск взаимно простых чисел. Алгоритм Евклида для целых чисел. Описание выбранного языка программирования. Алгоритм решения задачи. Обзор средств программирования. Текст и описание программы. Руководство оператора, программа и методика испытаний.
курсовая работа [843,5 K], добавлен 15.06.2011Факторизация натурального числа. Метод квадратичного решета. Факторизация с помощью эллиптических кривых. Реализация алгоритмов натуральных чисел и оценка их эффективности. Применение алгоритмов факторизации натуральных чисел в программной среде Maple.
курсовая работа [851,6 K], добавлен 25.06.2013Преобразование чисел из естественной формы в нормализованную. Алгоритм нормализации числа. Способы кодирования чисел и действия над ними. Особенности прямого, дополнительного, смещенного и обратного кода. Понятие вещественных чисел, их представление.
презентация [42,6 K], добавлен 14.06.2011Организационно-правовое обеспечение электронной цифровой подписи. Закон "Об электронной цифровой подписи". Функционирование ЭЦП: открытый и закрытый ключи, формирование подписи и отправка сообщения. Проверка (верификация) и сфера применения ЭЦП.
курсовая работа [22,9 K], добавлен 14.12.2011Симметричные и асиметричные методы шифрования. Шифрование с помощью датчика псевдослучайных чисел. Алгоритм шифрования DES. Российский стандарт цифровой подписи. Описание шифрования исходного сообщения асимметричным методом с открытым ключом RSA.
курсовая работа [101,1 K], добавлен 09.03.2009Формирование устойчивой последовательности псевдослучайных чисел с использованием метода "середины квадрата". Разработка программы для определения среднего значения чисел, среднего значения квадратов чисел и дисперсии для последовательности из 20 чисел.
лабораторная работа [1,4 M], добавлен 21.01.2015Анализ характеристик средств криптографической защиты информации для создания электронной цифровой подписи. Этапы генерации ключевого контейнера и запроса при помощи Удостоверяющего центра с целью получения сертификата проверки подлинности клиента.
реферат [604,6 K], добавлен 14.02.2016Изучение основных методов и алгоритмов криптографии с открытым ключом и их практического использования. Анализ и практическое применение алгоритмов криптографии с открытым ключом: шифрование данных, конфиденциальность, генерация и управление ключами.
дипломная работа [1,2 M], добавлен 20.06.2011Написание программы для генерации случайных чисел, в которой реализуются возможности генерации абсолютно случайных чисел. Приложение на языке С/С++. Описание узла, содержащего данные; функций и методов работы; чтения данных из памяти и вывода их на экран.
курсовая работа [172,4 K], добавлен 23.05.2012Анализ возможностей платформы. Классификация грамматик по Хомскому. Способы задания языков. Разработка алгоритмов выполнения файловых операций на основе спроектированных интерфейсов. Криптосистема с открытым ключом. Свойства электронной цифровой подписи.
дипломная работа [3,6 M], добавлен 24.07.2014Программирование микро ЭВМ на МП БИС КР580ИК80. Арифметические команды. Представление чисел в различных системах счисления и отображение их на дисплее. Сложение массива однобайтных чисел. Вычитание одинаковых чисел. Сложение двух десятичных чисел.
лабораторная работа [263,8 K], добавлен 03.03.2009Двоичный код, особенности кодирования и декодирования информации. Система счисления как совокупность правил записи чисел с помощью определенного набора символов. Классификация систем счисления, специфика перевода чисел в позиционной системе счисления.
презентация [16,3 K], добавлен 07.06.2011Общая характеристика электронной подписи, ее признаки и составляющие, основные принципы и преимущества применения. Использование электронной цифровой подписи в России и за рубежом. Правовое признание ее действительности. Сертификат ключа проверки ЭЦП.
курсовая работа [27,2 K], добавлен 11.12.2014Способы получения случайных чисел в программировании и их использование для решения ряда задач. Принцип действия и тестирование работы генератора случайных чисел в Borland C++, его преимущества. Генерация одномерной и двумерной случайной величины.
лабораторная работа [105,4 K], добавлен 06.07.2009Общая схема цифровой подписи. Особенности криптографической системы с открытым ключом, этапы шифровки. Основные функции электронной цифровой подписи, ее преимущества и недостатки. Управление ключами от ЭЦП. Использование ЭЦП в России и других странах.
курсовая работа [288,2 K], добавлен 27.02.2011Этапы статистического анализа данных, приемы и методы его проведения. Ключевые положения закона больших чисел в теории вероятностей, его общий смысл. Теорема Бернулли - простейшая форма закона больших чисел. Количество данных, способы его измерения.
реферат [112,3 K], добавлен 03.03.2014Основные алгоритмы реализации электронной цифровой подписи. Понятие секретного и открытого ключа. Программные модули, сроки действия и порядок функционирования электронной подписи. Технология работы с информационной системой "ЭЦП", перспективы развития.
курсовая работа [1,1 M], добавлен 07.12.2010Применение случайных чисел в моделировании, выборке, численном анализе, программировании и принятии решений. Понятие равномерного распределения вероятности. Способы получения последовательности. Правила выбора модуля. Критерий Колмогорова-Смирнова.
курсовая работа [1,3 M], добавлен 17.03.2011Подання чисел у нормальній формі. Порядок нормалізації чисел з рухомою комою. Правила додавання двійкових чисел з рухомою комою. Алгоритми і програми додавання чисел в арифметиці з рухомою комою в інструкціях навчального комп'ютера-симулятора DeComp.
лабораторная работа [31,7 K], добавлен 13.03.2011
