Новый генератор повышает безопасность и скорость

В компьютерной безопасности случайные числа являются важными значениями, которые должны быть непредсказуемыми – такие как секретные ключи или векторы инициализации (IVS) – формирование основания систем безопасности. Для достижения этого используются детерминированные генераторы случайных битов (DRBG), которые производят числа, которые кажутся случайными. Тем не менее, существующие DRBGS имели ограничения как в безопасности (непредсказуемость от взлома), так и скорости выхода.

Исследователи KAIST разработали DRBG, который теоретически достигает максимально возможного уровня безопасности с помощью новой техники доказательств, максимизируя скорость путем параллелизирования ее структуры. Это обеспечивает безопасное и сверхбыстрое генерацию случайных чисел, применимые от устройств IoT, до крупномасштабных серверов.

Исследовательская команда, возглавляемая профессором Jooyoung Lee из Школы вычислений, создала Новая теоретическая структура Для анализа безопасности детерминированных генераторов случайных битов, основанных на перестановке (DRBG, детерминированный генератор случайных битов) и разработал DRBG, который достигает оптимальная эффективностьПолем

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

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

Функции перестановки, как фундаментальные компоненты криптографических алгоритмов, которые допускают двунаправленные вычисления, привлекли значительное внимание к их превосходной безопасности и эффективности, особенно с тем, чтобы быть принятыми в стандартной функции HASH SHA-3 в США.

Тем не менее, строительство губки, принятое в SHA-3, подвергалось критике за ее ограниченную эффективность выходной продукции по сравнению с размером перестановки. Поскольку все существующие DRBG, основанные на перестановке, использовали губчатые конструкции в своих выходных функциях, они также страдали от ограничений выходной эффективности.

Кроме того, существующие DRBGS, основанные на перестановке, использовали технику под названием «Запрыгивание игры», чтобы доказать безопасность. Однако этот метод имел ограничение на получение более низких гарантий безопасности, чем теоретически.

Например, когда пропускная способность перестановки составляет 256 бит, теоретическое ожидание составляет min {c/2, λ}, то есть 128-битная безопасность. Но при традиционном методе доказательства гарантия была только min {c/3, λ}, около 85 бит. (λ относится к порогу энтропии, а мин указывает на получение меньшего из двух значений.)

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

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

В результате они продемонстрировали, что уровень безопасности DRBG, основанных на перестановке, фактически соответствует MIN {C/2, λ} битам-улучшение приблизительно 50% по сравнению с существующими доказательствами. Они также доказали, что это значение является теоретическим максимально достижимым.

Исследовательская группа также разработала POSDRBG (DRBG на основе параллельных выводов) для устранения ограничения эффективности выработки существующей структуры губки, вызванной его последовательной (однострочной) обработкой. Недавно предложенная параллельная структура обрабатывает несколько потоков одновременно, тем самым достигая максимальной эффективности, возможной для DRBG на основе перестановки.

Профессор Jooyoung Lee заявил: «POSDRBG-это новый детерминированный генератор случайных битов, который улучшает как скорость генерации, так и безопасность случайных чисел, что делает его применимым от небольших устройств IoT к крупномасштабным серверам. Это исследование, как ожидается, положительно повлияет на постоянный пересмотр международных DRBG SP800-90A, что приведет к формальному включению DRBG, основанных на перемещениях.

Это исследование с Woohyuk Chung (Kaist, First Author), Seongha Hwang (Kaist), Hwigyeom Kim (Samsung Electronics) и Jooyoung Lee (Kaist, автор -соответствующий), будет представлена в августе. Крипто (Ежегодная международная криптологическая конференция) и была опубликована как часть Достижения в области криптологии – Crypto 2025

Функция вывода случайного числа существующей губки-DRBG использует структуру губки, которая непосредственно соединяет перестановку P. Для справки, все существующие DRBG, основанные на перестановке, имеют эту структуру губки. В структуре губки, среди N-битных входов P, только верхние r-биты используются в качестве выходного Z. Следовательно, выходная эффективность всегда ограничена R/N.

В этом исследовании функция вывода случайного числа POSDRBG была разработана для разрешения параллельных вычислений, и все N-битные выходы функции перестановки p становятся случайными числами Z. Следовательно, она обладает выходной эффективностью 1.