Гарантии твердости для AES

Многие криптосистемы с открытым ключом имеют доказуемую безопасность. Например, криптосистема Рабина доказуемо так же сложна, как и факторинг.

Интересно, существует ли такая доказуемая безопасность для криптосистем с секретным ключом, таких как AES. Если нет, то каковы доказательства того, что взломать такие криптосистемы сложно? (кроме устойчивости к методам проб и ошибок)

Примечание: я знаком с операциями AES (AddRoundKey, SubBytes, ShiftRows и MixColumns). Кажется, что жесткость AES проистекает из операции MixColumns, которая, в свою очередь, должна унаследовать свою трудность от некоторой сложной проблемы над полями Галуа (и, таким образом, алгеброй). Фактически, я могу перефразировать мой вопрос следующим образом: «Какая сложная алгебраическая задача гарантирует безопасность AES?»

MIXCOLUMNS предотвращает атаки, которые направлены только на несколько S-блоков, поскольку для смешивания столбцов требуется, чтобы все S-блоки участвовали в шифровании. (Дизайнеры Rijndael назвали это «стратегией широкого следа».) Анализ причин S-блока труден из-за использования операции инверсии конечного поля. Инверсия «сглаживает» таблицы распределения записей S-блоков, поэтому записи кажутся (почти) однородными, то есть неотличимыми от случайного распределения без ключа. Именно комбинация этих двух функций делает Rijndael надежно защищенным от известных атак.

Кроме того, книга The Design of Rijndael очень хорошо читается и обсуждает теорию и философию криптографии.

Как сказал Дэвид, у нас нет таких сокращений для AES. Однако это не означает, что криптосистема Рабина или RSA более безопасна, чем AES. На самом деле, я бы доверял (по крайней мере, односторонней, возможно, также псевдо-случайной) безопасности блочных шифров, таких как AES / DES и т. Д. (Возможно, с немного большим количеством раундов, чем обычно используется), чем предположению, что факторинг это трудно, именно потому, что нет алгебраической структуры, и поэтому сложнее представить, что будет какой-то прорывной алгоритм.

Можно создать блочные шифры непосредственно из односторонних функций, что является минимальным допущением для большей части криптографии, но полученная конструкция будет ужасно неэффективна и, следовательно, не будет использоваться.

Поскольку можно универсально преобразовать любую схему шифрования с открытым ключом в схему с секретным ключом, можно получить схемы с секретным ключом с аналогичными доказуемыми гарантиями безопасности.

Но этот ответ педантичен: для типичного развернутого блочного шифра у нас нет доказуемого анализа безопасности в смысле проблемы «сокращение до вычисления». Были предложения для блочных шифров с уменьшением безопасности, но вычислительный багаж, необходимый для облегчения сокращения, делает их неконкурентоспособными с более эффективными схемами, такими как алгоритмы AES.

Интересно, что доказуемое сообщество безопасности в целом согласилось с тем, что разумно принять безопасность блочного шифра (псевдослучайную перестановку) в качестве предположения, а затем сократить ее при анализе протоколов более высокого уровня, которые используют блочный шифр в качестве компонента. То есть, в отличие от некоторых других проблем в разработке защищенных протоколов, кажется, что достаточно доверять интуиции криптоаналитиков для обеспечения безопасности, когда речь идет о блочных шифрах.