Определение 13.3

Вероятность — это максимальная вероятность успешной атаки имперсонации, т.е.

. (13.2)

В примере 13.4 каждое кодовое слово является образом какого-то сообщения относительно ровно двух из четырех ключей (в каждом столбце из 4 клеток — 2 непрочерка). Поэтому .

В случае атаки подмены перехватывается кодовое слово . Это сужает множество ключей, которые могли быть использованы отправителем и получателем, до множества . Тогда наилучшая атака для противника — искать среди кодовых слов, допустимых для данных ключей, слово, которое встречается наиболее часто.

Говоря иными словами, в матрице аутентификации данного кода отыскивается столбец с перехваченным индексом и из матрицы удаляются все строки, содержащие прочерк в этом столбце (это строки, индексированные ключами, которые не могли быть использованы). Удаляется также столбец с индексом . Среди оставшихся столбцов ищется столбец с наибольшим количеством непрочерков. Индекс или . (13.3)

В примере 13.4 каждое кодовое слово является образом какого-то сообщения относительно ровно двух из четырех ключей. Для каждого из этих двух ключей различные возможные сообщения отображаются в различные кодовые слова. Поэтому .

Максимальная из двух вероятностей (13.2) и (13.3) часто называется вероятностью успешного обмана (deception). Она дается формулой

. (13.4)

Поскольку функция аутентификации инъективна для каждого , ровно кодовых слов должны быть аутентичны для любого данного ключа. Другими словами, каждая строка матрицы аутентификации кода аутентификации содержит ровно непрочерков. Из того, что имеет строк и столбцов, следует, что среднее число непрочерков на столбец из равно .

Таким образом, максимальная доля непрочерков на столбец не меньше . Это доказывает следующую теорему.