Вычислительная сложность и криптография

В 1976 году Уитфилд Диффи задал вопрос, перевернувший криптографию: «Что если существует математическая операция, которую легко выполнить, но невозможно обратить?» Если такие функции существуют - можно шифровать без предварительного обмена секретами. Если нет - безопасная связь через интернет принципиально невозможна. Парадокс: мы до сих пор не доказали, что такие функции существуют, но вся цифровая безопасность стоит на предположении, что они есть.

• **HTTPS/TLS:** при открытии сайта банка браузер полагается на то, что факторизация больших чисел и дискретный логарифм - вычислительно сложные задачи
• **Квантовая угроза:** алгоритм Шора решает факторизацию за полиномиальное время на квантовом компьютере - поэтому NIST стандартизирует post-quantum криптографию, основанную на других предположениях о сложности
• **Криптовалюты:** безопасность Bitcoin основана на сложности нахождения коллизий SHA-256 и дискретного логарифма на эллиптических кривых - два вычислительных предположения

Предварительные знания

• Probability and Randomness in Cryptography

Классы P и NP: вопрос на миллион долларов

Судоку 9×9 с несколькими заполненными клетками. **Решить** - может потребовать часы перебора. Но при виде уже заполненной сетки **проверить** правильность - секунды. Эта асимметрия между «решить» и «проверить» - суть вопроса P vs NP, одной из семи задач тысячелетия с призом в 1 000 000.

**Класс P** (Polynomial) - задачи, которые можно **решить** за полиномиальное время. Примеры: сортировка массива (O(n log n)), поиск кратчайшего пути (алгоритм Дейкстры), проверка числа на простоту (тест AKS). Полиномиальное время означает: при удвоении входа время растёт в фиксированное число раз (n², n³), а не экспоненциально.

**Класс NP** (Nondeterministic Polynomial) - задачи, для которых **правильный ответ можно проверить** за полиномиальное время. Ключевой момент: NP не означает «Non-Polynomial»! Это значит, что существует короткий «сертификат» (доказательство), который можно быстро верифицировать.

**Факторизация** - идеальный пример для криптографии. Перемножить два простых числа - мгновенно. Разложить произведение обратно - алгоритмы экспоненциального (или субэкспоненциального) времени. Проверить ответ - снова мгновенно (просто умножить факторы).

**Если бы доказали P = NP**, вся криптография рухнула бы. Каждый шифр, каждая цифровая подпись, каждый протокол - всё можно было бы взломать за полиномиальное время. Банковские транзакции, мессенджеры, блокчейн - всё стало бы беззащитным.

Односторонние функции

**Односторонняя функция** (one-way function) - функция f, которую легко вычислить, но практически невозможно инвертировать. «Легко» означает полиномиальное время. «Невозможно» означает: ни один алгоритм, работающий за полиномиальное время (PPT - Probabilistic Polynomial Time), не может по f(x) найти x с заметной вероятностью.

Рассмотрим умножение больших простых чисел. Два 512-битных простых числа перемножаются за микросекунды. Но разложить 1024-битное произведение обратно на множители - задача, для которой лучший известный алгоритм (General Number Field Sieve) требует субэкспоненциального времени.

**Формальное определение.** Функция f: {0,1}* → {0,1}* является односторонней, если выполнены два условия:

1. **Эффективность:** существует полиномиальный алгоритм, вычисляющий f(x) для любого x
2. **Односторонность:** для любого PPT-алгоритма A вероятность Pr[A(f(x)) ∈ f⁻¹(f(x))] ≤ negl(n), где negl(n) - пренебрежимо малая функция (убывает быстрее любого полинома)

**Важный парадокс:** строго доказать существование односторонних функций пока не удалось - это потребовало бы доказательства P ≠ NP. Но криптография работает на **предположении**, что такие функции существуют. Вся безопасность интернета основана на гипотезе, которую никто не доказал.

Trapdoor-функции: односторонние с секретным ходом

Односторонняя функция - как сейф без ключа: положить можно, достать - нет. Но для криптографии нужно, чтобы **законный получатель** мог расшифровать сообщение! **Trapdoor-функция** (функция с «потайным ходом») - это односторонняя функция, которая становится легко обратимой, если знать секрет (trapdoor).

