Электронная подпись (ЭП) · Блог "Дети ОИТа"

Электронная подпись (ЭП) — это криптографический механизм, позволяющий подтвердить подлинность документа, его целостность и неотказуемость (невозможность отказа автора от подписи). В отличие от ручной подписи, электронная подпись зависит от содержимого документа, поэтому подделать её невозможно без знания секретного ключа.

В этой статье мы:

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

1.1. Задачи, которые решает ЭП

Целостность (integrity): любое изменение документа делает подпись недействительной.
Аутентификация (authentication): подпись подтверждает, что документ исходит от заявленного отправителя.
Неотказуемость (non‑repudiation): отправитель не может впоследствии отрицать факт подписания документа.

1.2. Симметричные и асимметричные схемы

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

1.3. Общая схема работы с ЭП

Генерация ключей: создаётся пара (секретный ключ SK, открытый ключ PK).
Подписание: для сообщения M вычисляется хеш h = H(M), затем подпись σ = sign(SK, h). Подпись прикрепляется к сообщению.
Проверка: получатель вычисляет h’ = H(M), используя открытый ключ PK проверяет, что σ соответствует h’. Если да, подпись верна.

2.1. Кратко о RSA

RSA основана на сложности факторизации произведения двух больших простых чисел p и q.

n = p·q
φ(n) = (p‑1)(q‑1)
Выбираем e (открытая экспонента), взаимно простое с φ(n), обычно 65537.
Вычисляем d = e⁻¹ mod φ(n) (секретная экспонента).

2.2. Подпись RSA

Подпись сообщения m (после хеширования) вычисляется как:
σ = mᵈ mod n

Проверка: m’ = σᵉ mod n, затем сравнивается m’ с оригинальным хешем m.

2.3. Почему это работает?**

По теореме Эйлера (mᵉ)ᵈ ≡ m (mod n). Таким образом, если подпись создана корректно, то возведение её в степень e даст исходный хеш.

2.4. Важность хеширования**

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

3.1. Вспомогательные функции: расширенный алгоритм Евклида, генерация простых

import random
import hashlib

def egcd(a, b):
    """Расширенный алгоритм Евклида: (g, x, y) где a*x + b*y = g = gcd(a,b)"""
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

def modinv(a, m):
    """Обратный элемент a по модулю m (a и m взаимно просты)"""
    g, x, _ = egcd(a, m)
    if g != 1:
        return None
    return x % m

def is_prime(n, k=10):
    """Тест Миллера-Рабина"""
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False
    r, d = 0, n-1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n-1)
        x = pow(a, d, n)
        if x == 1 or x == n-1:
            continue
        for _ in range(r-1):
            x = (x * x) % n
            if x == n-1:
                break
        else:
            return False
    return True

def generate_prime(bits):
    """Генерирует простое число заданной битовой длины"""
    while True:
        candidate = random.getrandbits(bits)
        candidate |= (1 << (bits-1)) | 1   # старший бит=1, младший=1
        if is_prime(candidate):
            return candidate

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

