Случайность и псевдослучайность

Случайность является основой криптографии — ключи, одноразовые коды (nonces) и запросы (challenges) должны быть непредсказуемыми — а псевдослучайность позволяет растянуть короткое истинно случайное начальное значение в длинные последовательности, неотличимые от случайных для любого эффективного противника.

Definition

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

Scope

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

Core questions

• Почему криптография требует непредсказуемой случайности, и что происходит без нее?
• Что отличает криптографически стойкий генератор от статистического?
• Как короткое истинно случайное начальное значение может быть растянуто в длинный псевдослучайный выходной поток?
• Что такое псевдослучайные функции и перестановки, и как они моделируют шифры?
• Как собирается и обрабатывается высококачественная энтропия в реальных системах?

Key concepts

• энтропия и истинная случайность
• генераторы случайных чисел
• псевдослучайный генератор (PRG)
• псевдослучайная функция (PRF)
• псевдослучайная перестановка (PRP)
• вычислительная неотличимость
• начальное значение и вывод ключа
• сбои из-за повторного использования случайности
• кондиционирование энтропии

Key theories

Псевдослучайные генераторы

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

Псевдослучайные функции и перестановки

Семейство псевдослучайных функций, конструируемое из любого псевдослучайного генератора, неотличимо от истинно случайной функции для противника, запрашивающего ее; этот объект лежит в основе моделирования безопасности блочных шифров и кодов аутентификации сообщений.

Mechanisms

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

Clinical relevance

Сбои в случайности являются повторяющимся источником катастрофических реальных уязвимостей: ошибка Debian OpenSSL 2008 года парализовала генерацию ключей, предсказуемые одноразовые коды ECDSA привели к утечке закрытых ключей (Sony PlayStation 3, некоторые биткойн-кошельки), а слабая энтропия встроенных устройств привела к массовому созданию угадываемых ключей. Поэтому надежная случайность — правильный сбор энтропии и проверенные псевдослучайные генераторы — необходима для каждого криптографического развертывания.

Evidence & guidelines

NIST SP 800-90A/B/C определяют утвержденные детерминированные генераторы случайных битов, валидацию источников энтропии и рекомендации по их построению. Передовая практика предполагает использование проверенного криптографического ГСЧ операционной системы (вместо создания собственного), обеспечение достаточной энтропии перед генерацией ключей и никогда не повторное использование одноразовых кодов. Наборы статистических тестов помогают выявить грубые недостатки, но не могут установить криптографическую стойкость.

History

Вычислительная теория псевдослучайности была основана Блюмом и Микали, а также Яо около 1982 года, определив непредсказуемость и неотличимость. Голдрейх, Голдвассер и Микали показали, как строить псевдослучайные функции из генераторов в 1986 году, а Хастад, Импальяццо, Левин и Люби позже доказали, что псевдослучайные генераторы существуют, если существуют односторонние функции. Повторяющиеся практические катастрофы из-за слабой случайности сделали качество энтропии и ГСЧ центральной инженерной проблемой.

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

Почему я не могу использовать обычную случайную функцию, такую как rand(), для криптографии?

Обычные генераторы случайных чисел созданы для статистической однородности и скорости, а не для непредсказуемости; их выходные данные могут быть предсказаны по нескольким образцам. Криптографии нужны генераторы, чьи будущие выходные данные невозможно предсказать даже при наличии прошлых выходных данных, что требует криптографически стойкого ГСЧ, инициализированного реальной энтропией.

В чем разница между истинной случайностью и псевдослучайностью?

Истинная случайность исходит из физического, непредсказуемого источника и ограничена в количестве. Псевдослучайность генерируется детерминированно из короткого истинно случайного начального значения и может быть произведена в больших объемах; ей достаточно быть неотличимой от истинной случайности для любого эффективного противника, что достаточно для криптографического использования.