Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Псевдослучайные функции и псевдопроизвольные генераторы.
| Блочные шифры. На практике, блочные шифры создаются как защищенные эк-
земпляры (сильных) псевдослучайных перестановок с некоторой фиксированной длиной ключа и длиной брока. Мы обсудим различные подходы к созданию блоч- ных шифров, а также некоторые популярные варианты блочных шифров в Главе 6. Для целей текущей главы детали конструкций неважны, и на данный момент мы просто предположим, что (сильные) псевдослучайные перестановки существуют. Псевдослучайные функции и псевдопроизвольные генераторы. Как можно ожидать, существует тесная связь между псевдослучайными функци- ями и прсевдопроизвольными генераторами. Построить псевдослучайный генератор tt из псевдослучайной функции F достаточно легко, просто вы- числив F на серии различных аргументов. Например, мы можем определить для любой A. Если бы вместо Fs была равномерная функция f , результат tt был бы равномерным; таким образом, при использова- нии вместо этого F , результат получается псевдослучайным. Вам нужно будет 94 формально доказать это утверждение в Упражнении 3.14 . В более общем плане, мы можем использовать эту идею для построения по- точного шифра (Init, GetBits) который принимает синхропосылку IV . (См. Раз- дел 3.3.1) Единственное отличие состоит в том, что вместо вычисления Fs на фиксированной последовательности входных данных 1, 2, 3, . . ., мы вычисляем F на данных IV + 1, IV + 2, . . . . КОНСТРУКЦИЯ 3.29 Пусть F - псевдослучайная функция. Определим поточный шифр (Init, GetBits) где каждых вызов GetBits выдает n битов, следующим образом: • Init на входе s∈{0,1}n и IV∈ {0,1}n так st0 := (s, IV ). • GetBits: на входе sti=(s, IV ) на выходе IVr=IV+1и y:= Fs(IV r) и sti+1 := (s, IV r). Вывести (y, sti+1). так st0 := (s, IV ). Поточный шифр из любой псевдослучайной функции/блочного шифра. Несмотря на то, что поточные шифры могут быть построены из блочных шифров, специально созданные поточные шифры на практике обычно более эффективны, особенно в условиях ограниченных ресурсов. С другой стороны, судя по всему, по- точные шифры менее понятны (на практике), чем блочные шифры, и поэтому уве- ренность в их безопасности меньше. Поэтому, рекомендуется по мере возможности использовать блочные шифры (возможно, сначала преобразовывая их в поточные). Рассмотрим противоположное направление. псевдослучайный генератор tt незамедлительно выдает псевдослучайную функцию F с малой длиной блока. Более конкретно, предположим, что tt имеет коэффициент расширения n • 2t(n). Мы можем дать определение функции с ключом F :{0, 1}n×{0, 1}t(n)→{0, 1}n следующим образом: чтобы вычислить Fk (i), сначала вычислить tt(k) и пред- ставить результат как таблицу с количеством строк 2t(n), каждая из которых со- держит n битов; вывести i-ую строку. Вычисление происходит в полиномиаль- ном времени, только если t(n) = O(log n). Также можно, хотя сложнее, построить псевдослучайные функции с большой блочной длиной из псевдослучайных ге- нераторов; это показано в Разделе 7.5. псевдослучайные генераторы, в свою очередь, могут быть построены на основе определенных предположительно сложных математических задач. Существование псевдослучайных функций, основанных на таких сложных математических задачах, представляют одно из поразительных достижений современной криптографии. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|