Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Глава 7 *Теоретические конструкции примитивов симметричного ключа
| Подсказка: Используйте упраждение 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 конструкции псевдослучайных генераторов, функций и перестановок, сравнимых по эффективности с лучшими доступными поточными шифрами и блочными шифрами. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|