Криптосистема ГПТ

Криптосистема ГПТ (Габидулина-Парамонова-Третьякова) — криптосистема с открытыми ключами, основанная на ранговых кодах, разработанная в 1991 году Э. М. Габидулиным, А. В. Парамоновым и О. В. Третьяковым на основе криптосистемы McEliece.

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

Большинство версий системы были взломаны Р. Овербеком.

Описание

Открытый текст

В качестве открытого текста может использоваться любой $k$-вектор $m=(m_1,m_2,\mathrm{...},m_k)$, $m_s\in {𝔽}_{q^N},s=1,2,\mathrm{...},k$.

Открытый ключ

Открытым ключом является порождающая матрица размера $k\times (n+t_1)$:

$G_{pub}=S[X$ $G_k]P$,

где:

• $G_k$ — порождающая матрица $(n,k,d)$ кода с максимальным ранговым расстоянием $d$ для длины кода $n\le N$ с количеством символов $k$, задающаяся матрицей следующей формы:

$G_k=\left[\begin{array}{cccc}{g}_1& g_2& \cdots & g_n\\ g_1^{[1]}& g_2^{[1]}& \cdots & g_n^{[1]}\\ ⋮& ⋮& \ddots & ⋮\\ g_1^{[k-1]}& g_2^{[k-1]}& \cdots & g_n^{[k-1]}\end{array}\right]$

где $g_1,g_2,\mathrm{...},g_n$ — любой набор элементов расширенного поля ${𝔽}_{q^N}$, линейно независимых над полем ${𝔽}_q$.

главная матрица $G_k$ используется для исправления ошибок. Ошибки ранга не более $\frac{n-k}{2}$ могут быть исправлены.

• Cтроковый скремблер $S$ — невырожденная квадратная матрица порядка $k$ над полем ${𝔽}_{q^N}$
• $X$ — матрица искажений размера $(k\times t_1)$ над полем ${𝔽}_{q^N}$ со столбцовым рангом $R{k}_{col}(X$ | ${𝔽}_q)=t_1$ и рангом $Rk(X$ | ${𝔽}_{q^N})=t_X,$ $t_X\le t_1$.

Матрица $[X$ $G_k]$ имеет столбцовый ранг $R{k}_{col}([X$ $G_k]$ | ${𝔽}_q)=n+t_1$.

• Столбцовый скремблер $P$ — квадратная матрица порядка $(t_1+n)$ над полем ${𝔽}_q$.
• $t_1+n$ может быть больше $N$, но $n\le N$.

Закрытый ключ

В качестве закрытого ключа выступает набор $(S,G_k,X,P)$, а также алгоритм быстрого декодирования МРР-кода, в котором используется матрица проверки четности $H^{(n-k)\times n}$, такая, что $G_k{H}^T=0:$

$H=\left[\begin{array}{cccc}{h}_1& h_2& \cdots & h_n\\ h_1^{[1]}& h_2^{[1]}& \cdots & h_n^{[1]}\\ ⋮& ⋮& \ddots & ⋮\\ h_1^{[d-2]}& h_2^{[d-2]}& \cdots & h_n^{[d-2]}\end{array}\right]$,

где $h_1,h_2,\mathrm{...},h_n$ — элементы расширенного поля ${𝔽}_{q^N}$, линейно независимые над основным полем ${𝔽}_q$

Матрица $X$ не используется для расшифровки криптотекста и может быть удалена после вычисления закрытого ключа.

Оптимальные параметры кода

• Длина кода $n\le N$,
• Размерность $k=n-d+1$,
• Ранговое расстояние кода $d=n-k+1$

Шифрование

Соответствующий открытому тексту криптотекст вычисляется следующим образом:

$c=m{G}_{pub}+e=mS[X$ $G_k]P+e$,

где $e$ — искусственный вектор ошибок ранга не выше $t_2$, причем $t_1+t_2\le t=\lfloor \frac{n-k}{2}\rfloor$.

Дешифрование

Законный получатель, получая $c$, выполняет следующие действия:

1. Вычисляет $c^{\prime }=({c_1}^{\prime },{c_2}^{\prime },\mathrm{...},c_{{t_1}^{\prime }+n})=c{P}^{-1}=mS[X$ $G_k]+e{P}^{-1}$
2. Из $c^{\prime }$ выделяет подвектор $c^{″}=(c_{{t_1}^{\prime }+1},c_{{t_1}^{\prime }+2},\mathrm{...},c_{{t_1}^{\prime }+n})=mS{G}_k+e^{″}$, где $e^{″}$ — подвектор $e{P}^{-1}$
3. Применяет алгоритм быстрого декодирования для исправления ошибки $e^{″}$
4. Получает $mS$
5. Восстанавливает $m=(mS)S^{-1}$

В данной системе размер открытого ключа составляет $V=k(t_1+n)N$ бит, а скорость передачи информации $R=\frac{k}{t_1+n}$.

Взлом

Автоморфизм Фробениуса

Введем автоморфизм Фробениуса: $\sigma (x)=x^q,$ $x\in {𝔽}_{q^N}$. Он обладает следующими свойствами:

1. Для матрицы $L=(l_{ij})$ над тем же полем $\sigma (L)=(\sigma (l_{ij}))=(l_{ij}^q)$
2. Для любого целого s: ${\sigma }^s(L)=\sigma ({\sigma }^{s-1}(L))$
3. ${\sigma }^N=\sigma$
4. ${\sigma }^{-1}={\sigma }^{N-1}$
5. $\sigma (a+b)=\sigma (a)+\sigma (b)$
6. $\sigma (ab)=\sigma (a)\sigma (b)$
7. В общем случае $\sigma (L)\ne L$. Равенство достигается, если $L$ — матрица над основным полем ${𝔽}_q$

