Русская Википедия:Многомерная криптография

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Многомерная криптография или многомерная криптография открытого ключа  — это общий термин, описывающий асимметричные криптографические схемы, построенные на решениях уравнений, основанных на многомерных полиномах над конечным полем <math>\mathbb{F}</math>.

Безопасность многомерной криптографии основывается на предположении, что решения системы квадратичных многочленов над конечным полем <math>\mathbb{F}</math>, в общем случае, является NP-полной задачей в сильном смысле или просто NP-полной. Вот почему эти схемы часто считаются хорошими кандидатами для постквантовой криптографии. [1]

История создания

Первая попытка построения криптографической схемы на основе многомерных квадратичных полиномов была сделана Онгом, Шнором и Шамиром [2], где они предлагали схему подписи, основанную на сложности решения уравнения:
<math>s^2_1 + k*s^2_2 = m (\mod n)</math>;

Однако безопасность этой схемы по-прежнему основана на сложности факторизации <math>n = p*q</math> и поэтому эта схема неустойчива к атакам при помощи квантовых компьютеров. Разработка многомерных криптографических схем в современном смысле началась в 1988 году со схемы С* Системы Матцумото-Имаи[3].

Мацумото и Имаи использовали биективное отображение <math>\mathcal{F}</math> над степенью <math>n</math> полем расширения <math>\mathbb{E}</math> из <math>GF(2)</math> формы: <math>\mathcal{F} : \mathbb{E} \rightarrow \mathbb{E}, \mathcal{F} (X) = X^{2^ \theta +1}</math>.
Чтобы убедиться, что это преобразование обратимо, необходимо выбрать <math>\theta</math> таким образом, что <math>\text{НОД}(2^ \theta +1,2^n -1) = 1</math>. Уравнение выше даёт, благодаря каноническому изоморфизму между <math>GF(2^n)</math> и векторным пространством <math>GF(2)^n</math> систему многомерных квадратичных уравнений <math>\mathcal{F}</math> на полем <math>GF(2)</math>, объясняется это Эндоморфизмом Фробениуса. Для того чтобы спрятать структуру <math>\mathcal{F}</math> Мацумото и Имай использовали два аффинных преобразования <math>\mathcal{S}</math> и <math>\mathcal{T}</math>. Таким образом, они представили открытый ключ в форме: <math>\mathcal{P}=\mathcal{S} \circ \mathcal{F} \circ \mathcal{T}</math>.

Эта конструкция называемая биполярной. Она по-прежнему является стандартным методом построения многомерных криптосистем с открытым ключом. [4]

Стандартная двухполярная конструкция
Стандартная двухполярная конструкция

Многомерная криптография была активной областью исследований, однако, до сих пор отсутствуют многомерные схемы, такие как: протоколы обмена ключами и схемы подписи со специальными свойствами[5].

Актуальность и перспективы развития

Большинство криптосистем с открытым ключом, используемых на практике, основаны на целочисленной факторизации или дискретных логарифмах (в конечных полях или эллиптических кривых). [6] Однако, эти системы страдают от двух недостатков.

  1. Достижения в области теории чисел привели к снижению эффективности вычислений, поэтому размеры параметров должны быть увеличены в соответствии с требованиями безопасности.[1]
  2. Если можно построить достаточно большие квантовые компьютеры, алгоритм Шора сделает текущие системы полностью небезопасными. Поэтому важно искать альтернативные системы, которые способствуют эффективной и безопасной связи.[1]

Многомерная криптография с открытым ключом — одна из возможных альтернатив нынешних реализаций алгоритмов шифрования с открытым ключом. В 2003 году система подписи Sflash стала окончательным выбором проекта NESSIE (Новые европейские схемы подписи, целостности и шифрования) [7]. Первая книга о многомерной криптографии, написанная Дингом, Гауэром и Шмидтом, была опубликована в 2006 году [5]. Существует также международный воркшоп, PQCrypto, который посвящен вопросам постквантовой криптографии, в том числе многомерной криптографии.[8]

Основной алгоритм работы

Основной идеей стандартного построения многомерной криптографии является выбор системы <math>\mathcal{F}:\mathbb{F}^m \rightarrow \mathbb{F}^n</math> (центральное преобразование) из <math>m</math> многомерных квадратичных многочленов от <math>n</math> переменных, которые могут быть легко инвертированы. [9] После этого выбираются два случайных аффинных обратимых преобразования <math>\mathcal{S}:\mathbb{F}^m \rightarrow \mathbb{F}^m</math> и <math>\mathcal{T}:\mathbb{F}^n \rightarrow \mathbb{F}^m</math> для того, чтобы скрыть структуру центрального преобразования <math>\mathcal{F}</math> в открытом ключе. [10]

