Актуальные способы оценки простоты чисел

Применение простых чисел в области защиты информации, вызванное изобретением криптографии с ассиметричным ключом, применяющейся в алгоритмах электронной цифровой подписи. Классы алгоритмов тестирования чисел на простоту. Вероятность ошибки теста.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.