MulBasicIdent
MulBasicIdent — базовый мультилинейный алгоритм шифрования на основе идентификационных данных.[1] Данный алгоритм является обобщением метода выработки общего ключа с помощью билинейных спариваний (BasicIdent), предложенного Дэном Боне и Мэтью К. Франклином в 2001 году.[2]
Параметры протокола
В протоколе используются следующие параметры и группы:
- — число участвующих в генерации общего ключа сторон;
- — уникальное двоичное число (идентификатор) пользователя с номером ;
- — аддитивная циклическая группа;
- — мультипликативная циклическая группа.
Группы и используются для дальнейшего построения мультилинейного отображения.
Описание алгоритма
Данный алгоритм решает задачу шифрования сообщения для абонентов с идентификаторами .[1] Протокол состоит из этапов инициализации, получения закрытого ключа, шифрования и расшифрования. Пусть — принимаемый алгоритмом на этапе инициализации параметр стойкости.
Инициализация
- На основе Центром генерации закрытых ключей (PKG) вырабатывается простой порядок групп и , -мультилинейное отображение и произвольный образующий элемент группы .
- Центром PKG случайным образом выбираются элементы и вычисляется набор открытых ключей .
- Центром PKG выбираются криптографические хеш-функции и для некоторого , где — множество двоичных векторов произвольной длины, а — множество двоичных векторов длины .
В данном алгоритме пространства сообщений и шифротекстов представляют собой множества и соответственно, элементы являются мастер-ключами абонентов, а системными параметрами является набор .
Получение закрытого ключа
Для идентификаторов абонентов :
- Центр вычисляет .
- Центр вычисляет закрытые ключи , где — мастер-ключи.
Шифрование
Для шифрования сообщения с помощью идентификаторов абонент выполняет следующие операции:
- Вычисляет .
- Выбирает случайный элемент .
- Вычисляет шифротекст , где .
Расшифрование
Для расшифрования шифротекста абонентом с идентификатором с помощью закрытого ключа вычисляется открытый текст следующим образом:
Корректность схемы
Корректность алгоритма подтверждается выполнением следующего равенства, смысл которого сводится к подстановке в аргумент функции на этапе расшифрования выражений для закрытого ключа и элемента :
Так как , то на этапе расшифрования получаем .
Криптографическая стойкость
Протокол является стойким при адаптивной атаке с выбором открытого текста и в предположении сложности мультилинейной проблемы Диффи-Хеллмана (MDH).[1]
Описание атаки на протокол
Модели безопасности широковещательного шифрования основаны на играх, проводимых злоумышленником (атакующим алгоритмом) с запросчиком (challenger).
Игра злоумышленника, проводящего атаку на алгоритм широковещательного шифрования, состоит из процедуры инициализации, 2-х этапов проведения запросов, постановки задачи и вывода результата.
Инициализация
Запросчик принимает параметр стойкости , запускает процедуру инициализации алгоритма, передает атакующему алгоритму параметры и сохраняет мастер-ключи в секрете. Определены — аддитивная циклическая группа простого порядка с образующим элементом , и — мультипликативная циклическая группа простого порядка .
Этап 1
Атакующий алгоритм генерирует запросы и отправляет их запросчику, где является:
- Запросом закрытого ключа . В данном случае запросчик запускает процедуру генерации закрытого ключа , соответствующего открытому ключу , и передает атакующему алгоритму.
- Запросом расшифрования . В данном случае запросчик запускает процедуру генерации закрытого ключа , соответствующего открытому ключу . Далее запускает процедуру расшифрования шифротекста с помощью и передает полученный открытый текст атакующему алгоритму.
Данные запросы проводятся адаптивно, то есть каждый запрос может зависеть от ответов на запросы .
После завершения этапа 1 атакующий алгоритм генерирует 2 открытых текста равной длины и набор идентификаторов абонентов , для которых он проводит атаку, где — множество открытых текстов произвольной длины. Единственным ограничением является тот факт, что при во время этапа 1.
Постановка задачи
Запросчик случайно выбирает бит и отправляет алгоритму.
Этап 2
Атакующий алгоритм генерирует и отправляет запросчику дополнительные запросы , где является:
- Запросом закрытого ключа , где для . Запросчик отвечает так же, как и во время этапа 1.
- Запросом расшифрования , где для . Запросчик отвечает так же, как и во время этапа 1.
Данные запросы могут проводиться адаптивно, как и во время этапа 1.
Результат
Атакующий алгоритм возвращает бит и выигрывает игру, если .
Выигрышем при проведении атаки злоумышленника на алгоритм называется следующая функция параметра стойкости : , где — вероятность события, состоящего в совпадении значений битов и .
Улучшение
На основе алгоритма MulBasicIdent с помощью метода Фуджисаки-Окамото построен полный алгоритм широковещательного шифрования на основе идентификационных данных MulFullIdent.
Примечания
- ↑ 1 2 3 Косолапов Д. О. Построение многосторонних мультилинейных алгоритмов в условиях различных моделей безопасности : Дисс.. канд. физ.-мат. наук. — М., 2010.
- ↑ Boneh D. and Franklin M. Identity-based encryption from the Weil Pairing, Crypto'2001 // Springer-Verlag : Lecture Notes in Computer Science. — 2001.
Литература
- Косолапов Д. О. Построение многосторонних мультилинейных алгоритмов в условиях различных моделей безопасности. — 2010.
- Косолапов Д. О., Харин Е. А., Гончаров С. М., Корнюшин П. Н. Мультилинейные криптосистемы в асимметричной криптографии (рус.) : статья в журнале - научная статья. — Томск: Томский государственный университет систем управления и радиоэлектроники, 2008. — № 2—1 (18). — С. 51—53. — ISSN 1818-0442.