**RSA как trapdoor-функция.** В RSA генерируются два больших простых числа p и q. Публичный ключ - это (n = p·q, e). Приватный ключ - d, вычисляемый из p и q. Шифрование: c = m^e mod n (легко). Расшифровка без d: нужно разложить n на p и q (сложно). Расшифровка с d: m = c^d mod n (легко).

**Другие trapdoor-функции в криптографии:**

• **RSA:** trapdoor = разложение n на p × q
• **Эллиптические кривые (ECC):** trapdoor = скалярный множитель k в точке Q = k·G
• **Решётки (Lattice):** trapdoor = короткий базис решётки (основа post-quantum криптографии)
• **Схема Рабина:** trapdoor = факторизация модуля (доказуемо эквивалентна факторизации)

**Ключевое отличие от просто односторонних функций:** хеш SHA-256 - односторонняя, но НЕ trapdoor: никакой секрет не поможет эффективно найти прообраз. Для асимметричной криптографии нужны именно trapdoor-функции - иначе даже получатель не сможет расшифровать сообщение.

Доказуемая безопасность: reduction proofs

Как убедиться, что криптосистема безопасна? Проверить все возможные атаки? Их бесконечно много. Вместо этого криптографы используют **reduction proofs** (доказательства через сведение): «если эта схема взломана, значит решена задача X, которая считается неразрешимой».

**Пример: безопасность RSA.** Предположим, кто-то нашёл алгоритм A, который расшифровывает RSA без приватного ключа. Тогда мы можем использовать A для факторизации любого числа n = p·q. Но факторизация считается вычислительно неразрешимой (для больших n). Противоречие. Значит, алгоритм A не существует - при условии, что факторизация действительно сложна.

Существуют два принципиально разных уровня безопасности:

**Доказательство безопасности всегда условно.** Оно говорит: «если задача X сложна, то схема S безопасна». Но если завтра найдут быстрый алгоритм факторизации - RSA рухнет. Если построят мощный квантовый компьютер - алгоритм Шора факторизует за полиномиальное время, и RSA, и эллиптические кривые окажутся уязвимы.

Ключевые идеи

• **P vs NP** - главный открытый вопрос: совпадают ли классы задач, решаемых и проверяемых за полиномиальное время. Если P = NP, вся криптография рушится. Вопрос Диффи из 1976 года до сих пор не получил строгого ответа - но от него зависит безопасность каждого байта в интернете
• **Односторонние функции** - легко вычислить, невозможно инвертировать за полиномиальное время. Примеры: умножение простых чисел, хеширование, дискретный логарифм
• **Trapdoor-функции** - односторонние с секретным ходом, позволяющим эффективную инверсию. Основа асимметричной криптографии (RSA, ECC)
• **Доказуемая безопасность** - reduction proof сводит взлом схемы к решению задачи, считающейся неразрешимой. Безопасность условна: она зависит от истинности вычислительных предположений

Связанные темы

Вычислительная сложность - фундамент, на котором строится вся прикладная криптография:

• Теория чисел — Факторизация и дискретный логарифм - конкретные предположительно сложные задачи из теории чисел
• RSA: математика — RSA - главный пример trapdoor-функции на практике, безопасность сводится к факторизации
• Квантовая угроза — Квантовые компьютеры меняют вычислительные предположения - алгоритм Шора решает факторизацию за полиномиальное время
• Модели безопасности — Формальные модели (CPA, CCA, IND-CCA2), в рамках которых строятся reduction proofs

Вопросы для размышления

• Если бы завтра доказали P = NP, какие конкретные последствия это имело бы для цифровой жизни в целом?
• Мы строим безопасность на предположениях, которые не доказаны. Это приемлемый риск или фундаментальная проблема?
• Квантовые компьютеры угрожают RSA и ECC, но не AES (достаточно удвоить длину ключа). Почему разные предположения о сложности по-разному уязвимы к квантовым атакам?

Связанные уроки

• cplx-01