CEILIDH

CEILIDH - это открытый ключ криптосистема, основанная на задаче дискретного логарифмирования в алгебраическом торе. Эта идея была впервые предложена Алисой Сильверберг и Карлом Рубином в 2003 году; Сильверберг назвала CEILIDH в честь своей кошки. Основным преимуществом системы является уменьшенный размер ключей для той же безопасности по сравнению с базовыми схемами.

• 1 Алгоритмы
  • 1.1 Параметры
  • 1.2 Схема согласования ключей
  • 1.3 Схема шифрования
• 2 Безопасность
• 3 Ссылки
• 4 Внешние ссылки

Параметры

• Пусть $q\; \{\backslash \; displaystyle\; q\}$будет простой степенью.
• целое число $n\; \{\backslash \; displaystyle\; n\}$выбирается так, что:
  • тор $T\; n\; \{\backslash \; displaystyle\; T\_\; \{n\}\}$имеет явную рациональную параметризацию.
  • $\Phi \; n\; (q)\; \{\backslash \; displaystyle\; \backslash \; Phi\; \_\; \{n\}\; (q)\}$делится на большое простое число $l\; \{\backslash \; displaystyle\; l\}$где $\Phi \; n\; \{\backslash \; displaystyle\; \backslash \; Phi\; \_\; \{n\}\}$- это $n-й\; \{\backslash \; displaystyle\; n\; ^\; \{th\}\; \}$Циклотомический многочлен.
• Пусть $m\; =\; \varphi \; (n)\; \{\backslash \; displaystyle\; m\; =\; \backslash \; phi\; (n)\}$где $\varphi \; \{\backslash \; displaystyle\; \backslash \; phi\}$- функция Эйлера..
• Пусть $\rho :\; T\; n\; (F\; q)\; \to \; F\; qm\; \{\backslash \; displaystyle\; \backslash \; rho:\; T\_\; \{n\}\; (\backslash \; mathbb\; \{F\}\; \_\; \{q\})\; \backslash \; правый\; row\; \{\backslash \; mathbb\; \{F\}\; \_\; \{q\}\}\; ^\; \{m\}\}$бирациональное отображение и его обратное $\psi \; \{\backslash \; displaystyle\; \backslash \; psi\}$.
• Выберите $\alpha \; \in \; T\; n\; \{\backslash \; displaystyle\; \backslash \; alpha\; \backslash \; in\; T\_\; \{n\}\}$порядка $l\; \{\backslash \; displaystyle\; l\}$и пусть $g\; =\; \rho \; (\alpha ))\; \{\backslash \; displaystyle\; g\; =\; \backslash \; rho\; (\backslash \; alpha))\}$.

Схема согласования ключей

Эта схема основана на согласовании ключей Диффи-Хеллмана.

• Алиса выбирает случайное число $a\; (mod\; \Phi \; N\; (q))\; \{\backslash \; Displaystyle\; a\; \backslash \; \{\backslash \; pmod\; \{\backslash \; Phi\; \_\; \{n\}\; (q)\}\}\}$.
• Она вычисляет $PA\; =\; \rho \; (\psi \; (g)\; a)\; \in \; F\; qm\; \{\backslash \; displaystyle\; P\_\; \{A\}\; =\; \backslash \; rho\; (\backslash \; psi\; (g)\; ^\; \{a\})\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\}\}$и отправляет его Бобу.
• Боб выбирает случайное число $b\; (mod\; \Phi \; n\; (q))\; \{\backslash \; displaystyle\; b\; \backslash \; \{\backslash \; pmod\; \{\backslash \; Phi\; \_\; \{n\}\; (q)\}\}\}$.
• Он вычисляет $PB\; знак\; равно\; \rho \; (\psi \; (г)\; б)\; \in \; F\; qm\; \{\backslash \; Displaystyle\; P\_\; \{B\}\; =\; \backslash \; rho\; (\backslash \; psi\; (g)\; ^\; \{b\})\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\}\}$и отправляет его Алисе.
• Алиса вычисляет $\rho \; (\psi \; (PB))\; a)\; \in \; F\; qm\; \{\backslash \; displaystyle\; \backslash \; rho\; (\backslash \; psi\; (P\_\; \{B\}))\; ^\; \{a\})\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\}\}$
• Бо b вычисляет $\rho \; (\psi \; (PA))\; b)\; \in \; F\; qm\; \{\backslash \; displaystyle\; \backslash \; rho\; (\backslash \; psi\; (P\_\; \{A\}))\; ^\; \{b\})\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{\; m\}\}$

$\psi \; \circ \; \rho \; \{\backslash \; displaystyle\; \backslash \; psi\; \backslash \; circ\; \backslash \; rho\}$- это тождество, поэтому мы имеем: $\rho \; (\psi \; (PB))\; a)\; =\; \rho \; (\psi \; (\; PA))\; б)\; знак\; равно\; \rho \; (\psi \; (g)\; ab)\; \{\backslash \; displaystyle\; \backslash \; rho\; (\backslash \; psi\; (P\_\; \{B\}))\; ^\; \{a\})\; =\; \backslash \; rho\; (\backslash \; psi\; (P\_\; \{A\}))\; ^\; \{b\; \})\; =\; \backslash \; rho\; (\backslash \; psi\; (g)\; ^\; \{ab\})\}$, который является общим секретом Алисы и Боба.

