💻Cryptography and Security

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

Проблема, которую не решить силой

2013 год. Эдвард Сноуден сливает документы АНБ. Выясняется: спецслужбы США перехватывают трафик интернет-провайдеров по всему миру. Программа PRISM — прямой доступ к серверам Google, Facebook, Microsoft.

Вопрос: почему не взломали переписку Сноудена? Ответ: он использовал Tor (луковая маршрутизация) и PGP-шифрование (асимметричная криптография на основе RSA).

АНБ с бюджетом $10 миллиардов в год не смогло расшифровать сообщения одного человека. Потому что математика сильнее вычислительной мощности.

Факторизация 2048-битного числа (основа RSA) займёт миллиарды лет на всех компьютерах Земли вместе взятых. Это не слабость алгоритма — это физический предел вычислений.

Шифр Цезаря: где всё началось

Юлий Цезарь (I век до н.э.) шифровал военные приказы сдвигом на 3 буквы: A→D, B→E, C→F.

Сообщение: АТАКА
Шифр: ДФДКД

Ключ — число 3 (величина сдвига). Расшифровка — сдвиг на -3.

Слабость: всего 25 вариантов ключа (для латиницы). Перебор вручную за 5 минут. Частотный анализ (в русском языке «О» встречается чаще всего) ломает шифр за секунды.

Но принцип правильный: секретность алгоритма не важна (шифр Цезаря всем известен), важна секретность ключа.

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

Симметричное шифрование: один ключ для всех

Алиса и Боб хотят переписываться. Договариваются о секретном ключе K. Алиса шифрует сообщение M: C = E(M, K). Боб расшифровывает: M = D(C, K).

AES (Advanced Encryption Standard, 2001): стандарт США, выбран в открытом конкурсе из 15 кандидатов. Размеры ключа: 128, 192, 256 бит.

AES-256: 2²⁵⁶ вариантов ключа. Это 10⁷⁷ — больше, чем атомов во Вселенной (10⁸⁰, но сопоставимо). Перебор невозможен физически.

Как работает AES:

1. Блочный шифр: данные разбиваются на блоки по 128 бит
2. Раунды преобразований (10/12/14 в зависимости от размера ключа)
3. Операции: подстановка байтов (SubBytes), сдвиг строк (ShiftRows), перемешивание столбцов (MixColumns), добавление ключа (AddRoundKey)

Каждый раунд перемешивает биты так, что изменение одного бита входа меняет ~50% бит выхода (лавинный эффект). После 10 раундов связь между входом и выходом полностью разрушена.

Применение: шифрование диска (BitLocker, FileVault), архивов (7-Zip с паролем), Wi-Fi (WPA2/WPA3), мессенджеров (Signal, Telegram).

Проблема симметричного шифрования: как безопасно передать ключ K? Если Ева перехватит K, она прочтёт все сообщения. Нужна встреча Алисы и Боба лично (не всегда возможно) или защищённый канал (но его и пытаемся создать!).

Асимметричное шифрование: революция RSA

1977 год. Рон Ривест, Ади Шамир, Леонард Адлеман публикуют алгоритм RSA. Идея: у каждого два ключа — публичный (открытый) и приватный (секретный).

Публичный ключ: можно публиковать в интернете, передавать кому угодно.
Приватный ключ: никому не показывать, хранить на своём компьютере.

Шифрование: Алиса берёт публичный ключ Боба, шифрует сообщение → отправляет. Только приватный ключ Боба может расшифровать.

Цифровая подпись: Боб берёт свой приватный ключ, «подписывает» документ → отправляет с подписью. Алиса проверяет подпись публичным ключом Боба. Если проверка прошла, документ точно от Боба и не изменён.

Математическая основа RSA:

1. Выбрать два больших простых числа: p и q (по 1024 бита каждое)
2. Вычислить n = p × q (2048 бит)
3. Публичный ключ: (n, e). Приватный ключ: (n, d)

Шифрование: c = m^e mod n
Расшифровка: m = c^d mod n

Стойкость: чтобы взломать, нужно факторизовать n (разложить на p × q). Для 2048-битного числа это невозможно за разумное время на классических компьютерах.

Парадокс: алгоритм RSA опубликован в 1977 году, его математическая основа известна всем. Но за 49 лет никто не нашёл эффективного способа факторизации больших чисел. Это предположение, а не доказанный факт. Если кто-то найдёт алгоритм — вся криптография рухнет мгновенно.

Хеш-функции: цифровые отпечатки

Хеш-функция: H(x) → строка фиксированной длины. Любой вход (1 байт или 1 ГБ) → всегда 256 бит (для SHA-256).

Свойства:

