Криптография и информационная безопасность

Когда Лейла платит в банковском приложении, данные проходят через десятки чужих устройств, но никто не может прочитать или изменить сумму, а банк уверен, что запрос пришёл именно от Лейлы. Это обеспечивает криптография. Она служит четырём целям: конфиденциальность (посторонние не прочитают), целостность (изменения обнаруживаются), аутентичность (известно, кто отправил) и неотказуемость (отправитель не сможет потом сказать «это был не я»).

Симметричное шифрование

Современный стандарт — AES (ключи 128, 192 или 256 бит): он очень быстр и поддерживается процессорами аппаратно. У 128-битного ключа 2¹²⁸ ≈ 3,4 · 10³⁸ вариантов — перебрать их практически невозможно. Настоящая проблема в другом: как передать ключ? Каждой паре из n человек нужен свой ключ — n(n − 1)/2 ключей, для 1000 пользователей это 499 500. К тому же впервые передать ключ по незащищённому каналу нельзя.

Асимметричная криптография: Диффи — Хеллман и RSA

В асимметричной криптографии у каждого пользователя два ключа: открытый, который дают всем, и закрытый, который никому не показывают. Зашифрованное открытым ключом может расшифровать только закрытый. Это опирается на математические операции «легко в одну сторону, трудно обратно»: перемножить два больших простых числа легко, а разложить произведение на множители очень трудно; вычислить gᵃ mod p легко, а найти a (дискретный логарифм) трудно.

p, g = 23, 5
a, b = 6, 15
A, B = pow(g, a, p), pow(g, b, p)
print('DH public:', A, B, '| shared:', pow(B, a, p), pow(A, b, p))

p, q, e = 3, 11, 3
n, phi = p * q, (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = 4
c = pow(m, e, n)
print('RSA n =', n, 'phi =', phi, 'd =', d)
print('encrypt', m, '->', c, '| decrypt ->', pow(c, d, n))
s = pow(m, d, n)
print('signature', s, '| verify ->', pow(s, e, n))

DH public: 8 19 | shared: 2 2
RSA n = 33 phi = 20 d = 7
encrypt 4 -> 31 | decrypt -> 4
signature 16 | verify -> 4

Хеш-функции и цифровые подписи

Криптографический хеш (например, SHA-256) превращает данные любой длины в «отпечаток» фиксированной длины (256 бит). Требования: каждый раз один и тот же результат; по хешу нельзя восстановить данные (односторонность); найти два разных входа с одинаковым хешем практически невозможно (стойкость к коллизиям); изменение одного бита меняет примерно половину битов хеша (лавинный эффект). Хеш — не шифрование: у него нет ключа, и его нельзя обратить.

import hashlib, math

for text in ['Educora', 'educora', 'Educora!']:
    print(text, hashlib.sha256(text.encode()).hexdigest()[:16])

rate = 10 ** 10
for name, n, length in [('8 lowercase', 26, 8), ('12 mixed', 94, 12)]:
    bits = length * math.log2(n)
    seconds = n ** length / rate
    print(name, '|', round(bits, 1), 'bits |', f'{seconds:.3g}', 'seconds')

Educora b3dbb4d80128c71a
educora 48ecb7c2aeec01dc
Educora! 836636e98b18e97a
8 lowercase | 37.6 bits | 20.9 seconds
12 mixed | 78.7 bits | 4.76e+13 seconds

Пароли нельзя хранить ни открытым текстом, ни простым SHA-256: сервер выдаёт каждому пользователю случайную соль и хеширует пароль намеренно медленной функцией — Argon2, bcrypt, scrypt или PBKDF2. Соль не даёт одинаковым паролям давать одинаковые хеши и обесценивает заранее вычисленные таблицы, а медлительность мешает миллиардам быстрых попыток. Цифровая подпись устроена так: отправитель подписывает хеш сообщения своим закрытым ключом, а любой проверяет её открытым ключом отправителя. Кому принадлежит открытый ключ, подтверждает сертификат — документ, подписанный доверенным центром (CA).

Атаки и защита

-- the program glues user input into the query:
--   WHERE email = '<input>'
-- the attacker types:  x' OR '1'='1
SELECT COUNT(*) AS leaked_rows
FROM students
WHERE email = 'x' OR '1'='1';

leaked_rows
12