Значимость генерации простых чисел в асимметричных системах шифрования

Стремительное развитие коммуникационных и информационных технологий значительно повышает актуальность проблемы, связанной с информационной безопасностью. На этом основании целесообразной является разработка ряда новых средств и методов, направленных, в первую очередь, на обеспечение информационной безопасности. Требуется комплексный подход для надёжного её обеспечения. На этой почве возникла необходимость эффективного использования организационных, правовых и инженерно-технических обеспечений защиты информации. Криптографические методы, в частности, играют важную роль в этом процессе. Как следствие, на сегодняшний день широкое распространение получили криптографические системы защиты информации. Их основу составляет работа криптографического алгоритма. В настоящее время в качестве базиса для многих криптографических стандартов берутся алгоритмы Эль-Гамаль и RSA, которые основаны на задаче факторизации и дискретном логарифмировании в конечном поле. Для создания электронной цифровой подписи и шифрования данных в обоих алгоритмах используются большие и 1024-битные простые числа. Таким образом, генерирование больших простых чисел и работа с ними стали одним из главных вопросов, решением которых занимается криптография. Собственно, на основании трудности их обнаружения они и получили столь широкое использование в криптографии и весомую значимость в области её исследований.

Одной из главных проблем асимметричного шифрования является генерация больших простых чисел. Простейшим методом проверки простоты натурального числа N является метод пробных делений: для d = 2, 3, 4 … мы проверяем выполнение условия – d, N > 1 (здесь (d, N – наибольший общий делитель чисел d и N). Количество операций, требуемых для этого метода, имеет порядок корня из N. Поэтому он не применим уже для чисел порядка 1040–1050.

В отличие от подобных «детерминированных» тестов существуют также «вероятностные» тесты проверки простоты, суть которых в проверке выполнения для исследуемого числа некоторых условий, связанных со случайными числами. Если какое-либо из них условий не является выполнимым, то делаем вывод, что N – составное число. В противном случае с некоторой вероятностью можно утверждать, что N – простое число. Чем большее количество случайных чисел проверяется, тем вероятность ближе к ста процентам. Как правило, эти условия основаны на малой теореме Ферма, которая гласит, что для любого положительного числа b, не превосходящего некоторое простое число p: b(p–1) = 1(mod p).

Например, 26 ⇒ 64 ⇒ 63+1 = 1(mod 7). Если требуется определить, является ли целое число a простым, можно выбрать любое положительное целое число b, которое меньше, чем число a, и проверить, выполняется ли равенство b(a–1) = 1(mod a).

Если равенство невыполнимо, то на основании теоремы Ферма можно с полной уверенностью сказать, что a простым числом не является. В противном случае можно лишь предполагать, что r – простое число, и на этом основании назвать его «псевдопростым по основанию b». Вероятность P (x) того, что число x окажется в итоге псевдопростым по некоторому основанию, убывает с ростом x.

Простые числа повсеместно используются в нашей повседневной жизни, например, в персональных компьютерах и кредитных картах, поэтому существует потребность в новых простых числах для генерации секретных кодов (чем больше, тем лучше). Таким образом, имеется спрос на простые числа, но их производство имеет не большую значимость, чем контроль качества. Для того чтобы некоторому большому числу присвоить статус простого, его сначала должна проверить специальная организация. Поиск больших простых чисел прежде требовал специального программного обеспечения, которое, как правило, можно было купить лишь в специализированных фирмах или в университетах, занимающихся такими исследованиями. Однако появление более совершенных алгоритмов b экспоненциальный рост вычислительных мощностей изменили рынок простых чисел, сделав их гораздо более доступными.

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