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