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

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

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

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

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

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

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

где:

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

${\displaystyle 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}}}$

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

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

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

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

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

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

${\displaystyle 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}}}$,

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 автоморфизма Фробениуса: ${\displaystyle \sigma (P)=P}$, так как ${\displaystyle P}$ — матрица над основным полем ${\displaystyle \mathbb {F} _{q}}$.

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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