1. Детерминированность: H(x) всегда одинаков
2. Быстрое вычисление: миллиарды хешей в секунду
3. Необратимость: по H(x) нельзя восстановить x
4. Лавинный эффект: изменение 1 бита x → меняется ~50% бит H(x)
5. Стойкость к коллизиям: сложно найти x ≠ y, где H(x) = H(y)

Пример SHA-256:

H("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
H("Hello") = 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969

Изменение одной буквы (h→H) полностью меняет хеш. Предсказать невозможно.

Применения:

1. Хранение паролей: сервер хранит не пароль, а H(пароль). При входе проверяет: H(введённый пароль) == сохранённый хеш. Даже если базу украдут, пароли восстановить нельзя.

2. Целостность файлов: скачали файл, вычислили SHA-256. Сравнили с хешем на сайте. Совпадает → файл не повреждён и не подменён.

3. Блокчейн (Bitcoin): каждый блок содержит хеш предыдущего. Изменить прошлый блок → нужно пересчитать все последующие (миллиарды долларов электричества). Поэтому блокчейн неизменяем.

Атака на хеш: rainbow tables — предвычисленные таблицы H(пароль) для популярных паролей. Защита: salt (случайная строка, добавляемая к паролю перед хешированием). H(пароль + salt) уникален для каждого пользователя.

HTTPS: как работает безопасный интернет

Открываете https://bank.com. Как браузер и сервер договариваются о ключе, если их соединение прослушивает злоумышленник?

Протокол TLS (Transport Layer Security):

1. Сервер отправляет свой публичный ключ RSA + сертификат (подпись от центра сертификации, например Let's Encrypt)
2. Браузер проверяет сертификат: подпись верна? Срок действия не истёк? Имя домена совпадает?
3. Браузер генерирует случайный ключ сессии (256 бит для AES)
4. Шифрует ключ сессии публичным ключом сервера → отправляет
5. Сервер расшифровывает приватным ключом → получает ключ сессии
6. Дальнейшая переписка идёт через AES с ключом сессии

RSA нужен только для обмена ключом (медленный, но безопасный). Основной трафик шифруется AES (быстрый).

Центры сертификации: Let's Encrypt, DigiCert, Comodo. Их публичные ключи зашиты в браузер. Если сертификат подписан одним из них, браузер доверяет сайту.

Атака Man-in-the-Middle: злоумышленник перехватывает трафик, подменяет сертификат сервера своим. Защита: браузер отклоняет сертификат, не подписанный доверенным центром. Поэтому нельзя просто так прослушать HTTPS (в отличие от HTTP).

Квантовые компьютеры: угроза для RSA

2026 год. Квантовых компьютеров достаточной мощности ещё нет. Но когда будут (прогноз: 2030-2040), они сломают RSA.

Алгоритм Шора (1994): квантовый алгоритм факторизации чисел за полиномиальное время. 2048-битное число — несколько часов на квантовом компьютере с ~4000 стабильными кубитами.

Сейчас (2026) рекорд — ~1000 кубитов (IBM, Google), но они «шумные» (ошибки каждые 0.1-1 мс). Для алгоритма Шора нужны «чистые» кубиты с коррекцией ошибок.

Постквантовая криптография: NIST (США) в 2024 году утвердил стандарты, устойчивые к квантовым атакам:

- CRYSTALS-Kyber (шифрование на решётках)
- CRYSTALS-Dilithium (цифровые подписи)
- FALCON, SPHINCS+ (альтернативные подписи)

Основаны на задачах, которые квантовые компьютеры решают не быстрее классических (поиск коротких векторов в решётках, задачи о изогениях).

Harvest now, decrypt later: спецслужбы уже сейчас записывают зашифрованный трафик. Когда появятся квантовые компьютеры, расшифруют архивы. Поэтому переход на постквантовую криптографию — срочная задача.

Реальные взломы: где криптография не помогла

1. Слабые пароли: AES-256 бесполезен, если пароль — «12345». Брутфорс пароля, а не ключа.

2. Уязвимости реализации: Heartbleed (2014) — баг в OpenSSL позволял читать память сервера, включая приватные ключи. Алгоритм RSA не взломан, взломана программа.

3. Социальная инженерия: фишинг, вирусы, кейлоггеры. Криптография не защищает от того, что пользователь сам отдал пароль.

4. Backdoors: Dual_EC_DRBG — генератор случайных чисел, стандартизованный NIST в 2006. В 2013 выяснилось: АНБ вшило бэкдор. Если использовать Dual_EC_DRBG, АНБ может предсказать «случайные» числа и взломать шифрование.

Урок: доверяй, но проверяй. Открытые алгоритмы (AES, RSA) проверены миллионами исследователей. Закрытые (от спецслужб, производителей) — потенциально скомпрометированы.