Зачем это всё нужно? PRG | PRF

Зачем это всё нужно? PRG | PRF | GGM

В данной статье могут быть недочеты, изучайте это чтобы примерно понять что это такое.

Есть такая задача: чтобы шифровать данные, нужны случайные биты. Много. Генерация настоящей случайности — штука медленная и дорогая.

...штука медленная и дорогая.
Уточнение: Это верно для качественной энтропии. Современные CPU имеют инструкции типа RDRAND, но для криптографии часто комбинируют несколько источников энтропии (тайминги, шум ADC), что действительно требует времени для накопления достаточного количества битов.

При этом во многих алгоритмах (шифрование, аутентификация) нам не нужна случайность «в вакууме» — нам нужно, чтобы результат выглядел случайным для любого, у кого нет секретного ключа.

Отсюда рождаются две базовые концепции.

PRG — растягиваем случайность

Проблема: у нас есть мало "настоящей" случайности (например, 256 бит), а нужно много (гигабайты).

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

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

Ключевое слово "вычислительно" - означает, что не существует эффективного алгоритма, который мог бы их отличить за полиномиальное время.

Аналогия: если дать вам два листа с числами — на одном вывод PRG, на другом настоящая случайность — вы не сможете сказать, где что.

Запомни: истинно случайные биты — это эталон, к которому мы стремимся для создания криптографических ключей и seed'ов. PRG и PRF — это криптографические примитивы, которые должны быть вычислительно неотличимы от этого эталона для любого, у кого нет секретного ключа.

Важно: если seed известен, всю псевдослучайную последовательность можно воспроизвести. Безопасность держится на секретности seed'а и на стойкости самого PRG. Если PRG уязвим, то даже при секретном seed'e можно предсказать выход.

PRF — псевдослучайные функции

Проблема: нам нужно не просто генерировать числа, а получать «случайный» результат для каждого входа. Например, для аутентификации сообщений.

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

Требование: зная даже миллионы пар «вход-выход», нельзя предсказать значение для нового входа без ключа.

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

Важно: PRF — это криптографическое семейство функций, которое ведёт себя практически неотличимо от совершенно случайной функции для любого, у кого нет ключа. На основе PRF строятся MAC-ы, схемы выработки ключей и многое другое.

GGM — мост между PRG и PRF

Интуиция: если у нас есть PRG (можем растягивать случайность), можно ли из него сделать PRF (функцию с произвольным входом)?

Оказывается, да — через дерево Голдрейха-Гольдвассера-Микали.

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

Берём PRG, который из одного семечка делает два непредсказуемых
Строим бинарное дерево, где корень — наш секретный ключ
Чтобы вычислить значение для сообщения x, идём по дереву: каждый бит x говорит, в какую ветвь идти
Результат — лист, в котором мы оказались

Проще: превращаем последовательность битов сообщения в путь по дереву, на каждом шаге применяя PRG.

Вывод: GGM — это в первую очередь теоретическая конструкция, которая доказывает в принципе, что из любого стойкого PRG можно построить стойкую PRF. На практике используют более эффективные конструкции (HMAC, CMAC), но GGM важна для доказательства безопасности.

Уточнение: В GGM дерево строится не физически, а виртуально — мы вычисляем путь на лету, экономя память.

PRG — это статический генератор. Дали seed, получили длинную предопределённую последовательность. Всё заранее предсказуемо после инициализации.

PRF — это функция, которая может адаптироваться. Дали ключ и произвольное сообщение — получили уникальный результат, зависящий от этого сообщения.

GGM создаёт из PRG эту самую адаптивность через дерево. Каждый бит входного сообщения говорит PRG, в какую ветку дерева идти дальше. Таким образом, разные сообщения ведут к разным конечным точкам в дереве.

PRF нужна именно для этой адаптивности — чтобы один ключ мог генерировать разные непредсказуемые результаты для разных входов, а не просто производить статический поток данных как PRG.

это нужно для изменчивости

Что в сухом остатке

PRG нужен, чтобы из малого случайного seed'а делать много псевдослучайных данных
PRF нужна, чтобы получать детерминированные, но случайно выглядящие результаты для любых входов
GGM показывает, что эти концепции связаны: имея PRG, можно построить PRF

Вся современная криптография в той или иной степени использует эти идеи. Когда вы слышите про HMAC, поточные шифры, схемы аутентификации — за ними почти всегда стоят либо PRG, либо PRF, либо их гибриды.

Это не абстрактная теория — это фундамент, на котором построено всё остальное.