ID-based encryption

ID-based encryption или identity-based encryption — асимметричная криптосистема, в которой открытый ключ вычисляется на основе некоторой уникальной информации о личности пользователя (идентификационных данных). В качестве такой информации могут выступать имя пользователя, адрес электронной почты, контактный телефон или любые другие данные.

Кроме того, употребляются и другие названия данной криптосистемы: IBE, шифрование на основе идентификации, личностное шифрование.

История

В 1984 году Ади Шамир выдвинул идею о создании криптосистемы с открытым ключом, полученным на основе идентификационных данных[1]. В своей работе Ади Шамир не дал полного описания системы, а разработал подпись, основанную на идентификационной информации и инфраструктуру открытых ключей, основанную на адресе электронной почты.

Первые практические реализации были представлены в 2001 году Клиффордом Коксом — Cocks IBE scheme^[англ.][2], а также Дэном Боне и Мэтью К. Франклином — Boneh–Franklin scheme^[англ.][3].

Описание работы IBE, предложенное Ади Шамиром

Личностное шифрование позволяет любой стороне генерировать открытый ключ из любой идентификационной информации пользователя, безопасно обмениваться сообщениями, проверять подписи без обмена ключами. Схема предполагает наличие надёжного центра генерации закрытых ключей — третья доверенная сторона, называемой Private Key Generator (PKG), целью которой является предоставление каждому новому пользователю персональной смарт-карты. Карта состоит из микропроцессора, I/O порта, ОЗУ, ПЗУ с закрытым ключом пользователя, а также программы для шифрования, расшифровывания, подписи сообщений и проверки подлинности подписей. Ранее выпущенные смарт-карты не требуют обновления при добавлении новых пользователей с систему. Схема может успешно использоваться для замкнутого круга пользователей — международная компания, крупный банк и т. п., так как штаб-квартира такой организации способна организовать и администрировать доверенный PKG для данной группы пользователей[1].

В схеме шифрования на основе идентификации взята за основу криптосистема с открытым ключом с некоторыми изменениями. Отличие IBE заключается в том, что вместо генерации случайной пары закрытых и открытых ключей и публикации соответствующего открытого ключа, пользователь выбирает в качестве открытого ключа своё имя, почту или иные общеизвестные идентификационные данные, которые могут быть однозначно ассоциированы с данным пользователем. Соответствующий закрытый ключ вычисляется с помощью PKG и выдаётся пользователю в виде смарт-карты, описанной выше[1].

Процесс установления защищённого IBE канала связи можно описать следующим образом:

Пользователь A подписывает некоторое сообщение с помощью своего закрытого ключа на персональной смарт-карте, зашифровывает результат, используя идентификационные данные получателя и отправляет сообщение получателю — пользователю B. После приёма сообщения пользователь B расшифровывает его с помощью закрытого ключа на своей персональной смарт-карте, проверяет подпись отправителя, используя его идентификационные данные.

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

Наглядно работу алгоритма можно представить в виде:

Иллюстрация 1. Личностное шифрование. Описание работы

Общая надёжность данной криптосистемы зависит от:

• Надёжность основных криптографических функций
• Надёжность хранения информации (ключи) на сервере PKG
• Тщательность проверок информации о будущих пользователях перед выдачей смарт-карт
• Меры предосторожности для предотвращения утери, кражи, дублирования или несанкционированного доступа к смарт-картам и их соблюдение пользователями[1].

Иллюстрация 2. Личностное шифрование. Различие между криптосистемами

