Alex Maszański

Kaggle expert⚛️ Пишу материал о различных алгоритмах и техниках в сфере Machine Learning. Объясняем, почему простые числа важны в криптографии. Для этого мы рассмотрим конкретную криптосистему, а именно алгоритм RSA и сосредоточимся на его основных аспектах.

Свойства простых чисел

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

С другой стороны, вычислить значение гораздо легче, когда простые числа нам заранее известны:

Легко вычислить x из простых чисел 1 и 2. Но сложно вычислить простые числа 1 и 2 из x.

В идеальных условиях у нас имеются два больших числа, которые являются простыми. Затем мы вычисляем произведение этих двух чисел, чтобы зашифровать сообщение. Позже, чтобы расшифровать его, нам нужно одно из данных простых чисел, потому что нет простого способа вычислить «Число 1» и «Число 2» исключительно по x. Перед тем как углубиться в детали использования данных чисел, давайте рассмотрим различные криптографические системы.

Криптографические системы

В криптографии существует два основных метода шифрования сообщений: симметричное и асимметричное.

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

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

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

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

Публичный ключ → Автор сообщения → Зашифрованное сообщение → Получатель → Приватный ключ

Используем простые числа для шифрования

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

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

Затем мы соединяем каждое число, чтобы создать другое (назовем его m), которое мы потом зашифруем. Самым простым примером списка является присвоение каждой букве ее позиции в алфавите, например, A – 1, Б – 2 и т. д. Несмотря на то, что данный список позволяет использовать только крайне простые слова, его достаточно для понимания теории, лежащей в основе RSA.

Создаем ключ

Как было ранее сказано, некоторое большое число легко вычислить при условии, что простые числа уже известны. С другой стороны, очень трудно определить множители (факторы) известного нам большого числа. Чтобы создать два ключа – закрытый и открытый, – мы осуществляем следующий процесс:

1. Выберите два случайных, стохастически независимых и простых числа, p и q.
2. Вычислите их произведение: N = p * q
3. Далее вычислите φ-функцию: φ(N) = (p – 1) * (q – 1)
4. Выберите простое натуральное число e, которое меньше значения φ(N) и является кратным по отношению к нему.
5. Вычислите мультипликативную обратную величину k от e по модулю φ(N), то есть: e * k + d * φ(N) = 1

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

Шифрование и дешифрование сообщения

Теперь мы зашифруем наше сообщение m с помощью открытого ключа:

s≅memodN

И расшифруем его:

m≅skmodN

Из выражений выше следует, что мы можем инвертировать наше шифрование только если нам известна мультипликативная обратная k от e по модулю φ(N). Эти данные возможно получить, если у нас есть:

1. Приватный (закрытый) ключ
2. Простые множители N

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

Практический пример

• Создаем ключ.

Пусть буква, которую мы хотим зашифровать – O. Преобразуем ее в число m=15, так как это пятнадцатая буква латинского алфавита. Теперь мы выбираем случайные простые числа. Чтобы упростить задачу, выберем простые числа p = 13 и q = 17.

Таким образом, функция: φ(N) = (p – 1) * (q – 1) = 192

Мы также выбираем число e, которое кратно φ(N). Пусть это будет 29.

Осталось вычислить обратное k от e. С помощью алгоритма Евклида мы узнаем, что оно равно 53.

Таким образом, у нас есть открытый ключ N = p * q = 221 и закрытый ключ k = 53.

• Шифрование и дешифрование сообщения.

Далее мы зашифруем наше число:

15≅s29mod221

Это дает s = 19. Теперь у нас есть зашифрованное сообщение, и мы можем безопасно передать его получателю. Никто не узнает, что оно обозначает букву O.

Теперь нам нужно наше обратное k, которое равно 53:

15≅1953mod221

После этого мы снова смотрим на алфавит и видим, что его пятнадцатая буква – это O. Таким образом, мы успешно зашифровали и расшифровали наше сообщение.

***

Из данного материала вы узнали об алгоритме RSA (Rivest, Shamir и Aldeman – создатели алгоритма) и о том, как правильно его применять для шифрования данных.

Мы можем использовать другие, более объемные числа. Их невозможность разложения на простые множители поможет созданию безопасной и асимметричной криптографической системы.

Материалы по теме

• 🐍 Python: взлом криптографической хеш-функции через BruteForce
• 🔑 Криптография и главные способы шифрования информации
• 🔑 Взламываем шифры: криптография за 60 минут
• 🕵 GPG и все-все-все: настраиваем шифрование переписки за 10 минут по методу Кристофера Робина