Ключевой механизм инкапсуляции

Не путать с переносом ключей .

Механизм инкапсуляции ключей для безопасной транспортировки секретного ключа. $k$ от отправителя к получателю состоит из трех алгоритмов: Gen, Encap и Decap. Кружочки, заштрихованные синим цветом — открытый ключ получателя. $pk$ и инкапсуляция $c$— может быть безопасно раскрыт злоумышленнику, а поля закрашены красным — закрытый ключ получателя $sk$ и инкапсулированный секретный ключ $k$— должно храниться в тайне.

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

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

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

Отличие от шифрования с открытым ключом

Схема шифрования с открытым ключом.

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

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

Большинство схем шифрования с открытым ключом, таких как RSAES-PKCS1-v1_5 , RSAES-OAEP и шифрование Эльгамала , ограничены небольшими сообщениями. и в любом случае почти всегда используются для шифрования короткого случайного секретного ключа в гибридной криптосистеме. И хотя схему шифрования с открытым ключом, наоборот, можно преобразовать в KEM, выбрав случайный секретный ключ и зашифровав его как сообщение, легче спроектировать и проанализировать безопасный KEM, чем разработать безопасную схему шифрования с открытым ключом как основе.Таким образом, большинство современных схем шифрования с открытым ключом основаны на KEM, а не наоборот.

Определение

Синтаксис

КЕМ состоит из трех алгоритмов:

