Схемы электронной подписи, основанные на идентификаторах

From CryptoWiki
Jump to: navigation, search

Contents

Описание технологии

А. Шамир впервые ввел понятие криптографии на основе идентификационных данных, которая из-за наличия системы управления цифровыми сертификатами во многом могла бы уменьшить сложность, присущую традиционным асимметричным криптосистемам c инфраструктурой открытых ключей. Лишь в 2001 г. удалось реализовать идею А. Шамира. Использование технологии IBE (Identity Based Encryption) стало возможным благодаря билинейным отображениям [6], [7]. В криптографии билинейные отображения впервые были использованы для проведения атак с целью сведения задачи дискретного логарифмирования на эллиптических кривых к аналогичной, более простой задаче, в конечном поле. В последнее время билинейные отображения нашли практическое применение в криптографии, являясь основой построения большинства криптосистем на основе идентификационных данных[1].

Криптосистемы на основе идентификационных данных (IBE) – ассиметричная криптосистема, в которой открытый ключ пользователя вычисляется известным способом на основе идентификационных данных пользователя [1]. В качестве идентификационной информации может использоваться имя пользователя, адрес электронной почты, номер мобильного телефона и др.

В криптографии на основе идентификационных данных закрытый ключ генерируется и выпускается доверенным источником. Этот закрытый ключ соответствует открытому ключу пользователя, который подтверждает подлинность пользователя, не требуя при этом наличия его сертификата. IBE-криптосистемы вполне могут заменить криптосистемы, использующие PKI. Стойкость таких систем базируется на предположениях о сложности решения различных проблем Диффи – Хеллмана. Однако, несмотря на очевидные преимущества идентификационной криптографии, имеются также и некоторые нерешенные задачи. Математический аппарат таких криптосистем непрерывно совершенствуется и основан на билинейном отображении, которое с прикладной точки зрения представляет трудности из-за высокой трудоемкости вычисления.

Сравнение IBE и PKI

Критерий IBE PKI
Криптографическая система Асимметричная криптография Асимметричная криптография
Технология генерации ключей Ключевая пара в ID – PKC генерируется непосредственно из данных, которые имеют отношение к идентификатору. Например, ключи для шифрования дешифрования могут быть получены из идентификационной информации системы, в которой они используются. Ключевая пара генерируется с помощью случайной информации, не связанной с методом идентификации этой ключевой пары, со стороны системы. Таким образом, существуют требования к сертификатам, для привязки открытых ключей к их применению.
Расположение закрытого ключа на сервере да нет
Возможность отмены и сброса ключа подписи нет да
Возможность отмены и сброса ключа расшифрования нет да
Необходимость распределения сертификатов нет да
Требуется хранилище сертификатов открытых ключей нет да
Необходимость использования безопасного канала для распределения ключей да нет

Преимущества и недостатки IBE

Главным преимуществом перед классическими ассиметричными криптосистемами является упрощение инфраструктуры открытых ключей (PKI).

Основные недостатки технологии IBE:

  • PKG знает секретный ключ пользователей;
  • Необходимость аутентификации пользователя в PKG;
  • Обеспечение PKG безусловным доверием и защищенным каналом связи.

Однако, существуют способы преодоления недостатка – возможности со стороны PKG контролировать секретные ключи пользователей. Один из способов преодоления является использование пороговых схем.

IBE шифрование

Пример IBE шифрования

Пусть Алиса отправляет сообщение на адрес (e-mail) Боба, она зашифровывает текст открытым ключом, полученным из строки (e-mail). При этом Алисе не нужно получать и верифицировать сертификат открытого ключа Боба.

Когда Боб получает зашифрованное сообщение, он обращается к Центру Генерации Секретных ключей (Private Key Generator, PKG), проходит процедуру аутентификации, получает свой секретный ключ и затем расшифровывает сообщение. Заметим, что Алиса может отправлять зашифрованное сообщение при отсутствии сертификата открытого ключа Боба.

IBE подпись

Пример IBE подписи

Пусть Алиса отправляет подписанное сообщение на адрес (e-mail) Бобу, она обращается к Центру Генерации Секретных ключей (Private Key Generator, PKG), проходит процедуру аутентификации, получает свой секретный ключ и затем подписывает сообщение.

Когда Боб получает подписанное сообщение, он получает открытый ключ из строки e-mail (идентификатора Алисы) и проверят подпись.

Вернуться к оглавлению

Математические основы

Определение

Пусть (G1,+) – циклическая аддитивная группа порядка p и (G2,*) – мультипликативная группа порядка p, где p — большое простое число.

Билинейным отображением (спариванием) называется отображение:

e: G1xG1 → G2,

которое обладает следующими свойствами:

Аддитивность:

Image003.png

Image0004.png

Невырожденность:

Image005.png

Отметим следствие из определения: e(R,S) = e(aP,bP) = e(P,P)^ab = e(S,R) (билинейность).

Вейль-спаривание

Для заданного положительного целого m Вейль – спаривание e(m) – билинейное отображение, которое сопоставляет двум точкам m – подгруппы группы точек эллиптической кривой корень m-й степени в конечном поле.

e: Image059.png

Конкретизируя:

e: Image061.png

где Image063.png – группа корней m-й степени из единицы.

Определим Вейль-спаривание для двух точек P,Q Image065.png. Пусть Ap – некоторый делитель. Легко понять, что nAp – дивизор. Следственно, существует функция fp, такая, что (fp) =nAp. Определим Aq и fq аналогично. Тогда Вейль-спаривание определяется как:

Image067.png

Тейт-спаривание

