Роль больших простых чисел в современной криптографии | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Информатика

Опубликовано в Молодой учёный №9 (113) май-1 2016 г.

Дата публикации: 01.05.2016

Статья просмотрена: 1877 раз

Библиографическое описание:

Норматов Ш. Б. Роль больших простых чисел в современной криптографии // Молодой ученый. — 2016. — №9. — С. 74-77. — URL https://moluch.ru/archive/113/20400/ (дата обращения: 19.12.2018).



Роль больших простых чисел в современной криптографии

Норматов Шербек Бахтиёрович, старший преподаватель

Каршинский филиал Ташкентского университета информационных технологий (Узбекистан)

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

Ключевые слова: информационная безопасность, криптография, простые числи, алгоритмы шифрование, проверка числа на простоту.

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

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

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

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

Определяем общее количество всех 32-битных натуральных чисел и 32-битных простых чисел.

Самое большое 32-битное число и 31-битное число . Количество всех 32-битные чисел можно вычислить следующим образом:

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

Количество, не превышающее 32 уровни простых чисел, можно вычислить следующим образом:

(Здесь,).

Количество, не превышающее 31 уровня простых чисел, можно вычислить следующим образом:

Таким образом, количество 32-битных простых чисел равно Значит, можно сделать вывод о том, что существует единое простое число в каждой 30 чисел в этом интервале.

Мы можем отобразить 32-битное число по следующему выражению:

1

1

Для того что бы использовать 32-разрядное число, последний разряд должен быть равен единице. Первый разряд равен единице, что означает, число является нечетным. Все простые числа являются нечетными, так что придётся игнорировать все четные числа.

В алгоритме генерирования простых чисел в данном интервале предусматриваются следующие две задачи:

а) выбор числа в данном интервале;

б) проверка чисел на простоту.

Если выбранное число из данного интервала является простым, то оно добавляется в таблицу простых чисел. В противном случае придётся выбрать другое число и проверить его на простоту (1-схема).

Рис. 1. Алгоритм генерация простых чисел.

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

Следующей задачей является проверка выбранного числа на простоту. Существуют некоторые вероятностные тесты на простоту. Одним из них является тест Рабина-Миллера, который основан на идею малой теоремы Ферма.

Малая теорема Ферма утверждает, что если простое число, то выполняется условие: при всех имеет место сравнение Если для некоторого имеет место соотношение , то говорят, что число является простыми по основанию [4].

Сначала обозначаем как , где нечетное число. Обозначаем . Тогда достойна

Любое двоичное число может быть обозначено как: Если вынести за скобки , получим следующее выражение: здесь и , иначе число считается четным. Если и вынести за скобки то Где

Если выражение устраивает, тогда число считается нечетным. Если то вынести за скобки получиться Где

а) если , то и является простыми числами с вероятностями.

б) если не устраивает, тогда проверяется .

Если , то и является простыми числами с вероятностями. Если отношение не устраивает, тогда проверяется .

Точно также проверяется степень до раза. Если во всех случаях отношения не устраивает, тогда не является простыми.

Если во всех случаях уточняется, является простыми с вероятностями [3].

Необходимо учитывать следующие вопросы генерации больших простых чисел:

а) выбора числа случайном образом в данном интервале;

б) распределения найденных простых чисел в таблице простых чисел;

в) при необходимости из таблицы простых чисел выбрать последовательным или случайным образом.

Литература:

  1. Алгебра теория чисел. II часть. Р. Н. Назаров, Б. Т. Тошпулатов, А. Д. Дусимбетов. “Тошкент” 1995.
  2. Нильс Фергюсон, Брюс Шнайер. Практическая криптография. Москва. Санкт-Петербург. Киев. 2005. 421 стр.
  3. http://www.sans.org/reading-room/whitepapers/vpns/prime-numbers-public-key-cryptography-969
  4. http://home.sandiego.edu/~dhoffoss/teaching/cryptography/10-Rabin-Miller.pdf
Основные термины (генерируются автоматически): число, информационная безопасность, алгоритм, выбранное число, выбор числа, RSA, современная криптография, случайный образ, малая теорема, интервал.


Ключевые слова

Информационная безопасность, криптография, простые числи, алгоритмы шифрование, проверка числа на простоту

Похожие статьи

Особенности проектирования и криптоанализа асимметричной...

RSA, число, простое число, тест, выбор показателей, случайный сеансовый ключ, случайный образ, секретный показатель, простой перебор, AES.

