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



Pdf көрінісі
бет195/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   191   192   193   194   195   196   197   198   ...   249
Криптография Катц

Подсказка Используйте упраждение 6.9(a–b).
(b) Покажите, как найти прообраз произвольного значения y (т.е., x1, x2 так, 
что h(x1||x2) = y) примерно в течение времени 256 .
(c) Покажите более умную атаку прообраза, которая проходит приблизитель-
но в течение времени 232 и успешна с высокой вероятностью.
Подсказка: Опирайтесь на результаты Приложения А.4.
Пусть F будет блочным шифром, для которого легко найти фиксированные 
точки для некоторого ключа: а именно, есть ключ k , для которого легко найти 
входы x , для которых Fk (x) = x. Найдите коллизию в конструкции Дэвиса-Мей-
ера при применении к F . (Рассмотрите это в свете упражнения 6.12).


265
Глава 7
*Теоретические конструкции примитивов симметричного ключа
В главе 3 мы ввели понятие псевдослучайности и определили некоторые основные 
криптографические примитивы, включая псевдослучайные генераторы, функции 
и перестановки. В главах 3 и 4 мы показали, что эти примитивы служат в качестве 
строительных блоков для криптографии с закрытым ключом. Как таковая, она имеет 
важное значение для понимания этих примитивов, с теоретической точки зрения. В 
этой главе мы формально введем понятие односторонних функций — функций, кото-
рые, неформально, легко вычислить, но трудно инвертировать, и покажем, как псев-
дослучайные генераторы, функции и перестановки могут быть сконструированы при 
единственном допущении, что односторонние функции существуют. 1 Кроме того, 
мы увидим, что односторонние функции необходимы для «нетривиальной» крипто-
графии с закрытым ключом. То есть: существование односторонних функций экви-
валентно существованию всей (нетривиальной) криптографии с закрытым ключом. 
Это одно из главных достижений современной криптографии.
Конструкции, которые мы покажем в этой главе, следует рассматривать как до-
полнения к конструкциям потоковых шифров и блочных шифров, обсуждавшихся 
в предыдущей главе. В центре внимания предыдущей главы было то, как различ-
ные криптографические примитивы реализуются в настоящее время на практике, 
целью этой главы было ввести некоторые используемые практические подходы и 
принципы проектирования. Несколько разочаровывает тот факт, что ни одна из по-
казанных нами конструкций не доказала безопасность, основанную на слабых (т.е., 
более разумных) предположениях. В отличие от этого, в настоящей главе мы до-
кажем, что возможно построить псевдослучайные перестановки, начиная с очень 
мягкого допущения, что односторонняя функция существует. Это предположение 
более приемлемо, чем, скажем, допущение, что AES является псевдослучайной пе-
рестановкой, как потому, что это качественно более слабое допущение, так и пото-
му, что у нас есть ряд вариантов теоретико-числовых функций, которые изучались 
в течение многих лет, даже до появления криптографии. (Дальнейшее обсуждение 
этого пункта см. в самом начале главы 6). Однако недостатком является то, что все 
конструкции, показанные нами здесь, гораздо менее эффективны, чем конструк-
ции главы 6 и, поэтому, фактически не используются. Остается важный вызов для 
криптографов, чтобы «преодолеть разрыв» и разработать доказуемые безопасные
___________________________________________________________
1Это не совсем верно, поскольку, мы, по большей части, собираемся опираться на односто-
ронние перестановки в этой главе. Но известно, что односторонних функций достаточно.


266
конструкции псевдослучайных генераторов, функций и перестановок, сравнимых по 
эффективности с лучшими доступными поточными шифрами и блочными шифрами.


Достарыңызбен бөлісу:
1   ...   191   192   193   194   195   196   197   198   ...   249




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

    Басты бет