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

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

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

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

Описание

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

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

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

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

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

где:

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

$G_{k}={\begin{bmatrix}g_{1}&g_{2}&\cdots &g_{n}\\g_{1}^{[1]}&g_{2}^{[1]}&\cdots &g_{n}^{[1]}\\\vdots &\vdots &\ddots &\vdots \\g_{1}^{[k-1]}&g_{2}^{[k-1]}&\cdots &g_{n}^{[k-1]}\end{bmatrix}}$

где $g_{1},g_{2},...,g_{n}$ — любой набор элементов расширенного поля $\mathbb {F} _{q^{N}}$, линейно независимых над полем $\mathbb {F} _{q}$.

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

• Cтроковый скремблер $S$ — невырожденная квадратная матрица порядка $k$ над полем $\mathbb {F} _{q^{N}}$
• $X$ — матрица искажений размера $(k\times {t_{1}})$ над полем $\mathbb {F} _{q^{N}}$ со столбцовым рангом $Rk_{col}(X$ | $\mathbb {F} _{q})=t_{1}$ и рангом $Rk(X$ | $\mathbb {F} _{q^{N}})=t_{X},$ $t_{X}\leq t_{1}$.
  

Матрица $[X$ $G_{k}]$ имеет столбцовый ранг $Rk_{col}([X$ $G_{k}]$ | $\mathbb {F} _{q})=n+t_{1}$.

• Столбцовый скремблер $P$ — квадратная матрица порядка $(t_{1}+n)$ над полем $\mathbb {F} _{q}$.
• $t_{1}+n$ может быть больше $N$, но $n\leq N$.

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

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

$H={\begin{bmatrix}h_{1}&h_{2}&\cdots &h_{n}\\h_{1}^{[1]}&h_{2}^{[1]}&\cdots &h_{n}^{[1]}\\\vdots &\vdots &\ddots &\vdots \\h_{1}^{[d-2]}&h_{2}^{[d-2]}&\cdots &h_{n}^{[d-2]}\end{bmatrix}}$,

где $h_{1},h_{2},...,h_{n}$ — элементы расширенного поля $\mathbb {F} _{q^{N}}$, линейно независимые над основным полем $\mathbb {F} _{q}$

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

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

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

Шифрование

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

$c=mG_{pub}+e=mS[X$ $G_{k}]P+e$,

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

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

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

1. Вычисляет $c'=(c_{1}',c_{2}',...,c_{t_{1}+n}')=cP^{-1}=mS[X$ $G_{k}]+eP^{-1}$
2. Из $c'$ выделяет подвектор $c''=(c_{t_{1}+1}',c_{t_{1}+2}',...,c_{t_{1}+n}')=mSG_{k}+e''$, где $e''$ — подвектор $eP^{-1}$
3. Применяет алгоритм быстрого декодирования для исправления ошибки $e''$
4. Получает $mS$
5. Восстанавливает $m=(mS)S^{-1}$

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

Взлом

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

Введем автоморфизм Фробениуса: $\sigma (x)=x^{q},$ $x\in \mathbb {F} _{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)\neq L$. Равенство достигается, если $L$ — матрица над основным полем $\mathbb {F} _{q}$

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

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

$G_{ext,pub}={\begin{Vmatrix}G_{pub}\\\sigma (G_{pub})\\\cdots \\\sigma ^{u}(G_{pub})\end{Vmatrix}}={\begin{Vmatrix}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{Vmatrix}}$

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

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

где

$S_{ext}=diag{\begin{bmatrix}S&\sigma (S)&\cdots &\sigma ^{u}(S)\end{bmatrix}}$,

$X_{ext}={\begin{bmatrix}X\\\sigma (X)\\\vdots \\\sigma ^{u}(X)\end{bmatrix}}$, $G_{ext}={\begin{bmatrix}G_{k}\\\sigma (G_{k})\\\vdots \\\sigma ^{u}(G_{k})\end{bmatrix}}$.

• Выбирает $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$: $\mathbb {F} _{q^{N}}^{k\times t_{1}}\rightarrow \mathbb {F} _{q^{N}}^{(k-1)\times t_{1}}$ по следующему правилу:

если $X\in \mathbb {F} _{q^{N}}^{k\times t_{1}}$, тогда $T(X)=Y=\sigma (X_{1})-X_{2}$

• Записывает $Y_{ext}={\begin{bmatrix}Y&\sigma (Y)&\sigma ^{2}(Y)&\cdots &\sigma ^{u-1}(Y)\end{bmatrix}}^{\top }$
  

• С помощью матричных преобразований приводит расширенный открытый ключ к виду:
  

${\widetilde {G}}_{pub,ext}={\widetilde {S}}_{ext}{\begin{bmatrix}Z&|&G_{n-1}\\Y_{ext}&|&0\end{bmatrix}}P$

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

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

${\widetilde {S}}_{ext}={\begin{bmatrix}Z&|&G_{n-1}\\Y_{ext}&|&0\end{bmatrix}}Pu^{T}=0$,

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

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

$Pu^{T}={\begin{bmatrix}y&h\end{bmatrix}}^{\top }$

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

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

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

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

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

Это позволит найти первую строку матрицы проверки четности для кода с данной порождающей матрицей ${\widetilde {G}}_{pub,ext}$. Следовательно, это решение взламывает описанную криптосистему за полиномиальное время. Атака Овербека требует $O((n+t_{1})^{3})$ операций над полем $\mathbb {F} _{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.