Криптография. Основные методы и проблемы. Современные...

Основные термины (генерируются автоматически): криптография, RSA, ключ, квантовая криптография, канал связи, алгоритм, электронная

Современные проблемы в области информационной безопасности: классические угрозы, методы и средства их предотвращения.

Исследование криптосистем с открытым ключом на основе...

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

3. Выбирается целое число e, взаимно простое со значением функции Эйлера от числа n из интервала (1; φ(n)).

Методы генерации случайных чисел | Статья в журнале...

Чаще всего случайные числа требуются в задачах моделирования, численного анализа, тестирования, криптографии и теории игр

Основные термины (генерируются автоматически): число, случайное число, простое число, случайная последовательность, работа алгоритма...

Анализ алгоритма RSA. Некоторые распространённые...

Прежде всего, на случайные числа и необходимо наложить следующие ограничения

Теорема (Винера).

3. Венбо Мао Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice.

Генераторы случайных и псевдослучайных чисел

Те, кто знаком с криптографией, прекрасно понимают важность случайных чисел. Практически каждый алгоритм шифрования содержит как минимум один параметр с характеристиками «случайное число».

Теория чисел в криптографии | Статья в журнале...

Теория чисел в криптографии. Автор: Тагиров Кадир Межвединович.

Корректность алгоритма: согласно теореме Ферма [6, с. 90], для каждого целого числа , взаимно простого с модулем , выполняется

Вычисление факторизации чисел RSA-1024, RSA-2048, и других.

Реализация Windows-приложения, выполняющего шифрование...

Ключевые слова: шифрование, криптосистема RSA. На данный момент в современном мире защита информации играет немаловажную задачу.

Затем пользователи получают случайное целое число е в диапазоне , такое, что: НОД.

Исследование алгоритмов генерации простых чисел

Ключевые слова:вероятностный алгоритм, простые числа, псевдопростые числа, слабо псевдопростые числа, эффективность теста.

7. Выбираем в заданном интервале случайное число . 8. Если меньше чем 2000, то

5. Коблиц Н. Курс теории чисел в криптографии.

Особенности проектирования и криптоанализа асимметричной...

RSA, число, простое число, тест, выбор показателей, случайный сеансовый ключ, случайный образ, секретный показатель, простой перебор, AES.

Криптография. Основные методы и проблемы. Современные...

Основные термины (генерируются автоматически): криптография, RSA, ключ, квантовая криптография, канал связи, алгоритм, электронная

Современные проблемы в области информационной безопасности: классические угрозы, методы и средства их предотвращения.

Исследование криптосистем с открытым ключом на основе...

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

3. Выбирается целое число e, взаимно простое со значением функции Эйлера от числа n из интервала (1; φ(n)).

Методы генерации случайных чисел | Статья в журнале...

Чаще всего случайные числа требуются в задачах моделирования, численного анализа, тестирования, криптографии и теории игр

Основные термины (генерируются автоматически): число, случайное число, простое число, случайная последовательность, работа алгоритма...

Анализ алгоритма RSA. Некоторые распространённые...

Прежде всего, на случайные числа и необходимо наложить следующие ограничения

Теорема (Винера).

3. Венбо Мао Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice.

Генераторы случайных и псевдослучайных чисел

Те, кто знаком с криптографией, прекрасно понимают важность случайных чисел. Практически каждый алгоритм шифрования содержит как минимум один параметр с характеристиками «случайное число».

Теория чисел в криптографии | Статья в журнале...

Теория чисел в криптографии. Автор: Тагиров Кадир Межвединович.

Корректность алгоритма: согласно теореме Ферма [6, с. 90], для каждого целого числа , взаимно простого с модулем , выполняется

Вычисление факторизации чисел RSA-1024, RSA-2048, и других.

Реализация Windows-приложения, выполняющего шифрование...

Ключевые слова: шифрование, криптосистема RSA. На данный момент в современном мире защита информации играет немаловажную задачу.

Затем пользователи получают случайное целое число е в диапазоне , такое, что: НОД.

Исследование алгоритмов генерации простых чисел

Ключевые слова:вероятностный алгоритм, простые числа, псевдопростые числа, слабо псевдопростые числа, эффективность теста.

7. Выбираем в заданном интервале случайное число . 8. Если меньше чем 2000, то

5. Коблиц Н. Курс теории чисел в криптографии.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Особенности проектирования и криптоанализа асимметричной...