1. Генерация ключей , $({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()$, не принимает никаких входных данных и возвращает пару открытых ключей ${\mathit {pk}}$ и закрытый ключ ${\mathit {sk}}$.
2. Инкапсуляция , $(k,c):=\operatorname {Encap} ({\mathit {pk}})$, принимает открытый ключ ${\mathit {pk}}$, случайным образом выбирает секретный ключ $k$и возвращает $k$ вместе с его инкапсуляцией $c$.
3. Декапсуляция , $k':=\operatorname {Decap} ({\mathit {sk}},c')$, принимает закрытый ключ ${\mathit {sk}}$ и инкапсуляция $c'$и любой из них возвращает инкапсулированный секретный ключ $k'$ или терпит неудачу, что иногда обозначается возвратом $\bot$ (так называемое « дно »).

Корректность

KEM является правильным , если для любой пары ключей $({\mathit {pk}},{\mathit {sk}})$ созданный $\operatorname {Gen}$, декапсуляция инкапсуляции $c$ возвращенный $(k,c):=\operatorname {Encap} ({\mathit {pk}})$ с высокой вероятностью дает тот же ключ $k$, то есть, $\operatorname {Decap} ({\mathit {sk}},c)=k$.

Безопасность: IND-CCA

Безопасность KEM количественно определяется его неотличимостью от атаки с выбранным зашифрованным текстом , IND-CCA, которая примерно определяет, насколько лучше злоумышленник может сделать, чем подбрасывание монеты, чтобы определить, инкапсулирован ли ключ, учитывая случайный ключ и инкапсуляцию, эта инкапсуляция или является независимым случайным ключом.

В частности, в игре IND-CCA:

1. Алгоритм генерации ключей запускается для генерации $({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()$.
2. ${\mathit {pk}}$ раскрывается противнику.
3. Противник может запросить $\operatorname {Decap} ({\mathit {sk}},c')$ для произвольных инкапсуляций $c'$ по выбору противника.
4. Алгоритм инкапсуляции запускается для случайной генерации секретного ключа и инкапсуляции. $(k_{0},c):=\operatorname {Encap} ({\mathit {pk}})$и еще один секретный ключ $k_{1}$ генерируется независимо случайным образом.
5. Подбрасывается честная монета, дающая результат $b\in \{0,1\}$.
6. Пара $(k_{b},c)$ раскрывается противнику.
7. Противник может снова запросить $\operatorname {Decap} ({\mathit {sk}},c')$ для произвольных инкапсуляций $c'$ по выбору противника, исключением за $c$.
8. Противник возвращает предположение $b'\in \{0,1\}$, и выигрывает игру, если $b=b'$.

Преимущество IND-CCA противника по $\left|\Pr[b'=b]-1/2\right|$, то есть вероятность правильного различения инкапсулированного ключа от независимо случайно выбранного ключа, выходящая за рамки честного подбрасывания монеты.

Примеры и мотивация

ЮАР

Традиционное шифрование RSA с $t$-битовые модули и экспонента $e$, определяется следующим образом:

• Генерация ключей , $({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()$:

1. Создать $t$-полупервичный бит $n$ с $2^{t-1}<n<2^{t}$ случайное удовлетворение $\gcd(e,\lambda (n))=1$, где $\lambda (n)$ – функция Кармайкла .
2. Вычислить $d:=e^{-1}{\bmod {\lambda }}(n)$.
3. Возвращаться ${\mathit {pk}}:=n$ как открытый ключ и ${\mathit {sk}}:=(n,d)$ в качестве закрытого ключа. (Доступно множество вариаций алгоритмов генерации ключей и форматов закрытых ключей. )

• Шифрование ​ $(t-1)$-битное сообщение $m$ к открытому ключу ${\mathit {pk}}=n$, давая $c:=\operatorname {Encrypt} ({\mathit {pk}},m)$:

1. Закодировать битовую строку $m$ как целое число $r$ с $0\leq r<n$.
2. Возвращаться $c:=r^{e}{\bmod {n}}$.

• Расшифровка зашифрованного текста $c'$ с секретным ключом ${\mathit {sk}}=(n,d)$, давая $m':=\operatorname {Decrypt} ({\mathit {sk}},c')$:

1. Вычислить $r':=(c')^{d}{\bmod {n}}$.
2. Расшифровать целое число $r'$ как битовая строка $m'$.

Этот наивный подход совершенно небезопасен.Например, поскольку оно нерандомизировано, оно не может быть защищено даже от атак с использованием известного открытого текста — злоумышленник может определить, отправляет ли отправитель сообщение. ATTACK AT DAWN против сообщения ATTACK AT DUSK просто зашифровав эти сообщения и сравнив зашифрованный текст.

Даже если $m$ всегда является случайным секретным ключом, например 256-битным ключом AES , когда $e$ выбран для оптимизации эффективности, поскольку $e=3$, сообщение $m$ можно вычислить по зашифрованному тексту $c$ просто извлекая кубические корни действительных чисел, и существует множество других атак на простой RSA . различные схемы рандомизированного заполнения В ходе попыток были разработаны , иногда неудачные, например RSAES-PKCS1-v1_5. — чтобы сделать его безопасным для произвольных коротких сообщений $m$.

Поскольку сообщение $m$ почти всегда является коротким секретным ключом для с симметричным ключом, аутентифицированного шифра используемого для шифрования сообщения произвольной битовой строки, более простой подход, называемый RSA-KEM, заключается в выборе элемента $\mathbb {Z} /n\mathbb {Z}$ случайным образом и использовать это для получения секретного ключа с помощью функции получения ключа. $H$, примерно так:

• Генерация ключей : Как указано выше.
• Инкапсуляция открытого ключа ${\mathit {pk}}=n$, давая $(k,c):=\operatorname {Encap} ({\mathit {pk}})$:

1. Выберите целое число $r$ с $0\leq r<n$ равномерно случайным образом.
2. Возвращаться $k:=H(r)$ и $c:=r^{e}{\bmod {n}}$ как его инкапсуляция.

• Декапсуляция ​ $c'$ с секретным ключом ${\mathit {sk}}=(n,d)$, давая $k':=\operatorname {Decap} ({\mathit {sk}},c')$:

1. Вычислить $r':=(c')^{d}{\bmod {n}}$.
2. Возвращаться $k':=H(r')$.

Этот подход проще реализовать и обеспечивает более четкое решение проблемы RSA , чем схемы заполнения, такие как RSAES-OAEP .

Эльгамаль

Традиционное шифрование Эльгамаля определяется над мультипликативной подгруппой конечного поля. $\mathbb {Z} /p\mathbb {Z}$ с генератором $g$ порядка $q$ следующее:

• Генерация ключей , $(pk,sk):=\operatorname {Gen} ()$:

1. Выбирать $x\in \mathbb {Z} /q\mathbb {Z}$ равномерно случайным образом.
2. Вычислить $y:=g^{x}{\bmod {p}}$.
3. Возвращаться ${\mathit {sk}}:=x$ в качестве закрытого ключа и ${\mathit {pk}}:=y$ в качестве открытого ключа.

• Шифрование сообщения $m\in \mathbb {Z} /p\mathbb {Z}$ к открытому ключу ${\mathit {pk}}=y$, давая $c:=\operatorname {Encrypt} ({\mathit {pk}},m)$:

1. Выбирать $r\in \mathbb {Z} /q\mathbb {Z}$ равномерно случайным образом.
2. Вычислить: $${\begin{aligned}t&:=y^{r}{\bmod {p}}\\c_{1}&:=g^{r}{\bmod {p}}\\c_{2}&:=(t\cdot m){\bmod {p}}\end{aligned}}$$
3. Вернуть зашифрованный текст $c:=(c_{1},c_{2})$.

• Расшифровка зашифрованного текста $c'=(c'_{1},c'_{2})$ для секретного ключа ${\mathit {sk}}=x$, давая $m':=\operatorname {Decrypt} ({\mathit {sk}},c')$:

1. Проиграть и вернуться $\bot$ если $(c'_{1})^{(p-1)/q}\not \equiv 1{\pmod {p}}$ или если $(c'_{2})^{(p-1)/q}\not \equiv 1{\pmod {p}}$, то есть, если $c'_{1}$ или $c'_{2}$ не входит в подгруппу, созданную $g$.
2. Вычислить $t':=(c'_{1})^{x}{\bmod {p}}$.
3. Возвращаться $m':=t^{-1}c'_{2}{\bmod {p}}$.

Это соответствует синтаксису схемы шифрования с открытым ключом, ограниченной сообщениями в пространстве. $\mathbb {Z} /p\mathbb {Z}$ (что ограничивает его сообщением размером в несколько сотен байт для типичных значений $p$).Проверяя зашифрованные тексты при расшифровке, он позволяет избежать утечки битов закрытого ключа. $x$ через злонамеренно выбранные зашифрованные тексты вне группы, созданные $g$.

Однако это не позволяет добиться неотличимости от атаки с выбранным зашифрованным текстом .Например, противник, имеющий зашифрованный текст $c=(c_{1},c_{2})$ за неизвестное сообщение $m$ может тривиально расшифровать его, запросив у оракула дешифрования отдельный зашифрованный текст $c':=(c_{1},c_{2}g)$, давая связанный открытый текст $m':=mg{\bmod {p}}$, из которого $m$ может быть восстановлен с помощью $m=m'g^{-1}{\bmod {p}}$.

Традиционное шифрование Эльгамаля можно адаптировать к настройке эллиптической кривой, но для этого требуется какой-то способ обратимого кодирования сообщений в виде точек на кривой, что менее тривиально, чем кодирование сообщений в виде целых чисел mod. $p$.

Поскольку сообщение $m$ почти всегда является коротким секретным ключом для с симметричным ключом, аутентифицированного шифра используемого для шифрования сообщения произвольной битовой строки, более простой подход состоит в том, чтобы получить секретный ключ из $t$ и обойтись без $m$ и $c_{2}$ вообще, как КЕМ, используя функцию деривации ключей $H$:

• Генерация ключей : Как указано выше.
• Инкапсуляция открытого ключа ${\mathit {pk}}=y$, давая $(k,c):=\operatorname {Encap} ({\mathit {pk}})$:

1. Выбирать $r\in \mathbb {Z} /q\mathbb {Z}$ равномерно случайным образом.
2. Вычислить $t:=y^{r}{\bmod {p}}$.
3. Возвращаться $k:=H(t)$ и $c:=g^{r}{\bmod {p}}$ как его инкапсуляция.

• Декапсуляция ​ $c'$ с секретным ключом ${\mathit {sk}}=x$, давая $k':=\operatorname {Decap} ({\mathit {sk}},c')$:

1. Проиграть и вернуться $\bot$ если $(c')^{(p-1)/q}\not \equiv 1{\pmod {p}}$, то есть, если $c'$ не входит в подгруппу, созданную $g$.
2. Вычислить $t':=(c')^{x}{\bmod {p}}$.
3. Возвращаться $k':=H(t')$.

В сочетании с аутентифицированным шифром для шифрования сообщений произвольной битовой строки такая комбинация по сути представляет собой интегрированную схему шифрования .Поскольку этому KEM требуется только односторонняя функция получения ключа для хэширования случайных элементов группы, в которой он определен, $\mathbb {Z} /p\mathbb {Z}$ в этом случае, а не обратимое кодирование сообщений, его легко расширить до более компактных и эффективных групп эллиптических кривых для той же безопасности, что и в ECIES, Elliptic Curve Integrated Encryption Scheme .

См. также

• Ключевая упаковка
• Оптимальное заполнение асимметричного шифрования
• Гибридная криптосистема