def generate_rsa_keys(bits=1024):
    """
    Генерирует пару (открытый ключ (n, e), закрытый ключ (n, d))
    """
    # Размер каждого простого – половина бит модуля
    p = generate_prime(bits // 2)
    q = generate_prime(bits // 2)
    while q == p:
        q = generate_prime(bits // 2)
    n = p * q
    phi = (p-1)*(q-1)
    e = 65537
    if e >= phi:
        # Запасной вариант для малых n
        e = 3
        while e < phi and modinv(e, phi) is None:
            e += 2
    d = modinv(e, phi)
    return (n, e), (n, d)


pub, priv = generate_rsa_keys(128)
print(f"Открытый ключ: n={pub[0]}, e={pub[1]}")
print(f"Закрытый ключ: n={priv[0]}, d={priv[1]}")

3.3. Хеширование и преобразование в число

Для подписи мы будем использовать SHA-256, который выдаёт 32 байта. Преобразуем их в целое число.

def hash_message(message):
    """Возвращает хеш сообщения как целое число"""
    h = hashlib.sha256(message.encode()).digest()
    return int.from_bytes(h, 'big')

3.4. Создание и проверка подписи

def rsa_sign(message, private_key):
    """Подпись сообщения с использованием секретного ключа (n, d)"""
    n, d = private_key
    h = hash_message(message)
    # Убедимся, что хеш меньше n (если нет — надо обрезать, но для SHA-256 с n≥256 бит это выполняется)
    if h >= n:
        h %= n
    signature = pow(h, d, n)
    return signature

def rsa_verify(message, signature, public_key):
    """Проверка подписи: возвращает True, если подпись корректна"""
    n, e = public_key
    h = hash_message(message)
    if h >= n:
        h %= n
    h_ver = pow(signature, e, n)
    return h == h_ver


msg = "Важный контракт с суммой 1000000 рублей"
pub, priv = generate_rsa_keys(512)   # 512 бит для теста
sig = rsa_sign(msg, priv)
valid = rsa_verify(msg, sig, pub)
print(f"Сообщение: {msg}")
print(f"Подпись (число): {sig}")
print(f"Подпись верна? {valid}")


msg_fake = "Важный контракт с суммой 999999 рублей"
valid_fake = rsa_verify(msg_fake, sig, pub)
print(f"Подпись для изменённого сообщения верна? {valid_fake}")

3.5. Подпись с PKCS#1 v1.5 padding (обзор)

Реальные системы (например, OpenSSL) используют структурированное дополнение перед подписью, чтобы избежать атак. Обычно к хешу добавляют специальный идентификатор алгоритма (например, для SHA-256) и случайные байты. Однако наша упрощённая версия достаточна для понимания принципа.

4.1. Защита от подделки

Если злоумышленник не знает секретного ключа d, он не может вычислить корень степени e по модулю n (дискретный логарифм или взятие корня). Безопасность сводится к задаче факторизации n.

4.2. Атака на отсутствие хеширования

Если подписывать сообщение напрямую без хеширования, злоумышленник может создать подделку на основе мультипликативности: подпись произведения сообщений равна произведению подписей. Хеширование исключает это.

4.3. Атака на малую экспоненту e (например, 3) с недостаточным padding

Если e=3 и сообщение не дополнено случайными байтами, а хеш мал, то (хеш)³ может быть меньше n, и подпись тривиально извлекается как корень кубический. Именно поэтому используют e=65537 и принудительное дополнение PKCS#1.

4.4. Неотказуемость

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

Реальные приложения используют кодирование ASN.1/DER и PEM. Примеры кода с библиотекой `cryptography` или `pycryptodome` выходят за рамки этой статьи, но упомянем, что стандартные форматы важны для совместимости.

Сгенерируйте ключи RSA размером 1024 бита, подпишите строку «Hello, world!» и проверьте подпись.
Модифицируйте сообщение на один символ и убедитесь, что проверка не проходит.
Попробуйте подписать сообщение без хеширования (прямо m) и покажите мультипликативную атаку: sign(m1)*sign(m2) mod n == sign(m1*m2).
Реализуйте функцию, которая сохраняет подпись в файл и загружает её.
Изучите, как формат PKCS#1 v1.5 структурирует данные перед подписью.

Электронная подпись на основе RSA — это устоявшийся стандарт, обеспечивающий целостность, аутентификацию и неотказуемость. Её реализация требует генерации больших простых чисел, хеширования и возведения в степень по модулю. В промышленности используются дополнения (PKCS#1, PSS) и стандартизированные форматы. Понимание принципов работы позволяет разработчикам интегрировать цифровую подпись в свои приложения и оценивать риски.

Операция	Формула / действие
Генерация ключей	n = p·q, φ = (p‑1)(q‑1), e·d ≡ 1 (mod φ)
Подпись	σ = H(m)ᵈ mod n
Проверка	H’(m) = σᵉ mod n, сравнить с H(m)
Хеш-функция	SHA-256 (или другой)
Безопасность	сложность факторизации n

Все блоки кода независимы и используют только стандартную библиотеку Python (random, hashlib). Для запуска в Emacs нажмите C-c C-c внутри блока. Генерация 1024‑битных ключей может занять несколько секунд. Для учебных целей используйте меньшие размеры (128–256 бит), но они небезопасны в реальности.