Насколько мне известно, большинство реализаций генерации псевдослучайных чисел на практике используют такие методы, как регистры обратной связи с линейным сдвигом (LSFR) или эти алгоритмы "Mersenne Twister". Хотя они проходят множество (эвристических) статистических тестов, нет никаких теоретических гарантий того, что они выглядят псевдослучайно, скажем, для всех эффективно вычисляемых статистических тестов. Тем не менее, эти методы используются без разбора во всех видах приложений, от криптографических протоколов до научных вычислений и банковских операций (вероятно). Я нахожу несколько беспокоящим, что у нас практически нет гарантий того, работают ли эти приложения, как предполагалось (потому что любой вид анализа, вероятно, предполагал бы истинную случайность в качестве входных данных).
С другой стороны, теория сложности и криптография предоставляют очень богатую теорию псевдослучайности, и у нас даже есть подходящие конструкции псевдослучайных генераторов, которые могли бы обмануть ЛЮБОЙ эффективный статистический тест, который вы могли бы придумать, используя возможные односторонние функции-кандидаты.
Мой вопрос: эта теория нашла свое применение на практике? Я надеюсь, что для важных применений случайности, таких как криптография или научные вычисления, теоретически используются надежные PRG.
Кроме того, я мог бы найти ограниченный анализ того, насколько хорошо работают популярные алгоритмы, такие как быстрая сортировка, при использовании LSFR в качестве источника случайности, и, очевидно, они работают хорошо. См. Карлофф и Рагхаван "Рандомизированные алгоритмы и псевдослучайные числа" .
Ответы:
Понятие «теоретически обоснованных» псевдослучайных генераторов не очень хорошо определено. В конце концов, ни у одного псевдослучайного генератора нет доказательства безопасности. Я не знаю, что можно сказать, что генератор псевдослучайных данных, основанный на сложности вычисления больших целых чисел, «более безопасен», чем, скажем, использование AES в качестве генератора псевдослучайных чисел. (На самом деле, есть ощущение, что он менее безопасен, так как мы знаем алгоритмы квантового факторинга, но не квантовые алгоритмы для взлома AES.)
У нас есть математические доказательства - это различные результаты композиции, говорящие о том, что если вы составляете блочные шифры или хэш-функции определенным образом, вы можете получить псевдослучайные генераторы или псевдослучайную функцию. Некоторые такие результаты широко используются на практике, например, HMAC . Но это правда, что результаты, которые достигают PRG и начинаются с предположения, что базовый компонент является простой односторонней функцией, недостаточно эффективны для использования в приложениях (и это, по крайней мере, частично присуще). Итак, обычно нам нужно принять PRG / потоковый шифр / блочный шифр / хэш-функцию в качестве базового примитива и начать строить из него другие вещи. Проблема не в асимптотическом анализе, поскольку по существу все криптографические сокращения (за исключением, возможно, универсальной PRG Левина) могут быть конкретизированы и, таким образом, давать конкретные гарантии при конкретных допущениях.
Но даже если они не основаны на односторонних функциях, в некотором смысле такие конструкции, как AES, «теоретически обоснованы», потому что: (1) существуют формальные предположения об их безопасности. (2) Есть работа, чтобы попытаться опровергнуть эти предположения, а также извлечь из них следствия.
И действительно, люди знают, что для многих приложений было бы неразумно использовать PRG, такие как LSFR, которые не удовлетворяют (1) и (2) выше.
источник
Вы, кажется, путаете теорию с практикой. Теоретически обоснованный псевдослучайный генератор плохо подходит для практического использования по нескольким причинам:
В противоположность этому, псевдослучайные генераторы являются быстрыми и могут быть разных типов в зависимости от их использования. Для не криптографического использования подойдет почти все, кроме простого LFSR - не доказуемо, но на практике (что более важно для людей, использующих вещи в реальности).
Для криптографического использования люди стараются быть умнее. На этом этапе ваша критика имеет смысл: мы не можем знать, что конкретный используемый генератор псевдослучайных данных является «безопасным», и действительно некоторые старые были сломаны, например RC4, используемый в WEP. Однако по причинам, изложенным выше, использование теоретически (условно) звукового псевдослучайного генератора, к сожалению, не является реалистичным решением. Вместо этого криптологическое сообщество полагается на «экспертную оценку» - другие исследователи, которые пытаются «сломать» систему (их определение того, когда шифр взломан, очень широко).
Наконец, в приложениях, когда деньги могут быть инвестированы и безопасность достаточно важна - скажем, ядерные коды - люди используют физически генерируемый шум (пропускаемый через экстрактор случайности), хотя даже это не выходит за рамки теоретической критики.
Когда исследователи пишут предложения по грантам или вводят в документы, они часто утверждают, что их исследования относятся к практике и дают ей представление. Верят ли они в это, или это просто на словах, я не знаю (и это может зависеть от исследователя), но вы должны знать, что связь сильно преувеличена в академических кругах по очевидным причинам.
Одна вещь, которая ограничивает нас как математических исследователей, это наша догматическая привязанность к формальным доказательствам. Вы упоминаете анализ рандомизированных алгоритмов, питаемых простыми псевдослучайными генераторами. Этот вид анализа не может быть распространен на реальные проблемы, поскольку они просто слишком сложны. И все же на практике люди все время решают даже NP-сложные задачи, используя информированные методы.
Проблемы реального мира лучше понимаются более научным и экспериментальным взглядом. Они лучше решаются с инженерной точки зрения. Они вдохновляют теоретическое исследование, и иногда сообщают им. Как сказал Дийсктра, (теоретическая) компьютерная наука на самом деле не о компьютерах, а уже не о них.
источник