Какова временная и пространственная сложность S-блоков AES?

Время $O(1)$ Память $O(1)$ Мы можем реализовать S-блок с поиском, или как схему, или воссоздать исходный полином GF, использованный для его генерации. Во всех случаях это фиксированный размер, иначе это не был бы AES. И без н. для обсуждения время и память постоянны.

В качестве более общего примечания, нотации сложности проблематичны в криптографии, а взлом AES с помощью грубой силы технически невозможен. $O(1)$ поэтому мы часто говорим о количестве операций и говорим что-то вроде $2^{256}$ операции, часто оставляя неясным, что это за операция. Иногда это вызов криптографического примитива, который делает это ясным, и мы можем считать, но часто мы делаем что-то еще, и то, какие операции мы считаем, становится неясным.