Схема IBE петухов

Схема Cocks IBE — это система шифрования на основе идентификации, предложенная Клиффордом Коксом в 2001 году. ^[1] Надежность схемы основана на сложности квадратичной проблемы невязкости .

Протокол

Настраивать

ПКГ выбирает:

общедоступный RSA-модуль $\textstyle n=pq$ , где $\textstyle p,q,\,p\equiv q\equiv 3{\bmod {4}}$ являются главными и хранятся в секрете,
сообщение и шифровальное пространство $\textstyle {\mathcal {M}}=\left\{-1,1\right\},{\mathcal {C}}=\mathbb {Z} _{n}$ и
безопасная общедоступная хэш-функция $\textstyle f:\left\{0,1\right\}^{*}\rightarrow \mathbb {Z} _{n}$ .

Извлекать

Когда пользователь $\textstyle ID$ хочет получить свой закрытый ключ, он связывается с PKG через защищенный канал. ПКГ

выводит $\textstyle a$ с $\textstyle \left({\frac {a}{n}}\right)=1$ детерминированным процессом из $\textstyle ID$ (например, многократное применение $\textstyle f$ ),
вычисляет $\textstyle r=a^{(n+5-p-q)/8}{\pmod {n}}$ (который выполняет либо $\textstyle r^{2}=a{\pmod {n}}$ или $\textstyle r^{2}=-a{\pmod {n}}$ , см. ниже) и
передает $\textstyle r$ пользователю.

Шифровать

Чтобы немного зашифровать (закодировано как $\textstyle 1$ / $\textstyle -1$ ) $\textstyle m\in {\mathcal {M}}$ для $\textstyle ID$ , пользователь

выбирает случайный $\textstyle t_{1}$ с $\textstyle m=\left({\frac {t_{1}}{n}}\right)$ ,
выбирает случайный $\textstyle t_{2}$ с $\textstyle m=\left({\frac {t_{2}}{n}}\right)$ , отличается от $\textstyle t_{1}$ ,
вычисляет $\textstyle c_{1}=t_{1}+at_{1}^{-1}{\pmod {n}}$ и $c_{2}=t_{2}-at_{2}^{-1}{\pmod {n}}$ и
отправляет $\textstyle s=(c_{1},c_{2})$ пользователю.

Расшифровать

Чтобы расшифровать зашифрованный текст $s=(c_{1},c_{2})$ для пользователя $ID$ , он

вычисляет $\alpha =c_{1}+2r$ если $r^{2}=a$ или $\alpha =c_{2}+2r$ в противном случае, и
вычисляет $m=\left({\frac {\alpha }{n}}\right)$ .

Обратите внимание: здесь мы предполагаем, что шифрующий объект не знает, $ID$ имеет квадратный корень $r$ из $a$ или $-a$ . В этом случае нам нужно отправить зашифрованный текст для обоих случаев. Как только эта информация станет известна шифрующему объекту, необходимо отправить только один элемент.

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

Прежде всего отметим, что поскольку $\textstyle p\equiv q\equiv 3{\pmod {4}}$ (т.е. $\left({\frac {-1}{p}}\right)=\left({\frac {-1}{q}}\right)=-1$ ) и $\textstyle \left({\frac {a}{n}}\right)\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)$ , или $\textstyle a$ или $\textstyle -a$ является квадратичным вычетом по модулю $\textstyle n$ .

Поэтому, $\textstyle r$ является квадратным корнем из $\textstyle a$ или $\textstyle -a$ :

{\begin{aligned}r^{2}&=\left(a^{(n+5-p-q)/8}\right)^{2}\\&=\left(a^{(n+5-p-q-\Phi (n))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-(p-1)(q-1))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-n+p+q-1)/8}\right)^{2}\\&=\left(a^{4/8}\right)^{2}\\&=\pm a\end{aligned}}

Более того, (для случая, когда $\textstyle a$ является квадратичным вычетом, та же идея справедлива и для $\textstyle -a$ ):

{\begin{aligned}\left({\frac {s+2r}{n}}\right)&=\left({\frac {t+at^{-1}+2r}{n}}\right)=\left({\frac {t\left(1+at^{-2}+2rt^{-1}\right)}{n}}\right)\\&=\left({\frac {t\left(1+r^{2}t^{-2}+2rt^{-1}\right)}{n}}\right)=\left({\frac {t\left(1+rt^{-1}\right)^{2}}{n}}\right)\\&=\left({\frac {t}{n}}\right)\left({\frac {1+rt^{-1}}{n}}\right)^{2}=\left({\frac {t}{n}}\right)(\pm 1)^{2}=\left({\frac {t}{n}}\right)\end{aligned}}

Безопасность

Можно показать, что нарушение схемы эквивалентно решению квадратичной проблемы невязкости , которая, как предполагается, является очень сложной. Общие правила выбора модуля RSA сохраняются: Используйте безопасный $\textstyle n$ , сделать выбор $\textstyle t$ единообразными и случайными и, кроме того, включают некоторые проверки подлинности для $\textstyle t$ (в противном случае атака с адаптивным выбранным зашифрованным текстом может быть организована путем изменения пакетов, передающих один бит, и использования оракула для наблюдения за влиянием на расшифрованный бит).

Проблемы

Основным недостатком этой схемы является то, что она может шифровать сообщения только побитно, поэтому она подходит только для небольших пакетов данных, таких как сеансовый ключ. Для иллюстрации рассмотрим 128-битный ключ, который передается с использованием модуля 1024 бит. Тогда нужно отправить 2×128×1024 бит = 32 Кбайт (когда неизвестно, будет ли $r$ является квадратом a или −a ) , что приемлемо только для сред, в которых ключи сеанса изменяются нечасто.

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

Ссылки

^ Клиффорд Кокс, Схема шифрования на основе идентичности, основанная на квадратичных остатках, заархивированная 6 февраля 2007 г. в Wayback Machine , Труды 8-й Международной конференции IMA по криптографии и кодированию , 2001 г.

[1] Клиффорд Кокс, Схема шифрования на основе идентичности, основанная на квадратичных остатках, заархивированная 6 февраля 2007 г. в Wayback Machine , Труды 8-й Международной конференции IMA по криптографии и кодированию , 2001 г.

[1]