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

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

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

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

Схема Сакаи — Касахара позволяет зашифровать сообщение $𝕄$ для получателя с конкретным идентификатором $I_U$. Таким образом, только пользователь с закрытым ключом $K_U$, соответствующим $I_U$, сможет расшифровать переданное сообщение.

Для реализации схемы необходимо, чтобы отправитель и получатель доверяли одному и тому же генератору закрытых ключей (ГЗК), который так же может называться системой управления ключами (Шаблон:Iw). Целью ГЗК является генерация приватного ключа $K_U$, соответствующего публичному идентификатору $I_U$. ГЗК должен сохранно и безопасно доставить закрытый ключ получателю, а также свой (зависящий от ГЗК) открытый параметр $Z$ всем участникам схемы. Данные действия не рассматриваются в определении самой схемы.

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

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

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

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

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

Также необходимо наличие двух хэш-функций: $H_1$ и $H_2$, таких, что:

• $H_1$ возвращает положительное целое число $x$, удовлетворяющее $1<x<q$.
• $H_2$ возвращает $n$ битов, где $n$ является длиной сообщения $𝕄$.

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

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

$K_U=(\frac{1}{z+H_1(I{D}_U)})P$

Шифрование

Чтобы зашифровать неповторяющееся сообщение $𝕄$, отправителю необходимо знать идентификатор получателя $I{D}_U$ и открытый ключ генератора закрытых ключей $Z$. Далее отправителю необходимо произвести следующие операции:

1. Вычилить $id=H_1(I{D}_U)$
2. Сгенерировать $r$: $r=H_1(𝕄||id)$, где операция $||$ является побитовым «или».
3. Сгенерировать точку $R$ в группе $E$:

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

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

   $S=𝕄\oplus H_2(g^r)$

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

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

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

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

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

   $w=e(R,K_U)$

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

   $𝕄=S\oplus H_2(w)$

5. Чтобы проверить полученное сообщение, нужно вычислить $r=H_1(𝕄||id)$. Сообщение достоверно тогда и только тогда, когда:

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

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

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

$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)$

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

$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$

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

$S\oplus H_2(w)=(𝕄\oplus H_2(g^r))\oplus H_2(w)=𝕄$

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

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

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