СРАВНЕНИЕ МЕТОДОВ ШИФРОВАНИЯ «RSA» И «ЭЛЬ-ГАМАЛЯ»

​COMPRESSION OF «RSA» AND «EL-GAMAL» ENCRYPTION METHODS

Shkabara Anastasia

Student, Faculty of Information Technology, Belarusian State Technological University,

Belarus, Minsk

Narkevich Adelina

Scientific supervisor, senior lecturer, Department of Software Engineering, Belarusian State Technological University,

Belarus, Minsk

АННОТАЦИЯ

В статье рассмотрены два асимметричных алгоритма криптографии – «RSA» и «Эль-Гамаля». Целью исследования является сравнительная оценка эффективности алгоритмов по скорости шифрования/дешифрования и объему шифротекста. Для этого было разработано авторское приложение на языке Python, которое позволяет оценить скорость выполнения операций для каждого алгоритма, а также размер шифротекста.

ABSTRACT

The article considers two asymmetric cryptographic algorithms – «RSA» и «El-Gamal». The aim of the study is the comparative efficiency of the algorithms in terms of encryption/decryption speed and ciphertext volume. For this purpose, a proprietary application was developed in Python, which allows one to evaluate the speed of operations for each algorithm, as well as the size of the ciphertext.

Ключевые слова: шифрование; дешифрование; шифротекст; криптостойкость; алгоритм RSA; алгоритм Эль-Гамаля.

Keywords: encryption; decryption; ciphertext; cryptographic strength; RSA algorithm; El-Gamal algorithm.

«RSA» – асимметричный алгоритм, который использует два математически связанных ключа: публичный (открытый) ключ – для шифрования открытого текста, тайный (закрытый) – для дешифрования шифротекста. Таким образом, чтобы безопасно отправить сообщение M получателю B, отправителю A нужно с помощью открытого ключа получателя зашифровать сообщение M и передать его. Получатель же, чтобы извлечь исходное сообщение, должен использовать свой тайный ключ [1].

Сам алгоритм включает в себя следующие этапы:

1. Генерация ключей

a) Выбрать два больших простых числа p и q.

b) Вычислить произведение n = p × q, которое будет являться общей составляющей для открытого и закрытого ключей.

c) Вычислить функцию Эйлера: φ(n) = (p – 1) × (q – 1).

d) Случайным образом выбрать показатель шифрования e, такой, что φ(n) и e являются взаимно простыми числами, и 1 < e < φ(n).

e) Вычислить показатель дешифрования d с помощью алгоритма Евклида из выражения: .

Открытый ключ = (e, n), тайный ключ = (d, n) [2].

2. Шифрование

a) Чтобы зашифровать сообщение M, его преобразуют в числовое представление с помощью ASCII или других схем кодирования.

b) Преобразованное сообщение M состоит из r блоков: m₁, m₂, …, m_i, …, m_r. Шифротекст C будет состоять из такого же числа (r) блоков, представляемых числами:

3. Расшифрование

a) Для расшифрования каждого блока шифротекста производятся вычисления вида:

Разобрав математические основы и этапы работы алгоритма «RSA», перейдем к его программной реализации, представленной на рисунке 1.

Рисунок 1. Реализация алгоритма «RSA» на Python

Криптостойкость алгоритма «RSA» основывается на проблеме факторизации, а именно на разложении числа n на простые сомножители p и q.

Основной функцией является «rsa». Она выполняет все этапы алгоритма и выводит в консоль исходное сообщение, шифротекст и расшифрованное сообщение. В процессе выполнения также используются булевая функция «is_prime» для проверки чисел на простоту и функция «gcd» для подбора показателя шифрования e, взаимно простого с функцией Эйлера φ(n).

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

Алгоритм состоит из следующих этапов:

1. Генерация ключей

a) Выбрать простое число p и число g (g < p), являющееся первообразным корнем числа p.

b) Выбрать число x (x < p) и вычислить последний компонент ключевой информации:

