На чем основан алгоритм асимметричного шифрования

Асимметричное шифрование: математические основы

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

RSA (Rivest-Shamir-Adleman)

Основан на сложности факторизации больших чисел.

Принцип

Найти два больших простых числа легко. Перемножить их тоже легко. Но разложить их произведение на множители почти невозможно (без приватного ключа).

# Упрощённо:
# 1. Выбираем два больших простых числа
p = 61  # На практике 2^1024 или больше
q = 53

# 2. Вычисляем модуль
n = p * q  # n = 3233

# 3. Вычисляем функцию Эйлера
phi = (p - 1) * (q - 1)  # phi = 60 * 52 = 3120

# 4. Выбираем открытую экспоненту (обычно e = 65537)
e = 17  # 1 < e < phi, gcd(e, phi) = 1

# 5. Вычисляем приватную экспоненту
# d такая, что (e * d) mod phi = 1
d = 2753  # Вычисляется через расширенный алгоритм Евклида

# Открытый ключ: (n, e) = (3233, 17)
# Приватный ключ: (n, d) = (3233, 2753)

# Шифрование: C = M^e mod n
m = 65  # Сообщение
c = pow(m, e, n)  # C = 65^17 mod 3233 = 2790

# Расшифровка: M = C^d mod n
m_decrypted = pow(c, d, n)  # M = 2790^2753 mod 3233 = 65

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

from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization, hashes
from cryptography.hazmat.primitives.asymmetric import padding

# 1. Генерируем ключи
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,  # На практике используем большие ключи
)
public_key = private_key.public_key()

# 2. Шифруем сообщение открытым ключом
message = b"Secret message"
encrypted = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# 3. Расшифровываем приватным ключом
decrypted = private_key.decrypt(
    encrypted,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print(decrypted)  # b'Secret message'

Почему RSA работает?

• Вперёд легко: перемножение чисел — O(log n)
• Назад сложно: факторизация — O(2^(log n)) без приватного ключа
• С приватным ключом: возвести в степень по модулю легко

ECC (Elliptic Curve Cryptography)

Основан на дискретном логарифме на эллиптических кривых.

Принцип

Дано: точка P на кривой и число k. Легко: вычислить Q = k*P (сложить точку саму с собой k раз). Сложно: найти k, зная P и Q.

# Уравнение эллиптической кривой
# y² = x³ + ax + b (на конечном поле)

# Пример (упрощённо):
a, b = 2, 3
p_field = 17  # Простое число для конечного поля

# Точка на кривой
G = (2, 5)  # Генератор

# Приватный ключ: случайное число
priv_key = 7

# Открытый ключ: повторное сложение точки
# pub_key = priv_key * G = 7 * (2, 5)
def point_double(p):
    # Сложение точки с собой
    pass

def point_add(p1, p2):
    # Сложение двух точек
    pass

pub_key = G  # Упрощённо
for _ in range(priv_key - 1):
    pub_key = point_add(pub_key, G)

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

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import serialization, hashes

# 1. Генерируем ECC ключи
private_key = ec.generate_private_key(ec.SECP256R1())  # SECP256R1 — curve P-256
public_key = private_key.public_key()

# 2. Подписываем сообщение приватным ключом
message = b"Sign this message"
signature = private_key.sign(
    message,
    ec.ECDSA(hashes.SHA256())
)

# 3. Проверяем подпись открытым ключом
public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
print("Signature valid")

# Попытка подделать подпись вызовет исключение
try:
    public_key.verify(signature, b"Different message", ec.ECDSA(hashes.SHA256()))
except Exception:
    print("Signature invalid")

Почему ECC работает?

• Вперёд легко: сложение точек — алгоритм Монтгомери O(log k)
• Назад сложно: дискретный логарифм — O(sqrt(n)) даже с лучшими алгоритмами
• Преимущество: меньше размер ключа (256-bit ECC ≈ 3072-bit RSA)

Сравнение: RSA vs ECC

Другие основы

Диффи-Хеллман (Diffie-Hellman)

Основан на сложности дискретного логарифма в мультипликативной группе:

# Прямо: g^x mod p легко
# Обратно: найти x, зная g, p, g^x mod p — сложно

p = 23  # Простое число
g = 5   # Примитивный корень

# Алиса выбирает приватный ключ
alice_private = 6
alice_public = pow(g, alice_private, p)  # 5^6 mod 23 = 8

# Боб выбирает приватный ключ
bob_private = 15
bob_public = pow(g, bob_private, p)  # 5^15 mod 23 = 19

# Они обмениваются открытыми ключами
# И вычисляют общий секрет
alice_secret = pow(bob_public, alice_private, p)  # 19^6 mod 23 = 2
bob_secret = pow(alice_public, bob_private, p)     # 8^15 mod 23 = 2

print(alice_secret == bob_secret)  # True — общий секрет найден

Модули и сложность

# RSA: факторизация n требует времени экспоненциального от log(n)
from sympy import factorint

n = 91  # 7 * 13
factors = factorint(n)  # {7: 1, 13: 1}

# Для n = 2^2048 (600 цифр) факторизация невозможна классическим способом
# Требуется квантовый компьютер для алгоритма Шора

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

# ✅ Правильно: используй проверенные библиотеки
from cryptography.hazmat.primitives.asymmetric import rsa, ec
from cryptography.hazmat.primitives import hashes

# ❌ Неправильно: не реализуй сам
# def my_rsa_encrypt():  # НИКОГДА
#     pass

# Всегда используй:
# - cryptography
# - PyCryptodome
# - Standardized curves (P-256, P-384)
# - Достаточный размер ключей (2048+ для RSA, 256+ для ECC)

Итоговое резюме

RSA основан на том, что факторизация больших чисел — вычислительно неразрешима.

ECC основан на том, что дискретный логарифм на эллиптических кривых — вычислительно неразрешим.

Диффи-Хеллман основан на дискретном логарифме в мультипликативной группе.

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