Что такое простые числа и почему криптография так хочет их использовать?
Простые числа широко используются в криптографии, потому что они дают больше шансов создать уникальные значения для хэш-функций. Хеш-функции используют модули, а использование комплексных чисел (т. е. Не простых) увеличивает вероятность хеш-коллизий (т. е. Разные входные данные дают один и тот же хэш ). Простые числа увеличивают вероятность создания уникальных значений во время хеширования путем умножения значения на простое число. Например, если у вас есть строка «Разблокировать цепочку», умножение каждой буквы на простое число и последующее сложение их всех вместе даст вам очень уникальное значение хеш-функции.
Таким же образом простые числа также используются для создания закрытых ключей, которые широко используются в алгоритмах подписания транзакций и криптографического хеширования. В инфраструктуре открытого ключа цифровые подписи пользователей используются для проверки подлинности подписи транзакции, обеспечивая безопасный способ проверки того, что транзакция пользователя была подписана их закрытым ключом. Кто угодно может отправить сообщение, используя открытый ключ получателя, но только получатель сможет открыть сообщение, используя свой закрытый ключ.
Каждый раз, когда мы отправляем или получаем транзакцию в сети Биткойн (и почти в любой другой цепочке блоков), мы используем случайные числа, чтобы помочь нам создать большие простые числа, которые используются для создания надежных и безопасных закрытых ключей.
Что такое простое число?
Простое число - это такое число, которое делится только на 1 и само себя. Вот некоторые примеры простых чисел: 1, 3, 5, 7, 11, 13, 17… и 89, 97, 8191. Самое большое известное простое число - 2⁸² 589 933, что является астрономически большим числом, состоящим из 24 862 048 цифр.
Чем выше простое число, тем меньше вероятность его найти. Например, существует 25 простых чисел от 1 до 100, но только 21 простое число от 100 до 200, 15 простых чисел от 200 до 300 и только 6 простых чисел от 10 000 до 10 100.
Более 2000 лет назад Евклид доказал, что простых чисел бесконечно много. Хотя легко проверить, является ли маленькое число простым или нет, чем больше число, тем труднее узнать, является ли оно простым числом. Это, конечно, большая проблема для математики и информатики. Более того, чем выше диапазон чисел, тем меньше вероятность найти простое число и тем труднее доказать, действительно ли это простое число. Подготовка эффективного алгоритма проверки простых чисел - чрезвычайно сложная задача.
Простые числа можно приблизительно вычислить с помощью формулы x / In (x) и плотности простых чисел: 1 / In (x). Чем больше X, тем точнее формула.
Простые числа в криптографии
Чтобы создать надежный закрытый ключ, нам нужно 2 больших простых числа, и убедитесь, что эти простые числа очень сложно угадать. Создайте большое случайное число и проверьте, простое ли оно.
Как мы можем проверить, простое число или нет? Самый прямой подход - разделить число на любое меньшее его число. Если оно не делится ни на одну из них, то оно, безусловно, простое. Однако следует признать, что эта процедура довольно трудоемка.
Чтобы проверить, является ли простое число простым или нет, нам нужно применить какой-нибудь проверенный тест или алгоритм . Еще раз подчеркнем, что если мы ищем небольшое 6-значное простое число, довольно легко и быстро определить, является ли 100699 простым числом. Однако если мы ищем большие простые числа, скажем, более 1000 цифр, работа становится «немного» труднее.
Тесты на простоту в криптографии - детерминированные и вероятностные
Есть два основных способа вычислить простое число. Одним из них является использование детерминированного алгоритма, такого как пробное деление (деление простого числа на все числа перед ним, чтобы проверить, возможно ли деление) или теоремы Вильсона. Детерминированный способ означает, что мы сможем определить, является ли число простым числом со 100% точностью. Однако детерминированные алгоритмы чрезвычайно неэффективны с точки зрения вычислений.
Другой альтернативой для более быстрого получения ответа является вероятностный метод, хотя он не может определить со 100% уверенностью, что данное число является простым числом (хотя и умеренно точный, он не дает 100% уверенности).
Детерминированные методы проверки простых чисел очень трудоемки, поскольку требуют большого количества вычислений. Пробное деление требует, чтобы n (проверяемое целое) было разделено на любое меньшее число. Обработка проверки теоремы Вильсона также требует много энергии. Он работает следующим образом: для натурального числа n> 1 оно является простым только тогда, когда произведение всех положительных целых чисел меньше n на единицу меньше кратного n.
Метод Миллера-Рабина является вероятностным, т. е. Он не точен на 100%, но он достаточно точен для большинства криптографических алгоритмов. Большинство криптографических систем используют тест простоты Миллера-Рабина, чтобы определить, является ли число (!) Вероятным простым числом или нет.
Метод Миллера-Рабина также широко используется в блокчейнах для поиска простых чисел. Он является частью библиотек Python и подробно документирован на GitHub.