Открытый ключ = (p, g, y), закрытый ключ = (p, g, x) [3].

2. Шифрование

a) Чтобы зашифровать сообщение M, его преобразуют в числовое представление с помощью ASCII или других схем кодирования. Преобразованное сообщение M состоит из r блоков: m₁, m₂, …, m_i, …, m_r.

b) Для зашифрования исходного сообщения M для каждого блока m_i выбирается случайное число k (1 < k < p – 1).

c) Блок шифротекста c_i состоит из двух чисел – a_i и b_i:

3. Расшифрование

a) Для расшифрования блока шифротекста применяется следующая формула:

где:

(a^x)^-1 – обратное значение числа a^x по модулю p.

Криптостойкость алгоритма «Эль-Гамаля» основана на проблеме дискретного логарифмирования [4], а именно на сложности нахождения числа x по уравнению:

Рассмотрим программную реализацию алгоритма «Эль-Гамаля», представленную на рисунке 2.

Рисунок 2. Реализация алгоритма «Эль-Гамаля» на Python

Основной функцией является «elgamal». Функция «is_prime» аналогична одноименной функции в реализации алгоритма «RSA».

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

Рисунок 3. Результат работы приложения для сравнения «RSA» и «Эль-Гамаля»

Для входного сообщения «an article about comprasion of RSA and ElGamal algorithms» алгоритм «RSA» генерирует шифротекст размером 128 байт с временем шифрования 137,80 мкс и дешифрования 10282,10 мкс. Алгоритм «Эль-Гамаля» генерирует шифротекст размером примерно 255 байт. Время шифрования 10675,70 мкс и дешифрования 4553,40 мкс.

«RSA» производит фиксированный объем данных (128 байт) из-за 1024-битного ключа и добавления заполнения, тогда как алгоритм «Эль-Гамаля» генерирует два числа по 1024 бита, что дает общий размер около 255 байт.

По времени выполнения операции шифрования исходного текста алгоритм «RSA» заметно опережает алгоритм «Эль-Гамаля». Это связано с тем, что «RSA» использует малое фиксированное значение e, что упрощает вычисления, производимые для шифрования (формула 1). Алгоритм «Эль-Гамаля» предусматривает генерацию нового числа k для каждого блока шифротекста и требует двух возведений в степень (формулы 4, 5) с 1024-битным p, что замедляет процесс шифрования.

Операция дешифрования при использовании алгоритма «RSA» выполняется медленнее, чем в случае использования алгоритма «Эль-Гамаля». Это объясняется тем, что «RSA» выполняет сложное возведение в степень с большим значением числа d (формула 2), тогда как алгоритма «Эль-Гамаля» предусматривает одно возведение в степень и инверсии, для нахождения обратного элемента (формула 6).

Исходя из полученных данных при тестировании, можно сделать следующие выводы: алгоритм «RSA» лучше использовать в задачах, где приоритет – быстрое шифрование и простота реализации. Алгоритма «Эль-Гамаля», в свою очередь, обеспечивает лучшую безопасность благодаря использованию случайных чисел, однако размер шифротекста будет значительно больше.

Список литературы:

1. «Алгоритм RSA». [электронный ресурс] – URL: https://habr.com/ru/articles/745820/ (дата обращения 01.07.2025).
2. «Алгоритм RSA в криптографии». [электронный ресурс] – URL: https://www.geeksforgeeks.org/computer-networks/rsa-algorithm-cryptography/ (дата обращения 01.07.2025).
3. «Схема Эль-Гамаля». [электронный ресурс] – URL: https://ru.wikipedia.org/wiki/%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%AD%D0%BB%D1%8C-%D0%93%D0%B0%D0%BC%D0%B0%D0%BB%D1%8F (дата обращения 03.07.2025).
4. «Алгоритм шифрования Эль-Гамаля». [электронный ресурс] – URL: https://www.geeksforgeeks.org/computer-networks/elgamal-encryption-algorithm/ (дата обращения 03.07.2025).