Различия между схемами с закрытым, открытым ключом и личностным шифрованием наглядно представлены на иллюстрации 2. Во всех схемах сообщение ${\displaystyle m}$ зашифровано ключом ${\displaystyle ke}$, передано по открытому каналу как шифротекст ${\displaystyle c}$ и расшифровано ключом ${\displaystyle kd}$. Генерация ключей происходит с использованием случайного параметра ${\displaystyle k}$. В схеме с закрытым ключом ${\displaystyle ke=kd=k}$, с открытым ключом ключи шифрования ${\displaystyle ke}$ и дешифрования ${\displaystyle kd}$ генерируются с использованием случайного параметра ${\displaystyle k}$через две различные функции ${\displaystyle ke=fe(k)}$ и ${\displaystyle kd=fd(k)}$. Иной принцип лежит в схеме шифрования на основе идентификационных данных: идентификационная информация о пользователе выступает в качестве ключа шифрования ${\displaystyle ke=i}$, ключ дешифрования генерируется с использованием некоего идентификатора пользователя ${\displaystyle i}$и случайного параметра ${\displaystyle k}$ через функцию ${\displaystyle kd=f(i,k)}$[1].

Иллюстрация 3. Личностное шифрование. Различие схем подписи

Схема подписи в криптосистеме с открытым ключом отличается от таковой для личностного шифрования. Различие между данными схемами подписи можно отследить на иллюстрации 3.

Реализация, предложенная Ади Шамиром

В 1984 году Ади Шамир предложил конкретную реализацию только для схемы подписи сообщения, высказал предположение о существовании реализаций самой криптосистемы, а также призвал сообщество заняться их поиском и изучением.

Схема подписи основывается на проверке следующего условия: ${\displaystyle s^{e}=i*t^{f(t,m)}~(mod~n)}$, где ${\displaystyle m}$ — сообщение, ${\displaystyle (s,t)}$ — подпись, ${\displaystyle i}$ — идентификационные данные пользователя, ${\displaystyle n}$ — произведение двух больших простых чисел, ${\displaystyle e}$ — большое простое число, являющееся взаимно простым с ${\displaystyle \varphi (n)}$[1].

Параметры ${\displaystyle n,e}$ и функция ${\displaystyle f}$, выбираемые на стороне PKG, равны для всех пользователей. Алгоритмическое описание функции ${\displaystyle f}$ хранится у каждого пользователя в индивидуальной смарт-карте. Значения данных параметров могут быть публичными, но разложение ${\displaystyle n}$ на простые множители должно храниться только на сервере PKG. Отличать одного пользователя от другого можно только на основании его идентификатора ${\displaystyle i}$. Единственный закрытый ключ ${\displaystyle g}$, соответствующий ${\displaystyle i}$, есть не что иное, как: ${\displaystyle g^{e}=i~(mod~n)}$. Этот ключ может быть просто вычислен на сервере PKG, но никто другой не сможет вычислить ${\displaystyle e}$[1].

Каждое сообщение ${\displaystyle m}$ имеет большое количество возможных ${\displaystyle (s,t)}$ подписей и в данном случае алгоритм случайного подбора пары ${\displaystyle (s,t)}$ неэффективен. Любая попытка зафиксировать случайное значение для одной переменной из пары ${\displaystyle (s,t)}$ и решить выражение ${\displaystyle s^{e}=i*t^{f(t,m)}~(mod~n)}$ для иной незафиксированной переменной потребует разложения на множители ${\displaystyle n}$ , что является сложной вычислительной задачей на текущий момент. Однако, если значение ${\displaystyle g}$ достоверно известно, а разложение ${\displaystyle n}$ не известно, то существует простой способ генерации любого количества подписей для любого сообщения[1].

Чтобы подписать некоторое сообщение ${\displaystyle m}$, пользователь должен выбрать случайное число ${\displaystyle r}$ и вычислить: ${\displaystyle t=r^{e}~(mod~n)}$. Вышеобозначенное условие ${\displaystyle s^{e}=i*t^{f(t,m)}~(mod~n)}$ можно переписать в виде: ${\displaystyle s^{e}=g^{e}*r^{ef(t,m)}~(mod~n)}$. Так как ${\displaystyle e}$ является взаимно простым с ${\displaystyle \varphi (n)}$, то можно исключить общий множитель из экспоненты. В итоге: ${\displaystyle s=g*r^{f(t,m)}~(mod~n)}$ может быть вычислен без вычисления ${\displaystyle e}$[1].

Существующие IBE криптосистемы

В настоящее время схемы шифрования на основе идентификационных данных основаны на билинейных спариваниях (Вейля и Тейта) и эллиптических кривых. Дэн Боне и Мэтью К. Франклин^[англ.] разработали первую из этих схем в 2001 году — Boneh–Franklin scheme^[англ.][3]. Она выполняет вероятностное шифрование сообщения произвольной длины подобно схеме Эль-Гамаля[3].

Иной подход к шифрованию был предложен Клиффордом Коксом^[англ.] в 2001 году — Cocks IBE scheme^[англ.]. Данная криптосистема использует квадратичные вычеты по модулю большого числа, шифрует сообщения по одному биту за раз и увеличивает длину шифротекста по сравнению с начальным сообщением[2].

На практике используются следующие криптосистемы на основе идентификационных данных:

• Boneh–Franklin scheme^[англ.] (BF-IBE)[3]
• Sakai–Kasahara scheme^[англ.] (SK-IBE)[4]
• Boneh-Boyen scheme (BB-IBE)[5]

Исследования стойкости современных IBE систем

В 2010 году Xu An Wang и Xiaoyuan Yang провели исследование стойкости двух Hierarchical Identity-based Encryption схем, в которых подразумевается использование нескольких PKG серверов разных "уровней" для генерации ключей пользователей. Исследователи провели атаку с использованием случайно выбранного закрытого ключа первого "уровня", получив необходимый закрытый ключ для целевого ${\displaystyle ID}$ пользователя-жертвы. Полученный закрытый ключ позволит расшифровать любые зашифрованные сообщения пользователя-жертвы[6].

В 2014 году Jyh-Haw Yeh исследовал Boneh–Franklin scheme^[англ.] и заключил, что авторы данной криптосистемы дают только указание на использование криптографической хеш-функции, но не предлагают каких-либо конкретных реализаций данной хеш-функции. Jyh-Haw Yeh в своей работе разработал и предложил к использованию криптографическую хеш-функцию, удовлетворяющую следующим требованиям[7]:

• Простое "прямое" вычисление (функция однонаправленная)
• Стойкость к поиску первого прообраза
• Стойкость к поиску второго прообраза
• Стойкость к коллизиям

Кроме того, Jyh-Haw Yeh при разработке криптографической хеш-функции дополнил список требований следующим[7]:

• Стойкость к поиску соотношения между прообразами

Иными словами, данное дополнительное свойство требует сложности вычисления коэффициента ${\displaystyle c}$ для произвольных прообразов ${\displaystyle m_{1},m_{2}}$ в соотношении ${\displaystyle H(m_{1})=c*H(m_{2})}$ или в ${\displaystyle H(m_{2})=c*H(m_{1})}$, где ${\displaystyle H}$ — хеш-функция. Важно отметить, что без введения дополнительного свойства работа Jyh-Haw Yeh представляла бы собой исследование криптостойкости схемы Boneh-Franklin[7].

Преимущества

• Одним из основных преимуществ схем шифрования на основе идентификационных данных является то, что в системе с конечным числом пользователей и неизменными идентификаторами после генерации ключей в PKG, главный закрытый ключ может быть уничтожен или остановлена работа PKG (может сократить затраты на поддержку сервера). Это возможно благодаря тому, что ключи пользователей после генерации всегда действительны (система не имеет методов отмены ключей). Системы, в которых реализован метод отмены ключа, лишены этого преимущества[8][9].
• В связи с тем, что в системе IBE генерация открытых ключей производится по идентификатору, отпадает необходимость в создании инфраструктуры распространения открытых ключей. Подлинность открытого ключа гарантируется, пока отправка закрытых ключей пользователей остается безопасной[8][9].
• Для получения зашифрованного сообщения со стороны получателя не требуется подготовка[8][9].

