Схема Сакаи — Касахары

Схема Сакаи — Касахары (SAKKE) — личностная криптографическая система, предложенная Раучи Сакаи и Масао Касахара в 2003 году. Вместе со схемой Боне — Франклина, данный алгоритм является одной из немногих личностных схем, применяемых в индустрии. Является криптографическим приложением спаривания на эллиптических кривых и конечных полях. Доказательство безопасности схемы было изложено в 2005 году Ченом и Ченгом. Схема описана в Инженерном совете Интернета (RFC) RFC 6508.

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

Описание схемы

Схема Сакаи — Касахара позволяет зашифровать сообщение $\mathbb {M}$ для получателя с конкретным идентификатором $\textstyle I_{U}$. Таким образом, только пользователь с закрытым ключом $\textstyle K_{U}$, соответствующим $\textstyle I_{U}$, сможет расшифровать переданное сообщение.

Для реализации схемы необходимо, чтобы отправитель и получатель доверяли одному и тому же генератору закрытых ключей (ГЗК), который так же может называться системой управления ключами (KMS). Целью ГЗК является генерация приватного ключа $\textstyle K_{U}$, соответствующего публичному идентификатору $\textstyle I_{U}$. ГЗК должен сохранно и безопасно доставить закрытый ключ получателю, а также свой (зависящий от ГЗК) открытый параметр $\textstyle Z$ всем участникам схемы. Данные действия не рассматриваются в определении самой схемы.

Предварительные замечания

Схема использует две мультипликативные группы $\textstyle E$ и $\textstyle G$. Предполагается, что:

• Задача Диффи — Хелмана, также известная как задача дискретного логарифмирования, тяжело решаема в $\textstyle E$. Это означает, что при данных элементах группы $\textstyle P$ и $\textstyle Q$, вычислительно тяжело найти такой $\textstyle x$, что $\textstyle Q=xP$.
• Задача дискретного логарифмирования, тяжело решаема в $\textstyle G$. Это означает, что для двух элементов группы $g$ и $t$, вычислительно сложно найти такой $\textstyle x$, что $\textstyle g^{x}=t$.
• Существует билинейное отображение — спаривание Тейта — Лихтенбаума $\textstyle e(,)$ из $\textstyle E$ в $\textstyle G$. Это означает, что для члена $\textstyle P$ группы $\textstyle E$ и для $\textstyle g=e(P,P)$ из группы $\textstyle G$ выполняется:

$\textstyle e(P,xP)=e(xP,P)=e(P,P)^{x}=g^{x}$

Зачастую $\textstyle E$ является суперсингулярной эллиптической кривой, как, например, $\textstyle E:y^{2}=x^{3}-3x$ (над конечным полем простого порядка $\textstyle p$). Генератор $\textstyle P$ простого порядка $\textstyle q$ выбирается из $\textstyle E$. Группа $\textstyle G$ является образом группы, сгенерированной $\textstyle P$, с помощью спаривания (над расширением второй степени конечного поля с простым порядком $\textstyle p$).

Также необходимо наличие двух хэш-функций: $\textstyle H_{1}$ и $\textstyle H_{2}$, таких, что:

• $\textstyle H_{1}$ возвращает положительное целое число $\textstyle x$, удовлетворяющее $\textstyle 1<x<q$.
• $\textstyle H_{2}$ возвращает $\textstyle n$ битов, где $\textstyle n$ является длиной сообщения $\mathbb {M}$.

Генерация ключей

На вход ГЗК подаётся главный ключ $\textstyle z$, удовлетворяющий $\textstyle 1<z<q$, а также открытый ключ $\textstyle Z=zP$, являющимся элементом группы $\textstyle E$. Алгоритм вычисляет закрытый ключ $\textstyle K_{U}$, соответствующий $\textstyle ID_{U}$ следующим образом:

$\textstyle K_{U}=({\frac {1}{z+H_{1}(ID_{U})}})P$

Шифрование

Чтобы зашифровать неповторяющееся сообщение $\mathbb {M}$, отправителю необходимо знать идентификатор получателя $\textstyle ID_{U}$ и открытый ключ генератора закрытых ключей $\textstyle Z$. Далее отправителю необходимо произвести следующие операции:

1. Вычилить $\textstyle id=H_{1}(ID_{U})$
2. Сгенерировать $\textstyle r$: $\textstyle r=H_{1}(\mathbb {M} ||id)$, где операция $\textstyle ||$ является побитовым «или».
3. Сгенерировать точку $\textstyle R$ в группе $\textstyle E$:

   $\textstyle R=r((id)P+Z)$

4. Создать зашифрованное сообщение с помощью битовой маски:

   $\textstyle S=\mathbb {M} \oplus H_{2}(g^{r})$

5. Зашифрованным сообщением является пара: $\textstyle (R,S)$

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

Дешифрование

Для того чтобы расшифровать сообщение, адресованное $\textstyle ID_{U}$, получателю необходимо знать закрытый ключ $\textstyle K_{U}$, сгенерированный ГЗК и открытое значение $\textstyle Z$. Процедура расшифровки сообщения состоит из следующих действий:

1. Вычислить $\textstyle id=H_{1}(ID_{U})$
2. Получить зашифрованное сообщение: $\textstyle (R,S)$.
3. Вычислить:

   $\textstyle w=e(R,K_{U})$

4. Выделить сообщение:

   $\textstyle \mathbb {M} =S\oplus H_{2}(w)$

5. Чтобы проверить полученное сообщение, нужно вычислить $\textstyle r=H_{1}(\mathbb {M} ||id)$. Сообщение достоверно тогда и только тогда, когда:

   $\textstyle r((id)P+Z)\equiv R$

Демонстрация корректности алгоритма

Данные равенства показывают корректность приведённого алгоритма:

$\textstyle w=e(R,K_{U})=e(r((id)P+Z),K_{U})=e(r((id)P+zP),K_{U})=e((r(id+z))P,K_{U})$

Благодаря билинейности отображения:

$\textstyle w=e((r(id+z))P,K_{U})=e((r(id+z))P,({\frac {1}{(id+z)}})P)=e(P,P)^{\frac {r(id+z)}{(id+z)}}=g^{r}$

В результате получаем:

$\textstyle S\oplus H_{2}(w)=(\mathbb {M} \oplus H_{2}(g^{r}))\oplus H_{2}(w)=\mathbb {M}$

Стандартизация

С данным протоколом связаны два стандарта:

• Первоначальная стандартизация была произведена IEEE в 2006.
• Схема была стандартизована IETF в 2012 году по RFC 6508. Алгоритм используется как часть протокола MIKEY_SAKKE, описанного в RFC 6509.