Список обозначений

Код аутентификации сообщений

message authentication code (MAC)
Определение 1 код аутентификации сообщений
Предположим, что каждому числу $n\in\mathbb N$ (играющему роль параметра стойкости) поставлены в соответствие подмножества $K_n\ne\varnothing$ и $M_n$ множества $\{0,1\}^*$, называемые соответственно пространством ключей и пространством сообщений при данном $n$. Тогда кодом аутентификации сообщений называется полиномиально вычислимое доступное семейство функций $(f_{n,k}\,|\, n\in\mathbb N,\, k\in K_n)$, где $f_{n,k}\colon M_n\to\{0,1\}^*$ для любых $n\in\mathbb N$ и $k\in K_n$.

Схема применения кода аутентификации сообщений из определения 1 может выглядеть следующим образом. Пусть $n$ — параметр стойкости. Отправитель и получатель сообщений предварительно выбирают общий секретный ключ $k\in_{\mathfrak U} K_n$. Чтобы передать получателю сообщение $m\in M_n$ с обеспечением аутентичности, отправитель вычисляет $f_{n,k}(m)$ и посылает пару $(m,f_{n,k}(m))$ получателю. Получатель, получив эту пару, также вычисляет $f_{n,k}(m)$ и считает сообщение аутентичным, если вычисленное им значение $f_{n,k}(m)$ совпадает с полученным. Отметим, что значение кода аутентификации сообщений может зависеть не только от $n$, $k$ и $m$, но и от некоторой дополнительной информации (например, порядкового номера сообщения $m$; см. пример 3 ниже).

Коды аутентификации сообщений предназначены для той же цели, что и протоколы электронной подписи. Однако между ними имеются важные различия. Во первых, коды аутентификации сообщений принадлежат к криптографии с секретным ключом, а протоколы электронной подписи — к криптографии с открытым ключом. В частности, арбитраж для кодов аутентификации сообщений невозможен, поэтому они пригодны для использования только в том случае, когда отправитель и получатель полностью доверяют друг другу. Во-вторых, в традиционном определении значение кода аутентификации сообщений вычисляется по ключу и сообщению детерминированно, тогда как подпись, вообще говоря, — вероятностно. Основное преимущество кодов аутентификации сообщений перед протоколами электронной подписи состоит в возможности достижения более высокой эффективности.

Стойкость кодов аутентификации сообщений определяется, естественно, против конкретной угрозы на основе конкретной атаки. Наиболее сильное условие стойкости — это стойкость против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений. Такая стойкость для кода аутентификации сообщений $(f_{n,k}\,|\, n\in\mathbb N,\, k\in K_n)$ означает, что для любого полиномиального вероятностного алгоритма $\mathcal A$ величина \[ \Pr\left(\mathcal A^{f_{n,k}}(1^n)=(m,f_{n,k}(m)),\, m\text{ отлично от запросов алгоритма }\mathcal A\right), \] где $k\in_{\mathfrak U} K_n$, пренебрежимо мала как функция от $n\in\mathbb N$.

Предложение 2 см. также [1]
Пусть $(f_{n,k}\,|\, n\in\mathbb N,\, k\in K_n)$ — псевдослучайное семейство функций, в котором $f_{n,k}\colon\{0,1\}^{r(n)}\to\{0,1\}^{s(n)}$ для любых $n\in\mathbb N$ и $k\in K_n$. Предположим, что $s(n)=\omega(\log n)$ при $n\in\mathbb N\setminus\{0\}$. Тогда данное семейство функций является кодом аутентификации сообщений, стойким против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений.
Пример 3
Пусть $t$ — произвольный полиномиальный параметр. Предположим, что значения кода аутентификации сообщений требуется вычислять лишь для $t(n)$ сообщений, где $n$ — параметр стойкости. В этом случае существует хорошо известный код аутентификации сообщений, стойкий в теоретико информационном смысле против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений, число которых не должно превышать $t(n)-1$. А именно, положим $K_n=(\{0,1\}^n)^{t(n)}$, $M_n=\{0,1\}^n$ и \[ f_{n,(k_1,\dots,k_{t(n)})}(i,m)=(i,m\oplus k_i), \] где $k_1,\dots,k_{t(n)},m\in\{0,1\}^n$, а $i\in\{1,\dots,t(n)\}$ — порядковый номер сообщения $m$ ($n\in\mathbb N$). Тогда $(f_{n,k}\,|\, n\in\mathbb N,\, k\in K_n)$ является кодом аутентификации сообщений, удовлетворяющим требуемому условию стойкости. Это следует из того, что противник, даже обладая неограниченными вычислительными возможностями, может осуществить для данного кода аутентификации сообщений указанную угрозу на основе указанной атаки лишь с вероятностью не более $2^{-n}$.

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна