124
Синтаксис кода аутентификации сообщений
Прежде чем дать формальное определение устойчивости кода аутентифика-
ции сообщений, определим сначала, что такое КАС и как он используется. Два
пользователя, желающие общаться аутентифицированным образом, начинают
с того, что делятся секретным ключом k перед коммуникацией. Когда один из
участников хочет послать сообщение m другому, он вычисляет тэг КАС (или
просто тэг) t на основе сообщения и общего ключа, и посылает сообщение m и
тэг t другому участнику. Тэг вычисляется с помощью алгоритма генерации тэга,
обозначенного Mac. Таким образом, иными словами, отправитель сообщения
m вычисляет t ← Mack (m) и передает (m, t) получателю. По получении (m, t),
второй участник проверяет, является ли t действующим тэгом для сообщения
m (в отношении общего ключа) или нет. Это делается путем запуска алгоритма
верификации Vrfy , который принимает на входе общий ключ, а также сообще-
ние m и тэг t, и
указывает, является ли данный тэг действующим. Формально:
ОПРЕДЕЛЕНИЕ 4.1 Код аутентификации сообщения (или КАС)
состоит
из трех вероятностных алгоритма, работающих за полиномиальное время
(Gen, Mac, Vrfy) ,
таких как :
4.2.2 Алгоритм генерации ключа Gen
принимает на входе параметр безопас-
ности 1n и выдает ключ k , при |k| ≥ n.
4.2.3 Алгоритм генерации тэга Mac
принимает на входе ключ k и сообщение
m ∈
{0, 1}*, и выдает тэг t. Так как этот алгоритм может быть рандомизи-
рован, мы запишем это как t ← Mack (m).
4.2.4 Детерминистский алгоритм верификации Vrfy
принимает на входе ключ
k , сообщение m, и тэг t. Он выдает бит b, при этом b = 1 означает действите-
лен, b = 0 означает недействителен. Запишем это как b := Vrfyk (m, t).
Необходимо, чтобы для каждого n каждый ключ k, выведенный алгоритмом
Gen(1n) и каждого m ∈
{0, 1}*, было бы верным утверждение Vrfyk (m, Mack (m)) = 1.
Есди существует функция A , такая что для каждого k , полученного Gen(1n),
алгоритм Mack определен только для сообщений m ∈
{0, 1}A(n), то мы назо-
вем схему КАС с фиксированной длиной для сообщений длиной A(n).
Как и при шифровании с закрытым ключом, Gen(1n) почти всегда просто
выбирает единообразный ключ k ∈ {0, 1}n, и в таком случае мы опускаем Gen .
Достарыңызбен бөлісу: