Введение в современную криптографию



Pdf көрінісі
бет68/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   64   65   66   67   68   69   70   71   ...   249
Криптография Катц

Блочные шифры. На практике, блочные шифры создаются как защищенные эк-
земпляры (сильных) псевдослучайных перестановок с некоторой фиксированной 
длиной ключа и длиной брока. Мы обсудим различные подходы к созданию блоч-
ных шифров, а также некоторые популярные варианты блочных шифров в Главе 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. псевдослучайные генераторы, в свою 
очередь, могут быть построены на основе определенных предположительно 
сложных математических задач. Существование псевдослучайных функций
основанных на таких сложных математических задачах, представляют одно из 
поразительных достижений современной криптографии.


Достарыңызбен бөлісу:
1   ...   64   65   66   67   68   69   70   71   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет