Для других алгоритмов нотация «большой О» обычно скрывает постоянные множители, делая точные элементарные операции неважной деталью. Но криптографические документы точно указывают сложности, что меня удивляет.
Вы правы удивляетесь---вообще писать "точные сложности" безнадежно из-за того что называется теорема о линейном ускорении --- мы можем определить вычислительную сложность только до произвольного мультипликативного коэффициента.
Это связано с тем, что мы всегда можем увеличить размер базового алфавита на некоторый постоянный коэффициент, чтобы позволить нам вычислять большее количество операций за единицу временного шага. Это (вроде) имеет практический компонент — вы можете увеличить размер архитектуры набора команд, чтобы выполнять больше вычислений за такт (за счет чипов, использующих больше кремния).
Итак, какую метрику стоимости используют люди? Это В самом деле зависит от приложения.
Например, известная атака на AES — это Библейская атака, который восстанавливает ключ AES по сложности $2^{126.1}$. Конечно, авторы не склонны заявлять в качестве результатов произвольные числа — как они это вычисляют?
Полная сложность подхода независимой биклики
оценивается следующим образом:
$$C_{полный} = 2^{n-2d}[C_{biclique} + C_{precomp} + C_{recomp} + C_{falsepos}],$$
куда
- $C_{прекомпьютер}$ - сложность предварительного вычисления на шаге 3. Это эквивалентно менее чем $2^d$ прогоны подшифра $г$.
- $C_{рекомендуется}$ сложность пересчета внутренней переменной $v$ $2^{2d}$ раз. Это
сильно зависит от диффузионных свойств шифра. Для AES это значение варьируется от
$2^{2d–1,5}$ к $2^{2d–4}$.
В этой парадигме бикликальная конструкция довольно дешева. Метод в разделе 3.1 позволяет
строительство биклика всего за $2^{д+1}$ вызовы субшифра $f$. Поэтому обычно полный ключ
сложность восстановления будет определяться $2^{nâ2d}C_{recomp}$. Однако он зависит от
ширина соответствующей переменной и размер биклики $д$ тоже. Мы даем более подробную информацию по делу
AES в следующих разделах. Сложность памяти при восстановлении ключа ограничена сверху
путем хранения $2^d$ полные вычисления шифра.
В частности, для AES они говорят:
В общем, нам нужен эквивалент $3.4375$ Операции SubBytes (т. е. 55 S-блоков), 2,3125
Операции MixColumns и незначительное количество операций XOR в расписании ключей. Количество
Очевидно, что вычисление SubBytes является большим слагаемым. S-блоки также являются основным источником
к практической сложности AES как в аппаратном, так и в программном обеспечении. Поэтому, если мы стремимся к
единственное число, относящееся к сложности, имеет смысл подсчитывать количество суббайтов
операции, которые нам нужны, и сравните их с таковыми в полном шифре. Последнее число
$10 + 2.5 = 12.5$ так как мы должны учитывать нелинейность ключевого расписания. Как результат,
$C_{рекомендуется}$ эквивалентно $2^{16}\раз 3,4375/12,5 = 2^{14,14}$ работает полный AES-128. Ценности $C_{биклик}$
и $C_{прекомпьютер}$ вместе не превышает $2^8$ звонки полного AES-128.
Полная вычислительная сложность составляет около
$2^{112} (2^7 + 2^7 + 2^{14.14} + 2^8) = 2^{126.18}$.
Это означает, что «примитивной операцией» biclique-атаки является количество вызовов SubBytes, где каждый нормализует вещи так, чтобы атака грубой силы заняла $2^{128}$ сложности.
Конечно, есть и другие понятия сложности.
Например
Я слышал о метрике «Площадь x время», измеряющей сложность атаки с точки зрения времени, которое требуется цепи определенного размера для ее завершения (но сейчас не могу найти ссылки),
аналогичным образом, атаки обычно измеряют как некоторое понятие вычислительной сложности, так и некоторое понятие сложности памяти/выборки,
в криптографии на основе решетки определенная метрика, известная как «Количество основных SVP», довольно популярна в анализе.
А вообще, как то совсем не очевидно, что $2^{128}$ примитивные операции означают (например), что авторы должны определять эти термины, что они обычно и делают.