Схема шифрования

Эта схема основана на шифровании Эль-Гамаля.

• Генерация ключа
  • Алиса выбирает случайное число $a\; (mod\; \Phi \; n\; (q))\; \{\backslash \; displaystyle\; a\; \backslash \; \{\backslash \; pmod\; \{\backslash \; Phi\; \_\; \{n\}\; (q)\}\}\}$в качестве ее закрытого ключа.
  • Полученный открытый ключ равен $PA\; =\; \rho \; (\; \psi \; (g)\; a)\; \in \; F\; qm\; \{\backslash \; displaystyle\; P\_\; \{A\}\; =\; \backslash \; rho\; (\backslash \; psi\; (g)\; ^\; \{a\})\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\}\}$.
• Шифрование
  • Сообщение $M\; \{\backslash \; displaystyle\; M\}$является элементом $F\; qm\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\}\}$.
  • Боб выбирает случайное целое число $k\; \{\backslash \; displaystyle\; k\}$из диапазона $1\; \le \; k\; \le \; l\; -\; 1\; \{\backslash \; displaystyle\; 1\; \backslash \; leq\; k\; \backslash \; leq\; l-1\}$.
  • Боб вычисляет $\gamma \; знак\; равно\; \rho \; (\psi \; (г)\; К)\; \in \; F\; qm\; \{\backslash \; Displaystyle\; \backslash \; gamma\; =\; \backslash \; rho\; (\backslash \; psi\; (g)\; ^\; \{k\})\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\}\; \}$и $\delta \; =\; \rho \; (\psi \; (M)\; \psi \; (PA)\; k)\; \in \; F\; qm\; \{\backslash \; displaystyle\; \backslash \; delta\; =\; \backslash \; rho\; (\backslash \; psi\; (M)\; \backslash \; psi\; (P\_\; \{A\})\; ^\; \{k\})\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\}\}$.
  • Боб отправляет зашифрованный текст $(\gamma ,\; \delta )\; \{\backslash \; displaystyle\; (\backslash \; gamma,\; \backslash \; delta)\}$Алисе.
• Decr yption
  • Алиса вычисляет $M\; =\; \rho \; (\psi \; (\delta )\; \psi \; (\gamma )\; -\; a)\; \{\backslash \; displaystyle\; M\; =\; \backslash \; rho\; (\backslash \; psi\; (\backslash \; delta)\; \backslash \; psi\; (\backslash \; gamma)\; ^\; \{-\; a\})\; \}$.

Схема CEILIDH основана на схеме Эль-Гамаля и, следовательно, имеет аналогичные свойства безопасности.

Если вычислительное предположение Диффи-Хеллмана содержит основную циклическую группу $G\; \{\backslash \; displaystyle\; G\}$, то функция шифрования одно- путь. Если решающее предположение Диффи-Хеллмана (DDH) выполняется в $G\; \{\backslash \; displaystyle\; G\}$, то CEILIDH достигает семантической безопасности. Семантическая безопасность не подразумевается только вычислительным предположением Диффи-Хеллмана. См. решающее предположение Диффи-Хеллмана для обсуждения групп, в которых предположение, как предполагается, выполняется.

Шифрование CEILIDH безусловно податливое и, следовательно, небезопасно при атаке с выбранным шифротекстом . Например, при шифровании $(c\; 1,\; c\; 2)\; \{\backslash \; displaystyle\; (c\_\; \{1\},\; c\_\; \{2\})\}$некоторого (возможно, неизвестного) сообщения $m\; \{\backslash \; displaystyle\; m\}$, можно легко построить действительное шифрование $(c\; 1,\; 2\; c\; 2)\; \{\backslash \; displaystyle\; (c\_\; \{1\},\; 2c\_\; \{2\})\}$из сообщение $2\; m\; \{\backslash \; displaystyle\; 2m\}$.

1. ^Сильверберг, Алиса (ноябрь 2006 г.). «Алиса в стране NUMB3Rland» (PDF). Сосредоточьтесь. Математическая ассоциация Америки. Проверено 12 июля 2018 г.
2. ^Кирш, Рэйчел (декабрь 2010 г.). «Криптография: как сохранить секрет». Математическая ассоциация Америки. Проверено 12 июля 2018 г.
3. ^ «Схема шифрования Эль-Гамаля». КРИПТЮТОР. Архивировано с оригинального 21 апреля 2009 года. Проверено 21 апреля 2009 г.
4. ^Abdalla, M.; Bellare, M.; Rogaway, P. (сентябрь 1998 г.). «DHIES: схема шифрования, основанная на проблеме Диффи-Хеллмана (приложение A)» (PDF). Для цитирования журнала требуется | journal =()

• Рубин, К.; Сильверберг, А. (2003). «Криптография на основе тора». Ин Бонех, Д. (ред.). Достижения в криптологии - CRYPTO 2003. Конспект лекций по информатике. 2729 . Springer, Berlin, Heidelberg. Pp. 349–365. doi : 10.1007 / 978-3-540-45146-4_21. ISBN 9783540406747.

• Криптография на основе тора : статья, представляющая концепцию (в формате PDF с веб-страницы университета Сильверберга).