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

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

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

История созданияПравить

Первая попытка построения криптографической схемы на основе многомерных квадратичных полиномов была сделана Онгом, Шнором и Шамиром , где они предлагали схему подписи, основанную на сложности решения уравнения:
$s_1^2+k\ast <!--\; \ast \; -->s_2^2=m(\mathrm{mod}n)$$s_{1}^{2}+k*s_{2}^{2}=m(\mod n)$ ;

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

$\mathcal{P}(x_1,\dots <!--\; \dots \; -->,x_n)=\left(\begin{array}{c}{f}_1(x_1,\dots <!--\; \dots \; -->,x_n)\\ ⋮<!--\; ⋮\; -->\\ f_m(x_1,\dots <!--\; \dots \; -->,x_n)\end{array}\right)$${\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}}$ ; где $f_i\in <!--\; \in \; -->\mathbb{F}[x_1,\dots <!--\; \dots \; -->,x_n]$$f_{i}\in \mathbb {F} [x_{1},\ldots ,x_{n}]$  — многочлен второй степени.

Для шифрования и дешифрования считаем, что $m\ge <!--\; \ge \; -->n$$m\geq n$ , для электронной подписи: $m\le <!--\; \le \; -->n$$m\leq n$ .

ШифрованиеПравить

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

РасшифрованиеПравить

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

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

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

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

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

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

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

БезопасностьПравить

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

• Сложность решения квадратичных многомерных систем уравнений над конечными полями.

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

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

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

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

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

• Скорость

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

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

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

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

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

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

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

XL алгоритмПравить

Пусть $T_D^n$$T_{D}^{n}$  — множество всех многочленов из $\mathbb{F}[x_1,\dots <!--\; \dots \; -->,x_n]$$\mathbb {F} [x_{1},\ldots ,x_{n}]$  степени $\le <!--\; \le \; -->D$$\leq D$ .

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

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

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

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

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

СсылкиПравить

1. [1] Multivariate Public Key Cryptography