Реально ли построить целую отрасль криптографии на семействе псевдослучайных источников?
Теоретически да. Если был эффективный и криптографически безопасный генератор псевдослучайных чисел, построенный из хаотической системы, который мог бы служить основой разумно практичной симметричной криптографии и даже подписи.
Проблема в том, что мы не знаем ничего подобного. ГПСЧ, построенные из хаотической системы и имеющие даже слегка убедительный аргумент безопасности¹, бледнеют по эффективности по сравнению с современными CSPRNG² (если только мы не расширим определение «хаотической системы» далеко за пределы обычных повторяющихся непрерывных функций на $\mathbb R$, или их дискретные приближения).
(Криптографически безопасный) Генератор псевдослучайных чисел, в его современное определение, является достаточно мощным инструментом для создания всех других функций симметричной криптографии: цена за конверсию и ОСО(2)- безопасный шифр, блочный шифр, Код аутентификации сообщения, аутентифицированное шифрование, хэш¦ Некоторые примеры:
- Шифр может быть построен из (CS)PRNG с использованием ключа и действительно случайного случайного IV для заполнения PRNG и построения зашифрованного текста с помощью XOR вывода PRNG с открытым текстом³.Безопасность напрямую следует из безопасности ГПСЧ, и это настолько хороший и распространенный способ создания шифра, что у него есть имя: потоковый шифр.
- Блочный шифр может быть построен из ГПСЧ как шифр Фейстеля, используя PRNG для построения функций округления. Ключ, круглое число и правая половина блока задают PRNG, результатом которого является значение XOR с левой половиной.
Эти конструкции явно криптографически безопасным, если PRNG является. Но за исключением потоковых шифров, на практике они не используются, в первую очередь, из соображений эффективности. Обычные CSPRNG строятся из блочных шифров и/или хэшей, а не наоборот.
Возможно ли построить криптографические примитивы с открытым ключом из PRNG?
Да для подписи. Мы можем построить безопасный хеш из безопасного PRNG, а затем защитить подпись из хэша, используя различные подходы, включая СФИНКИ. Таким путем любой эффективный PRNG приводит к правдоподобной схеме подписи.
Для шифрования и обмена ключами я сомневаюсь, что известен метод с доказательством безопасности или хотя бы убедительным аргументом. Меня не убеждают попытки построить асимметричное шифрование из непрерывных хаотических систем более прямыми путями».
¹ Мы не можем требовать доказательства в математическом смысле, поскольку у нас нет такого доказательства безопасности для любого CPRNG. Но мы не хотим принимать в качестве аргумента безопасности факт прохождения предопределенного теста на случайность, такого как NIST SP800-22rev1a или же несгибаемый. Экспериментальный тест должен быть, по крайней мере, невозможным для опытных криптографов-людей. зная конструкцию ГПСЧ, с помощью классических компьютеров, чтобы отличить от истинной случайности вывод ГПСЧ, засеянный истинной случайностью. И мы хотели бы расширить это до такой невозможности, начиная с минимального значения некоторых параметров PRNG, таких как размер состояния или/и количество раундов, с фактически используемыми параметрами, установленными комфортно большими.
² Например, полученный из ЧаЧа рассматривая ключ и IV как начальное значение и полностью нулевой открытый текст.
³ Расшифровка аналогична обмену открытым текстом и зашифрованным текстом, за исключением того, что шифрование рисует IV и делает его преамбулой зашифрованного текста, в то время как при дешифровании IV извлекается из преамбулы.
один такой пытаться (платный доступ) использует Полиномы Чебышева $T_r$ большой степени $г$. Закрытый ключ $г$, соответствующий открытый ключ $T_r(x)$ для некоторых общедоступных фиксированных случайно выбранных реальных $х\в[-1,1]$. Для любого целого числа $s>0$ он держит $T_r(T_s(x))=T_s(T_r(x))$ и (игнорируя проблемы, связанные с тем, как это вычисляется), что позволяет использовать аналог Обмен ключами Диффи-Хеллмана, и от того Шифрование Эль-Гамаля. Когда я впервые прочитал его, меня не убедило бесаргументированное утверждение безопасности, а также некоторые аспекты осуществимости (например, что с точностью 2048 битов для действительных значений целые числа $г$ и $s$ могут быть выбраны как случайные 910-битные целые числа, а не как произведение простых чисел не более 133, как в статье).
Обновление: криптосистема оказалась небезопасной, см. статья (платный доступ). Это все еще представлено в этом глава о криптографии с открытым ключом (платный доступ) гораздо позже книга о криптографии, основанной на хаосе (платный доступ), с подтверждением отсутствия безопасности. Я считаю, что это говорит о состоянии всей этой академической области. И это в лучшем случае: большинство заявлений о безопасности, сделанных со сравнительно слабыми аргументами, никогда серьезно не расследуются и не опровергаются.