Недостатки

• Если Private Key Generator будет скомпрометирован, то все сообщения за всё время, защищённые парой закрытый-открытый ключ, тоже будут скомпрометированы. Это делает Private Key Generator ценной мишенью для злоумышленников. Для уменьшения потерь из-за взлома PKG, пара главных ключей (главный открытый и закрытый ключи) могут быть заново сгенерированы с помощью новой пары независимых ключей. Однако в таком случае необходимо реализовать схему управления ключами, так как каждый пользователь должен иметь корректные в данный момент времени ключи[8][9].
• Согласно основным принципам шифрования на основе идентификаторов, Private Key Generator генерирует закрытые ключи пользователей, поэтому может подписывать сообщения от имени любого пользователя, а также расшифровывать сообщения без авторизации. Однако этот недостаток не должен стать проблемой для организаций, размещающих свои собственные PKG, готовых доверять системным администраторам и не требующих возможности подтверждения совершенных пользователем действий (неотрекаемость). Традиционное асимметричное шифрование с инфраструктурой открытых ключей лишено этого недостатка[8][9].
• Для безопасной отправки закрытого ключа требуется защищённый канал передачи данных между Private Key Generator и пользователем. Пользователи, имеющие учётные записи в PKG, должны иметь возможность аутентифицироваться в системе. Это может быть достигнуто, например, с помощью пары логин-пароль или пары открытых ключей на смарт-картах[8][9].
• Система IBE может основываться на криптографических методах, которые не подходят для защиты от атак квантовых компьютеров (алгоритм Шора)[8][9].

См. также

• Предикативное шифрование
• Attribute-based Encryption

Примечания

1. Shamir A. Identity based cryptosystems and signature schemes // Advances in Cryptology. // Proceedings of CRYPTO 84. — 1985. — С. 47—53. Архивировано 8 августа 2017 года.
2. Clifford Cocks. An Identity Based Encryption Scheme Based on Quadratic Residues  (неопр.). Proceedings of the 8th IMA International Conference on Cryptography and Coding (2001). Дата обращения: 12 декабря 2017. Архивировано 22 сентября 2017 года.
3. Dan Boneh, Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing // Springer Berlin Heidelberg. — 2001.
4. Sakai, Ryuichi; Kasahara, Masao. ID Based cryptosystems with pairing on elliptic curve (англ.) // Cryptography ePrint Archive : journal. — 2003. — Vol. 2003/054. Архивировано 19 января 2022 года.
5. Boneh, Dan; Boyen, X. Efficient selective-ID secure identity based encryption without random oracles (англ.) // LNCS : journal. — Springer-Verlag, 2004. — Vol. Advances in Cryptography — EUROCRYPT 2004. — P. 223—238. — doi:10.1007/978-3-540-24676-3_14.
6. Jian WENG, Min-Rong CHEN, Kefei CHEN, Robert H. DENG. Cryptanalysis of a Hierarchical Identity-Based Encryption Scheme (англ.) // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 2010-04-01. — Vol. E93.A, iss. 4. — ISSN 1745-1337 0916-8508, 1745-1337. — doi:10.1587/transfun.E93.A.854. Архивировано 29 марта 2018 года.
7. Jyh-Haw Yeh. Security Vulnerability in Identity-Based Public Key Cryptosystems from Pairings // International Journal of Information and Education Technology. — С. 466—470. — doi:10.7763/ijiet.2013.v3.319. Архивировано 2 июня 2018 года.
8. Carl Youngblood. An Introduction to Identity-based Cryptography // CSEP 590TU. Архивировано 29 августа 2017 года.
9. Mao, Wenbo. Modern cryptography : theory and practice. — Upper Saddle River, NJ: Prentice Hall PTR, 2004. — xxxviii, 707 pages с. — ISBN 0130669431.