RSA, число, простое число, тест, выбор показателей, случайный сеансовый ключ, случайный образ, секретный показатель, простой перебор, AES.

Криптография. Основные методы и проблемы. Современные...

Основные термины (генерируются автоматически): криптография, RSA, ключ, квантовая криптография, канал связи, алгоритм, электронная

Современные проблемы в области информационной безопасности: классические угрозы, методы и средства их предотвращения.

Исследование криптосистем с открытым ключом на основе...

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

3. Выбирается целое число e, взаимно простое со значением функции Эйлера от числа n из интервала (1; φ(n)).

Методы генерации случайных чисел | Статья в журнале...

Чаще всего случайные числа требуются в задачах моделирования, численного анализа, тестирования, криптографии и теории игр

Основные термины (генерируются автоматически): число, случайное число, простое число, случайная последовательность, работа алгоритма...

Анализ алгоритма RSA. Некоторые распространённые...

Прежде всего, на случайные числа и необходимо наложить следующие ограничения

Теорема (Винера).

3. Венбо Мао Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice.

Генераторы случайных и псевдослучайных чисел

Те, кто знаком с криптографией, прекрасно понимают важность случайных чисел. Практически каждый алгоритм шифрования содержит как минимум один параметр с характеристиками «случайное число».

Теория чисел в криптографии | Статья в журнале...

Теория чисел в криптографии. Автор: Тагиров Кадир Межвединович.

Корректность алгоритма: согласно теореме Ферма [6, с. 90], для каждого целого числа , взаимно простого с модулем , выполняется

Вычисление факторизации чисел RSA-1024, RSA-2048, и других.

Реализация Windows-приложения, выполняющего шифрование...

Ключевые слова: шифрование, криптосистема RSA. На данный момент в современном мире защита информации играет немаловажную задачу.

Затем пользователи получают случайное целое число е в диапазоне , такое, что: НОД.

Исследование алгоритмов генерации простых чисел

Ключевые слова:вероятностный алгоритм, простые числа, псевдопростые числа, слабо псевдопростые числа, эффективность теста.

7. Выбираем в заданном интервале случайное число . 8. Если меньше чем 2000, то

5. Коблиц Н. Курс теории чисел в криптографии.

Особенности проектирования и криптоанализа асимметричной...

RSA, число, простое число, тест, выбор показателей, случайный сеансовый ключ, случайный образ, секретный показатель, простой перебор, AES.

Криптография. Основные методы и проблемы. Современные...

Основные термины (генерируются автоматически): криптография, RSA, ключ, квантовая криптография, канал связи, алгоритм, электронная

Современные проблемы в области информационной безопасности: классические угрозы, методы и средства их предотвращения.

Исследование криптосистем с открытым ключом на основе...

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

3. Выбирается целое число e, взаимно простое со значением функции Эйлера от числа n из интервала (1; φ(n)).

Методы генерации случайных чисел | Статья в журнале...

Чаще всего случайные числа требуются в задачах моделирования, численного анализа, тестирования, криптографии и теории игр

Основные термины (генерируются автоматически): число, случайное число, простое число, случайная последовательность, работа алгоритма...

Анализ алгоритма RSA. Некоторые распространённые...

Прежде всего, на случайные числа и необходимо наложить следующие ограничения

Теорема (Винера).

3. Венбо Мао Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice.

Генераторы случайных и псевдослучайных чисел

Те, кто знаком с криптографией, прекрасно понимают важность случайных чисел. Практически каждый алгоритм шифрования содержит как минимум один параметр с характеристиками «случайное число».

Теория чисел в криптографии | Статья в журнале...

Теория чисел в криптографии. Автор: Тагиров Кадир Межвединович.

Корректность алгоритма: согласно теореме Ферма [6, с. 90], для каждого целого числа , взаимно простого с модулем , выполняется

Вычисление факторизации чисел RSA-1024, RSA-2048, и других.

Реализация Windows-приложения, выполняющего шифрование...

Ключевые слова: шифрование, криптосистема RSA. На данный момент в современном мире защита информации играет немаловажную задачу.

Затем пользователи получают случайное целое число е в диапазоне , такое, что: НОД.

Исследование алгоритмов генерации простых чисел

Ключевые слова:вероятностный алгоритм, простые числа, псевдопростые числа, слабо псевдопростые числа, эффективность теста.

7. Выбираем в заданном интервале случайное число . 8. Если меньше чем 2000, то

5. Коблиц Н. Курс теории чисел в криптографии.

Задать вопрос