Описание атаки Овербека

• Криптоаналитик вычисляет расширенный открытый ключ из открытого ключа:

$G_{ext,pub}=\Vert \begin{array}{c}{G}_{pub}\\ \sigma (G_{pub})\\ \cdots \\ {\sigma }^u(G_{pub})\end{array}\Vert =\Vert \begin{array}{cccc}S& [X& G_k]& P\\ \sigma (S)& [\sigma (X)& \sigma (G_k)]& P\\ \cdots & \cdots & \cdots & \cdots \\ {\sigma }^u(S)& [{\sigma }^u(X)& {\sigma }^u(G_k]& P\end{array}\Vert$

Здесь использовано свойство 7 автоморфизма Фробениуса: $\sigma (P)=P$, так как $P$ — матрица над основным полем ${𝔽}_q$.

• Переписывает эту матрицу как $G_{ext,pub}=S_{ext}[X_{ext}$ $G_{ext}]$,

где

$S_{ext}=diag\left[\begin{array}{cccc}S& \sigma (S)& \cdots & {\sigma }^u(S)\end{array}\right]$,

$X_{ext}=\left[\begin{array}{c}X\\ \sigma (X)\\ ⋮\\ {\sigma }^u(X)\end{array}\right]$, $G_{ext}=\left[\begin{array}{c}{G}_k\\ \sigma (G_k)\\ ⋮\\ {\sigma }^u(G_k)\end{array}\right]$.

• Выбирает $u=n-k-1$.
• Определяет матрицы:

$X_1^{(k-1\times t_1)}$, получаемая из $X^{(k\times t_1)}$ удалением последней строки,

$X_2^{(k-1\times t_1)}$, получаемая из $X^{(k\times t_1)}$ удалением первой строки.

• Определяет линейное отображение $T$: ${𝔽}_{q^N}^{k\times t_1}\to {𝔽}_{q^N}^{(k-1)\times t_1}$ по следующему правилу:

если $X\in {𝔽}_{q^N}^{k\times t_1}$, тогда $T(X)=Y=\sigma (X_1)-X_2$

• Записывает $Y_{ext}={\left[\begin{array}{ccccc}Y& \sigma (Y)& {\sigma }^2(Y)& \cdots & {\sigma }^{u-1}(Y)\end{array}\right]}^{\mathrm{\top }}$
• С помощью матричных преобразований приводит расширенный открытый ключ к виду:

${\tilde{G}}_{pub,ext}={\tilde{S}}_{ext}\left[\begin{array}{ccc}Z& |& G_{n-1}\\ Y_{ext}& |& 0\end{array}\right]P$

где $G_{n-1}$ — порождающая матрица $(n,n-1,2)$ МРР-кода.

• Пробует найти решение системы

${\tilde{S}}_{ext}=\left[\begin{array}{ccc}Z& |& G_{n-1}\\ Y_{ext}& |& 0\end{array}\right]P{u}^T=0$,

где $u$ — вектор-строка над расширенным полем ${𝔽}_{q^N}$ длины $t_1+n$

• Представляет вектор $P{u}^T$ в виде:

$P{u}^T={\left[\begin{array}{cc}y& h\end{array}\right]}^{\mathrm{\top }}$

где $y$ — подвектор длины $t_1$, а $h$ — длины $n$

• Теперь система уравнений эквивалентна следующей:

$\{\begin{array}{c}Z{y}^T+G_{n-1}{h}^T=0,\\ Y_{ext}{y}^T=0\end{array}$

• Полагая верным условие $Rk(Y_{ext}|{𝔽}_{q^N})=t_1$, видим, что указанная выше система имеет только тривиальное решение $y^T=0$. Следовательно, первое уравнение из системы преобразуется к виду:

$G_{n-1}{h}^T=0$.

Это позволит найти первую строку матрицы проверки четности для кода с данной порождающей матрицей ${\tilde{G}}_{pub,ext}$. Следовательно, это решение взламывает описанную криптосистему за полиномиальное время. Атака Овербека требует $O((n+t_1{)}^3)$ операций над полем ${𝔽}_{q^N}$, так как каждый шаг атаки имеет сложность не выше кубической на $n+t_1$.

Литература

• Габидулин Э. М., Пилипчук Н. И., Хонари Б., Рашван Х. Защита информации в сети со случайным сетевым кодированием // Пробл. передачи информ., 2013, том 49, выпуск 2, 92-106
• Gadouleau M., Yan Zh. Security of GPT-type cryptosystems // Proc. 2006 IEEE Int. Sympos. on Information Theory (ISIT’2006). — ISIT.2006.261627
• Rashwan H., Gabidulin E.M., Honary B. A smart approach for GPT Cryptosystem Based on Rank Codes // Proc. 2010 IEEE Int. Sympos. on Information Theory (ISIT’2010). Austin, Texas, USA. June 13-18, 2010. P. 2463—2467.
• Kshevetskiy A.S. Security of GPT-like cryptosystems based on linear rank codes // Signal Design and Its Applications in Communications, 2007. IWSDA 2007. On page(s): 143—147.
• Ourivski A. V., Gabidulin E. M. Column Scrambler for the GPT Cryptosystem // Discrete Applied Mathematics.128(1): 207—221 (2003).
• Overbeck R. Extending Gibson’s attacks on the GPT cryptosystem // In Proc. of WCC 2005, volume 3969 of LNCS, pp. 178–188, Springer Verlag,2006.