Открытый ключ криптосистемы — составное квадратичное преобразование <math>\mathcal{P}=\mathcal{S} \circ \mathcal{F} \circ \mathcal{T}</math>, которое, как предполагается, вряд ли отличается от случайного и поэтому его трудно инвертировать.

Закрытый ключ состоит из <math>\mathcal{S}</math>, <math>\mathcal{F}</math>, <math>\mathcal{T}</math> и следовательно, это позволяет инвертировать <math>\mathcal{P}</math>.

Построение публичного ключа

Пусть <math>\mathbb{F}</math> — конечное поле. Публичный ключ алгоритмов многомерной криптографии — это полиномиальное отображение <math>\mathcal{P}: \mathbb{F}^n \rightarrow \mathbb{F}^m</math>

<math>\mathcal{P}(x_1,\ldots,x_n) =

\begin{pmatrix} f_1(x_1,\ldots,x_n) \\ \vdots \\ f_m(x_1,\ldots,x_n) \end{pmatrix}</math>; где <math>f_i \in \mathbb{F}[x_1,\ldots,x_n]</math> — многочлен второй степени.

Для шифрования и дешифрования считаем, что <math>m \ge n</math>, для электронной подписи: <math>m \le n</math>. [1]

Шифрование

Чтобы зашифровать сообщение <math>\mathbf{z}\in\mathbb{F}^n</math> или <math>(x_1,\ldots,x_n) \in \mathbb{F}^n</math> необходимо вычислить <math>\mathbf{h=}\mathcal{P}(\mathbf{z})</math>. Шифротекст полученного сообщения <math>\mathbf{z}</math> есть <math>\mathbf{h}\in\mathbb{F}^m</math> или <math>(y_1,\ldots,y_m)=\mathcal{P}(x_1,\ldots,x_n)</math>. [6]

Расшифрование

Что бы расшифровать шифротекст <math>\mathbf{h}\in\mathbb{F}^m</math> рекурсивно вычисляется: <math>\mathbf{x=}\mathcal{S}^{-1}(\mathbf{h})</math>, <math>\mathbf{y=}\mathcal{F}^{-1}(\mathbf{x})</math> и <math>\mathbf{z=}\mathcal{T}^{-1}(\mathbf{y})</math>.

<math>\mathbf{z}\in\mathbb{F}^n</math> — это открытый текст шифротекста <math>\mathbf{h}</math>. Так как <math>m \ge n</math>, то отображение из <math>\mathbf{z}</math> в <math>\mathcal{F}</math>, а следовательно, и результирующий открытый текст являются уникальными. [6]

Или другими словами, если дан шифротекст <math>(y_1,\ldots,y_m) \in \mathbb{F}^m </math>, необходимо найти <math>(x_1,\ldots,x_n) \in \mathbb{F}^n</math> такой, что <math>\mathcal{P}(x_1,\ldots,x_n)=(y_1,\ldots,y_m)</math>. Обычно <math>\mathcal{P}</math> является инъекцией в криптографических системах, поэтому дешифровка выполняется при помощи вычисления <math>\mathcal{P}^{-1}(y_1,\ldots,y_n)</math>.

Цифровая подпись

Для того, что бы подписать документ <math>d</math>, используется хеш-функция <math>\mathcal{H}:\{0,1\}^* \rightarrow \mathbb{F}^m</math> для вычисления значения <math>\mathbf{h}=\mathcal{H}(d)\in\mathbb{F}^m</math>.
Затем необходимо вычислить <math>\mathbf{x=}\mathcal{S}^{-1}(\mathbf{h})</math>, <math>\mathbf{y=}\mathcal{F}^{-1}(\mathbf{x})</math> и <math>\mathbf{z=}\mathcal{T}^{-1}(\mathbf{y})</math>. Здесь <math>\mathcal{F}^{-1}(\mathbf{x})</math> означает один, возможно, много прообраз <math>x</math> для центрального отображения <math>\mathcal{F}</math>. Так как <math>n \ge m</math>, то такое отображение существует. Таким образом каждое сообщение может быть подписано. [6]

Проверка цифровой подписи

Чтобы проверить подлинность документа, необходимо просто вычислить <math>\mathbf{h^,=}\mathcal{P}(\mathbf{z})</math> и значение хеш-функции <math>\mathbf{h}=\mathcal{H}(d)</math> от документа. Если <math>\mathbf{h^,=h}</math>, то подпись принимается, в противном случае отклоняется. [6]

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

