Интернет магазин китайских планшетных компьютеров

Компьютеры - CBC-MAC - Безопасность семейства OMAC

Определение защищённости

Пусть Perm означает набор всех перестановок из {0,1}, так же пусть P является случайной перестановкой, если Р — случайная выборка из Perm. Безопасность блочного шифра E может быть количественно определена как , максимальное преимущество, которое противник A может получить, когда пытается выделить из случайной перестановки P, когда допускается вычисление времени t и q запросов" src="/c/img/10104.png" /> либо ). Это преимущество определяется следующим образом.

Скажем, что блочный шифр E — защищён, если существенно мало. Аналогично, MAC-алгоритм — F : K_F × {0,1} → {0,1}, где K_F — набор ключей, тогда запишем для F. Скажем, что противник взламывает, если A выдаёт ), где A никогда не запрашивает M из . Тогда мы определяем преимущество как

где максимум берётся по всем противникам, кто «работает» не мобее времени t, производит не более q запросов, и кадлый запрос не более μ бит. Будем говорить, MAC алгоритм защищён, если величина пренебрежимо мала. Обозначим Rand набор всех функций из {0, 1}* в {0,1}. Этот набор даётся вероятностной мерой в предположении, что случайный элемент R набора Rand связан или ассоциирован с каждой строкой M ∈ {0, 1}* случайной строки R∈{0,1}. Далее, мы определим преймущество как

где максимум берётся по всем противникам, кто «работает» время не больше t, делает не более q запросов, и каждый запрос не более μ бит. Тогда можно сказать, что MAC алгоритм псевдослучайный, если величина пренебрежимо мала. Без ограничения общности, как предполагается, противники никогда не делают запросы вне области {0,1}, а так же никогда не повторяют запросы.

Далее приведём основные теоремы.

Lemma 5.1. Предположим, что H, Cst1 и Cst2 удовлетворяют условиям Sec. 3 для некоторых пренебрежимо малых ε₁,...,ε₆, а так же пусть Cst — произвольная n-битная константа. Так же предположим, что случайная перестановка P ∈ Perm используется в семействе OMAC как базовый блочный шифр. Пусть A — противник, который делает не более q запросов, и каждый запрос не более nm бит. Положим m ≤ 2n/4. Тогда

где ε = maxε₁,...,ε₆. Следующие результаты присущи как OMAC1 так и OMAC2. Сначала, мы получили следующую лемму заменой є = 2−n в Lemma 5.1.

Lemma 5.2. Предположим, что случайная перестановка P ∈ Perm используется в OMAC как базовый блочный шифр . Пусть A будет противником, который делает не более q запросов, и каждый запрос не более nm бит. Положим m ≤ 2n/4. Тогда

Далее покажем, что OMAC является псевдослучайным, если базовый блочный шифр Е защищён.

Замечание 5.1. Пусть E : K_E × {0,1} → {0,1} является базовым блочным шифром, который используется в OMAC. Тогда , где t’ = t + O and q’ = mq + 1.
В конце покажем, что OMAC защищён как aMAC алгоритм из Замечание 5.1 в обычном смысле. Theorem 5.1. Пусть E : KE × {0,1} → {0,1} является базовым блочным шифром, используемый в OMAC. Тогда
,
где t’ = t + O and q’ = mq + 1.