Введение в современную криптографию
Создание криптостойких систем шифрования
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 3.3.1 Псевдослучайные генераторы и поточные шифры
| 3.3 Создание криптостойких систем шифрования
Определив, какая система шифрования является надежной, читатель, вероятно, ждет, что мы немедленно перейдем к конструированию криптографически надеж- ных систем шифрования. Однако перед этим нам необходимо ввести понятия «псев- дослучайные генераторы» (ПСГ) и «поточные шифры», являющиеся важными структурными элементами шифрования с закрытым ключом. Они в свою очередь подведут нас к обсуждению псевдослучайности, которая играет важнейшую роль для криптографии в целом и для шифрования с закрытым ключом в частности. 3.3.1 Псевдослучайные генераторы и поточные шифры Генератор псевдослучайных чисел tt - это эффективный, детерминированный алгоритм для преобразования коротких, однородных строк, так называемых на- чальных чисел, в более длинные, «выглядящие однородными» (или «псевдослу- чайные») выходные строки. Иначе говоря, генератор псевдослучайных чисел использует небольшой объем реальной случайности для генерации большого объема псевдослучайности. Это может быть полезно всякий раз, когда требу- ется большой объем случайных (выглядящих случайными) битов, поскольку по-настоящему случайные биты генерируются медленно и сложно. (См. пояс- нение в начале Главы 2.) Действительно, псевдослучайные генераторы изуча- ются с 1940-х гг., когда они были предложены для работы со статистическими моделями. Тогда исследователи предложили различные статистические испы- тания, которые генератор псевдослучайных чисел должен был пройти, чтобы считаться «хорошим». Например, первый бит, выведенный генератором псев- дослучайных чисел, должен быть равен 1 с вероятностью, очень близкой к 1/2 71 (где вероятность вычисляется по равномерному выбору начальных чисел), по- скольку первый бит равномерной строки равен 1 с вероятностью ровно 1/2. Действительно, соответствие любого фиксированного подмножества выведен- ных битов также должно равняться 1 с вероятностью, очень близкой 1/2. Также могут быть рассмотрены и более сложные статистические испытания. Такой исторический подход определения качества потенциально пригодного генератора псевдослучайных чисел является ситуативным, и не всегда очевид- ным, прохождение некоторого набора статистических тестов достаточно для обеспечения надежности использования потенциально пригодного генератора псевдослучайных чисел для некоторого приложения. (В частности, может су- ществовать другой статистический тест, который успешно отличит выходные данные генератора от по-настоящему случайных битов.) Исторический подход представляет еще большую проблему при использовании генераторов псевдос- лучайных чисел для криптографического применения. В таких условиях крип- тостойкость системы может быть скомпрометирована, если перехватчик сумеет отличить равномерные и выходные данные генератора; и мы не можем заранее определить, какую стратегию выберет перехватчик. Приведенные выше соображения объясняют криптографический подход к опре- делению генераторов псевдослучайных чисел в 1980-х гг. Основным было то, что хороший генератор псевдослучайных чисел должен пройти все (эффективные) ста- тистические испытания. Иными словами, для любого эффективного статистиче- ского испытания (или дистинктора) D, вероятность того, что D выдаст 1 при полу- чении выходных данных генератора псевдослучайных чисел, должна быть близка к вероятности того, что D выдаст 1 при получении однородной строки той же длины. Тогда, неформально, любому эффективному наблюдателю выходные данные гене- ратора псевдослучайных чисел должны «казаться» однородной строкой. (Обращаем ваше внимание на то, что, формально говоря, не имеет смысла говорить о том, что любая фиксированная строка является «псевдослучайно», также как и бессмысленно называть любую строку «случайной». Точнее, псев- дослучайность - это свойство распределения по строкам. Тем не менее, мы ино- гда неформально называем строку, отобранную в соответствии с равномерным распределением, «однородной строкой», а строку, выданную генератором псев- дослучайных чисел - «псевдослучайно строкой».) Мы получаем другое представление, когда определяем, что значит псевдос- лучайное распределение. Пусть Dist является распределением по A-битным строкам. (Это значит, что Dist присваивает некоторую вероятность каждой строке в {0, 1}A. Выборка из Dist означает, что мы выбираем A-битную строку в соответствии с этим распределением вероятности.) Неформально, Dist явля- ется псевдослучайным, если эксперимент, в котором строка отбирается из Dist, 72 неразличим с экспериментом, в котором отбирается однородная строка с длиной A. (Строго говоря, поскольку мы находимся в асимптотическом окружении, нам не- обходимо говорить о псевдослучайности последовательности распределений Dist = {Distn}, где распределение Distn используется в качестве параметра безопасности n. В настоящем обсуждении мы этот момент игнорируем.) Точнее, любой полино- миально-временной алгоритм не должен быть в состоянии определить (с вероятно- стью выше, чем при догадке), дана ли ему строка, отобранная в соответствии с Dist, или же ему дана однородная A-битная строка. Это означает, что псевдослучайная строка так же хороша, как и однородная строка, пока мы рассматриваем только полиномиально-временных наблюдателей. Как и неразличимость, являющаяся вы- числительным ослаблением абсолютная стойкость , псевдослучайность является вычислительным ослаблением истинной случайности. (Мы обобщим это пред- ставление, когда будем обсуждать понятие неразличимости в главе 7.) Теперь пусть tt : {0, 1}n → {0, 1}A является функцией, а Dist - распределением по A-битным строкам, полученным в результате выбора однородного s ∈ {0, 1} n и вывода tt(s). Тогда tt является генератором псевдослучайных чисел тогда и только тогда, когда распределение Dist является псевдослучайным. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|