Безопасность алгоритмов многомерной криптографии опирается на следующее:

Дана система <math>\mathcal{P} = (p^{1},\ldots,p^{m})</math> из <math>m</math> нелинейных полиномиальных уравнений с переменными <math>x_1,\ldots,x_n</math>. Необходимо найти значения <math>\mathbf{x_1},\ldots,\mathbf{x_n}</math> такие, что <math>p^{1}(\mathbf{x_1},\ldots,\mathbf{x_n})=\ldots=p^{m}(\mathbf{x_1},\ldots,\mathbf{x_n})</math>.

Решение случайной многомерной квадратичной системы над конечным полем является NP-полной задачей в сильном смысле или просто NP-полной. Сложность решения этой задачи препятствует злоумышленику вычислить закрытый ключ, зная открытый ключ. [11]

  • Изоморфизм многочленов.[12]

Патарин и соавторы показали, что трудность решения этой проблемы по крайней мере такая же, как и изоморфизм графов [13]

Преимущества систем, построенных на алгоритмах многомерной криптографии

  • Скорость

Системы, построенные на алгоритмах многомерной криптографии достаточно быстры, особенно для подписи документов. Есть много предпосылок, что они могут быть быстрее, чем классические криптографические схемы с открытыми ключами, например RSA. [14] [15]

  • Скромные требования к вычислительным ресурсам

Математические операции, выполняемые многомерными схемами, обычно очень просты: большинству схем требуется только сложение и умножение по небольшим конечным полям. Поэтому многомерные схемы требуют скромных вычислительных ресурсов, что делает их привлекательными для использования на недорогих устройствах, таких как RFID чипы и смарт-карты, без необходимости наличия криптографического сопроцессора. Вариант схемы С*, называемый SFLASH, был предложен Европейской комиссией в качестве стандарта для схем подписи на недорогих устройствах. [16] [17]

В системе SFLASH [1] используется конечное поле <math>\mathbb{F}= \frac{Z_2[2]}{x^7+x+1}</math> также определяется отображение <math>\mathcal{P^{-}}: \mathbb{F}^{67} \rightarrow \mathbb{F}^{56}</math>. Обозначение <math>\mathcal{P^{-}}</math> указывает, что <math>11</math> уравнений были удалены из функции <math>\mathcal{P}</math>, которая построена следующим образом: <math>\mathcal{P}=\mathcal{L_1} \circ \mathcal{f} \circ \mathcal{L_2}</math>. Здесь <math>\mathcal{L_1}</math> и <math>\mathcal{L_2}</math> — два обратимых линейных преобразования. Функция <math>\mathcal{f^-}</math> имеет вид:<math>\mathcal{f^-}(X)=X^{1+128^{33}}</math>. Таким образом, открытый ключ состоит из <math>56</math> квадратичных полиномов c <math>67</math> переменными коэффициентами в <math>\mathbb{F}</math>. Каждый квадратичный полином будет иметь <math>67 * 34 + 67 + 1</math> коэффициентов. Для этого требуется <math>128,3</math> КБ памяти, если каждый коэффициент хранится в одном байте, также его можно уменьшить до <math>112,3</math> КБ, если использовать только <math>7</math> бит для каждого коэффициента

Атаки на системы многомерной криптографии

Повторная линеаризация

Атака релинеризации направлена на решение переопределенных систем многомерных квадратичных уравнений. Пусть <math>\mathcal{P}</math> - система из <math>m</math> квадратичных уравнений по <math>n</math> переменным <math>x_1,\ldots,x_n</math>. Основная идея заключается в введении новой переменной <math>x_{ij}</math> для каждого квадратичного одночлена <math>x_{i}x_{j}</math>. Таким образом, получается система линейных уравнений, если число уравнений достаточно велико, можно использовать метод Гаусса. Нужно удостовериться, действительно ли полученное таким образом решение является решением квадратичного система, при условии, что <math>x_{ij}=x_{i}x_{j} \forall i,j \in \{1,\ldots,n\}</math>. Для решения системы квадратичных уравнений по <math>n</math> переменным этим методом необходимо <math>m\ge{\frac{(n+1)(n+2)}{2}}-1</math> уравнений. Таким образом атака методом повторной линеаризации позволяет уменьшить количество неизвестных переменных в закрытом ключе т.е уменьшить его размерность. [18]

XL алгоритм

Пусть <math>T^{n}_D</math> — множество всех многочленов из <math>\mathbb{F}[x_1,\ldots,x_n]</math> степени <math>\le D</math>.

