Алгоритмы RSA и Диффи-Хеллмана (DH): детальный разбор

Введение

Криптография — это фундаментальная область кибербезопасности, позволяющая защищать данные от несанкционированного доступа. Она используется везде: в банковских системах, защищённых соединениях, цифровых подписях и аутентификации пользователей. Одними из наиболее значимых алгоритмов асимметричной криптографии являются RSA и Диффи-Хеллман (DH). Они используются для шифрования данных и безопасного обмена ключами.

Виды криптографии

Существует два основных типа криптографии:

1. Симметричное шифрование — использует один и тот же ключ для шифрования и дешифрования сообщений. Пример: AES.
2. Асимметричное шифрование — использует два разных ключа: открытый (для шифрования) и закрытый (для расшифровки). Примеры: RSA, ECC, DH.

Алгоритм RSA

RSA (Rivest-Shamir-Adleman) — один из самых известных алгоритмов асимметричного шифрования, основанный на сложности факторизации больших чисел. Он используется для шифрования данных и цифровых подписей.

Генерация ключей в RSA

1. Выбираются два больших простых числа p и q.
2. Вычисляется их произведение: n = p * q.
3. Вычисляется функция Эйлера: φ(n) = (p - 1) * (q - 1).
4. Выбирается число e (открытая экспонента), такое, что 1 < e < φ(n) и gcd(e, φ(n)) = 1.
5. Вычисляется закрытая экспонента d, являющаяся мультипликативным обратным к e:
6. d ≡ e⁻¹ (mod φ(n)).
7. Пара (e, n) — открытый ключ, а (d, n) — закрытый.

Шифрование и расшифрование в RSA

Шифрование:

C=Memod  nC = M^e \mod nC=Memodn

Расшифрование:

M=Cdmod  nM = C^d \mod nM=Cdmodn

Пример расчёта RSA

Допустим, выбираем два простых числа:

• p = 61, q = 53
• n = 61 * 53 = 3233
• Функция Эйлера: φ(n) = (61 - 1) * (53 - 1) = 3120
• Выбираем e = 17 (простое с 3120)
• Находим d, такое что d * 17 ≡ 1 (mod 3120), получаем d = 2753
• Открытый ключ: (17, 3233), закрытый ключ: (2753, 3233)

Шифруем сообщение M = 65:

C=6517mod  3233=2790C = 65^{17} \mod 3233 = 2790C=6517mod3233=2790

Дешифруем:

M=27902753mod  3233=65M = 2790^{2753} \mod 3233 = 65M=27902753mod3233=65

Безопасность RSA

RSA считается безопасным благодаря сложности разложения большого числа на множители.

Однако при малых значениях p и q возможны атаки (метод квадратичного решета, метод Ферма).

Рекомендуется использовать ключи от 2048 бит.

Протокол Диффи-Хеллмана

Протокол Диффи-Хеллмана (DH) используется для безопасного обмена ключами в открытом канале.

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

Как работает обмен ключами в DH

1. Выбирается большое простое число p и основание g.
2. Два участника (Алиса и Боб) выбирают секретные числа a и b.
3. Они вычисляют открытые ключи:
4. Алиса: A = g^a mod p
5. Боб: B = g^b mod p
6. Обмениваются этими значениями и вычисляют общий ключ:
7. K = B^a mod p = A^b mod p

Пример расчёта DH

Допустим, выбираем:

• p = 23, g = 5
• Алиса выбирает a = 6, вычисляет A = 5⁶ mod 23 = 8
• Боб выбирает b = 15, вычисляет B = 5¹⁵ mod 23 = 19
• Обмениваются значениями A и B
• Алиса вычисляет K = 19⁶ mod 23 = 2
• Боб вычисляет K = 8¹⁵ mod 23 = 2
• Теперь у них общий секретный ключ K = 2

Атаки на DH

DH уязвим к атаке "человек посередине" (MITM), если не используется аутентификация участников.

Решение — применение RSA или цифровых подписей.

Сравнение RSA и DH

RSA и DH — разные криптографические механизмы:

• RSA используется для шифрования и цифровых подписей
• DH — для обмена ключами
• RSA более требователен к вычислительным ресурсам
• DH требует аутентификации для защиты от атак MITM

Заключение

RSA и DH — два ключевых алгоритма криптографии.

RSA применяется для защищённой передачи сообщений, а DH помогает безопасно обмениваться ключами.

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

4o