Многомерная криптография

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ f_i \in \mathbb{F}[x_1,\ldots,x_n] }[/math] — многочлен второй степени.

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

Шифрование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

XL алгоритм

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

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

  • for [math]\displaystyle{ i = 1 }[/math] to [math]\displaystyle{ n }[/math] do
    • Фиксируется целое число [math]\displaystyle{ D\gt 2 }[/math].
    • Формируются все многочлены:[math]\displaystyle{ h \cdot f^{(j)} }[/math], где [math]\displaystyle{ h \in T^{n}_{D-2} }[/math] и [math]\displaystyle{ j=1,\ldots,m }[/math].
    • Необходимо воспользоваться методом Гауса для уравнений, полученных на предыдущем шаге, чтобы сгенерировать одно уравнение, содержащее только [math]\displaystyle{ x_i }[/math].
    • Если на предыдущем шаге получился, по крайней мере один одномерный многочлен от [math]\displaystyle{ x_i }[/math], то его необходимо решить, например при помощи алгоритма Берлекэмпа.
    • Необходимо упростить уравнения [math]\displaystyle{ f^{(1)},\ldots,f^{(m)} }[/math] путем замены значения [math]\displaystyle{ x_i }[/math].
  • end for [math]\displaystyle{ \mathbf{x=}(x_1,\ldots,x_n) }[/math]
  • return [math]\displaystyle{ \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,0 1,1 1,2 1,3 1,4 JINTAI DING, DIETER SCHMIDT. Reuleaux Triangle (англ.). MULTIVARIABLE PUBLIC–KEY CRYPTOSYSTEMS. Дата обращения: 18 декабря 2017. Архивировано 9 августа 2016 года.
  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 Albrecht Petzoldt. Selecting and Reducing Key Sizes for Multivariate Cryptography (англ.). Дата обращения: 21 декабря 2017. Архивировано 8 августа 2017 года.
  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 Jintai Ding and Bo-Yin Yang. Multivariate Public Key Cryptography (англ.). Дата обращения: 4 декабря 2017. Архивировано 5 декабря 2017 года.
  7. ↑ NESSIE. Reuleaux Triangle (англ.). NESSIE: New European Schemes for Signatures, Integrity, and Encryption. NESSIE project announces final selection of crypto algorithms. Information Society Technologies Programme of the European Commission (IST-1999-12324). Дата обращения: 3 декабря 2017. Архивировано 12 июня 2018 года.
  8. ↑ Introduction. Дата обращения: 16 декабря 2017. Архивировано 14 декабря 2017 года.
  9. ↑ Shuaiting Qiao, Wenbao Han, Yifa Li, and Luyao Jiao. Construction of Extended Multivariate Public Key Cryptosystems (англ.). Дата обращения: 21 декабря 2017. Архивировано 22 декабря 2017 года.
  10. ↑ Lih-Chung Wang, Bo-Yin Yang, Yu-Hua Hu, and Feipei Lai. A Medium-Field Multivariate Public-Key Encryption Scheme (англ.). Дата обращения: 18 декабря 2017. Архивировано 5 июля 2017 года.
  11. ↑ Jacques Patarin, Louis Goubin, and Nicolas Courtois. Reuleaux Triangle (англ.). Improved Algorithms for Isomorphisms of Polynomials (1998). Springer. Дата обращения: 21 декабря 2017. Архивировано 16 июля 2017 года.
  12. ↑ Jacques Patarin. IHidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (англ.). Дата обращения: 21 декабря 2017. Архивировано 15 декабря 2017 года.
  13. ↑ Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi and Kouichi Sakurai1. MQ Challenge (англ.). MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems. Дата обращения: 3 декабря 2017. Архивировано 4 декабря 2017 года.
  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. ↑ Raymond Heindl. New Directions in Multivariate Public Key Cryptography (англ.). Дата обращения: 18 декабря 2017. Архивировано 26 декабря 2017 года.
  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.

Ссылки

  1. [1] Multivariate Public Key Cryptography
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Многомерная_криптография&oldid=5825077