Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Блочные шифры.
Вспомним из Раздела 3.5.1, что блочный шифр является эффективной ключе- вой перестановкой F : {0, 1}n × {0, 1}A → {0, 1}A. Это означает, что функция Fk, определенная F (x) F (k, x), является биекцией (то есть перестановкой), и, более того, F и ее обратная величина F −1 являются эффективно вычисля- емыми, если имеется k. Мы будем называть n - длиной ключа и A - длиной блока F, и здесь мы явно позволим им отличаться. Длина ключа и длина блока теперь фиксированные константы, тогда как в Главе 3 они рассматривались как функции параметра защиты. Это ставит нас в условие конкретной защиты, а не асимптотической. 2 Требования конкретной защиты для блочных шиф- ров довольно жесткие, и блочный шифр, в общем, считается всего лишь «хо- рошим», если наиболее известная атака (с предварительной обработкой) имеет временные трудности, сравнимые с атакой с использованием «грубой силы» для поиска ключа. Таким образом, если шифр с длиной ключа n = 256 может быть взломан за время 2128, шифр (в общем) считается незащищенным, даже если атака продолжительностью 2128 все еще невозможна. В то же время, в асимптотических условиях атака сложностью 2n/2 не считается эффективной, пока для нее требуется экспоненциальное временя (следовательно, шифр, для которого такая атака возможна, все еще может удовлетворять определение псев- дослучайно перестановки). В конкретных условиях, однако, мы должны пред- упредить о реальной сложности атаки (а не о ее асиптотическом поведении). Более того, есть проблема, что существование такой атаки может указывать на более фундаментальную слабость в конструкции шифра. Блочные шифры разработаны, чтобы вести себя, по крайней мере как (силь- ные) псевдослучайные перестановки; см. Определение 3.28. Моделирование блочных шифров в виде псевдослучайных перестановок позволяет добиться доказательств защиты для конструкций, на основе блочных шифров, а также открывают необходимые требования блочных шифров. Четкое понимание того, какую цель блочные шифры должны выполнять, играет важную роль в их раз ___________________________________________________________ 2Хотя блочный шифр с ключом фиксированной длины не имеет «параметра защиты», мы все еще рассматриываем защиту как такую, что зависит от длины ключа, и, таким образом, вы- ражаем это значение как n. 222 работке. Точка зрения о том, что блочные шифры должны моделироваться как псевдослучайные перестановки, служила, по крайней мере в недалеком про- шлом, основой их разработки. В качестве примера, на конкурсе проектов ка- сательно нового стандарта Advanced Encryption Standard (AES), с которым мы столкнемся позже в этой главе, прозвучали следующие критерии оценки: Защита, обеспеченная алгоритмом, является наиболее важным фак- тором.... Алгоритмы будут оцениваться по следующим факторам... • Степень, в которой алгоритм неотличим от случайной пере- становки... Современные блочные шифры подходят для всех конструкций, включая псев- дослучайные перестановки (или псевдослучайные шифры), которые мы виде- ли в данной книге. Часто блочные шифры разрабатываются (и предполагаются) для удовлетво- рения даже более сильных защитных свойств, как мы и писали в Разделе 6.3.1. Несмотря на тот факт, что блочные шифры сами по себе не являются схемами шифрования, стандартная терминология для атак на блочный шифр F такова: • При атаках на основе открытого текста, атакующий получает пары входных /выходных данных {(xi, Fk (xi))} (для неизвестного ключа k), с {xi} за пределами контроля атакующего. • При атаках на основе подобранного открытого текста, атакующий получает {Fk (xi)} (снова же, для неизвестного ключа k) для серии входных данных {xi}, подобранных атакующим. • При атаках на основе подобранного шифротекста, атакующий получает {Fk(xi)} для {xi}, подобранного атакующим, равно как и {F −1(yi)} для подобранного {yi}. Рассмотрение длины ключа в качестве параметра имеет смысл, при сравнении блочных шиф- ров с разной длиной ключей или при использовании блочного шифра, который поддерживает ключи разной длины. Кроме использование вышеописанного для отличия Fk от универсальной пере- становки, мы также будем заинтересованы в атаках с восстановлением ключа , при которых атакующий имеет возможность извлечь ключ k после взаимодействия с Fk . (Это сложнее, чем иметь возможность отличить Fk от универсальной.) Согласно таксономии, псевдослучайная перестановка не может быть отли- чима от универсальной перестановки во время атаки на основе подобранного открытого текста, так как сильная псевдослучайная перестановка не может вы- деляться даже при атаке на основе подобранного шифротекста. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|