Пусть q = p^m, p – простое, p>3, m –целое, m>0. Fq – конечное поле из q элементов, p – характеристика Fq и m – степень его расширения.

Пусть L – порядок точки P Image069.png E(Fq), L – простое.

Тейт – спаривание представляет собой отображение:

Image090.png

Определенное как:

Image092.png.

Вычисление спариваний

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

Спаривание Вейля связано со спариванием Тейта следующим соотношением:

Image094.png, где e_w (P,Q) – спаривание Вейля, e_t (P,Q) – спаривание Тейта.

Другие методы вычисления Вейль спаривания менее эффективны.

За основу вычисления спаривания взят алгоритм Миллера, который для любых P,Q ∈ G1 вычисляет e(P,Q) за полиномиальное время.

Вычислительные проблемы

Проблема дискретного логарифмирования (DLP)

Пусть G = (G, *) — конечная мультипликативная группа, a и α — элементы группы G, n есть порядок элемента α. Натуральное число x называется дискретным логарифмом элемента a при основании α, если

Image002.png

Проблема дискретного логарифмирования заключается в том, что необходимо найти дискретный логарифм x данного элемента a = α^­x при основании α. Все известные алгоритмы для решения этих проблем для мультипликативной группы конечного поля или группы точек эллиптической кривой субэкспоненциальные, т.е. число выполняемых или операций оценивается как Image003 .png, где C > 0 — некоторая константа, а n — порядок группы. Сложность дискретного логарифмирования слишком велика для современной (и ожидаемой в ближайшем будущем) вычислительной техники. На этом факте основана значительная часть криптографии с открытым ключом.

Пусть G1 — аддитивная группа порядка n, P — произвольный образующий группы. Для операции возведения в степень n в этой группе используем далее обозначение Image0006 .png скалярного произведения элемента группы на натуральное число.

Билинейная проблема Диффи–Хеллмана (BDHP)

Билинейная проблема Диффи–Хеллмана (BDHP): по данным P, aP, bP, cP ∈ G1, где a, b, c — натуральные числа, вычислить Image008 .png.

Труднорешаемость BDHP влечет за собой труднорешаемость обычной проблемы Диффи–Хеллмана (DHP) и проблемы дискретного логарифмирования (DLP) обеих группах Gi легкорешаема. Но справедливость обратного не доказана.

Проблема решения Диффи-Хеллмана (DDH)

Проблема Решения Диффи-Хеллмана (DDH) — заключается в различении двух наборов (P, aP, bP, abP) и (P, aP, bP, cP), где Image028.png выбираются случайно.

Теорема. Если существует спаривание на (G1,G2), то DDH проста в (G1,+). Доказательство. ab ≡ с ↔ e(aP,bP) = e(P,cP). Теорема доказана.

Вычислительная проблема Диффи-Хеллмана (CDH)

Вычислительная проблема Диффи-Хеллмана (CDH) — заключается в вычислении abP, если даны (P, aP, bP), где Image030.png. Доказано, что при определенных условиях возможность решения CDH подразумевает возможность эффективного решения задачи дискретного логарифмирования.

Промежуточная группа Диффи-Хеллмана (GDH)

Промежуточной группой Диффи-Хеллмана (GDH) — называется группа G1 простого порядка, если существует эффективный полиномиальный алгоритм, который решает DDH в G1, и не существует полиномиального алгоритма, который решает CDH.

Криптографические протоколы, основанные на данной технологии

BLS схема короткой подписи

Боне, Линн, Шахем, 2001

Короткие подписи используются в системах с ограничениями по пропускной способности. Если пользователю приходится вводить с клавиатуры цифровую подпись, желательно, чтобы подпись была минимально короткой. Две наиболее часто используемых схемы подписи — RSA и DSA. В RSA длина подписи 1024 бита, а в стандарте DSA или ECDSA (DSA c эллиптическими кривыми) – 320 бит. Эти подписи слишком длинные, чтобы вводить их с клавиатуры. В BLS схеме, при длине подписи приблизительно 160 бит, достигается примерно такой же уровень защиты, как и в DSA схеме.

IBE 1.PNG

Сложность схемы: KeyGen — 1 скалярное умножение, Sign — 1 вычисление хеш-функции, 1 скалярное умножение, Verify – 1 вычисление хеш-функции, 2 вычисления спаривания.

Предположение схемы: существование GDH групп.

Схема слепой подписи

Болдырева, 2003

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

IBE 2.PNG

Сложность схемы: KeyGen — 1 скалярное умножение в G1, Blind Signature Issuing Protocol — 1 вычисление хеш-функции, 3 скалярных умножения в G1 , Verify — 1 вычисление хеш-функции, 2 вычисления спариваний.

Предположение схемы: CDH проблема трудна.


Пороговая схема подписи

Болдырева, 2003

Идея (t, n) пороговых схем — распределение секретной информации (секретного ключа) и вычислений (генерации подписи или шифрования) между n участниками. Основное назначение этих схем – защита ключа от потери. Пороговые схемы также обеспечивают разделение ответственности за принятие решения, которое автоматически вводится при определении состава полномочных групп. Даже если противник подкупит не более чем t пользователей, ему все равно не удастся восстановить секрет. Секретная информация распределяется между n участниками при помощи доверенной стороны или при выполнении специального диалогового протокола между всеми участниками.

IBE 3.PNG

Предположение схемы: существование GDH групп.

Глоссарий (Glossary)

Библиографический указатель (Bibliography)

Перейти к списку литературы или по разделу "Схемы электронной подписи, основанные на идентификаторах".

Вернуться к оглавлению

Мигалин Антон, 2015