XL-алгоритм:
Входные данные: множество квадратичных многочленов <math>\mathcal{F}=\{f^{(1)},\ldots,f^{(m)}\}</math>.
Выходные данные: вектор <math>\mathbf{x=}(x_1,\ldots,x_n)</math> такой, что <math>f^{(1)}(\mathbf{x})=\ldots=f^{(m)}(\mathbf{x})</math>.

  • for <math>i = 1</math> to <math>n</math> do
    • Фиксируется целое число <math>D>2</math>.
    • Формируются все многочлены:<math>h \cdot f^{(j)}</math>, где <math>h \in T^{n}_{D-2}</math> и <math>j=1,\ldots,m</math>.
    • Необходимо воспользоваться методом Гауса для уравнений, полученных на предыдущем шаге, чтобы сгенерировать одно уравнение, содержащее только <math>x_i</math>.
    • Если на предыдущем шаге получился, по крайней мере один одномерный многочлен от <math>x_i</math>, то его необходимо решить, например при помощи алгоритма Берлекэмпа.
    • Необходимо упростить уравнения <math>f^{(1)},\ldots,f^{(m)}</math> путем замены значения <math>x_i</math>.
  • end for <math>\mathbf{x=}(x_1,\ldots,x_n)</math>
  • return <math>\mathbf{x=}(x_1,\ldots,x_n)</math>

Атака при помощи XL-алгритма позволяет уменьшить размерность закрытого ключа при помощи сведения системы уравнений к инварианту в некоторой переменной. Таким образом при помощи XL-алгоритма возможно проводить атаку на открытый ключ. [4]

Примеры многомерных криптосистем

  1. Треугольные криптосистемы [19].
  2. Системы Матцумото-Имаи [20].
  3. Минус-Плюс обобщения системы Мацумото-Имаи [21].
  4. Скрытые уравнения поля
  5. Unbalanced Oil and Vinegar

Примечания

Шаблон:Примечания

Ссылки

  1. [1] Multivariate Public Key Cryptography
Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 1,2 1,3 1,4 Шаблон:Cite web
  2. ↑ H. Ong, C.-P. Schnorr and A. Shamir Efficient signature schemes based on polynomial equations. In CRYPTO, volume 196 of Lecture Notes in Computer Science // Springer : journal. — 1984, pages 37–46.
  3. ↑ T. Matsumoto and H. Imai EPublic quadratic polynomial-tuples for efficient signature verifi- cation and message-encryption. In EUROCRYPT, volume 330 of Lecture Notes in Computer Science // Springer : journal. — 1988, pages 419–553
  4. ↑ 4,0 4,1 Шаблон:Cite web
  5. ↑ 5,0 5,1 Jintai Ding, Jason Gower, and Deiter Schmidt Multivariate Public Key Cryptosystems // Springer : journal. — 2006.
  6. ↑ 6,0 6,1 6,2 6,3 6,4 Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite web
  11. ↑ Шаблон:Cite web
  12. ↑ Шаблон:Cite web
  13. ↑ Шаблон:Cite web
  14. ↑ I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang SSE implementation of multivariate PKCs on modern x86 CPUs. In CHES, volume 5747 of Lecture Notes in Computer Science // Springer : journal. — 2009, pages 33–48
  15. ↑ A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves? // Springer : CHES, volume 5154 of Lecture Notes in Computer Science. — 2008, pages 45–61
  16. ↑ J. Patarin, N. Courtois and L. Goubin Flash, a fast multivariate signature algorithm // Springer : In CT-RSA, volume 2020 of Lecture Notes in Computer Science. — 2001, pages 298–307
  17. ↑ B. Preneel The NESSIE project: Towards new cryptographic algorithms // Swww.cryptonessie.org — 2000
  18. ↑ Шаблон:Cite web
  19. ↑ Harriet Fell and Whitfield Diffie Analysis of a public key approach based on polynomial substitution. In Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif.) // Springer : journal. — 1986. — volume 218, pages 340–349.
  20. ↑ T. Matsumoto and H. Imai Public quadratic polynomial-tuples for efficient signature verification and message encryption. In C. G. Guenther, editor, Advances in cryptology – EUROCRYPT ’88 // Springer : journal. — 1988. — volume 330, pages 419–453.
  21. ↑ Jacques Patarin, Louis Goubin, and Nicolas Courtois C∗−+ and HM: variations around two schemes of T. Matsumoto and H. Imai. In K. Ohta and D. Pei,editors, ASIACRYPT’98 // Springer : journal. — 1998. — volume 1514, pages 35–50.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Многомерная_криптография&oldid=10394889