message authentication code (MAC)
Визначення 1 код аутентифікації повідомлень
Припустимо, що кожному числу $ n \ in \ mathbb N $ (грає роль параметра стійкості) поставлені у відповідність підмножини $ K_n \ ne \ varnothing $ і $ M_n $ безлічі $ \ ^ * $, звані відповідно простором ключів і простором повідомлень при даному $ n $. Тоді кодом аутентифікації повідомлень називається полиномиально обчислюваності доступне сімейство функцій $ (f _ \, | \, n \ in \ mathbb N, \, k \ in K_n) $, де $ f_ \ colon M_n \ to \ ^ * $ для будь-яких $ n \ in \ mathbb N $ і $ k \ in K_n $.
Схема застосування коду аутентифікації повідомлень з визначення 1 може виглядати наступним чином. Нехай $ n $ - параметр стійкості. Відправник і одержувач повідомлень попередньо вибирають загальний секретний ключ $ k \ in_ K_n $. Щоб передати одержувачу повідомлення $ m \ in M_n $ із забезпеченням автентичності, відправник обчислює $ f_ (m) $ і посилає пару $ (m, f_ (m)) $ одержувачу. Одержувач, отримавши цю пару, також обчислює $ f_ (m) $ і вважає повідомлення автентичним, якщо обчислене їм значення $ f_ (m) $ збігається з отриманим. Відзначимо, що значення коду аутентифікації повідомлень може залежати не тільки від $ n $, $ k $ і $ m $, але і від деякої додаткової інформації (наприклад, порядкового номера повідомлення $ m $; см. Приклад 3 нижче).
Коди аутентифікації повідомлень призначені для тієї ж мети, що і протоколи електронного підпису. Однак між ними є важливі відмінності. По-перше, коди аутентифікації повідомлень належать до криптографії з секретним ключем, а протоколи електронного підпису - до криптографії з відкритим ключем. Зокрема, арбітраж для кодів аутентифікації повідомлень неможливий, тому вони придатні для використання тільки в тому випадку, коли відправник і одержувач повністю довіряють один одному. По-друге, в традиційному визначенні значення коду аутентифікації повідомлень обчислюється по ключу і повідомленням детерминированно, тоді як підпис, взагалі кажучи, - вероятностно. Основна перевага кодів аутентифікації повідомлень перед протоколами електронного підпису полягає в можливості досягнення більш високої ефективності.
Стійкість кодів аутентифікації повідомлень визначається, природно, проти конкретної загрози на основі конкретної атаки. Найбільш сильне умова стійкості - це стійкість проти екзистенціальної підробки на основі адаптивної атаки з вибором повідомлень. Така стійкість для коду аутентифікації повідомлень $ (f _ \, | \, n \ in \ mathbb N, \, k \ in K_n) $ означає, що для будь-якого полиномиального імовірнісного алгоритму $ \ mathcal A $ величина \ [\ Pr \ left ( \ mathcal A ^> (1 ^ n) = (m, f_ (m)), \, m \ text<отлично от запросов алгоритма>\ Mathcal A \ right), \] де $ k \ in_ K_n $, занадто мала як функція від $ n \ in \ mathbb N $.
Пропозиція 2 см. Також [1]
Нехай $ (f _ \, | \, n \ in \ mathbb N, \, k \ in K_n) $ - псевдовипадкове сімейство функцій. в якому $ f_ \ colon \ ^ \ to \ ^ $ для будь-яких $ n \ in \ mathbb N $ і $ k \ in K_n $. Припустимо, що $ s (n) = \ omega (\ log n) $ при $ n \ in \ mathbb N \ setminus \ $. Тоді дане сімейство функцій є кодом аутентифікації повідомлень, стійким проти екзистенціальної підробки на основі адаптивної атаки з вибором повідомлень.
Нехай $ t $ - довільний поліноміальний параметр. Припустимо, що значення коду аутентифікації Потрібно знати обчислювати лише для $ t (n) $ повідомлень, де $ n $ - параметр стійкості. У цьому випадку існує добре відомий код аутентифікації повідомлень, стійкий в теоретико інформаційному сенсі проти екзистенціальної підробки на основі адаптивної атаки з вибором повідомлень. число яких не повинно перевищувати $ t (n) -1 $. А саме, між іншим $ K_n = (\ ^ n) ^ $, $ M_n = \ ^ n $ і \ [f _)> (i, m) = (i, m \ oplus k_i), \] де $ k_1, \ dots, k_, m \ in \ ^ n $, а $ i \ in \ $ - порядковий номер повідомлення $ m $ ($ n \ in \ mathbb N $). Тоді $ (f _ \, | \, n \ in \ mathbb N, \, k \ in K_n) $ є кодом аутентифікації повідомлень, що задовольняє необхідному умові стійкості. Це випливає з того, що противник, навіть володіючи необмеженими обчислювальними можливостями, може здійснити для даного коду аутентифікації повідомлень зазначену загрозу на основі зазначеної атаки лише з ймовірністю не більше $ 2 ^ $.